4  Perceptron and Generalized Linear Models

Lecture 4

Keywords

perceptron, exponential family, generalized linear models, softmax regression, cross-entropy

Based on the lecture by Anand Avati — CS229, Stanford University, Autumn 2018.

Lectures 2 and 3 derived linear regression and logistic regression separately, and both ended with the same update, θj:=θj+α (y−hθ(x)) xj\theta_j := \theta_j + \alpha\,(y - h_\theta(x))\,x_j. This lecture, given by Anand Avati while Ng was away, explains why. Both models are instances of a generalized linear model: pick a distribution for yy from the exponential family, let its natural parameter be a linear function of xx, and the hypothesis, the likelihood and the update all follow — the same update every time, with only hθh_\theta changing. The sigmoid, which lecture 3 introduced without justification, falls out of this recipe once yy is assumed Bernoulli. The lecture opens with the perceptron, which has the same update for a different reason, and closes with softmax regression, which extends logistic regression to many classes.

4.1 The perceptron

1:35 The perceptron replaces logistic regression’s sigmoid with a hard threshold, g(z)=1g(z) = 1 if z≥0z \ge 0 and 00 otherwise, so hθ(x)=g(θ⊤x)h_\theta(x) = g(\theta^\top x) outputs a label rather than a probability. The update is the one from lecture 3, written for one example at a time:

θ:=θ+α(y(i)−hθ(x(i)))x(i).(4.1) \theta := \theta + \alpha \left(y^{(i)} - h_\theta(x^{(i)})\right) x^{(i)} . \tag{4.1}

Avati reads it from the inside out. Since yy and hθ(x)h_\theta(x) are both 0 or 1, the bracket can take only three values: 0 when the prediction is right, so nothing happens; +1+1 when a positive example was called negative; and −1-1 in the opposite case. A correctly classified example therefore leaves θ\theta alone, and a misclassified one adds or subtracts a multiple of itself.

7:27 The geometric picture makes that rule look inevitable rather than arbitrary. The decision boundary θ⊤x=0\theta^\top x = 0 is the line perpendicular to θ\theta, and θ⊤x\theta^\top x is positive for inputs on the side θ\theta points toward. We want θ\theta to have a positive dot product with the positive examples and a negative one with the negative examples — to be similar to the first and dissimilar to the second. When a positive xx lands on the wrong side, the most naive way to make θ\theta more like xx is to add a bit of xx to it. That rotates θ\theta toward xx, and the boundary rotates with it (Figure 4.1).

Figure 4.1: One perceptron step. The positive example xx lies on the wrong side of the dashed boundary θ⊤x=0\theta^\top x = 0; adding αx\alpha x (here α=1\alpha = 1, for visibility) gives θ′\theta', whose boundary puts xx on the positive side while every other point keeps its side. Computed by figures/04-perceptron-glm/make_diagrams.py.

The lecture calls α\alpha “some small learning rate”, but for the perceptron as usually run it has no effect at all. Starting from θ=0\theta = 0, every update adds ±αx(i)\pm\alpha x^{(i)}, so θ\theta is always α\alpha times a sum of examples, and the sign of θ⊤x\theta^\top x — the only thing the prediction depends on — does not depend on α\alpha. The generator checks this: on a separable set of 40 points, α=1\alpha = 1 and α=0.001\alpha = 0.001 make the same 8 mistakes in the same order and finish with parameter vectors that differ by exactly the factor of 1000. The learning rate starts to matter only if it changes over time, which is where a student question led.

12:39 Asked why the perceptron is not used in practice, Avati gives two reasons. It has no probabilistic interpretation: it draws a boundary but says nothing about how confident it is. And it has a famous limitation. The perceptron was celebrated in the late 1950s as a model of the brain (Rosenblatt, 1958); the 1969 book Perceptrons by Marvin Minsky and Seymour Papert (the lecture remembers it as a paper by Minsky) set out what a single linear threshold unit cannot compute, and the smallest example is XOR — two positive and two negative points at the corners of a square, diagonally opposite, which no line separates. Interest in the model collapsed afterwards.

13:39 A second question asked when to stop training. If the data are linearly separable, the answer is a theorem the lecture does not state: the perceptron stops making mistakes after finitely many updates. If every ∥x(i)∥≤R\lVert x^{(i)} \rVert \le R and some unit vector uu separates the classes with margin γ\gamma, the number of mistakes is at most (R/γ)2(R/\gamma)^2, whatever the order of the examples (Novikoff, 1962). On the generator’s 40 points the bound is 55 and the perceptron makes 8. If the data are not separable, it never settles — on XOR it is still making mistakes on all four points in the thousandth pass — so Avati’s practical advice is to anneal: shrink α\alpha with every example until θ\theta stops moving much. That is exactly the case where α\alpha is no longer irrelevant, since later updates then count for less than earlier ones.

13:31 Avati also offers the cleanest way to place the perceptron beside the previous lecture: logistic regression is a soft version of it. The step function is the limit of g(kz)=1/(1+e−kz)g(kz) = 1/(1 + e^{-kz}) as the slope kk grows (Figure 4.2); at k=12k = 12 the two already differ by less than 0.003 everywhere outside ∣z∣<0.5|z| < 0.5. What the sigmoid buys in exchange for that softness is a likelihood, and with it everything that follows.

Figure 4.2: The perceptron’s threshold as a hard sigmoid: g(kz)g(kz) for k=1,3,12k = 1, 3, 12 steepens toward the step function. Computed by figures/04-perceptron-glm/make_diagrams.py.
NoteIn the official notes

The perceptron is the short digression of cs229-notes1, section 6, which presents it only as an algorithm; the mistake bound above is not in the 2018 notes.

4.2 The exponential family

14:53 The exponential family is a class of distributions with convenient mathematics, and it is the bridge to generalized linear models. A distribution belongs to it if its density (or, for discrete yy, its probability mass function) can be written

p(y;η)=b(y)exp⁡ ⁣(η⊤T(y)−a(η)).(4.2) p(y; \eta) = b(y) \exp\!\left( \eta^\top T(y) - a(\eta) \right) . \tag{4.2}

Avati names each piece. The variable is called yy, not xx, on purpose: these distributions will model the output of a supervised problem, and xx enters only when the model is built. η\eta is the natural parameter. T(y)T(y) is the sufficient statistic, in the statistician’s sense, but for every distribution in this course T(y)=yT(y) = y, and the lecture tells the reader to make that substitution and move on. b(y)b(y) is the base measure, which may depend only on yy; and a(η)a(\eta) is the log-partition function, which may depend only on η\eta. In most of the course yy and η\eta are scalars; softmax will need a vector η\eta.

18:48 The name of aa explains its job. Moving it out of the exponent gives p(y;η)=b(y) eηT(y)/ea(η)p(y;\eta) = b(y)\, e^{\eta T(y)} / e^{a(\eta)}, so ea(η)e^{a(\eta)} is the normalising constant — the partition function — that makes the density integrate to one, and a(η)a(\eta) is its log. That has a consequence worth making explicit, because the lecture says one can choose aa, bb and TT freely as long as the result integrates to one. The condition is not a side constraint on aa; it determines it. Once bb and TT are fixed,

a(η)=log⁡∫b(y) eηT(y) dy, a(\eta) = \log \int b(y)\, e^{\eta T(y)}\, dy ,

with a sum in place of the integral for discrete yy. Choosing bb and TT chooses the family; aa comes with it. The generator confirms, for the three families below, that the a(η)a(\eta) read off by pattern matching equals this normaliser computed by brute-force summation.

21:44 To show that a familiar distribution is a member, write its density in the usual form and massage it until it matches Equation 4.2. For the Bernoulli with mean ϕ\phi, the density ϕy(1−ϕ)1−y\phi^y (1-\phi)^{1-y} — an “if–else written in maths”, as Avati puts it, since it equals ϕ\phi when y=1y = 1 and 1−ϕ1 - \phi when y=0y = 0 — becomes, after wrapping it in exp⁡log⁡\exp\log,

p(y;ϕ)=exp⁡ ⁣(ylog⁡ϕ1−ϕ+log⁡(1−ϕ)). p(y; \phi) = \exp\!\left( y \log\frac{\phi}{1-\phi} + \log(1-\phi) \right) .

Matching term by term gives b(y)=1b(y) = 1, T(y)=yT(y) = y, the natural parameter η=log⁡ϕ1−ϕ\eta = \log\frac{\phi}{1-\phi}, and a(η)=−log⁡(1−ϕ)a(\eta) = -\log(1-\phi). 26:14 Inverting the expression for η\eta gives

ϕ=11+e−η,(4.3) \phi = \frac{1}{1 + e^{-\eta}} , \tag{4.3}

the sigmoid, which arrives here without being asked for. Substituting it into aa gives a(η)=log⁡(1+eη)a(\eta) = \log(1 + e^{\eta}), now a function of η\eta alone as the definition requires.

28:41 The Gaussian works the same way once its variance is fixed. With σ2=1\sigma^2 = 1 — and lecture 3 showed that the variance has no effect on the fitted θ\theta in least squares, so nothing is lost —

12πexp⁡ ⁣(−12(y−μ)2)=12πe−y2/2⏟b(y) exp⁡ ⁣(μ y−12μ2⏟a(η)), \frac{1}{\sqrt{2\pi}} \exp\!\left( -\tfrac12 (y - \mu)^2 \right) = \underbrace{\frac{1}{\sqrt{2\pi}} e^{-y^2/2}}_{b(y)} \, \exp\!\Big( \mu\, y - \underbrace{\tfrac12 \mu^2}_{a(\eta)} \Big),

so η=μ\eta = \mu and a(η)=η2/2a(\eta) = \eta^2 / 2. A student asked what happens if the variance is unknown: the Gaussian is still in the family, but η\eta becomes a two-dimensional vector and T(y)=(y,y2)T(y) = (y, y^2). The Poisson, which the lecture uses later without deriving, fits the same mould: λye−λ/y!\lambda^y e^{-\lambda} / y! has b(y)=1/y!b(y) = 1/y!, η=log⁡λ\eta = \log \lambda and a(η)=eηa(\eta) = e^{\eta}.

NoteIn the official notes

The Bernoulli and Gaussian derivations are cs229-notes1, section 8, which also lists the multinomial, Poisson, gamma, exponential, beta and Dirichlet as members.

4.3 Why the exponential family is convenient

33:10 Three properties make the family worth the trouble, and Avati states them without proof — they are an exercise in the first problem set. First, maximum likelihood in the natural parameter is a concave problem, so it has no spurious local maxima; the negative log-likelihood, its cost-function form, is convex. Second and third, the log-partition function produces the moments by differentiation:

E[y;η]=∂a∂η,Var⁡[y;η]=∂2a∂η2.(4.4) \mathbb{E}[y; \eta] = \frac{\partial a}{\partial \eta} , \qquad \operatorname{Var}[y; \eta] = \frac{\partial^2 a}{\partial \eta^2} . \tag{4.4}

35:08 The point Avati makes about these is practical: computing a mean or a variance normally means integrating against the density, and here it means differentiating a single function, which is far easier. For the Bernoulli, a′(η)=1/(1+e−η)=ϕa'(\eta) = 1/(1+e^{-\eta}) = \phi and a′′(η)=ϕ(1−ϕ)a''(\eta) = \phi(1-\phi); for the Gaussian, a′=η=μa' = \eta = \mu and a′′=1a'' = 1; for the Poisson, both derivatives are eη=λe^\eta = \lambda, the textbook fact that a Poisson’s mean equals its variance. The generator checks all three by computing a′a' and a′′a'' by finite differences and the mean and variance by summing over the support. The first property follows from the third: a variance is never negative, so aa is convex, and the log-likelihood log⁡b(y)+ηy−a(η)\log b(y) + \eta y - a(\eta) is linear minus convex, which is concave. 36:06 When η\eta is a vector, as for a Gaussian with unknown variance, a student asked how this generalises; the gradient of aa gives the mean of T(y)T(y) and its Hessian the covariance.

4.4 Generalized linear models

36:35 A generalized linear model attaches the inputs to an exponential-family distribution, and the lecture frames it as three design choices.

  1. y∣x;θy \mid x; \theta is distributed according to some member of the exponential family, with natural parameter η\eta.
  2. The natural parameter is linear in the input: η=θ⊤x\eta = \theta^\top x, with θ,x∈Rn\theta, x \in \mathbb{R}^n.
  3. At test time, the prediction for xx is the mean of that distribution: hθ(x)=E[y∣x;θ]h_\theta(x) = \mathbb{E}[y \mid x; \theta].

38:36 The first choice is the modelling decision, and it is dictated by what kind of quantity yy is. Real-valued outputs such as house prices call for a Gaussian; binary labels for a Bernoulli; counts — non-negative integers, such as the number of visitors to a website — for a Poisson; positive reals such as a volume or the time until an event for a gamma or an exponential. Avati warns that the exponential distribution and the exponential family are different things, though the first is a member of the second, and the list ends with distributions over probabilities, the beta and the Dirichlet, which mostly appear in Bayesian statistics. Whether a GLM is a classifier or a regressor is therefore not a property of GLMs at all: it is decided by the distribution put in the first slot.

42:55 The picture to keep in mind has two halves. On the left is a linear model: xx goes in, a learnable θ\theta multiplies it, and out comes a number. On the right is a distribution from the exponential family, and that number becomes its natural parameter. 45:40 Only θ\theta is learned. A student asked whether training adjusts the distribution’s parameters, and the answer separates two uses of the word “parameter”: η\eta is not a variable that gradient descent touches, it is the output of the linear model for one particular xx. Training is maximum likelihood over θ\theta,

max⁡θ  ∑i=1mlog⁡p ⁣(y(i);η=θ⊤x(i)), \max_\theta \; \sum_{i=1}^m \log p\!\left(y^{(i)}; \eta = \theta^\top x^{(i)}\right) ,

which is concave in θ\theta because it is concave in η\eta and η\eta is linear in θ\theta.

48:46 Here the recipe pays off. One would expect each new distribution to need its own algebra: write pp as a function of θ⊤x\theta^\top x, differentiate, simplify. It does not, because for every GLM built this way the stochastic gradient-ascent update is

θj:=θj+α(y(i)−hθ(x(i)))xj(i),(4.5) \theta_j := \theta_j + \alpha \left( y^{(i)} - h_\theta(x^{(i)}) \right) x^{(i)}_j , \tag{4.5}

with hθ(x)=a′(θ⊤x)h_\theta(x) = a'(\theta^\top x) the only thing that changes. The derivation is one line: the log-likelihood of one example is log⁡b(y)+θ⊤x y−a(θ⊤x)\log b(y) + \theta^\top x\, y - a(\theta^\top x), and its gradient is (y−a′(θ⊤x)) x(y - a'(\theta^\top x))\, x, which by Equation 4.4 is (y−hθ(x)) x(y - h_\theta(x))\, x. This is why linear regression, logistic regression and Poisson regression share an update: the first is the Gaussian GLM with h=θ⊤xh = \theta^\top x, the second the Bernoulli with h=1/(1+e−θ⊤x)h = 1/(1+e^{-\theta^\top x}), the third the Poisson with h=eθ⊤xh = e^{\theta^\top x}. The generator checks the expression against a numerical gradient of the log-likelihood for all three.

“Every GLM” carries a qualification the lecture leaves implicit: the identity holds because the natural parameter itself is set to θ⊤x\theta^\top x. A model that instead connects θ⊤x\theta^\top x to the mean through some other function does not inherit it. The probit model of lecture 3, P(y=1∣x)=Φ(θ⊤x)P(y = 1 \mid x) = \Phi(\theta^\top x) with Φ\Phi the standard normal CDF, is a Bernoulli model with exactly the same shape, and the update that looks right for it — Equation 4.5 with h=Φ(θ⊤x)h = \Phi(\theta^\top x) — is not its gradient: at a test point on synthetic data it has the right direction but a length off by 41 percent. That would be harmless if it only rescaled the step, but it also moves the place where the step vanishes. Iterated to convergence, the look-alike update stops at θ=(−0.200,0.697)\theta = (-0.200, 0.697), while the probit maximum-likelihood estimate is (−0.210,0.707)(-0.210, 0.707). The two links are close, so the error is small, but the algorithm is now solving a different equation from the one it claims to.

50:43 For batch training, sum the update over the examples. Asked about Newton’s method, Avati calls it probably the most common way to fit a GLM, provided the number of features is below a few thousand, so that the Hessian is affordable — the same rule of thumb Ng gave in lecture 3. Concavity is what makes it safe: on a Poisson regression with 200 synthetic counts, Newton’s method reaches the maximum in 7 iterations, at the same θ\theta that plain gradient ascent eventually finds.

4.5 Three parametrisations

52:03 The lecture pauses on terminology, because a GLM has three sets of numbers called parameters and they are easy to confuse (Figure 4.3). The model parameters θ\theta are what learning adjusts. The natural parameter η\eta is the linear model’s output, one per example. The canonical parameters are the ones the distribution is usually written in: ϕ\phi for a Bernoulli, μ\mu (and σ2\sigma^2) for a Gaussian, λ\lambda for a Poisson. The step from θ\theta to η\eta is linear by design choice 2. The step from η\eta to the mean has a name: g(η)=E[y;η]=a′(η)g(\eta) = \mathbb{E}[y;\eta] = a'(\eta) is the canonical response function, and its inverse g−1g^{-1} is the canonical link function.

Figure 4.3: The three parametrisations of a GLM. Only θ\theta is learned; η=θ⊤x\eta = \theta^\top x is the natural parameter of the distribution for one input; the response function g=a′g = a' maps it to the mean, and the canonical link g−1g^{-1} maps back.

56:23 With the vocabulary in place, logistic regression stops being a choice and becomes a consequence. For a binary label the natural distribution is the Bernoulli; design choice 3 says the hypothesis is its mean, hθ(x)=ϕh_\theta(x) = \phi; and Equation 4.3 says ϕ=1/(1+e−η)\phi = 1/(1 + e^{-\eta}) with η=θ⊤x\eta = \theta^\top x. Lecture 3 pulled the logistic function “out of thin air” because it squashes the real line into (0,1)(0, 1). Here, as Avati puts it, it simply pops out: the sigmoid is the canonical response function of the Bernoulli. The same steps applied to the Gaussian return hθ(x)=θ⊤xh_\theta(x) = \theta^\top x, ordinary least squares.

The idea and the name are due to Nelder and Wedderburn (1972), who showed that one fitting procedure covered regression models that had been treated separately.

NoteIn the official notes

cs229-notes1, section 9, constructs the GLM from the same three assumptions and derives ordinary least squares (9.1) and logistic regression (9.2) from them.

4.6 What the assumptions say about the data

1:00:03 Avati’s last pass over GLMs draws the assumptions as a story about how the data were generated. For the Gaussian, take a line θ⊤x\theta^\top x; at every xx, stand a unit-variance Gaussian on the line; and draw each training yy from the Gaussian above its xx (Figure 4.4, left). Learning runs the story backwards: each choice of θ\theta is a different line, and maximum likelihood picks the line from whose Gaussians the observed points were most likely to have come.

1:04:50 For classification the story has one more step. The line now gives η\eta, which can be any real number; passing it through the sigmoid gives ϕ\phi, the probability that y=1y = 1 at that xx; and each label is a coin flip with that bias, so labels are mostly 0 where the curve is low and mostly 1 where it is high (Figure 4.4, right). Logistic regression asks which θ\theta would have produced a sigmoid from which these labels were most likely drawn.

Figure 4.4: The data-generating process each GLM assumes, sampled from the model. Left: Gaussian yy around the line θ⊤x\theta^\top x, with the density drawn sideways at three inputs. Right: Bernoulli labels whose probability of being 1 follows g(θ⊤x)g(\theta^\top x). Computed by figures/04-perceptron-glm/make_diagrams.py.

4.7 Softmax regression

1:07:58 Softmax regression extends logistic regression to kk classes. The notes present it as one more GLM, built on the multinomial distribution; the lecture deliberately takes another route and presents it as cross-entropy minimisation, an interpretation worth having because it is how classifiers with thousands of classes are usually described.

1:11:04 The labels are one-hot vectors: a vector of kk zeros with a single 1 in the position of the correct class. Where logistic regression had one parameter vector, softmax has one per class, θ1,…,θk\theta_1, \dots, \theta_k, which together form an n×kn \times k matrix. For an input xx, each class gets a score θc⊤x\theta_c^\top x, called a logit, which can be any real number. 1:16:24 To turn the scores into a probability distribution over classes, exponentiate them, which makes them all positive, and divide by their sum, which makes them add to one:

p^(y=c∣x)=exp⁡(θc⊤x)∑j=1kexp⁡(θj⊤x).(4.6) \hat p(y = c \mid x) = \frac{\exp(\theta_c^\top x)}{\sum_{j=1}^k \exp(\theta_j^\top x)} . \tag{4.6}

1:19:09 The label is read as a distribution too, p(y)p(y), which puts probability 1 on the correct class. Learning makes p^\hat p look like pp by minimising the cross entropy between them,

CE(p,p^)=−∑c=1kp(c)log⁡p^(c)=−log⁡p^(y∣x),(4.7) \mathrm{CE}(p, \hat p) = -\sum_{c=1}^k p(c) \log \hat p(c) = -\log \hat p(y \mid x) , \tag{4.7}

where the sum collapses because pp is zero everywhere except at the true class yy. (The minus sign is missing from the board the first time; it belongs there, since the loss has to be non-negative.) Figure 4.5 follows one example through the pipeline: an input whose true class is triangle but which scores highest for square receives p^(triangle)=0.19\hat p(\text{triangle}) = 0.19 and a loss of 1.67. The last expression in Equation 4.7 is the negative log-likelihood of a multinomial model, so the lecture’s route and the notes’ arrive at the same objective. Its gradient for class cc is (p^(c∣x)−1{y=c}) x(\hat p(c \mid x) - \mathbb{1}\{y = c\})\, x, the same “prediction minus truth, times input” shape as Equation 4.5; and with k=2k = 2 the softmax probability of class 1 is exactly 1/(1+e−(θ1−θ2)⊤x)1/(1 + e^{-(\theta_1 - \theta_2)^\top x}), logistic regression with θ=θ1−θ2\theta = \theta_1 - \theta_2.

Figure 4.5: Softmax regression for one example. The logits are exponentiated, then normalised into a distribution p^\hat p over the three classes; the label is a one-hot distribution on triangle, and the cross-entropy loss is −log⁡p^(triangle∣x)-\log \hat p(\text{triangle} \mid x). Computed by figures/04-perceptron-glm/make_diagrams.py.

1:12:53 That two-class reduction exposes something the board picture hides. The lecture draws one line per class, θc⊤x=0\theta_c^\top x = 0, with each class’s own region on the positive side, as though each θc\theta_c carves out its class independently. But Equation 4.6 is unchanged if the same vector cc is added to every θj\theta_j: the factor ec⊤xe^{c^\top x} cancels between numerator and denominator. Only the differences θi−θj\theta_i - \theta_j matter, so the decision boundary between two classes is (θi−θj)⊤x=0(\theta_i - \theta_j)^\top x = 0, and the individual lines θc⊤x=0\theta_c^\top x = 0 can be moved anywhere without changing a single prediction (Figure 4.6). On the fitted model in the figure, the board’s picture — exactly one positive score, and it belongs to the predicted class — holds on only 45 percent of the plotted square even before any shift. This redundancy is why the official notes give softmax only k−1k - 1 parameter vectors and fix θk=0\theta_k = 0: the kk-th vector adds nothing a shift could not remove.

Figure 4.6: The same softmax model with every θc\theta_c shifted by one common vector. The shaded decision regions are identical; the dashed lines θc⊤x=0\theta_c^\top x = 0 move to entirely different places, because they carry no meaning on their own. Fitted by gradient descent in figures/04-perceptron-glm/make_diagrams.py.
NoteIn the official notes

cs229-notes1, section 9.3, derives softmax regression as the GLM for the multinomial distribution, with T(y)T(y) a (k−1)(k-1)-dimensional indicator vector, and arrives at the same hypothesis and log-likelihood.