Loss functions, neural networks and a look back at the course

For binary classification the course has built up a long list: logistic regression, support vector machines, boosting and the perceptron, plus decision trees and k-nearest neighbours. Regression had essentially one method. Linear regression minimizes the squared loss, and ridge and LASSO add different regularizers to the same loss (Part 10, Part 12).

This lecture asks why classification is different, and answers with one framework that holds most of the classifiers: each one minimizes a different loss function.

The data set is \(\{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\}\) with \(\mathbf{x}_i \in \mathbb{R}^d\) and \(y_i \in \{+1, -1\}\), and the goal is a classifier \(h: \mathbb{R}^d \to \{+1, -1\}\). The most natural measure of how good \(h\) is: count its mistakes on the training set.

Minimizing this over every possible \(h\) is pointless: some \(h\) memorizes the training set, reaches zero error and learns nothing. So we search a restricted class \(\mathcal{H}\) of functions, and the most natural one is the linear classifiers 3:38.

The bias term comes for free L69 · 5:10

The algorithms so far learned only \(\mathbf{w}\), so their lines passed through the origin. A bias \(b\) lets the line sit anywhere, which is more natural, but it needs no new algorithm. Append a constant feature 1 to every point:

A line through the origin in the padded space is a general line in the original space. So from here on it is enough to learn \(\mathbf{w}\), with \(d\) understood as the padded dimension.

This problem is NP-hard

Finding the \(\mathbf{w}\) with the fewest training mistakes is NP-hard in general: we do not expect any polynomial-time algorithm for it. If the data is linearly separable the problem is easy, since the perceptron or the SVM finds a \(\mathbf{w}\) with zero training error (Part 15, Part 16). The general, non-separable case is the hard one.

This is the fundamental reason classification has no single algorithm: nobody knows how to minimize the training error efficiently, so each method gets around the problem its own way.

One way around it is to make assumptions about the data. Generative models do this (Part 14), and the perceptron's analysis assumes the data is linearly separable with margin \(\gamma\) (Part 15). Under such assumptions the problem becomes easy. The loss-function view shows the other ways 7:44.

Look at one point \((\mathbf{x}, y)\) at a time. Its loss under \(h\) is 0 if \(h(\mathbf{x}) = y\) and 1 otherwise. With \(h(\mathbf{x}) = \operatorname{sign}(\mathbf{w}^\top\mathbf{x})\), a mistake means \(\mathbf{w}^\top\mathbf{x}\) and \(y\) have opposite signs, which is the same as their product being negative:

The four sign cases in the table below check this 10:47. Nothing here needs \(h\) to be linear. Write \(h(\mathbf{x}) = \operatorname{sign}(g(\mathbf{x}))\) for a real-valued function \(g\): linear (\(g(\mathbf{x}) = \mathbf{w}^\top\mathbf{x}\)), quadratic, anything. The loss then depends on the point only through one number, which these notes call \(z\) (the standard name is the margin of the point):

At \(z = 0\), on the boundary, the lecture decides to count no loss.

The training loss is a sum of these per-point losses, so the trouble is already visible in a single point's loss:

• It jumps. The loss is discontinuous at \(z = 0\), dropping straight from 1 to 0.
• It is not convex. A sum of convex functions is convex, and convex functions can be minimized efficiently (convexity appeared in Part 9). Had each point's loss been convex, the total would be too, and the best solution could be found in polynomial time. The step function is not convex, so there is no such guarantee, and the problem is NP-hard in general.

Different algorithms deal with this NP-hardness differently. Seeing exactly how is the content of the rest of L69 to L71.

Start with a bad algorithm that still fits the framework: treat the labels \(\pm 1\) as real numbers and run linear regression (Part 10). The per-point loss is \((g(\mathbf{x}) - y)^2\) with \(g(\mathbf{x}) = \mathbf{w}^\top\mathbf{x}\). This is solved efficiently, by matrix operations, and the final classifier is still \(h(\mathbf{x}) = \operatorname{sign}(\mathbf{w}^\top\mathbf{x})\).

To compare it with the 0-1 loss, rewrite it in terms of \(z = y\,g(\mathbf{x})\). Because \(y \in \{+1, -1\}\), \(y^2 = 1\), and both expressions below expand to the same thing:

Against \(z\), the regression loss is a parabola with its minimum, 0, at \(z = 1\) 20:31. Using regression for classification means minimizing this surrogate loss in place of the NP-hard 0-1 loss.

The trouble is on the right 22:05. A point with a large positive \(z\) is classified correctly, since \(\operatorname{sign}(g(\mathbf{x})) = y\), yet its loss grows like \((z - 1)^2\). Regression wants \(g(\mathbf{x})\) to equal \(y\) exactly, so a confident correct prediction is punished. An outlier far out on the correct side gets a large loss and pulls the fitted \(\mathbf{w}\) toward itself, even though \(h\) already classifies it correctly 23:09.

The squared loss approximates the 0-1 loss badly. A good surrogate should not penalize correct predictions for being confident.

Start from the soft-margin SVM (Part 16):

The slack \(\xi_i\) is the "bribe" point \(i\) pays to get to the right side of the line. Its two constraints combine into one:

The objective grows with every \(\xi_i\), so at the optimum no point pays more than it must 3:04: a point classified correctly with margin at least 1 pays 0, any other pays exactly \(1 - y_i\,\mathbf{w}^\top\mathbf{x}_i\). Substitute \(\xi_i = \max(0, 1 - y_i\,\mathbf{w}^\top\mathbf{x}_i)\) and the constraints disappear:

The data \(\mathbf{x}_i, y_i\) appear only in the second term; the first depends only on \(\mathbf{w}\) 4:08. This is the shape of ridge regression (Part 12): squared loss plus \(\tfrac{\lambda}{2}\lVert\mathbf{w}\rVert^2\). There \(\lambda\) weighs the regularizer; here \(C\) weighs the loss instead. The balancing just happens on the other side, and dividing through by \(C\) would move it back.

As a function of \(z = y\,g(\mathbf{x})\), with \(g(\mathbf{x}) = \mathbf{w}^\top\mathbf{x}\) here 6:45:

• For \(z \ge 1\) the loss is 0, however large \(z\) gets. Confident correct predictions cost nothing, which fixes the squared loss's flaw: this loss is tuned for classification, the squared loss for regression 8:18.
• For \(z < 1\), a mistake or a correct prediction with margin below 1, the loss is positive and linear: 1 at \(z = 0\), falling to 0 at \(z = 1\).
• It is convex, so the optimization is easy, and it follows the 0-1 loss far more closely than the squared loss. The lecture describes it, informally, as in some sense the best convex approximation of the 0-1 loss 8:50. That is why SVMs do much better than regression for classification.

Logistic regression (Part 15) models \(P(y = 1 \mid \mathbf{x}) = \sigma(\mathbf{w}^\top\mathbf{x})\) and maximizes the likelihood of the labels, assumed independent. It was set up with labels 0 and 1. The lecture writes these as \(z_i\); to keep \(z\) for the margin, these notes call them \(t_i\), with \(t_i = 1\) when \(y_i = +1\) and \(t_i = 0\) when \(y_i = -1\).

Take the logarithm, then flip the sign to turn it into a minimization, so it can be read as a loss 13:28:

Now find the contribution of one point in each of the two cases.

Case \(t_i = 1\), that is \(y_i = +1\). Only the first term survives:

Case \(t_i = 0\), that is \(y_i = -1\). Only the second term survives. Divide the numerator and denominator by \(e^{-\mathbf{w}^\top\mathbf{x}_i}\), which is allowed because it is always positive:

The last step uses \(y_i = -1\). Both cases give the same expression 18:07.

Its shape 20:50. It decreases as \(z\) grows and is never exactly 0, since it is the log of something greater than 1, but it gets ever closer to 0. It is convex, so it can be minimized efficiently. Its name is the logistic loss 21:51. With the natural log used in the derivation it crosses \(z = 0\) at \(\log 2 \approx 0.69\); the lecture's sketch is not drawn to scale.

The lecture's conclusions:

1. The 0-1 loss is hard to minimize.
2. Different algorithms minimize different surrogate losses in its place.
3. The surrogates are convex, and hence easy to minimize.

This is why classification has many algorithms and regression does not 23:24. In regression the loss we care about, the squared loss, is already convex, so there was nothing to approximate, and only the regularization varied. In classification the loss we care about is not convex, and each surrogate is a different compromise. How well a surrogate represents the 0-1 loss shapes how well its algorithm performs.

Regularization can be added to any of them. The SVM has it built in: maximizing the margin is what produced the \(\tfrac12\lVert\mathbf{w}\rVert^2\) term. Logistic regression has none on its own, but in practice it is always run with a regularizer, which is easy since it is solved with gradient-based methods anyway.

The perceptron and boosting fit the same picture, less cleanly. That is the next lecture.

The perceptron (Part 15) looks at one point \((\mathbf{x}_t, y_t)\) per iteration and, if it misclassifies it, updates \(\mathbf{w}_{t+1} = \mathbf{w}_t + \mathbf{x}_t\,y_t\). This looks very much like a gradient-descent step, \(\mathbf{w}_{t+1} = \mathbf{w}_t - \eta_t\,\nabla L(\mathbf{w}_t)\) (Part 10). Which loss would produce it?

Try the hinge loss of one point, \(\max(0, 1 - y\,\mathbf{w}^\top\mathbf{x})\) 1:02. It is piecewise linear in \(\mathbf{w}\): on the sloped piece its gradient is \(-y\,\mathbf{x}\), on the flat piece 0. The perceptron's rule matches once the kink is moved from 1 to 0, a modified hinge loss:

At \(y\,\mathbf{w}^\top\mathbf{x} = 0\) two linear pieces meet and there is no derivative. Use subgradients instead (Part 12): any line through the kink that stays below the function. In terms of \(z\) these have slopes between \(-1\) and 0, so in terms of \(\mathbf{w}\) the subgradients are \(\{-\alpha\,y\,\mathbf{x} : \alpha \in [0, 1]\}\).

The perceptron makes a particular choice at the kink 5:11: \(\alpha = 1\), the subgradient \(-y\,\mathbf{x}\). So a point exactly on the boundary is treated as a mistake. With the step size fixed at \(\eta_t = 1\):

The lecture stresses that this is back-fitting 8:47. The perceptron was derived from a different motivation, and it does not solve an optimization over all the data points. Forcing it into the loss framework needs all these caveats. It is still worth knowing, because its update \(\mathbf{x}_t\,y_t\) is exactly the subgradient step of a hinge-type loss.

Boosting (Part 17) can also be read as optimizing a loss, the exponential loss 10:49:

It looks like the logistic loss, falling as \(z\) grows and never reaching 0, but it is a different function. Each round of boosting adds a new classifier chosen to reduce the exponential loss of the combined classifier. Algorithms of this kind are called coordinate descent algorithms.

The course did not prove that boosting works, so the lecture gives only this high-level motivation and does not derive the loss. As with the perceptron, putting boosting in this framework comes with caveats.

The clean conclusion is that logistic regression and SVMs are neatly explained as minimizing a convex surrogate in place of the 0-1 loss. Regression on \(\pm 1\) labels also fits, though it is never used for classification in practice. The perceptron and boosting fit with caveats.

Why convex? A convex function has only one minimum value, with no other local minima to get stuck in, and that minimum is easy to find. So convex functions are natural choices for surrogates 12:21. A different convex surrogate gives a different algorithm.

These are not the only convex surrogates. Others, Huber's loss for example, lead to yet more algorithms 12:51.

There is also a different class of algorithms that gives up convexity altogether. They accept ending up at a local minimum, and in practice still perform comparably to SVMs and logistic regression. These are neural networks 13:21. They have no convex surrogate, they too are inspired by the perceptron, and they led to major advances in deep learning. The course only gives a perspective on them; a deep learning course builds them from the bottom up.

L72 opens with the lens of the last three lectures in one formula:

The regularizer steers the model toward desirable properties; \(\tfrac12\lVert\mathbf{w}\rVert^2\), for instance, favours weights close to zero. The loss we want is the 0-1 loss, but that is NP-hard, so each algorithm uses a convex surrogate: hinge gives SVMs, logistic gives logistic regression, a modified hinge with step size 1 gives the perceptron, and the exponential loss gives boosting.

Convexity was the point of all this. With a carefully chosen convex loss and regularizer, the minimizing \(\mathbf{w}\) is unique, and optimization algorithms reach that optimum. Neural networks drop this requirement: their loss is not necessarily convex. They are the second family of algorithms inspired by the basic perceptron 3:37. The course introduces them only to show how they differ from what came before; the detail belongs to a deep learning course, which starts from neural networks.

First draw the perceptron as a picture. Each feature \(x_1, \dots, x_d\) is an input node. Edges carry the weights \(w_1, \dots, w_d\) to one node that computes \(\mathbf{w}^\top\mathbf{x}\), and the prediction is \(\operatorname{sign}(\mathbf{w}^\top\mathbf{x})\).

A neural network extends this picture. Each circle is a neuron, loosely modelled on neurons in the brain, which fire when their incoming signal is strong enough. Edges always point from left to right. Instead of one \(\mathbf{w}\) there are many, arranged in layers:

• Input layer. The features \(x_1, \dots, x_d\).
• Hidden layer. \(k\) neurons. Every one receives the same input, but each has its own weights \(\mathbf{w}_j \in \mathbb{R}^d\). Neuron \(j\) computes \(\mathbf{w}_j^\top\mathbf{x}\), a linear function of the input, then applies a non-linear activation function \(a\) and outputs \(a(\mathbf{w}_j^\top\mathbf{x})\) 9:17. Typically the activation takes a real number to a number between 0 and 1, or to another real number, depending on the choice of \(a\). Usually all hidden neurons use the same \(a\).
• Output layer. Combines the hidden outputs linearly, with its own weights \(\mathbf{w}_{\text{out}} \in \mathbb{R}^k\).

For a regression problem this real number is the prediction 11:52. Computing it is a single pass through the network from left to right: form each \(\mathbf{w}_j^\top\mathbf{x}\), apply \(a\), and combine the results with \(\mathbf{w}_{\text{out}}\).

The parameters are \(\mathbf{w}_1, \dots, \mathbf{w}_k \in \mathbb{R}^d\) and \(\mathbf{w}_{\text{out}} \in \mathbb{R}^k\) 13:27, that is \(dk + k\) numbers. The activation function, the number of hidden layers and the number of nodes in each are fixed in advance, as part of the network's specification 15:01. Once everything is fixed, the network is a map from \(\mathbb{R}^d\) to \(\mathbb{R}\) determined by the weights.

Why build this? A linear model assumes \(y\) can be explained by a linear function of \(\mathbf{x}\), which may be too simple. SVMs and logistic regression handled non-linearity with kernels (Part 5, Part 16). A network introduces it through the activation functions.

Picture each hidden neuron as checking whether some property holds for the input. If the input is an image given as pixel values, one neuron might say whether the image contains a particular edge, another whether it contains a curve: anything a linear function of the pixels can pick out 17:02.

Take the simplest activation, a threshold: output 1 if \(\mathbf{w}_j^\top\mathbf{x} \ge 0\) and 0 otherwise. Then each hidden neuron is a linear classifier reporting which side of its hyperplane the point is on, and the output layer takes a weighted vote of those reports. Different neurons have different \(\mathbf{w}_j\), so together they pin down where in \(\mathbb{R}^d\) the point lies. The threshold makes the whole map non-linear.

Nobody hands us these weights. All of \(\mathbf{w}_1, \dots, \mathbf{w}_k\) and \(\mathbf{w}_{\text{out}}\) must be learned from data, as \(\mathbf{w}\) was for SVMs, logistic regression and the perceptron, only now there are many more of them 19:04.

The threshold activation is discontinuous, like the 0-1 loss, and it makes learning the weights very hard. In practice people use activations such as these 20:43:

• Sigmoid, \(a(s) = \sigma(s) = \dfrac{1}{1 + e^{-s}}\), as in logistic regression (Part 15). It is differentiable and easy to handle, a soft vote: 0.5 at \(s = 0\), approaching 1 as \(s\) grows and 0 as \(s\) becomes very negative.
• ReLU, the rectified linear unit, \(a(s) = \max(0, s)\): equal to \(s\) when \(s\) is positive and 0 otherwise. Why one might prefer it to the sigmoid is left to a deep learning course.
• Others, such as tanh.

Smoothing removes the discontinuity but not the non-convexity. With sigmoid hidden units, the output is no longer a convex function of the parameters, and neither is the loss built on it 21:45. This is the step away from convexity.

Why have a non-linearity at all 23:48? If \(a\) were linear, every \(a(\mathbf{w}_j^\top\mathbf{x})\) would be a linear function of \(\mathbf{x}\), and a linear combination of linear functions is again linear. The network would be no richer than what a perceptron or an SVM already does. With \(a(s) = s\), for example:

The non-linear activation is what lets the network learn a richer class of maps from input to output. Try the four activations below.

Collect every parameter into one vector \(\theta\); for the network above, \(\theta\) holds \(\mathbf{w}_1, \dots, \mathbf{w}_k\) and \(\mathbf{w}_{\text{out}}\). Write \(\text{NN}(\mathbf{x}; \theta)\) for what the network with parameters \(\theta\) predicts for input \(\mathbf{x}\). For regression the loss is the usual squared loss, summed over the data:

\(\text{NN}(\mathbf{x}_i; \theta)\) plays the role \(\mathbf{w}^\top\mathbf{x}_i\) played before 1:34. With a single hidden neuron and the identity as activation, it is exactly \(\mathbf{w}^\top\mathbf{x}_i\), and this is ordinary least squares (Part 10).

If the activation is differentiable, start from some initial \(\theta\) and run gradient descent: repeatedly take a step in the negative gradient direction. \(\theta\) is high-dimensional, and the gradient captures how the output changes as each individual weight changes.

Deeper networks L73 · 3:42

Nothing limits a network to one hidden layer. A second hidden layer combines the votes of the first and votes on the combination, a third does the same with the second, and so on: each layer works one level above the previous one. With \(L\) hidden layers, an output layer then produces the prediction.

Every neuron has its own weight vector, whose size is set by the layer before it 4:43. First-layer weights live in \(\mathbb{R}^d\); a neuron in layer \(\ell\) has one weight per node of layer \(\ell - 1\). The number of nodes per layer is a design choice. Layers 1 to \(L\) usually have the same number of nodes, though they need not. Either way the number of parameters grows quickly.

Computing the gradient of such a complicated network looks hard, but there is an efficient way, based on the chain rule of differentiation. The algorithm is called backpropagation 6:16. Given the parameter values \(\theta\), it computes the gradient of the network's loss at \(\theta\); gradient descent then uses that gradient to update the weights as usual. Backpropagation computes the gradient, and gradient descent takes the step.

The chain rule fits because the gradient says how the output changes when one weight changes 12:31. Changing a weight changes the output of its neuron, which changes the next layer, which changes the layer after that, all the way to the output. The network's layer-by-layer structure lets this computation be organized efficiently.

There is a catch 6:47. The output is not a convex function of the parameters. The loss is very high-dimensional and highly non-convex, so gradient descent need not converge to the parameters that minimize the training loss. It converges to a local minimum.

At first glance that suggests poor solutions. In practice it works very well, provided the algorithm is initialized carefully and gradient descent is modified with some tricks, steps that do not follow the gradient direction exactly 8:19. How and why those tricks work is part of a deep learning course.

Neural networks find local minima of non-convex losses, and in practice those minima are usually very good.

Backpropagation is the same for regression and classification; only the loss changes. For binary classification keep the input and hidden layers, and let the output layer apply a sigmoid to its linear combination. If \(\mathbf{h}\) is the vector of outputs of the last hidden layer:

Compare this probability with the actual label using the cross-entropy loss, which measures how close the two are 11:29. The lecture's example: if the label is \(y = 0\), predicting 0.1 should cost little, and predicting 0.9 (saying \(y = 1\) is likely) should cost a lot. The lecture does not write the formula; the standard form is

which is the per-point negative log-likelihood that logistic regression minimizes (above). For the example, with \(y = 0\): \(\hat p = 0.1\) costs \(-\log 0.9 \approx 0.105\), and \(\hat p = 0.9\) costs \(-\log 0.1 \approx 2.303\).

Everything else is unchanged 12:00: the network is still a function of \(\theta\), backpropagation computes the gradient of this new loss, and gradient descent follows it.

Neural networks learn local minima of non-convex functions and typically work very well in practice, above all on unstructured data such as images, text, speech and time series 14:04. There is no table of features; the features have to be learned from raw pieces of information, and the network architecture has to differ for each kind of data.

There are two ways to see what a network does. One: it maps the input straight to the output. Two: it does two things in sequence. Layers 1 to \(L\) apply a non-linear map from \(\mathbb{R}^d\) to \(\mathbb{R}^m\), where \(m\) is the number of nodes in layer \(L\), and then the output layer applies a linear function to the result.

The second view should recall kernel machines (Part 5, Part 11, Part 16): map the data to a higher dimension, then learn a linear function there. The difference is who chooses the map. With a kernel you specify it; a polynomial kernel, for instance, turns height and weight into height², weight², height × weight and so on. A network learns the feature map and the weights on top of it together.

Seen this way, a network can be designed to suit the kind of data 18:13. For images, useful features look for edges, corners and simple shapes, and the network can be set up to look for such things. The last layer stays linear, with a sigmoid for classification; the real question is the architecture of the layers before it. A deep learning course covers the main designs 19:14:

• Convolutional neural networks for images, since convolution is a natural image operation.
• Recurrent neural networks and LSTMs (long short-term memory networks) for time series.
• Transformers and attention models.

Each is a well-designed way to map raw input to a feature space in which classification or regression becomes easier.

Neural networks in summary L73 · 20:16

• A network is a non-linear map from input to output, specified by an architecture: one hidden layer, many layers, or other designs.
• Its parameters are learned by gradient descent, with backpropagation computing the gradient. This usually ends at a local minimum of the loss, which is usually very good in practice.
• On unstructured data, modern networks give state-of-the-art results, beating classical methods such as SVMs or logistic regression whose kernels are not tuned to the kind of data 21:50.
• On structured, tabular data they are not necessarily the best. Boosting, SVMs and logistic regression remain very good choices there 21:18.

The final lecture looks back over the whole course: unsupervised learning first, in three kinds, then supervised learning, regression and then classification. The table follows that order and links each topic to its notes. The spoken summary does not name generative models or kernel and probabilistic regression; they are included so the map is complete.

The lecturer hopes this is a solid foundation. From here the natural next steps are implementing these algorithms in practice, as in the Machine Learning Practice course, and a deep learning course, which is easier to appreciate after this one.

With what this course covered, an interested learner should be able to pick these up if needed.

Everything in this course started instead from a whole data set \(\mathbf{x}_1, y_1, \dots, \mathbf{x}_n, y_n\) given in advance 3:05.

The course taught the most important piece of a practical system, the algorithm. But it is only one piece of a pipeline, and deploying it in the field raises further issues. The lecture names them, without solutions, to make you curious. Much current machine learning research is about them.

• Fairness. A system used in the US predicted a risk score for whether a person convicted of a crime would reoffend and return to prison, using features such as their previous records. Its scores came out favourable to one ethnicity and unfavourable to another, though risk should depend on past offences, not ethnicity. Nothing in an algorithm like logistic regression or an SVM prefers one group to another. The bias was in the data: if past judges gave higher risk scores or longer sentences to one ethnicity, any algorithm learning from those decisions reproduces the bias. So unfairness may come from the data rather than the algorithm. Making algorithms fair is still a research question, with some solutions so far.
• Explainability. Can a highly accurate but complicated model, such as a large neural network, be used in mission-critical settings? A doctor who gets a suggestion to prescribe a medicine needs to know why. A decision tree can explain itself: trace the path to the leaf, a series of if-then-else conditions on feature thresholds (Part 13). A network with 100 hidden layers has no simple explanation. Or suppose a self-driving car fails to brake and a pedestrian dies: why did it decide not to brake, and who is accountable, the person who wrote the algorithm or the training method used? Without a human-understandable explanation this is unclear. The area is called explainable AI or explainable machine learning.
• Privacy. A model trained on confidential data, such as salaries or health records, might leak information about the people in it. A patient may refuse to share data with an algorithm that could reveal their health status. How should privacy be defined, and can learning algorithms be made private?
• AI for the edge 12:18. Networks keep growing, to billions of parameters, while a phone has limited memory. Can precision be truncated, parameters subsampled, or small networks built that mimic large ones?
• Data that changes after deployment 13:19. A model predicting IPL match winners from past scores and player statistics goes stale as skills and teams change, so the test data drifts away from the training data. Retraining from scratch for every new data point is not feasible. How can a deployed model keep learning?

The full list the lecture gives of post-deployment questions 14:21: fairness, explainability, privacy, distributed learning, AI for the edge, transfer learning (carrying knowledge from one domain to another) and continual learning (learning after deployment).

The course was introductory by design 15:25. Its goal was a solid foundation for more advanced courses, such as deep learning for unstructured data, and for following the research in these areas.

0-1 loss

\(\mathbb{1}(y\,g(\mathbf{x}) < 0)\): 1 for a mistake, 0 otherwise. Discontinuous and not convex, so minimizing it over linear classifiers is NP-hard in general.

Margin \(z = y\,g(\mathbf{x})\)

The one number every loss here depends on. Positive exactly when \(\operatorname{sign}(g(\mathbf{x})) = y\).

Surrogate loss

A loss minimized in place of the 0-1 loss. Convex surrogates are easy to minimize; each gives a different algorithm.

Squared loss

\((z - 1)^2\) for \(\pm 1\) labels. Regression's loss; it penalizes confident correct predictions.

Hinge loss

\(\max(0, 1 - z)\). Soft-margin SVM = hinge loss + L2 regularization.

Logistic loss

\(\log(1 + e^{-z})\). Logistic regression's negative log-likelihood, written with \(\pm 1\) labels.

Modified hinge loss

\(\max(0, -z)\). The perceptron is stochastic subgradient descent on it with step size 1.

Exponential loss

\(e^{-z}\). Boosting reduces it one classifier per round, a coordinate descent method.

Subgradient

The slope of a line through a point that stays below a convex function; at a kink there are many.

Hidden layer

Neurons between input and output, each computing \(a(\mathbf{w}_j^\top\mathbf{x})\) with its own weights.

Activation function

The non-linearity a neuron applies to \(\mathbf{w}^\top\mathbf{x}\): threshold, sigmoid, ReLU \(\max(0, s)\), tanh. Without it the network is linear.

Backpropagation

Computing the gradient of a network's loss efficiently with the chain rule, layer by layer from the output back.

Cross-entropy loss

Classification loss comparing a predicted probability with the actual 0/1 label.

Feature learning

Hidden layers learn the map to a new feature space and the output layer is linear on it; kernels fix that map in advance.