Perceptron and logistic regression: learning the line directly

The course has modelled binary classification in two broad ways. A generative model describes how the data is produced. Naive Bayes models \(P(y)\) and \(P(\mathbf{x} \mid y)\) under class-conditional independence, first with binary features and then with real ones in Gaussian Naive Bayes, also called Gaussian discriminant analysis (Part 14). A discriminative model does not care how the data arose; it only maps an input to a prediction. k-nearest neighbours and decision trees (Part 13) are discriminative in this non-probabilistic sense.

Naive Bayes predicts with \(P(y \mid \mathbf{x})\), obtained from its model through Bayes' rule. Part 14 showed that its decision rule \(P(y = 1 \mid \mathbf{x}) \ge 0.5\) is a linear function of the input: a line separates the two classes. The generative assumptions ended in a linear classifier anyway, so the lecture asks why not model the classifier as a linear function directly.

That is the plan from here on: more discriminative models, each a model of \(P(y \mid \mathbf{x})\). Since \(P(y = 0 \mid \mathbf{x}) = 1 - P(y = 1 \mid \mathbf{x})\), it is enough to say how \(P(y = 1 \mid \mathbf{x})\) depends on the feature vector.

The simplest assumption about this discriminating function is that it is linear:

The "probability" takes only the values 0 and 1, so labelling is deterministic. The lecture tells it as a discriminative story for how a training set is made 6:18. Someone hands over an arbitrary \(\mathbf{x}\); there is no model of how \(\mathbf{x}\) arises. To label it, they toss a coin that has heads on both sides or tails on both sides. It is the two-headed coin, giving label 1, exactly when \(\mathbf{w}^\top\mathbf{x} \ge 0\) for a fixed \(\mathbf{w}\) that the labeller knows. The learner sees the labels and knows that such a \(\mathbf{w}\) exists, but not which one.

Assuming this model is the same as assuming the data is linearly separable. A model also decides which data sets can occur at all. In the figure, the left data set could have been produced by the model with some \(\mathbf{w}\). The right one could not: with the extra point, no \(\mathbf{w}\) puts every label-1 point on one side and every label-0 point on the other, so the labeller cannot have used any \(\mathbf{w}\).

Ruling out a data set like the right one, with a single outlier, is a real weakness: any reasonable model should allow it 11:59. The lecture accepts the weakness on purpose. If no good algorithm exists even under the strongest assumption, things will only be harder once outliers appear. If one does exist, it can later be adapted to messier data.

The goal set at the start of classification (Part 13) is a classifier from some family \(\mathcal{H}\) with the fewest training mistakes, the zero-one loss:

For a general data set this is NP-hard, even when \(\mathcal{H}\) contains only linear classifiers. "General" means no restriction on the data: outliers and any mixing of the two classes are allowed, and finding the line with the fewest mistakes is still hard.

Linear separability is a strong restriction. The labeller used some \(\mathbf{w}\), and with access to that \(\mathbf{w}\) we would make no mistakes on the training set, so the smallest possible zero-one loss is 0. The line is hidden from us. The question becomes whether a line with zero training error can be found efficiently, and the answer is yes.

The classic algorithm for finding such a line is the perceptron, given by Frank Rosenblatt in the 1950s. Rosenblatt was working on vision, recognizing objects, and took inspiration from what makes a neuron in the brain fire. He built a physical machine that ran exactly this algorithm and believed it could solve vision and most reasonable decision-making problems. With hindsight its power is limited: it works when the data is linearly separable and may fail when it is not.

Input: \(\{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\}\) with \(\mathbf{x}_i \in \mathbb{R}^d\). For this algorithm the labels are \(y_i \in \{+1, -1\}\) instead of \(\{1, 0\}\). That is only a renaming (spam is \(+1\), not spam is \(-1\)) that keeps the formulas short. Throughout, \(\operatorname{sign}(z) = +1\) if \(z \ge 0\) and \(-1\) otherwise, so a point with score exactly 0 is predicted \(+1\).

1. Perceptron
2. Initialize \(\mathbf{w}^0 = \mathbf{0}\). The superscript counts iterations.
3. Until convergence: pick a pair \((\mathbf{x}_i, y_i)\) from the data set.
4. If \(\operatorname{sign}(\mathbf{w}^{t\top}\mathbf{x}_i) = y_i\), do nothing.
5. Otherwise \(\mathbf{w}^t\) has made a mistake on this point: update \(\mathbf{w}^{t+1} = \mathbf{w}^t + \mathbf{x}_i\,y_i\).

In words: keep a current \(\mathbf{w}\), look through the data, and whenever the current \(\mathbf{w}\) gets a point wrong, add that point times its label. Then check the new \(\mathbf{w}\) against the data again. The algorithm has converged when the current \(\mathbf{w}\) classifies every training point correctly 25:47. No more updates happen and the algorithm stops.

The update rule is the only non-trivial step. Nothing yet guarantees that "until convergence" ever ends: we keep adding vectors to \(\mathbf{w}\), and it is not clear that this reaches a \(\mathbf{w}\) with zero mistakes. That claim needs an argument, and the next two lectures supply it, starting with a close look at the update. A step-by-step run of the algorithm is in the interactive figure in the Lecture 54 notes.

The current \(\mathbf{w}^t\) can be wrong on a point in two ways.

• Type 1: it predicts \(+1\) but the label is \(-1\). That is, \(\mathbf{w}^{t\top}\mathbf{x}_i \ge 0\) and \(y_i = -1\).
• Type 2: it predicts \(-1\) but the label is \(+1\). That is, \(\mathbf{w}^{t\top}\mathbf{x}_i < 0\) and \(y_i = +1\).

Both get the same update, so check what the update does to the point that caused it. The new \(\mathbf{w}\) scores that point as

Assume no data point is the zero vector, so \(\lVert\mathbf{x}_i\rVert^2 > 0\).

• Type 1: \(y_i = -1\), so a positive amount is subtracted from a score that was \(\ge 0\) and should have been negative.
• Type 2 5:30: \(y_i = +1\), so a positive amount is added to a score that was negative and should have been positive.

Either way the score moves toward the correct sign. It need not get there in one step: a score of \(-10\) might become \(-5\), still wrong but closer.

The update pushes \(\mathbf{w}\) in the right direction for the point that caused it. It does not promise to fix that point in one step.

That argument is local: it only looks at the point that triggered the update. Even when the update fixes that point, the new \(\mathbf{w}\) can get other points wrong that the old one got right. The lecture shows this with a sketch; the figure redraws it with specific numbers.

The numbers behind the figure: \(\mathbf{w}_{\text{old}} = (0, 1)\) gets every point right except \(\mathbf{x} = (2, -0.5)\), whose label is \(+1\) and whose score is \(-0.5\). The update gives \(\mathbf{w}_{\text{new}} = \mathbf{w}_{\text{old}} + \mathbf{x} = (2, 0.5)\), and the score of \(\mathbf{x}\) becomes \(3.75\), which is \(-0.5 + \lVert\mathbf{x}\rVert^2\). But \(A = (-1.5, 1.5)\), label \(+1\), now scores \(-2.25\), and \(E = (1, -1.5)\), label \(-1\), now scores \(1.25\). One mistake fixed, two created 11:55.

So the worry is real. The algorithm might keep fixing one mistake while creating another somewhere else, forever. To claim convergence we need an argument that covers the whole run of the algorithm 13:37.

A second example, a corner case, is more revealing. Take three points in \(\mathbb{R}^2\):

Is it linearly separable by the definition above? Yes 17:21. Any \(\mathbf{w}\) along the positive x-axis works, for example \(\mathbf{w} = (1, 0)\). Its boundary is the y-axis. Then \(\mathbf{w}^\top\mathbf{x}_1 = \mathbf{w}^\top\mathbf{x}_2 = 0\), and \(\operatorname{sign}(0) = +1\) matches both labels, while \(\mathbf{w}^\top\mathbf{x}_3 = -1 < 0\) matches \(y_3 = -1\).

Now run the perceptron from \(\mathbf{w}^0 = \mathbf{0}\).

\(\mathbf{w}^3\) equals \(\mathbf{w}^1\), so from here the algorithm alternates between \(\mathbf{w}^1\) and \(\mathbf{w}^2\) forever 23:26. Each of them makes exactly one mistake, so the order in which points are picked does not matter, and the perceptron never converges although the data set is linearly separable.

Why does it fail? The data set is separable only because two points lie exactly on the decision boundary of \(\mathbf{w} = (1, 0)\), and the convention \(\operatorname{sign}(0) = +1\) decides their label 25:41. A point on the boundary is a corner case that could as well have been labelled \(-1\), and this arbitrariness is what breaks convergence. The fix is to assume slightly more about the data: there is a separator with no data point on the boundary itself.

Draw the separator \(\mathbf{w}^\top\mathbf{x} = 0\) and two lines parallel to it, \(\mathbf{w}^\top\mathbf{x} = \gamma\) on the positive side and \(\mathbf{w}^\top\mathbf{x} = -\gamma\) on the negative side. The stronger assumption is that some \(\mathbf{w}\) classifies the data correctly with a gap: no data point lies strictly between those two lines.

Multiplying by \(y_i\) packs two conditions into one.

• If \(y_i = +1\) it says \(\mathbf{w}^{*\top}\mathbf{x}_i \ge \gamma\): positive points lie on the line \(\mathbf{w}^{*\top}\mathbf{x} = \gamma\) or beyond it.
• If \(y_i = -1\) it says \(-\mathbf{w}^{*\top}\mathbf{x}_i \ge \gamma\), that is \(\mathbf{w}^{*\top}\mathbf{x}_i \le -\gamma\): negative points lie on \(\mathbf{w}^{*\top}\mathbf{x} = -\gamma\) or beyond it.

The slab between the two lines is empty, and in particular no data point satisfies \(\mathbf{w}^{*\top}\mathbf{x}_i = 0\) 33:52. Nothing is assumed about how large \(\gamma\) is: 0.1, 5 and 100 are all fine, and the gap may be as thin as we like as long as it is not zero. The three-point data set is now excluded. (A one-line check: \(\mathbf{x}_2 = -\mathbf{x}_1\) and both have label \(+1\), so their scores \(\mathbf{w}^\top\mathbf{x}_1\) and \(-\mathbf{w}^\top\mathbf{x}_1\) cannot both be at least \(\gamma > 0\).)

Under this assumption the perceptron has a convergence proof, one of the first for any learning algorithm 34:54. The lecture goes through it because the proof shows which quantities of a problem control how hard it is, and that leads to stronger algorithms later in the course.

The proof uses three assumptions. The first, linear separability with \(\gamma\) margin, is the important one. The other two are simplifications rather than real assumptions. The proof works without them, but it would carry extra terms.

Assumption 2: a radius L54 · 1:03

There is an \(R > 0\) with \(\lVert\mathbf{x}_i\rVert \le R\) for every \(i\). Every finite data set satisfies this. Some data point is the longest; take \(R\) to be its length, and the Euclidean ball of radius \(R\) contains all the points (the dashed circle in the margin figure above).

Assumption 3: without loss of generality, ‖w*‖ = 1 L54 · 2:37

Suppose \(\mathbf{w}^*\) separates the data with margin \(\gamma\) but has some other length. Divide each condition by \(\lVert\mathbf{w}^*\rVert > 0\); dividing by a positive number keeps the inequality:

So \(\mathbf{w}^{*\prime} = \mathbf{w}^*/\lVert\mathbf{w}^*\rVert\) has length 1 and separates the data with margin \(\gamma'\), which is still positive. The lines are the same lines; only their equations are rescaled, just as \(y = mx + c\) and \(2y = 2mx + 2c\) describe one line. Assumption 1 only asks for some \(\gamma > 0\), so we may as well take the separator to have length 1. If \(\mathbf{w}^*\) separates with \(\gamma = 10\), its unit version separates with \(10/\lVert\mathbf{w}^*\rVert\).

The strategy is to bound the number of mistakes. The perceptron changes \(\mathbf{w}\) only when it makes a mistake. If it can make at most some finite number of mistakes, say 10,000, then once it has made them it makes no more: it classifies every point correctly, which is exactly convergence.

Notation: \(\mathbf{w}^l\) is the weight vector after \(l\) mistakes, so \(\mathbf{w}^0 = \mathbf{0}\). Suppose \(\mathbf{w}^l\) makes a mistake on a data point \((\mathbf{x}, y)\). The update gives \(\mathbf{w}^{l+1} = \mathbf{w}^l + \mathbf{x}\,y\). How much longer is the new vector? Write the squared length as a dot product and expand:

Bound the last two terms.

• Third term. \(y = \pm1\), so \(y^2 = 1\), and \(\lVert\mathbf{x}\rVert^2 \le R^2\) by the radius assumption 12:57. The term is at most \(R^2\).
• Middle term. \(\mathbf{w}^l\) made a mistake on \((\mathbf{x}, y)\), so \(\operatorname{sign}(\mathbf{w}^{l\top}\mathbf{x}) \ne y\). Either \(\mathbf{w}^{l\top}\mathbf{x} \ge 0\) and \(y = -1\), or \(\mathbf{w}^{l\top}\mathbf{x} < 0\) and \(y = +1\). In both cases the product \((\mathbf{w}^{l\top}\mathbf{x})\,y \le 0\), so dropping the term can only make the right-hand side larger 13:28.

The same holds one step earlier, because \(\mathbf{w}^l\) came from \(\mathbf{w}^{l-1}\) by an update after a mistake, and so on back to the start. Unrolling down to \(\mathbf{w}^0 = \mathbf{0}\):

The lecture writes the left side as \(\lVert\mathbf{w}^{l+1}\rVert^2\) with \(l\) on the right. Counting \(\mathbf{w}^0\) as the start, the tidy form is the one above, and the final bound comes out the same.

The margin assumption has not been used yet. We do not know \(\mathbf{w}^*\), but we know it exists, and that is enough to reason about it. Track how the dot product of the current \(\mathbf{w}\) with \(\mathbf{w}^*\) changes when \(\mathbf{w}^l\) makes a mistake on \((\mathbf{x}, y)\):

The inequality is the margin assumption: \((\mathbf{w}^{*\top}\mathbf{x})\,y \ge \gamma\) holds for every data point, including the one just misclassified. So every update raises the dot product with \(\mathbf{w}^*\) by at least \(\gamma\). The same argument applies to each earlier update. Unrolling down to \(\mathbf{w}^0 = \mathbf{0}\), whose dot product with anything is 0 20:34:

A dot product is at most the product of the lengths

Take any two vectors \(\mathbf{u}\) and \(\mathbf{v} \ne \mathbf{0}\). The projection of \(\mathbf{u}\) onto the direction of \(\mathbf{v}\) is \(\frac{\mathbf{u}^\top\mathbf{v}}{\lVert\mathbf{v}\rVert^2}\,\mathbf{v}\), the proxy from the PCA lectures (Part 2). The projection, the leftover \(\mathbf{u}\) minus the projection, and \(\mathbf{u}\) itself form a right-angled triangle with \(\mathbf{u}\) as the hypotenuse. By Pythagoras, \(\lVert\mathbf{u}\rVert^2\) is the projection's squared length plus the leftover's, so the projection is no longer than \(\mathbf{u}\):

This is a version of the Cauchy–Schwarz inequality. (The lecture names the two vectors \(\mathbf{x}\) and \(\mathbf{y}\); \(\mathbf{u}\) and \(\mathbf{v}\) avoid a clash with the label \(y\).)

The sandwich L54 · 24:26

Apply it with \(\mathbf{u} = \mathbf{w}^l\) and \(\mathbf{v} = \mathbf{w}^*\). Observation 2 says \(l\gamma \le \mathbf{w}^{l\top}\mathbf{w}^*\). Both sides are nonnegative, so squaring keeps the inequality. Then Cauchy–Schwarz, and finally \(\lVert\mathbf{w}^*\rVert = 1\):

This is observation 3: \(\lVert\mathbf{w}^l\rVert^2 \ge l^2\gamma^2\). Together with observation 1, the squared length is trapped between two bounds:

The last step divides by \(l\gamma^2 > 0\); the case \(l = 0\) needs nothing.

Why γ > 0 matters L54 · 27:49

The bound is finite only because \(\gamma > 0\). If we allowed \(\gamma = 0\), letting points sit on the separating hyperplane, the same argument would give \(l \le R^2/0 = \infty\), a useless statement. The three-point example shows that the perceptron really can fail in that case. With any positive margin, however small, the number of mistakes is finite and the perceptron must converge.

Summary, and what comes next L54 · 28:58

The perceptron is a very simple update rule: on a mistake, add \(\mathbf{x}\,y\) to \(\mathbf{w}\). Run until convergence, it is guaranteed to stop with a \(\mathbf{w}\) that classifies every training point correctly, provided the data is linearly separable with some margin \(\gamma\). \(R\) is a finite number you can compute from the data. It is one of the first machine learning algorithms with a provable convergence guarantee.

Two questions are left open 30:36. What does the bound say about the quality of the solution it finds? And what exactly is the role of the margin \(\gamma\)? Thinking about them leads to two major families of algorithms that both grew out of the perceptron and its analysis: support vector machines (Part 16) and neural networks (Part 18).

So far: the perceptron finds a linear classifier when the data is linearly separable, and with margin \(\gamma\) it makes at most \(R^2/\gamma^2\) mistakes. The margin deserves a longer discussion, which the course returns to in Part 16. For now the lecture parks the perceptron and rethinks its assumption.

Written as a probability, the perceptron assumes \(P(y = 1 \mid \mathbf{x}) = 1\) if \(\mathbf{w}^\top\mathbf{x} \ge 0\) and 0 otherwise. Because the probabilities are exactly 1 and 0, a data set with one minus among the pluses and one plus among the minuses cannot occur 3:05. Whatever \(\mathbf{w}\) the labeller used would have labelled those two points the other way. The culprit is the 0/1 probability, so the question is whether the probabilities can be modelled differently.

Start from a simple linear model again. For a feature vector \(\mathbf{x} \in \mathbb{R}^d\), the number

is a score that \(\mathbf{w}\) gives to \(\mathbf{x}\). Points with equal scores form lines parallel to the separator 5:39: \(\mathbf{w}^\top\mathbf{x} = 0\) is the separator, \(\mathbf{w}^\top\mathbf{x} = 1\) a parallel line on the positive side, and \(\mathbf{w}^\top\mathbf{x} = -1\) one on the negative side.

A positive score suggests label \(+1\) and a negative one suggests \(-1\). The size of the score should matter as well 6:42. A point \(\mathbf{x}_2\) with \(\mathbf{w}^\top\mathbf{x}_2 = 100\) is far from the separator, so we should be more confident that it is \(+1\) than for a point \(\mathbf{x}_1\) just beside the boundary. Likewise a point \(\mathbf{x}_4\) with \(\mathbf{w}^\top\mathbf{x}_4 = -150\) should be \(-1\) with more confidence than a point \(\mathbf{x}_3\) near the boundary on the negative side. In the new model every point gets a nonzero probability of each label, and the score decides how much.

A score can be any real number, \(z \in (-\infty, \infty)\), so it is not a probability itself. We need a function \(g\) that takes the score and returns \(P(y = 1 \mid \mathbf{x}) = g(\mathbf{w}^\top\mathbf{x})\). Larger scores should mean larger probabilities of \(+1\). Three properties pin down what is reasonable 10:44:

• \(g(0) = 0.5\). A point exactly on the separator is equally likely to be \(+1\) or \(-1\).
• \(g(z) \to 1\) as \(z \to \infty\). Very high scores make \(+1\) nearly certain.
• \(g(z) \to 0\) as \(z \to -\infty\). Very low scores make \(+1\) nearly impossible.

Any \(g\) with these properties is a reasonable choice. In the literature such a function is called a link function, because it links scores to probabilities, and several are used in practice. One popular choice is the sigmoid, also called the logistic function:

Since \(e^{-z} > 0\), the denominator is always larger than 1, so \(g(z)\) is always strictly between 0 and 1. It equals 0.5 at \(z = 0\), rises toward 1 for large \(z\) and falls toward 0 for very negative \(z\). Its graph looks like an S, which is where the name comes from 13:53. The lecture adds that this choice will make the maths easier, which the log-likelihood in the next lecture bears out.

Under this sigmoid or logistic model, the data set with a minus among the pluses is allowed. The labelling story is a coin toss for every point, with the coin's bias set by the point's score.

• A point on the line \(\mathbf{w}^\top\mathbf{x} = 1\) is labelled \(+1\) 15:27. Its coin came up heads with probability \(\frac{1}{1 + e^{-1}} = \frac{e}{e + 1} \approx 0.73\), and it did.
• A point on the line \(\mathbf{w}^\top\mathbf{x} = 10\) is labelled \(-1\) 16:28. Its coin had \(P(+1) = \frac{1}{1 + e^{-10}} = \frac{e^{10}}{e^{10} + 1} \approx 0.99995\), and it came up tails. That is very unlikely (probability about 0.00005) but not impossible, so this point no longer rules the data set out.

Which \(\mathbf{w}\) produced the labels? The same labels could also have come from a different vector \(\mathbf{w}'\). Relative to \(\mathbf{w}'\) each point has a different score and so a different coin, and the observed labels still have some probability. Every \(\mathbf{w}\) is a contender, and we have to pick one.

Pick the \(\mathbf{w}\) with the highest chance of having generated the observed labels. That is maximum likelihood estimation (Part 8), a problem we know how to set up.

This model is called logistic regression. "Logistic" refers to the logistic (sigmoid) function. "Regression" refers to the real-valued score \(\mathbf{w}^\top\mathbf{x}\) on which the probabilities depend. It is still a classification model, and that is what it is used for.

The data is \(\{(\mathbf{x}_1, y_1), \dots, (\mathbf{x}_n, y_n)\}\). For the likelihood the labels are back to \(y_i \in \{0, 1\}\), and for some unknown \(\mathbf{w}\)

The features are given and only the labels are random, each generated independently of the others, as usual. Each label is a Bernoulli outcome with success probability \(g(\mathbf{w}^\top\mathbf{x}_i)\). The likelihood has exactly the form of the Bernoulli likelihood from Part 8, with the single \(p\) replaced by a function of \(\mathbf{w}\):

Take the logarithm before substituting \(g\):

Now plug in the sigmoid 4:37. Write \(z_i = \mathbf{w}^\top\mathbf{x}_i\). The probability of label 0 is \(1 - g(z_i) = \frac{e^{-z_i}}{1 + e^{-z_i}}\), so

Substitute both and collect the \(\log(1 + e^{-z_i})\) terms. Their coefficients are \(-y_i\) and \(-(1 - y_i)\), which add up to \(-1\):

This is where the exponential form of \(g\) helps: the logarithms undo the exponentials and a few terms cancel.

The first term of the objective is linear in \(\mathbf{w}\). The second involves \(\log(1 + e^{-\mathbf{w}^\top\mathbf{x}_i})\). If you take the gradient and set it to zero, you do not get a nice formula for \(\mathbf{w}\): there is no closed-form solution. That does not stop us. A gradient method (Part 10) starts from a guess for \(\mathbf{w}\) and improves it step by step with some step size: against the gradient when minimizing (gradient descent), along it when maximizing (gradient ascent).

Differentiate each term. The first is linear; the second needs the chain rule twice, through the logarithm and then through the exponential:

Subtracting the second from the first and summing over the data:

The bracket simplifies, since \(1 - \frac{e^{-z}}{1 + e^{-z}} = \frac{1}{1 + e^{-z}}\), and the gradient takes a neat form:

Two things can be read off the update.

1. The gradient is a linear combination of the data points 12:54. Each term is \(\theta_i\,\mathbf{x}_i\) with the number \(\theta_i = y_i - g(\mathbf{w}^{t\top}\mathbf{x}_i)\), so the gradient is \(\sum_i \theta_i\,\mathbf{x}_i\).
2. Each point's weight \(\theta_i\) measures how well the current \(\mathbf{w}^t\) predicts it. \(g(\mathbf{w}^{t\top}\mathbf{x}_i)\) is the current model's probability that point \(i\) has label 1. If the label is 1 and that probability is 0.99, then \(\theta_i = 0.01\) and the point barely affects the step. If the label is 1 but the model gives it only 0.1, so it thinks the point is 90% likely to be the other class, then \(\theta_i = 0.9\) and the point has a large say.

So the next \(\mathbf{w}\) is shaped mostly by the points the current \(\mathbf{w}\) gets wrong. \(\theta_i\) is never exactly 0, because the sigmoid never reaches 0 or 1, but a well-predicted point contributes very little. (A comparison the lecture does not make here: the perceptron adds \(y_i\mathbf{x}_i\) only for misclassified points, while this update adds every point with a weight.)

Gradient ascent is the plain way to solve the problem. Faster second-order methods exist, for example iteratively reweighted least squares (IRLS), which solves a sequence of weighted least-squares problems to reach the maximum-likelihood \(\mathbf{w}\). The course does not cover it.

Prediction comes with a confidence

Let \(\hat{\mathbf{w}}\) be the solution gradient ascent converges to. For a test point \(\mathbf{x}_{\text{test}} \in \mathbb{R}^d\), predict by the sign of \(\hat{\mathbf{w}}^\top\mathbf{x}_{\text{test}}\), as usual: class 1 when \(\hat{\mathbf{w}}^\top\mathbf{x}_{\text{test}} \ge 0\), which is when \(g(\hat{\mathbf{w}}^\top\mathbf{x}_{\text{test}}) \ge 0.5\). Because probabilities are built into the model, it also returns \(g(\hat{\mathbf{w}}^\top\mathbf{x}_{\text{test}})\) itself, which can be read as the confidence of the prediction 17:00. This is one of the model's major advantages.

A kernel version L56 · 17:30

The optimal \(\mathbf{w}^*\) can be shown to be a linear combination of the data points, \(\mathbf{w}^* = \sum_i \alpha_i\mathbf{x}_i\). The theorem that guarantees this is the representer theorem 18:32. Substituting this form into the objective leaves only dot products \(\mathbf{x}_i^\top\mathbf{x}_j\), which can be replaced by a kernel (Part 5), as in kernel regression (Part 11). The lecture mentions this for awareness and does not derive it.

Regularized logistic regression L56 · 19:02

In practice a Bayesian, or regularized, version is very popular. Turn the maximization into a minimization of the negative log-likelihood and add the usual L2-norm penalty:

\(\lambda\) is a hyperparameter, chosen by cross-validation (Part 11). The gradient is the previous one, with its sign flipped for minimization, plus \(\lambda\mathbf{w}\), so gradient descent stays just as efficient. The link between a prior and an L2 penalty is the one seen for ridge regression in Part 12.

The \(\tfrac{\lambda}{2}\) scaling is chosen here so that the penalty adds exactly \(\lambda\mathbf{w}\) to the gradient, matching the lecture's description of the gradient.

Logistic regression and the perceptron L56 · 20:34

Logistic regression can model any data set, with or without outliers, and if the data has structure beyond linear, its kernel version can capture it. The perceptron works only for linearly separable data. Logistic regression converges to a good \(\mathbf{w}\) in its own way, by maximizing the likelihood of the observed labels under its model.

The perceptron gave something in return: a mistake bound, and the bound's dependence on the margin points to a more direct algorithm 21:36. That algorithm is the support vector machine, elegant and powerful in practice, especially for structured data. Part 16 develops it from the perceptron's mistake bound.

Discriminative model

A model of \(P(y \mid \mathbf{x})\) only, with no model of how \(\mathbf{x}\) is generated.

Linear separability

Some \(\mathbf{w}\) has \(\operatorname{sign}(\mathbf{w}^\top\mathbf{x}_i) = y_i\) for every training point; the least zero-one loss is then 0.

Perceptron

Rosenblatt's algorithm: start at \(\mathbf{w} = \mathbf{0}\) and add \(y_i\mathbf{x}_i\) whenever \(\mathbf{x}_i\) is misclassified, until no point is.

Update rule

\(\mathbf{w}^{t+1} = \mathbf{w}^t + \mathbf{x}_i y_i\); it changes the point's score by \(y_i\lVert\mathbf{x}_i\rVert^2\), toward the right sign.

Margin γ

Data is separable with margin \(\gamma > 0\) if some \(\mathbf{w}^*\) has \(y_i\,\mathbf{w}^{*\top}\mathbf{x}_i \ge \gamma\) for all \(i\): an empty slab around the boundary.

Radius R

A bound \(\lVert\mathbf{x}_i\rVert \le R\) on every data point; the longest point's length always works.

Radius–margin bound

On data separable with margin \(\gamma\), the perceptron makes at most \(R^2/\gamma^2\) mistakes, so it converges.

Cauchy–Schwarz inequality

\((\mathbf{u}^\top\mathbf{v})^2 \le \lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2\), from Pythagoras applied to a projection.

Score

\(z = \mathbf{w}^\top\mathbf{x}\); constant along lines parallel to the separator.

Link function

Turns a real score into a probability, with \(g(0) = 0.5\), \(g \to 1\) as \(z \to \infty\) and \(g \to 0\) as \(z \to -\infty\).

Sigmoid (logistic) function

\(g(z) = 1/(1 + e^{-z})\), an S-shaped link function.

Logistic regression

The classifier \(P(y = 1 \mid \mathbf{x}) = g(\mathbf{w}^\top\mathbf{x})\), fitted by maximum likelihood; the name's "regression" refers to the real-valued score.

Gradient ascent

Repeating \(\mathbf{w} \leftarrow \mathbf{w} + \eta\,\nabla\log\mathcal{L}(\mathbf{w})\) to maximize; needed because there is no closed form.

Representer theorem

Guarantees that the optimal logistic-regression \(\mathbf{w}\) is a linear combination of the data points, which allows a kernel version.