Machine Learning from First Principles

Chapter 7 · Part II: Supervised Learning

Generalized Linear Models

Linear, logistic, and softmax regression share one recipe: an exponential-family distribution whose natural parameter is linear in the inputs. Learn the recipe once and you can build a correct model for counts, durations, or any other kind of label.

After this chapter you will be able to

  • Recognize the common structure shared by linear, logistic, and softmax regression.
  • Write the Bernoulli, Gaussian, Poisson, and categorical distributions in exponential-family form.
  • Prove that the log-partition function generates the mean and the variance.
  • Construct a generalized linear model from three assumptions and derive its hypothesis.
  • Show that every GLM with a canonical link has the gradient “error times input” and a concave log-likelihood, and fit it with Newton’s method (IRLS).
  • Model count data with Poisson regression.

7.1Three Models, One Pattern

Look back at the models of the last three chapters:

ModelLabelDistribution of $y$ given $\vx$Prediction $\E[y\mid\vx]$
Linear regression$y\in\R$Gaussian$\vtheta\T\vx$
Logistic regression$y\in\{0,1\}$Bernoulli$\sigma(\vtheta\T\vx)$
Softmax regression$y\in\{1..K\}$Categorical$\softmax(\mathbf\Theta\T\vx)$

In each case a linear score $\vtheta\T\vx$ is passed through a fixed function to give the mean of a distribution, the loss is the negative log-likelihood, and the gradient has the same form, $\sum_i(\text{prediction}-\text{label})\,\vx^{(i)}$ (Equations (2.4), (6.4), and (6.7)). This is not a coincidence. All three are generalized linear models (GLMs) (Nelder and Wedderburn 1972), and the reason they behave alike is that all three distributions belong to the exponential family. Understanding the family once lets us build a correct model for any new kind of label, such as counts, durations, or proportions, in a few lines.

7.2The Exponential Family

Definition 7.1 (Exponential family)

A family of distributions over $y$ with parameter $\eta$ is an exponential family if its density or mass function can be written as

$$p(y;\eta) = b(y)\exp\big(\eta\,T(y)-a(\eta)\big). \tag{7.1}$$

Here $\eta$ is the natural parameter, $T(y)$ the sufficient statistic (for us usually $T(y)=y$), $b(y)$ the base measure, and $a(\eta)$ the log-partition function, which makes the distribution sum or integrate to one: $a(\eta)=\log\int b(y)e^{\eta T(y)}\dd y$.

Rewriting familiar distributions in this form is a matter of moving everything into one exponential.

Bernoulli. With mean $\phi$,

$$p(y;\phi)=\phi^y(1-\phi)^{1-y}=\exp\Big(y\log\frac{\phi}{1-\phi}+\log(1-\phi)\Big).$$

So $T(y)=y$, $b(y)=1$, $\eta=\log\frac{\phi}{1-\phi}$ (the log-odds), and inverting, $\phi=1/(1+e^{-\eta})=\sigma(\eta)$: the sigmoid appears on its own. The log-partition function is $a(\eta)=-\log(1-\phi)=\log(1+e^\eta)$.

Gaussian with unit variance.

$$p(y;\mu)=\frac{1}{\sqrt{2\pi}}e^{-(y-\mu)^2/2}=\underbrace{\frac{1}{\sqrt{2\pi}}e^{-y^2/2}}_{b(y)}\exp\Big(\mu y-\frac{\mu^2}2\Big),$$

so $\eta=\mu$ and $a(\eta)=\eta^2/2$. (A known variance $\sigma^2\ne1$ only rescales the loss; it does not change the fitted mean.)

Poisson. For counts $y\in\{0,1,2,\dots\}$ with rate $\lambda$,

$$p(y;\lambda)=\frac{e^{-\lambda}\lambda^y}{y!}=\frac{1}{y!}\exp\big(y\log\lambda-\lambda\big),$$

so $\eta=\log\lambda$, $b(y)=1/y!$, and $a(\eta)=e^\eta$.

Categorical. For $K$ classes with probabilities $\phi_1,\dots,\phi_K$, take $T(y)\in\R^{K-1}$ with $T(y)_k=\mathbb 1[y=k]$ (class $K$ is the reference, encoded as all zeros). Then $\eta_k=\log(\phi_k/\phi_K)$, and solving for the probabilities gives $\phi_k=e^{\eta_k}/\big(1+\sum_{j<K}e^{\eta_j}\big)$: the softmax function (with the reference class’s score fixed at 0).

Proposition 7.1 (The log-partition function generates moments)

For an exponential family with $T(y)=y$,

$$\E[y;\eta]=a'(\eta),\qquad \Var[y;\eta]=a''(\eta). \tag{7.2}$$
Show proof

Differentiate the identity $e^{a(\eta)}=\int b(y)e^{\eta y}\dd y$ with respect to $\eta$: $a'(\eta)e^{a(\eta)}=\int y\,b(y)e^{\eta y}\dd y$, so $a'(\eta)=\int y\,p(y;\eta)\dd y=\E[y]$. Differentiating $a'(\eta)=\int y\,b(y)e^{\eta y-a(\eta)}\dd y$ once more gives $a''(\eta)=\int y(y-a'(\eta))p(y;\eta)\dd y=\E[y^2]-\E[y]^2$.

Check it: for the Bernoulli, $a'(\eta)=e^\eta/(1+e^\eta)=\sigma(\eta)=\phi$ and $a''=\sigma(1-\sigma)=\phi(1-\phi)$; for the Poisson, $a'(\eta)=a''(\eta)=e^\eta=\lambda$, the famous fact that a Poisson’s mean equals its variance. Since a variance is nonnegative, $a$ is always convex, and this convexity is what makes GLMs easy to fit.

7.3Constructing a GLM

A GLM is built from three design choices:

  1. Distribution. Given $\vx$, the label follows an exponential-family distribution: $y\mid\vx;\vtheta\sim\mathrm{ExpFamily}(\eta)$. Choose the family that matches the type of label: Gaussian for real values, Bernoulli for binary, Poisson for counts, categorical for classes.
  2. Prediction. The model predicts the conditional mean: $h_{\vtheta}(\vx)=\E[y\mid\vx;\vtheta]$.
  3. Linearity. The natural parameter is linear in the inputs: $\eta=\vtheta\T\vx$.

Then $h_{\vtheta}(\vx)=a'(\vtheta\T\vx)$ by Equation (7.2). The function $g=(a')^{-1}$ that maps the mean to the natural parameter is called the canonical link, and its inverse $a'$ the response function:

FamilyResponse $h=a'(\eta)$Canonical link $\eta=g(\mu)$Resulting model
Gaussian$\eta$$\mu$ (identity)linear regression
Bernoulli$1/(1+e^{-\eta})$$\log\frac{\mu}{1-\mu}$ (logit)logistic regression
Poisson$e^{\eta}$$\log\mu$ (log)Poisson regression
Categoricalsoftmaxlog-ratiossoftmax regression

The sigmoid in logistic regression and the softmax in multiclass classification, which we introduced as convenient squashing functions in Chapter 6, are therefore not arbitrary choices: they are the canonical responses of the Bernoulli and categorical families.

7.4Fitting GLMs

With $\eta_i=\vtheta\T\vx^{(i)}$, the log-likelihood of the training data is

$$\ell(\vtheta) = \sum_{i=1}^n\Big[\log b(y^{(i)}) + y^{(i)}\,\vtheta\T\vx^{(i)} - a(\vtheta\T\vx^{(i)})\Big].$$

Differentiating, using $a'(\eta_i)=h_{\vtheta}(\vx^{(i)})$ and $a''(\eta_i)=\Var[y\mid\vx^{(i)}]$:

$$\nabla\ell(\vtheta)=\sum_{i=1}^n\big(y^{(i)}-h_{\vtheta}(\vx^{(i)})\big)\vx^{(i)},\qquad \nabla^2\ell(\vtheta)=-\sum_{i=1}^n a''(\eta_i)\,\vx^{(i)}\vx^{(i)\top}=-\mX\T\mathbf W\mX \tag{7.3}$$

with $\mathbf W=\diag(a''(\eta_1),\dots,a''(\eta_n))$. Two consequences hold for every GLM with a canonical link:

  • The gradient is “error times input,” explaining the identical update rules of linear, logistic, and softmax regression.
  • The Hessian is negative semidefinite, because the weights are variances. The log-likelihood is concave, so any local maximum is global and Newton’s method converges reliably.

Newton’s method and IRLS. Newton’s method (Section 3.8) updates $\vtheta\gets\vtheta-(\nabla^2\ell)^{-1}\nabla\ell$, which here is

$$\vtheta\gets\vtheta+(\mX\T\mathbf W\mX)^{-1}\mX\T(\vy-\vmu), \tag{7.4}$$

with $\vmu$ the vector of current predictions. Rearranging shows that each step solves a weighted least-squares problem, $\vtheta_{\text{new}}=(\mX\T\mathbf W\mX)^{-1}\mX\T\mathbf W\vz$, with the working response $\vz=\mX\vtheta+\mathbf W^{-1}(\vy-\vmu)$. This is why statistical software calls the algorithm iteratively reweighted least squares (IRLS). It typically converges in 5–10 iterations, far fewer than gradient descent, because the GLM log-likelihood is close to quadratic near its maximum.

7.5Poisson Regression for Counts

Suppose we want to predict the number of support tickets a software product receives per day from its number of active users, or the number of insurance claims per customer. Counts are nonnegative integers, and their variance typically grows with their mean. Linear regression ignores both facts: it can predict negative counts and assumes a constant variance.

Poisson regression assumes $y\mid\vx\sim\mathrm{Poisson}(\lambda)$ with $\log\lambda=\vtheta\T\vx$, so

$$\E[y\mid\vx]=e^{\vtheta\T\vx}. \tag{7.5}$$

Predictions are always positive, the variance equals the mean, and each weight has a multiplicative meaning: increasing $x_j$ by one multiplies the expected count by $e^{\theta_j}$. If counts are observed over different exposures (days, population sizes), add $\log(\text{exposure})$ as a feature with weight fixed to 1, an offset, so the model predicts a rate.

Pitfall: Overdispersion

Real counts are often more variable than a Poisson allows (variance much larger than the mean), for example because of unmeasured differences between customers. The fitted means can still be fine, but standard errors and probability statements will be overconfident. The negative binomial distribution, which adds a dispersion parameter, is the usual fix.

7.6Implementation

A generic GLM fitted by Newton’s method needs only the response function and its derivative for each family:

import numpy as np

FAMILIES = {   # response h(eta) and variance a''(eta)
    "gaussian":  (lambda e: e,               lambda e: np.ones_like(e)),
    "bernoulli": (lambda e: 1 / (1 + np.exp(-e)), lambda e: (1 / (1 + np.exp(-e))) * (1 - 1 / (1 + np.exp(-e)))),
    "poisson":   (lambda e: np.exp(e),       lambda e: np.exp(e)),
}

def fit_glm(X, y, family, iters=25, lam=1e-8):
    h, var = FAMILIES[family]
    theta = np.zeros(X.shape[1])
    for _ in range(iters):
        eta = X @ theta
        mu, w = h(eta), var(eta)
        grad = X.T @ (y - mu)                            # Eq. (7.3)
        H = X.T @ (w[:, None] * X) + lam * np.eye(len(theta))
        step = np.linalg.solve(H, grad)                  # Newton step = IRLS
        theta += step
        if np.max(np.abs(step)) < 1e-10:
            break
    return theta

rng = np.random.default_rng(0)
x = rng.uniform(0, 3, 300)
X = np.column_stack([np.ones_like(x), x])
y = rng.poisson(np.exp(0.4 + 0.8 * x))
theta = fit_glm(X, y, "poisson")
print(theta)                                             # close to [0.4, 0.8]

from sklearn.linear_model import PoissonRegressor
ref = PoissonRegressor(alpha=0).fit(x[:, None], y)
print(ref.intercept_, ref.coef_)                         # the same fit

7.7Common Pitfalls

Pitfall: Fitting counts or rates with least squares

Least squares on raw counts can predict negative values and gives the many small counts the same weight as a few huge ones. A log transform helps but cannot handle zeros cleanly. Use Poisson (or negative binomial) regression.

Pitfall: Separation and huge weights

As with logistic regression (Chapter 6), if the data make some predictions perfectly certain, the maximum likelihood estimate does not exist and Newton’s method diverges. Add a small ridge penalty, as lam does above.

7.8Summary

  • Exponential-family distributions have the form $b(y)\exp(\eta T(y)-a(\eta))$; Gaussian, Bernoulli, Poisson, and categorical distributions all qualify.
  • The log-partition function gives the mean, $a'(\eta)$, and the variance, $a''(\eta)$, so it is convex.
  • A GLM assumes an exponential-family label, predicts its mean, and makes the natural parameter linear: $h_{\vtheta}(\vx)=a'(\vtheta\T\vx)$.
  • For canonical links the gradient is $\sum_i(y^{(i)}-h(\vx^{(i)}))\vx^{(i)}$ and the log-likelihood is concave; Newton’s method is IRLS.
  • Poisson regression models counts with $\E[y\mid\vx]=e^{\vtheta\T\vx}$.

7.9Exercises

  1. MathWrite the exponential distribution $p(y;\lambda)=\lambda e^{-\lambda y}$, $y\ge0$, in exponential-family form. What are $\eta$, $a(\eta)$, and the canonical response? Verify Equation (7.2).
  2. MathDerive the softmax response from the categorical distribution in exponential-family form, and show that $\nabla_{\vtheta_k}\ell=\sum_i(\mathbb 1[y^{(i)}=k]-\phi_k^{(i)})\vx^{(i)}$.
  3. MathShow that the Newton update for a GLM equals the weighted least-squares solution with working response $\vz=\mX\vtheta+\mathbf W^{-1}(\vy-\vmu)$.
  4. MathFor Poisson regression with only an intercept, show that the maximum likelihood estimate is $\theta_0=\log\bar y$.
  5. CodingSimulate overdispersed counts by drawing $\lambda_i$ from a gamma distribution around $e^{\vtheta\T\vx_i}$ and then $y_i\sim\mathrm{Poisson}(\lambda_i)$. Fit Poisson regression and compare the empirical variance of the residuals with the model’s implied variance.
  6. CodingCompare gradient descent and Newton’s method for logistic regression on load_breast_cancer: plot the log-likelihood against iterations for each.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.