Multinomial and Softmax Regression

The model at the output layer of a language model, treated as a generalized linear model. The categorical distribution as an exponential family whose mean map is the softmax; the softmax derived from noisy scores (the Gumbel-max rule); identifiability, the reference class, and what gradient descent and an L2 penalty do with the free direction; the score X^T(Y - Π), the gradient π - y and the Hessian; concavity, strict concavity and Böhning's curvature bound; when the maximum likelihood estimate exists (separation, with the bigram model as a case where it does not); and maximum likelihood as conditional maximum entropy, all proved. Worked on NHANES self-rated health and on the output layer of a small character GPT trained for this article. Worked problems on the intercept-only fit, the saturated age-group model, separation in a three-class example and Gumbel-max sampling.

A small GPT trained for this article reads up to 32 characters of Shakespeare and, at each position, reduces what it has read to a list of 64 numbers. Its last layer turns that list into a probability for each of the 65 characters that could come next: 65 scores, each a weighted sum of the 64 numbers plus a bias, passed through a softmax. Thirty copies trained from different seeds reach a median validation loss of 1.874 nats per character. The Transformer of Vaswani et al. (2017, Section 3.4) ends the same way, with "the usual learned linear transformation and softmax function" to produce next-token probabilities. What statistical model is that last layer, what are its likelihood and its gradient, and does fitting it have a single answer? It is a multinomial logistic regression of the next character on the 64 numbers. Its log-likelihood is minus the training loss, up to the factor $n$ (the number of positions), and its gradient with respect to the scores is the predicted distribution minus the indicator of the character that occurred. Fitting it has a single answer only after the parameters that change no prediction are fixed, and only when no direction of the parameters separates the characters.

The model of that last layer is softmax regression, known in statistics as multinomial logistic regression or the baseline-category logit model. A categorical outcome $Y_i$ takes one of $K$ classes, and its probabilities are the softmax of $K$ linear scores of a vector of inputs $\mathbf{x}_i$:

$$\pi_{ik} = P(Y_i = k \mid \mathbf{x}_i) = \frac{e^{\eta_{ik}}}{\sum_{j=1}^{K} e^{\eta_{ij}}}, \qquad \eta_{ik} = \mathbf{x}_i^{\mathsf T}\boldsymbol\beta_k, \qquad k = 1, \ldots, K.$$

With $K = 2$ it is logistic regression. It is the last member of the Generalized Linear Models unit, and the one whose response is a vector rather than a number.

First we write one categorical observation as an exponential family and find that its mean map is the softmax. Then we derive the softmax a second way, as the choice of the largest of $K$ noisy scores. Next comes the parametrization: the coefficients are determined only up to a common shift, and we prove what a reference class, gradient descent and an L2 penalty each do about it. Then the likelihood: its score, the gradient $\boldsymbol\pi - \mathbf{y}$, its Hessian, its concavity and a bound on its curvature. Then the question of when the maximum exists at all, and the reading of the fitted model as a maximum entropy distribution. The model is fitted to two datasets throughout: self-rated health in NHANES and the output layer of a small GPT. The article assumes Exponential Families, Link Functions and the Structure of a Generalized Linear Model and Iteratively Reweighted Least Squares for the general theory, and Cross-Entropy and Kullback–Leibler Divergence for the divergence.

This article is the site's home of the multinomial model. Activation Functions defines the softmax and computes its Jacobian, and Maximum Entropy Distributions proves that the softmax of a fixed score vector is a maximum entropy distribution; both are used here and not repeated.

Notation and the running data

There are $n$ observations and $K$ classes. Observation $i$ has an input vector $\mathbf{x}_i$ of length $p$, with the intercept (a column of ones) counted in $p$ as in the Linear Models unit. Its class is $y_i \in \{1, \ldots, K\}$, written also as the one-hot vector $\mathbf{y}_i = (y_{i1}, \ldots, y_{iK})$ with $y_{ik} = 1$ if observation $i$ is in class $k$ and 0 otherwise. Context decides whether $y_i$ means the class or the vector. The design matrix $X$ is $n \times p$ with rows $\mathbf{x}_i^{\mathsf T}$ and full column rank $p$. The $n \times K$ matrices $Y$ and $\Pi$ hold the $\mathbf{y}_i$ and the probability vectors $\boldsymbol\pi_i = (\pi_{i1}, \ldots, \pi_{iK})$ as rows. The coefficients form the $p \times K$ matrix $B = [\boldsymbol\beta_1, \ldots, \boldsymbol\beta_K]$, one column per class, and $\mathbf{1}$ is a vector of ones of the length the context needs. Logarithms are natural. The machine-learning pages of the site write $\mathbf{p}$ for $\boldsymbol\pi_i$ and call the scores $\eta_{ik}$ logits; the two vocabularies name the same things.

Self-rated health. The NHANES 2017–2018 interview asked "Would you say your health in general is . . ." with the answers excellent, very good, good, fair or poor (question HUQ010 in the survey's documentation; National Center for Health Statistics, 2020). Of the 5,242 adults in the course's NHANES sample who answered, 5,171 also have a body mass index (BMI) measured. Their answers are 596 excellent, 1,367 very good, 1,932 good, 1,076 fair and 200 poor. The inputs are age (in decades from 50), sex (an indicator for female; 2,661 women) and BMI (in units of 5 kg/m² from 30). The sample is treated as a population of individuals and its survey weights are ignored, as on the course pages.

The output layer of a small GPT. The site's walkthrough Language Models from Scratch builds a character-level GPT and trains it on the Tiny Shakespeare text (Karpathy, 2015). Its final model has 10,788,929 parameters (Scaling the Shakespeare GPT), more than could be trained 30 times on a CPU for this article. So we trained a reduced model with the same structure: token and position embeddings of width $C = 64$, three pre-norm Transformer blocks with four attention heads each, a final layer normalization and the LM head, as in Assembling the Transformer Block. The context is 32 characters, there is no dropout, and training uses Adam with learning rate 0.001, batches of 32 windows and 2,500 steps. The model was trained 30 times, with seeds 1 to 30, on the walkthrough's training split, the first 90% of the text (PyTorch 2.15 on a CPU). After training the network is held fixed. At each position $i$ the output $\mathbf{h}_i$ of the final layer normalization is the input of the head, so the head is a softmax regression with $\mathbf{x}_i = (\mathbf{h}_i, 1)$, $p = 65$ and $K = 65$ classes, one per character. Its $65 \times 65 = 4{,}225$ weights and biases are the $pK$ entries of $B$.

One categorical observation as an exponential family

Here is the idea. A single categorical observation has probability $\prod_k \pi_k^{y_k}$, which is the exponential of a linear function of the one-hot vector. Rewriting that linear function with one class as a reference puts it in the exponential family form of Exponential Families, whose general theorems then say that the mean is the gradient of the log-partition function and the covariance its Hessian. For this family the gradient is the softmax.

Theorem 1 (the categorical distribution as an exponential family). Let $\mathbf{Y}$ be the one-hot vector of a categorical variable with probabilities $\pi_1, \ldots, \pi_K$, all positive. Write $\mathbf{T}(\mathbf{y}) = (y_1, \ldots, y_{K-1})$ and

$$\theta_k = \ln\frac{\pi_k}{\pi_K}, \qquad k = 1, \ldots, K - 1, \qquad A(\boldsymbol\theta) = \ln\Big(1 + \sum_{k=1}^{K-1} e^{\theta_k}\Big).$$

  1. The mass function is $P(\mathbf{Y} = \mathbf{y}) = \exp\{\boldsymbol\theta^{\mathsf T}\mathbf{T}(\mathbf{y}) - A(\boldsymbol\theta)\}$, for every $\boldsymbol\theta$ in $\mathbb{R}^{K-1}$.
  2. The gradient of $A$ is the softmax: $\partial A/\partial\theta_k = e^{\theta_k}/(1 + \sum_j e^{\theta_j}) = \pi_k$, which is $E[Y_k]$.
  3. The Hessian of $A$ is $\operatorname{Cov}(\mathbf{T}) = \operatorname{diag}(\pi_1, \ldots, \pi_{K-1}) - \tilde{\boldsymbol\pi}\tilde{\boldsymbol\pi}^{\mathsf T}$, where $\tilde{\boldsymbol\pi} = (\pi_1, \ldots, \pi_{K-1})$. It is positive definite.
  4. The covariance of the whole one-hot vector, $\Sigma(\boldsymbol\pi) = \operatorname{diag}(\boldsymbol\pi) - \boldsymbol\pi\boldsymbol\pi^{\mathsf T}$, is positive semidefinite of rank $K - 1$, and its null space is spanned by $\mathbf{1}$.

Proof. Part 1. Since $y_K = 1 - \sum_{k<K} y_k$,

$$\prod_{k=1}^{K}\pi_k^{y_k} = \exp\Big\{\sum_{k=1}^{K} y_k\ln\pi_k\Big\} = \exp\Big\{\sum_{k=1}^{K-1} y_k\ln\frac{\pi_k}{\pi_K} + \ln\pi_K\Big\}.$$

From $\pi_k = \pi_K e^{\theta_k}$ for $k < K$ and $\sum_k\pi_k = 1$ we get $\pi_K(1 + \sum_{k<K}e^{\theta_k}) = 1$, so $\ln\pi_K = -A(\boldsymbol\theta)$. Conversely every $\boldsymbol\theta$ in $\mathbb{R}^{K-1}$ gives positive probabilities $\pi_K = e^{-A(\boldsymbol\theta)}$ and $\pi_k = e^{\theta_k - A(\boldsymbol\theta)}$ that sum to 1, so the natural parameter space is all of $\mathbb{R}^{K-1}$.

Part 2. Differentiate: $\partial A/\partial\theta_k = e^{\theta_k}/(1 + \sum_j e^{\theta_j}) = e^{\theta_k - A} = \pi_k$. Setting $\theta_K = 0$, this is the softmax of $(\theta_1, \ldots, \theta_{K-1}, 0)$, and $E[Y_k] = P(Y_k = 1) = \pi_k$.

Part 3. Differentiate again: $\partial\pi_k/\partial\theta_l = \pi_k(\delta_{kl} - \pi_l)$, with $\delta_{kl} = 1$ if $k = l$ and 0 otherwise. Directly, $\operatorname{Var}(Y_k) = \pi_k - \pi_k^2$ and, for $k \ne l$, $E[Y_kY_l] = 0$, so $\operatorname{Cov}(Y_k, Y_l) = -\pi_k\pi_l$; the two agree, as Theorem 2 of Exponential Families (the log-partition function generates the cumulants) requires. For a vector $\mathbf{v} = (v_1, \ldots, v_K)$ let $v_Y$ be the entry picked out by the class. Then

$$\mathbf{v}^{\mathsf T}\Sigma(\boldsymbol\pi)\mathbf{v} = \sum_k\pi_k v_k^2 - \Big(\sum_k\pi_k v_k\Big)^2 = \operatorname{Var}(v_Y) \ge 0. \qquad (1)$$

The variance is zero only if $v_Y$ is constant with probability one, and since every $\pi_k > 0$ that means $v_1 = \cdots = v_K$. The matrix of part 3 is $\Sigma$ restricted to vectors with $v_K = 0$, for which equal entries means $\mathbf{v} = \mathbf{0}$; so it is positive definite. Part 4. By (1), $\Sigma$ is positive semidefinite and $\mathbf{v}^{\mathsf T}\Sigma\mathbf{v} = 0$ exactly when $\mathbf{v}$ is a multiple of $\mathbf{1}$. For a positive semidefinite matrix, $\mathbf{v}^{\mathsf T}\Sigma\mathbf{v} = 0$ is equivalent to $\Sigma\mathbf{v} = \mathbf{0}$ (write $\Sigma = LL^{\mathsf T}$; then $\mathbf{v}^{\mathsf T}\Sigma\mathbf{v} = \lVert L^{\mathsf T}\mathbf{v}\rVert^2$). So the null space is spanned by $\mathbf{1}$, and the rank is $K - 1$. $\square$

Three remarks follow.

  • The canonical link. The natural parameter is the vector of log-ratios $\theta_k = \ln(\pi_k/\pi_K)$, the generalized logits of each class against the reference class $K$. A generalized linear model with the canonical link sets the natural parameter equal to the linear predictor (Link Functions, Theorem 1, proves the consequences for one-dimensional responses). Here that is $K - 1$ linear predictors, $\ln(\pi_{ik}/\pi_{iK}) = \mathbf{x}_i^{\mathsf T}\boldsymbol\beta_k$, and inverting the link gives the softmax of the introduction with $\boldsymbol\beta_K = \mathbf{0}$. Agresti (2013, Section 8.1) calls these baseline-category logit models, and McCullagh and Nelder (1989, Chapter 5) treat polytomous responses within the theory of generalized linear models.
  • Counts. For $m$ independent categorical draws with the same probabilities, the vector of counts is multinomial. Its mass function is the product of $m$ copies of part 1 times the multinomial coefficient. So it has the same natural parameter, with log-partition function $mA(\boldsymbol\theta)$, mean $m\boldsymbol\pi$ and covariance $m\Sigma(\boldsymbol\pi)$. The Chi-Square Goodness-of-Fit Test derives that mean and covariance directly. Data grouped by identical inputs are therefore fitted with the counts, as in Problem 2.
  • Two classes. With $K = 2$, $\theta_1 = \ln[\pi_1/(1 - \pi_1)]$ is the logit and $A(\theta) = \ln(1 + e^\theta)$, the Bernoulli family of Link Functions.

Part 4 is the root of the identifiability question below: the one-hot vector lives in a $(K-1)$-dimensional set (its entries sum to 1), so one direction of any $K$-vector of scores carries no information.

The softmax as a choice among noisy scores

The softmax also arises without any exponential family, as the probability that each class wins a contest of noisy scores. This derivation explains the softmax's use in sampling from language models, and it extends the latent-variable derivation of the logit link in Link Functions (its Theorem 2) from two classes to $K$.

A standard Gumbel variable $G$ has distribution function $F(g) = \exp(-e^{-g})$ and density $f(g) = e^{-g}\exp(-e^{-g})$ on the whole line.

Theorem 2 (Gumbel-max). Let $G_1, \ldots, G_K$ be independent standard Gumbel variables, let $\eta_1, \ldots, \eta_K$ be real numbers, and let $U_k = \eta_k + G_k$. Then

$$P\big(U_k = \max_j U_j\big) = \frac{e^{\eta_k}}{\sum_{j} e^{\eta_j}},$$

and the maximum $\max_j U_j$ is itself Gumbel, located at $\ln\sum_j e^{\eta_j}$: $P(\max_j U_j \le u) = \exp\big(-e^{-(u - \ln S)}\big)$ with $S = \sum_j e^{\eta_j}$.

Proof. Ties have probability zero because the $U_j$ are independent with densities. Condition on $G_k = g$. Class $k$ wins when $G_j < \eta_k - \eta_j + g$ for every $j \ne k$, which by independence has probability $\prod_{j \ne k} F(\eta_k - \eta_j + g) = \exp\big(-e^{-g}\sum_{j \ne k} e^{\eta_j - \eta_k}\big)$. Multiply by the density of $G_k$ and integrate:

$$P(k \text{ wins}) = \int_{-\infty}^{\infty} e^{-g}\exp\Big(-e^{-g}\Big[1 + \sum_{j \ne k} e^{\eta_j - \eta_k}\Big]\Big)\,dg = \int_{-\infty}^{\infty} e^{-g}\exp\big(-e^{-g}\,c\big)\,dg, \qquad c = S e^{-\eta_k}.$$

Substitute $t = e^{-g}$, so $dt = -e^{-g}\,dg$ and $t$ runs from $\infty$ to 0: the integral is $\int_0^\infty e^{-ct}\,dt = 1/c = e^{\eta_k}/S$. For the maximum, $P(\max_j U_j \le u) = \prod_j F(u - \eta_j) = \exp\big(-e^{-u}\sum_j e^{\eta_j}\big) = \exp\big(-e^{-(u - \ln S)}\big)$. $\square$

Two consequences.

  • Sampling. To draw a class from the softmax of the scores, add independent Gumbel noise to each score and take the largest. A language model sampled at temperature $T$ draws from the softmax of $\eta_k/T$, so it can equally add Gumbel noise to $\eta_k/T$ and take the argmax. Problem 4 checks the rule by simulation.
  • The log-sum-exp. By the second part, $\max_j U_j$ has the distribution of $\ln\sum_j e^{\eta_j} + G$ with $G$ standard Gumbel, so $E[\max_j U_j] = \ln\sum_j e^{\eta_j} + E[G]$, where $E[G]$ is a constant that does not depend on the scores. The normalizing term $\ln\sum_j e^{\eta_j}$ of the softmax, which is $A$ in Theorem 1 when $\eta_K = 0$, is therefore the expected best noisy score up to a fixed constant. Train (2009, Section 3.5) meets the same term as the "log-sum term" of expected consumer surplus.

In econometrics this is the random-utility derivation of the multinomial logit model of choice, with the scores as the observed parts of the utilities. Train (2009, Section 3.1) recounts its history. The logit formula was first derived from axioms about choice probabilities, and extreme value errors were later shown to lead to it. McFadden (1974, Lemma 2) showed the converse under mild conditions, that the formula implies extreme value errors, and Train's derivation of the choice probabilities follows McFadden. In the same years Theil (1969) extended the linear logit model to several categories. With $K = 2$ the difference of two independent Gumbel variables has the logistic distribution (proved in Rating Models from Pairwise Comparisons, where the same Gumbel noise gives the Bradley–Terry model; Train, 2009, Section 3.1), and the theorem reduces to the latent-variable form of logistic regression.

Identifiability: one free direction

Back to the regression. The probabilities $\pi_{ik}$ depend on the scores only through their differences: adding the same number to every score of observation $i$ multiplies numerator and denominator of the softmax by the same factor (Activation Functions, "only differences matter"). For the coefficients this means that adding one vector $\mathbf{c}$ to every column of $B$ changes no probability, because it adds $\mathbf{x}_i^{\mathsf T}\mathbf{c}$ to every score of observation $i$. The next theorem says that this is the only freedom.

Theorem 3 (identifiability). Let $X$ have full column rank. Two coefficient matrices $B$ and $B'$ give the same probabilities $\pi_{ik}$ for every observation $i$ and class $k$ if and only if $B' = B + \mathbf{c}\mathbf{1}^{\mathsf T}$ for some vector $\mathbf{c}$ of length $p$, that is, $\boldsymbol\beta'_k = \boldsymbol\beta_k + \mathbf{c}$ for every $k$. In particular, under the constraint $\boldsymbol\beta_K = \mathbf{0}$ the coefficients are determined by the probabilities.

Proof. "If" was shown above. For "only if": equal probabilities give equal log-ratios, $\eta'_{ik} - \eta'_{iK} = \ln(\pi_{ik}/\pi_{iK}) = \eta_{ik} - \eta_{iK}$ for all $i$ and $k$. In matrix form, $X\big[(\boldsymbol\beta'_k - \boldsymbol\beta'_K) - (\boldsymbol\beta_k - \boldsymbol\beta_K)\big] = \mathbf{0}$. Full column rank means $X\mathbf{v} = \mathbf{0}$ only for $\mathbf{v} = \mathbf{0}$, so $\boldsymbol\beta'_k - \boldsymbol\beta_k = \boldsymbol\beta'_K - \boldsymbol\beta_K$ for every $k$. Call this common vector $\mathbf{c}$. $\square$

So the model has $p(K - 1)$ identified parameters, not $pK$. Statistics fixes the free direction by a reference class: in this article $\boldsymbol\beta_K = \mathbf{0}$, so each $\boldsymbol\beta_k$ describes the log-odds of class $k$ against class $K$. Which class is the reference is a labeling choice. Changing it to class $r$ replaces every $\boldsymbol\beta_k$ by $\boldsymbol\beta_k - \boldsymbol\beta_r$ and changes no fitted probability, by the theorem. In the NHANES fits below the reference class is "excellent".

A neural network does not fix it. The LM head stores all $K$ rows of weights and all $K$ biases, so it has $p$ more parameters than the model can identify (65 more for the GPT here). What happens to the extra direction depends on the training method.

Theorem 4 (gradient descent and an L2 penalty on the free direction). Let $\ell(B)$ be the log-likelihood of the model.

  1. The columns of the gradient sum to zero: $\sum_{k}\partial\ell/\partial\boldsymbol\beta_k = \mathbf{0}$. Hence any update that adds to $B$ a linear combination of past gradients (plain gradient descent, with or without momentum, full-batch or on mini-batches) leaves $\sum_k\boldsymbol\beta_k$ unchanged.
  2. For $\lambda > 0$, the penalized log-likelihood $\ell(B) - \frac{\lambda}{2}\lVert B\rVert_F^2$, with $\lVert B\rVert_F^2$ the sum of squares of all entries, has exactly one maximizer, and it satisfies $\sum_k\boldsymbol\beta_k = \mathbf{0}$.

Proof. Part 1. Theorem 5 below gives $\partial\ell/\partial\boldsymbol\beta_k = \sum_i(y_{ik} - \pi_{ik})\mathbf{x}_i$. Summing over $k$, and using $\sum_k y_{ik} = \sum_k\pi_{ik} = 1$, gives $\sum_i(1 - 1)\mathbf{x}_i = \mathbf{0}$. The same holds for the gradient on any subset of observations. An update $B \leftarrow B + \sum_t a_t G_t$, where each $G_t$ is such a gradient, adds $\sum_t a_t G_t\mathbf{1} = \mathbf{0}$ to $B\mathbf{1} = \sum_k\boldsymbol\beta_k$.

Part 2. The penalized objective is strictly concave, since $\ell$ is concave (Theorem 6) and $-\frac{\lambda}{2}\lVert B\rVert_F^2$ is strictly concave. It tends to $-\infty$ as $\lVert B\rVert_F \to \infty$, because $\ell \le 0$. So it has a maximizer, which is unique by strict concavity. (For existence: the set where the objective is at least its value at $B = 0$ is closed and bounded, because the objective is continuous and tends to $-\infty$. A continuous function attains its maximum on such a set.) Let $\hat{B}$ be the maximizer and $\bar{\mathbf{c}} = \frac{1}{K}\sum_k\hat{\boldsymbol\beta}_k$. The matrix $\hat{B} - \bar{\mathbf{c}}\mathbf{1}^{\mathsf T}$ has the same likelihood by Theorem 3, and

$$\lVert\hat{B} - \bar{\mathbf{c}}\mathbf{1}^{\mathsf T}\rVert_F^2 = \sum_k\lVert\hat{\boldsymbol\beta}_k\rVert^2 - 2\bar{\mathbf{c}}^{\mathsf T}\sum_k\hat{\boldsymbol\beta}_k + K\lVert\bar{\mathbf{c}}\rVert^2 = \lVert\hat{B}\rVert_F^2 - K\lVert\bar{\mathbf{c}}\rVert^2.$$

If $\bar{\mathbf{c}} \ne \mathbf{0}$ the centered matrix has a strictly higher penalized objective, contradicting maximality. So $\bar{\mathbf{c}} = \mathbf{0}$. $\square$

The theorem does not cover Adam, the optimizer of the site's GPT walkthrough (The Bigram Language Model and the later steps). Adam divides each coordinate of its update by a running estimate of that coordinate's own gradient scale (Kingma and Ba, 2015), so the update is no longer a linear combination of gradients, and $\sum_k\boldsymbol\beta_k$ can drift. The GPT experiment below measures how far.

The likelihood, its gradient and its curvature

The log-likelihood of independent observations is the sum of the log-probabilities of the observed classes. By Theorem 1, with $\eta_{ik} = \mathbf{x}_i^{\mathsf T}\boldsymbol\beta_k$,

$$\ell(B) = \sum_{i=1}^{n}\Big[\sum_{k=1}^{K} y_{ik}\,\eta_{ik} - \ln\sum_{j=1}^{K} e^{\eta_{ij}}\Big], \qquad (2)$$

the same expression whether or not a reference class is imposed. Its negative divided by $n$ is the average cross-entropy between the one-hot vectors and the predicted distributions, the training loss of every classifier and language model on the site; Cross-Entropy and Kullback–Leibler Divergence proves that it is the average negative log-likelihood.

Theorem 5 (score and Hessian). For the log-likelihood (2):

  1. $\dfrac{\partial\ell}{\partial\boldsymbol\beta_k} = \sum_i (y_{ik} - \pi_{ik})\,\mathbf{x}_i$, or in matrix form $\dfrac{\partial\ell}{\partial B} = X^{\mathsf T}(Y - \Pi)$. The derivative of the loss $-\ln\pi_{iy_i}$ of one observation with respect to its scores is $\boldsymbol\pi_i - \mathbf{y}_i$.
  2. $\dfrac{\partial^2\ell}{\partial\boldsymbol\beta_k\,\partial\boldsymbol\beta_l^{\mathsf T}} = -\sum_i \pi_{ik}(\delta_{kl} - \pi_{il})\,\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$. Stacking the coefficients class by class, the Hessian is $-\sum_i \Sigma(\boldsymbol\pi_i)\otimes\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$, where $\otimes$ is the Kronecker product (the block in row $k$ and column $l$ is the $(k, l)$ entry of $\Sigma(\boldsymbol\pi_i)$ times $\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$).
  3. The Hessian does not depend on $Y$. So the observed information equals the expected (Fisher) information, $\mathcal{I}(B) = \sum_i\Sigma(\boldsymbol\pi_i)\otimes\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$, and Newton's method is Fisher scoring.

Proof. Part 1. The term of observation $i$ depends on $B$ through its scores. Its derivative with respect to $\eta_{ik}$ is $y_{ik} - e^{\eta_{ik}}/\sum_j e^{\eta_{ij}} = y_{ik} - \pi_{ik}$, and $\partial\eta_{ik}/\partial\boldsymbol\beta_k = \mathbf{x}_i$ while $\eta_{ik}$ does not depend on $\boldsymbol\beta_l$ for $l \ne k$. Summing over $i$ gives the score. The loss of one observation is minus its term, with derivative $\pi_{ik} - y_{ik}$ in each score. Part 2. Differentiate $\sum_i (y_{ik} - \pi_{ik})\mathbf{x}_i$ with respect to $\boldsymbol\beta_l$: by Theorem 1 part 3 applied to the scores, $\partial\pi_{ik}/\partial\eta_{il} = \pi_{ik}(\delta_{kl} - \pi_{il})$, and the chain rule gives $\partial\pi_{ik}/\partial\boldsymbol\beta_l^{\mathsf T} = \pi_{ik}(\delta_{kl} - \pi_{il})\mathbf{x}_i^{\mathsf T}$. Part 3. $Y$ enters the score linearly and disappears on differentiating again; the expected information is minus the expected Hessian, which is minus the Hessian itself. $\square$

The gradient $\boldsymbol\pi - \mathbf{y}$ is the one Activation Functions derives for a softmax followed by the cross-entropy loss, there by differentiating the composition and here from the exponential family. Bridle (1990), who proposed the name "soft max", noted that with a normalized exponential output the derivative before the output nonlinearity is "the difference between the corresponding output and a one-from-N target". Parts 1 and 3 are the multinomial case of the canonical-link facts of Link Functions and Iteratively Reweighted Least Squares: the score is $X^{\mathsf T}$ times observed minus fitted, and Newton's method coincides with scoring. With $K = 2$ and the reference class removed, $\Sigma(\boldsymbol\pi_i)$ reduces to the number $\pi_{i1}(1 - \pi_{i1})$ and the information to the $X^{\mathsf T}WX$ of Logistic Regression.

Theorem 6 (concavity). The log-likelihood (2) is concave in $B$. In the reference parametrization ($\boldsymbol\beta_K = \mathbf{0}$, coefficients $\boldsymbol\beta_1, \ldots, \boldsymbol\beta_{K-1}$) it is strictly concave if and only if $X$ has full column rank, and then it has at most one maximizer. In the full parametrization, at any $B$, the directions of zero curvature are exactly the matrices $\mathbf{c}\mathbf{1}^{\mathsf T}$ (when $X$ has full column rank), a space of dimension $p$.

Proof. Take a direction $D = [\mathbf{d}_1, \ldots, \mathbf{d}_K]$ and let $\mathbf{v}_i = (\mathbf{x}_i^{\mathsf T}\mathbf{d}_1, \ldots, \mathbf{x}_i^{\mathsf T}\mathbf{d}_K)$, the change of observation $i$'s scores. By Theorem 5 part 2 and identity (1), the second derivative of $\ell$ along $D$ is

$$\frac{d^2}{dt^2}\ell(B + tD) = -\sum_i\mathbf{v}_i^{\mathsf T}\Sigma(\boldsymbol\pi_i)\mathbf{v}_i = -\sum_i\operatorname{Var}_{\boldsymbol\pi_i}\big(v_{i,Y}\big) \le 0,$$

where $\operatorname{Var}_{\boldsymbol\pi_i}(v_{i,Y})$ is the variance of the entry of $\mathbf{v}_i$ picked out by a class drawn from $\boldsymbol\pi_i$. So $\ell$ is concave. The curvature is zero exactly when every $\mathbf{v}_i$ has equal entries (every $\pi_{ik}$ is positive), that is, when $X(\mathbf{d}_k - \mathbf{d}_K) = \mathbf{0}$ for every $k$. With full column rank this means $\mathbf{d}_k = \mathbf{d}_K$ for all $k$, so $D = \mathbf{d}_K\mathbf{1}^{\mathsf T}$; that is the last claim. In the reference parametrization $\mathbf{d}_K = \mathbf{0}$, so zero curvature forces $D = 0$, and the curvature is strictly negative in every direction: strict concavity. If $X$ does not have full column rank, take $\mathbf{d}_1 \ne \mathbf{0}$ with $X\mathbf{d}_1 = \mathbf{0}$ and all other columns zero; the scores do not change along $D$ and $\ell$ is constant on that line, so it is not strictly concave. A strictly concave function has at most one maximizer: if $B_1 \ne B_2$ both attained the maximum $M$, the midpoint would have a value strictly above $M$. $\square$

Example (a final layer normalization makes the design rank-deficient). The full-rank condition fails for the LM head of the site's GPT, and of any network whose last step before the head is a layer normalization. Layer normalization maps a vector $\mathbf{z}$ of length $C$ to $h_j = g_j(z_j - \bar z)/\sqrt{s^2 + \epsilon} + b_j$, where $\bar z$ and $s^2$ are the mean and variance of the entries of $\mathbf{z}$, $\epsilon > 0$ is a small constant, and $g_j$ and $b_j$ are learned (Assembling the Transformer Block, "Layer normalization"). If every gain $g_j$ is nonzero,

$$\sum_{j=1}^{C}\frac{h_j - b_j}{g_j} = \frac{1}{\sqrt{s^2 + \epsilon}}\sum_{j=1}^{C}(z_j - \bar z) = 0$$

for every input, whatever $\epsilon$ is. So with $\mathbf{x}_i = (\mathbf{h}_i, 1)$ the vector $\mathbf{a} = (1/g_1, \ldots, 1/g_C, -\sum_j b_j/g_j)$ satisfies $X\mathbf{a} = \mathbf{0}$, and $X$ has rank at most $C = p - 1$. By the proof of Theorem 6, the directions of zero curvature are then all $D$ with $X(\mathbf{d}_k - \mathbf{d}_K) = \mathbf{0}$ for every $k$. If $\mathbf{a}$ spans the null space of $X$, these are $D = \mathbf{c}\mathbf{1}^{\mathsf T} + \mathbf{a}\mathbf{t}^{\mathsf T}$ for any $\mathbf{c}$ of length $p$ and $\mathbf{t}$ of length $K$, a space of dimension $p + K - 1$ (the two families share the direction $\mathbf{a}\mathbf{1}^{\mathsf T}$). Even with a reference class, $K - 1$ directions remain free: adding $t_k\mathbf{a}$ to each $\boldsymbol\beta_k$ changes no prediction, because it adds $t_k\mathbf{x}_i^{\mathsf T}\mathbf{a} = 0$ to every score. The head's weights are not identified from its predictions even up to a common shift. The GPT experiment below counts these directions in the Hessian.

The curvature is also bounded above, uniformly in $B$. The bound gives a step size for gradient methods that never overshoots.

Theorem 7 (Böhning's bound). For every probability vector $\boldsymbol\pi$,

$$\Sigma(\boldsymbol\pi) = \operatorname{diag}(\boldsymbol\pi) - \boldsymbol\pi\boldsymbol\pi^{\mathsf T} \preceq \tfrac12\Big(I - \tfrac1K\mathbf{1}\mathbf{1}^{\mathsf T}\Big),$$

where $M \preceq N$ means that $N - M$ is positive semidefinite. Consequently the information satisfies $\mathcal{I}(B) \preceq \frac12(I - \frac1K\mathbf{1}\mathbf{1}^{\mathsf T})\otimes X^{\mathsf T}X$ for every $B$, and every eigenvalue of the information is at most $\frac12\lambda_{\max}(X^{\mathsf T}X)$, in either parametrization.

Proof. Let $\mathbf{v}$ be any vector, $\bar v$ the mean of its entries and $\mathbf{w} = \mathbf{v} - \bar v\mathbf{1}$. By (1), $\mathbf{v}^{\mathsf T}\Sigma\mathbf{v} = \operatorname{Var}(v_Y) = \operatorname{Var}(w_Y)$, since subtracting a constant does not change a variance. A variable taking values in an interval $[a, b]$ has variance at most $E[(Z - \frac{a+b}{2})^2] \le (\frac{b-a}{2})^2$. With $a = \min_k w_k$ and $b = \max_k w_k$, and $(b - a)^2 \le 2(a^2 + b^2) \le 2\lVert\mathbf{w}\rVert^2$ (if all entries are equal, $\mathbf{w} = \mathbf{0}$ and both sides are 0; otherwise $a$ and $b$ are two different entries of $\mathbf{w}$),

$$\mathbf{v}^{\mathsf T}\Sigma\mathbf{v} \le \frac{(b - a)^2}{4} \le \frac12\lVert\mathbf{w}\rVert^2 = \frac12\,\mathbf{v}^{\mathsf T}\Big(I - \tfrac1K\mathbf{1}\mathbf{1}^{\mathsf T}\Big)\mathbf{v},$$

because $I - \frac1K\mathbf{1}\mathbf{1}^{\mathsf T}$ is the projection that subtracts the mean. For the information, if $M \preceq N$ and $S$ is positive semidefinite then $M\otimes S \preceq N\otimes S$, since $(N - M)\otimes S$ is positive semidefinite (the eigenvalues of a Kronecker product of symmetric matrices are the products of their eigenvalues). Summing over $i$ gives the matrix bound. The eigenvalues of $I - \frac1K\mathbf{1}\mathbf{1}^{\mathsf T}$ are 0 and 1, so those of the bound are at most $\frac12\lambda_{\max}(X^{\mathsf T}X)$. The reference parametrization deletes the rows and columns of class $K$, a principal submatrix, whose largest eigenvalue cannot exceed that of the whole. $\square$

Böhning (1992, Lemma 2.2) states the bound in the reference parametrization, for the $K - 1$ non-reference classes, which is a principal submatrix of Theorem 7's form; he refers its proof to earlier work of Böhning and Lindsay, and uses it in place of the Hessian in Newton's method: the fixed matrix is inverted once, and each step increases the likelihood. One consequence for gradient methods is worth stating. Let $f(B) = -\ell(B)/n$ be the mean loss and $L = \frac{1}{2}\lambda_{\max}(X^{\mathsf T}X/n)$. By Taylor's theorem along the segment from $B$ to $B'$, with the Hessian of $f$ at most $L$ in every direction, $f(B') \le f(B) + \langle\nabla f(B), B' - B\rangle + \frac{L}{2}\lVert B' - B\rVert_F^2$. The step $B' = B - \frac1L\nabla f(B)$ therefore lowers the loss by at least $\lVert\nabla f(B)\rVert_F^2/(2L)$. A full-batch gradient step of size $1/L$ never increases the loss of softmax regression, whatever the data.

The last two theorems settle the shape of the problem: a concave function, curved at most by a known amount, with at most one peak in the reference parametrization. They do not say that the peak exists.

When the maximum exists

Here is the idea. Concavity rules out several maxima but not none: the likelihood (2) is bounded above by 0, and it can approach a supremum without reaching it. That happens when some direction of the coefficients improves the fit of every observation at once. Logistic regression meets this as separation (Logistic Regression and Deviance and Inference for Generalized Linear Models); the theorem below is its version for $K$ classes.

Call a direction $D = [\mathbf{d}_1, \ldots, \mathbf{d}_K]$ separating for the data if it is not of the form $\mathbf{c}\mathbf{1}^{\mathsf T}$ and, along it, every observation's own class scores at least as high as any other class:

$$\mathbf{x}_i^{\mathsf T}\mathbf{d}_{y_i} \ge \mathbf{x}_i^{\mathsf T}\mathbf{d}_k \qquad \text{for every } i \text{ and every } k.$$

The data are completely separated if some direction satisfies all these inequalities strictly for $k \ne y_i$, and quasi-completely separated if a separating direction exists but none with all inequalities strict. Otherwise the classes overlap. Albert and Anderson (1984) sorted the possible patterns of data in multinomial logistic regression into these three, mutually exclusive and exhaustive, and proved existence theorems for them. Santner and Duffy (1986) stated that the estimate exists only under overlap. They gave modified statements and proofs for the other two cases, and a linear program that tells the three apart. The definitions above are our formulation, and the proof below is self-contained.

Theorem 8 (existence of the maximum likelihood estimate). Let $X$ have full column rank. The log-likelihood (2) attains its maximum if and only if no separating direction exists. The maximizer is then unique in the reference parametrization. Under complete separation the supremum is 0.

Proof. A separating direction prevents a maximum. Let $D$ be separating and $B$ any coefficient matrix. The term of observation $i$ in (2) is $-\ln\sum_j\exp\big(\eta_{ij} - \eta_{iy_i}\big)$. Along $B + tD$ the exponent of class $j$ changes by $t\,\mathbf{x}_i^{\mathsf T}(\mathbf{d}_j - \mathbf{d}_{y_i})$, and every such coefficient of $t$ is at most 0. So every term is nondecreasing in $t$. At least one coefficient is negative: if all were zero, then $\mathbf{x}_i^{\mathsf T}\mathbf{d}_k = \mathbf{x}_i^{\mathsf T}\mathbf{d}_{y_i}$ for all $i$ and $k$, so $X(\mathbf{d}_k - \mathbf{d}_K) = \mathbf{0}$, so $\mathbf{d}_k = \mathbf{d}_K$ for all $k$ by full rank, and $D = \mathbf{d}_K\mathbf{1}^{\mathsf T}$, which is excluded. The term containing a negative coefficient is strictly increasing in $t$. Hence $\ell(B + tD) > \ell(B)$ for $t > 0$, and no $B$ is a maximizer. Under complete separation every coefficient with $j \ne y_i$ is negative, so each term tends to $-\ln 1 = 0$ as $t \to \infty$, and $\ell(B + tD) \to 0$.

Without a separating direction the maximum exists. Work in the reference parametrization, where every nonzero direction has $\mathbf{d}_K = \mathbf{0}$ and so is not of the form $\mathbf{c}\mathbf{1}^{\mathsf T}$ (that form with $\mathbf{d}_K = \mathbf{0}$ is zero). Fix $B_0$. For a nonzero direction $D$, no separating direction exists, so some observation $i$ and class $k$ have $a = \mathbf{x}_i^{\mathsf T}(\mathbf{d}_k - \mathbf{d}_{y_i}) > 0$. Every term of (2) is at most 0, and the term of $i$ is at most minus the logarithm of its $k$-th summand:

$$\ell(B_0 + tD) \le -\big(\eta^{0}_{ik} - \eta^{0}_{iy_i} + t a\big) \to -\infty \quad (t \to \infty),$$

with $\eta^0$ the scores at $B_0$. So $\ell$ tends to $-\infty$ along every ray from $B_0$. Let $S = \{B : \ell(B) \ge \ell(B_0)\}$. It is closed ($\ell$ is continuous) and convex ($\ell$ is concave, Theorem 6). Suppose $S$ were unbounded: take $B_m \in S$ with $\lVert B_m - B_0\rVert \to \infty$, and directions $D_m = (B_m - B_0)/\lVert B_m - B_0\rVert$, which have a convergent subsequence on the unit sphere, with limit $D$. For any $t > 0$ and $m$ large, $B_0 + tD_m$ lies on the segment from $B_0$ to $B_m$, so in $S$ by convexity; letting $m \to \infty$ and using closedness, $B_0 + tD \in S$ for every $t > 0$. That contradicts $\ell \to -\infty$ along the ray. So $S$ is closed and bounded, the continuous function $\ell$ attains a maximum on it, and that maximum is the global one, since points outside $S$ have $\ell < \ell(B_0)$. Uniqueness is Theorem 6. $\square$

The first half of the proof uses full rank only to find a negative coefficient. A separating direction that visibly has one (as for a class that never occurs, below) rules out a maximum whatever the rank of $X$.

Two cases of the theorem come up constantly.

  • A class that never occurs. If no observation is in class $b$ and the model has an intercept, take $\mathbf{d}_b = -\mathbf{e}_{\text{int}}$, minus one on the intercept's coordinate (the first in the NHANES design, the last in the GPT's $\mathbf{x}_i = (\mathbf{h}_i, 1)$), and all other columns 0. Every observation's own class scores 0 and class $b$ scores $-1$, so the direction is separating, and the estimate does not exist: the intercept of class $b$ runs to $-\infty$. With an intercept the fitted class totals must equal the observed ones (the score equations, in the next section), which for a total of zero is impossible at any finite $B$.
  • The bigram table. The Bigram Language Model is a softmax regression whose input is the one-hot vector of the previous character: $\mathbf{x}_i = \mathbf{e}_{a_i}$, with $p = K = 65$ and no separate intercept. In the 1,003,853 adjacent pairs of the training split, 2,845 of the $65 \times 65 = 4{,}225$ possible pairs never occur. Every one of the 65 characters occurs as a previous character (so $X$ has full column rank), and every row of the table has at least one unseen successor. For an unseen pair $(a, b)$, the direction with $\mathbf{d}_b = -\mathbf{e}_a$ and all other columns 0 is separating: it lowers the score of $b$ after $a$ and changes nothing else, and $b$ never follows $a$ in the data. So the maximum likelihood estimate of the bigram model does not exist. The loss approaches the conditional entropy of the training text, 2.4519 nats, the floor that Cross-Entropy and Kullback–Leibler Divergence proves no bigram table can pass, but no finite table reaches it.

The script makes the second case concrete. Give each seen pair its logit $\ln(\text{count share})$ and each unseen pair the logit $-M$. The training loss is 2.6361 nats at $M = 5$, 2.4533 at $M = 10$ and 2.4519135 at $M = 20$, against the floor 2.4519134. The excess is exactly $\sum_a \hat p(a)\ln(1 + z_a e^{-M})$, with $\hat p(a)$ the share of pairs starting with $a$ and $z_a$ the number of unseen successors of $a$, which is positive for every finite $M$. Gradient descent on a bigram table keeps pushing the unseen logits down, ever more slowly. Count tables avoid the problem by smoothing (Perplexity and Source Coding), and an L2 penalty restores existence (Theorem 4).

The score equations: matching what was observed

At the maximum the score of Theorem 5 is zero: $X^{\mathsf T}(Y - \hat\Pi) = 0$. Column $k$ of this equation says

$$\sum_i \hat\pi_{ik}\,\mathbf{x}_i = \sum_i y_{ik}\,\mathbf{x}_i, \qquad k = 1, \ldots, K,$$

which holds for the reference class too, since the $K$ columns of $Y - \hat\Pi$ sum to zero. For every class and every input variable, the total of the variable over the observations, weighted by the fitted probability of the class, equals its total over the observations actually in the class. With an intercept the intercept's coordinate gives $\sum_i\hat\pi_{ik} = n_k$, the observed count of class $k$: the fitted model is calibrated in the large, in the language of Calibration and Proper Scoring Rules.

These equations have a second reading, and with it the result that Maximum Entropy Distributions cites from Berger, Della Pietra and Della Pietra (1996, Sections 3.3 to 3.5) can be proved. That article proves, for a single categorical variable, that maximum likelihood in an exponential family is maximum entropy subject to matching the sample's averages. A classifier is a conditional model, one distribution per input. The constraints are the score equations, and the entropy to maximize is the total entropy of the conditional distributions.

Theorem 9 (maximum likelihood is conditional maximum entropy). Suppose the maximum likelihood estimate $\hat B$ exists, with fitted distributions $\hat{\boldsymbol\pi}_i$. Let $\mathcal{Q}$ be the set of all choices of probability vectors $\mathbf{q}_1, \ldots, \mathbf{q}_n$ on the $K$ classes that satisfy the same equations, $\sum_i q_{ik}\mathbf{x}_i = \sum_i y_{ik}\mathbf{x}_i$ for every $k$. Then $(\hat{\boldsymbol\pi}_i)$ belongs to $\mathcal{Q}$, and for every member of $\mathcal{Q}$

$$\sum_i H(\mathbf{q}_i) = \sum_i H(\hat{\boldsymbol\pi}_i) - \sum_i D(\mathbf{q}_i \,\|\, \hat{\boldsymbol\pi}_i).$$

So the fitted model is the unique member of $\mathcal{Q}$ with the greatest total entropy $\sum_i H(\mathbf{q}_i)$.

Proof. Membership is the score equation. For each $i$, entropy, cross-entropy and divergence are related by $H(\mathbf{q}_i) = H(\mathbf{q}_i, \hat{\boldsymbol\pi}_i) - D(\mathbf{q}_i \,\|\, \hat{\boldsymbol\pi}_i)$ (Cross-Entropy and Kullback–Leibler Divergence). Since $\ln\hat\pi_{ik} = \hat\eta_{ik} - \ln\sum_j e^{\hat\eta_{ij}}$ and $\sum_k q_{ik} = 1$,

$$\sum_i H(\mathbf{q}_i, \hat{\boldsymbol\pi}_i) = -\sum_i\sum_k q_{ik}\,\mathbf{x}_i^{\mathsf T}\hat{\boldsymbol\beta}_k + \sum_i\ln\sum_j e^{\hat\eta_{ij}} = -\sum_k\hat{\boldsymbol\beta}_k^{\mathsf T}\Big(\sum_i q_{ik}\mathbf{x}_i\Big) + \sum_i\ln\sum_j e^{\hat\eta_{ij}}.$$

On $\mathcal{Q}$ the bracket equals $\sum_i y_{ik}\mathbf{x}_i$, so this total is the same for every member of $\mathcal{Q}$. In particular it equals its value at $\mathbf{q}_i = \hat{\boldsymbol\pi}_i$, which is $\sum_i H(\hat{\boldsymbol\pi}_i)$ because the divergence of a distribution from itself is zero. Substituting gives the identity. Each divergence is nonnegative and zero only when $\mathbf{q}_i = \hat{\boldsymbol\pi}_i$ (Gibbs' inequality), which gives the uniqueness. $\square$

Berger, Della Pietra and Della Pietra state the duality for features $f(x, y)$ of the input and the class together and state it without proof, as an instance of the Kuhn–Tucker theorem of Lagrange multipliers. Our constraints are the same construction with the features $x_j\,[y = k]$, one for each input variable and class, and the empirical distribution of the inputs; Berger, Della Pietra and Della Pietra take features to be binary, while age and BMI here are real-valued. Their footnote 2 adds that when the dual maximum is not attained, the maximum entropy model is a limit of models of the exponential form. The bigram table shows such a limit. Its constraints say that for each previous character $a$, the probabilities given to class $b$ over the pairs starting with $a$ sum to the count of the pair $(a, b)$. The total entropy is then greatest when every pair starting with $a$ gets the same distribution, the row of count shares, with its zeros. (Replacing the distributions of the pairs that start with $a$ by their average keeps every constraint. Since entropy is concave, it does not lower the total. And the constraints fix that average to be the row of shares.) That distribution is not a softmax of finite logits, and it is the limit of the logits $-M$ of the last section as $M \to \infty$.

Self-rated health in NHANES

Back to the 5,171 adults. With the reference class "excellent", the model has four columns of coefficients, one for each other answer against excellent, and four inputs (intercept, age, female, BMI): 16 parameters. Newton's method with the exact Hessian of Theorem 5, started from $B = 0$ (where every class has probability $\frac15$), gives:

Iteration Log-likelihood
0 −8,322.403
1 −7,237.361
2 −7,125.283
3 −7,115.725
4 −7,115.395
5 −7,115.394224

The starting value is $-5{,}171\ln 5$. The log-likelihood agrees with its maximum to the six decimals shown after five steps; the method stops after 8 steps, when no coefficient changes by more than $10^{-13}$, and the score's largest entry is then $1.2 \times 10^{-13}$. By Theorem 6 the log-likelihood is strictly concave, so this is the only maximum, and since it is attained the data are not separated (Theorem 8).

The estimates, with standard errors from the inverse of the information matrix of Theorem 5:

Answer, against excellent Intercept Age, per 10 years Female BMI, per 5 kg/m²
Very good 0.981 (0.075) 0.099 (0.027) 0.073 (0.099) 0.273 (0.043)
Good 1.345 (0.072) 0.164 (0.026) 0.106 (0.096) 0.461 (0.041)
Fair 0.703 (0.079) 0.272 (0.029) 0.123 (0.106) 0.610 (0.044)
Poor −1.120 (0.129) 0.418 (0.049) 0.219 (0.168) 0.631 (0.059)

Each entry is a change in a log-odds against the reference class. Five more units of BMI, at fixed age and sex, multiply the odds of answering "poor" rather than "excellent" by $e^{0.631} = 1.879$; the Wald interval $0.631 \pm 1.96 \times 0.059$ transforms to $(1.673, 2.109)$, and the Wald statistic is $0.631/0.059 = 10.69$. The standard errors rest on the large-sample normality of maximum likelihood estimates, proved in Asymptotics of the Maximum Likelihood Estimator, with the inference for generalized linear models in Deviance and Inference for Generalized Linear Models.

Likelihood ratio tests drop one input at a time. Each removes four parameters (one per non-reference class), so each statistic is referred to $\chi^2_4$:

Input dropped Likelihood ratio statistic p-value
Age 145.37 $2 \times 10^{-30}$
Female 2.34 0.674
BMI 305.72 $6 \times 10^{-65}$

Against the intercept-only model the three inputs together give 465.46 on 12 degrees of freedom.

The probabilities read more easily than the log-odds. For a woman of 50 with a BMI of 25, the fitted distribution over (excellent, very good, good, fair, poor) is (0.136, 0.298, 0.367, 0.169, 0.029); at a BMI of 40 it is (0.039, 0.192, 0.415, 0.299, 0.055).

The fitted distribution of self-rated health for a woman, stacked from excellent (bottom) to poor (top), against BMI at age 50 (left; BMI from 18 to 53, about the 1st to 99th percentiles of the sample) and against age at BMI 30 (right). Notice that the bands for excellent and very good shrink and the band for fair widens as BMI rises, while every vertical slice still sums to 1: each band is one coordinate of a softmax of linear scores. Over these ranges BMI moves the distribution further than age does: excellent or very good falls from about 0.55 to 0.12 across BMI and from about 0.46 to 0.26 across age.
The fitted distribution of self-rated health for a woman, stacked from excellent (bottom) to poor (top), against BMI at age 50 (left; BMI from 18 to 53, about the 1st to 99th percentiles of the sample) and against age at BMI 30 (right). Notice that the bands for excellent and very good shrink and the band for fair widens as BMI rises, while every vertical slice still sums to 1: each band is one coordinate of a softmax of linear scores. Over these ranges BMI moves the distribution further than age does: excellent or very good falls from about 0.55 to 0.12 across BMI and from about 0.46 to 0.26 across age.

Example (the model does not know the answers are ordered). The five answers form a scale, but the multinomial model treats them as unordered labels: any permutation of the classes gives the same fit. The order shows up in the estimates anyway. The BMI coefficients rise steadily from "very good" to "poor" (0.273, 0.461, 0.610, 0.631), and so do the age coefficients. A model that uses the order directly, such as the cumulative logit (proportional odds) model of McCullagh (1980), describes such a pattern with fewer parameters; it is outside this article (Agresti, 2013, Section 8.2, treats it).

Three of the theorems can be checked on the fit.

  • Score equations. With an intercept, the fitted probabilities summed over the 5,171 adults reproduce the observed counts 596, 1,367, 1,932, 1,076 and 200 to within $10^{-11}$.
  • Identifiability. In the reference parametrization the information matrix per observation, $\mathcal{I}/n$, has eigenvalues from 0.0037 to 1.087, all positive, as Theorem 6 requires. In the full parametrization, with all five classes, it has exactly four zero eigenvalues (to within $10^{-15}$), one for each input, and the next is 0.0080: the null space $\{\mathbf{c}\mathbf{1}^{\mathsf T}\}$ of Theorem 6, of dimension $p = 4$.
  • Böhning's bound. The largest eigenvalue, 1.087, is below the bound $\frac12\lambda_{\max}(X^{\mathsf T}X/n) = 1.717$ of Theorem 7.

The output layer of the GPT

Now the 30 trained heads. Each network is held fixed, the features $\mathbf{x}_i = (\mathbf{h}_i, 1)$ are computed, and the head is examined as the regression of the theorems. The training sample is 16,384 positions, the same for every model (512 windows of 32 characters, drawn with seed 0). The validation positions are all 111,520 in consecutive windows of the validation split, and some checks use all 1,003,840 positions of the training split in consecutive windows. Each number below is the median over the 30 models, with the interquartile range after it in brackets, unless it is stated as a maximum.

The gradient is $X^{\mathsf T}(\Pi - Y)/n$. On the first 4,096 training positions, PyTorch's automatic differentiation of its mean cross-entropy, in double precision, gives the gradient with respect to the head's weights and biases. It agrees with $X^{\mathsf T}(\Pi - Y)/n$ of Theorem 5 to within $3 \times 10^{-17}$ in every model, for gradient entries of size up to 0.038 (median of the largest entry). Its 65 class columns sum to zero to within $4 \times 10^{-17}$ (Theorem 4, part 1).

The free direction drifted. The mean of the head's 65 class vectors, $\bar{\mathbf{c}} = \frac{1}{K}\sum_k\boldsymbol\beta_k$, is the component that Theorem 4 says plain gradient descent cannot change. At initialization its length is 0.072 [0.068 to 0.075]; after training it is 0.303 [0.296 to 0.312], against 1.206 for the median length of a single class vector (0.580 at initialization). Adam moved it. Subtracting it from every class vector changes the validation loss by less than $10^{-15}$ in every model: by Theorem 3 the drift is invisible in every prediction.

The layer normalization's direction. The vector $\mathbf{a}$ of the example after Theorem 6, computed from each model's final layer normalization, gives $\lvert\mathbf{x}_i^{\mathsf T}\mathbf{a}\rvert$ at most $9 \times 10^{-8}$ of $\max_i\lVert\mathbf{x}_i\rVert\,\lVert\mathbf{a}\rVert$, which is the rounding of the network's single-precision arithmetic. The smallest singular value of $X/\sqrt{n}$ is $2 \times 10^{-7}$ against a largest of 5.94. The Hessian of the log-likelihood at the trained head, a $4{,}225 \times 4{,}225$ matrix, has in every model exactly 129 eigenvalues below $10^{-14}$ per position, followed by a jump to $6 \times 10^{-7}$. That is $p + K - 1 = 65 + 65 - 1$, the dimension the example predicts. In the reference parametrization, with the last class removed, exactly 64 remain, $K - 1$. Without the layer normalization's dependency the count would have been $p = 65$ in the full parametrization and 0 with a reference class, as on the NHANES data. The largest eigenvalue per position is 4.26, below Böhning's bound $\frac12\lambda_{\max}(X^{\mathsf T}X/n) = 17.62$ (Theorem 7) in every model.

The trained head is not at the maximum. On the 1,003,840 training positions the trained heads have a mean loss of 1.719 [1.716 to 1.726] nats per character, and on the validation positions a validation loss of 1.874 [1.866 to 1.879]. The largest entry of the score per position, $X^{\mathsf T}(Y - \Pi)/n$, is 0.025 [0.019 to 0.033]. It is not zero, because 2,500 mini-batch steps of Adam on the whole network do not solve the head's own likelihood equations. Calibration in the large shows the same thing. The fitted count of a character, $\sum_i\hat\pi_{ik}$, differs from its observed count by as much as 10,369 positions (the median over models of the largest difference; across the 30 models it is one of 9 different characters), where the maximum likelihood fit would make every difference zero.

Refitting the head alone. With the features held fixed, fitting the head is a concave problem (Theorem 6), and Newton's method solves it exactly. On only 16,384 positions, however, four characters ($, &, 3 and Q) never occur as the next character, and four more (J, X, Z and z) occur between one and four times. With the intercept, the unpenalized estimate does not exist. The design here does not have full column rank, so Theorem 8 as stated does not apply, but its first half does. The direction that puts $-1$ on the intercept of an absent character $b$, $\mathbf{d}_b = -\mathbf{e}_{65}$ (the intercept is the last coordinate of $\mathbf{x}_i = (\mathbf{h}_i, 1)$), with all other columns 0, gives every position a coefficient $-1$ on $b$, whatever the rank of $X$. We therefore fit the penalized problem of Theorem 4, part 2, minimizing the mean loss plus $\frac{\lambda}{2}\lVert B\rVert_F^2$, at $\lambda = 10^{-3}$ and then $\lambda = 10^{-5}$. The method is Newton's, in the full parametrization with the exact Hessian plus $\lambda I$, started from the trained head for $\lambda = 10^{-3}$ and from that solution for $\lambda = 10^{-5}$ (the objective is strictly convex (the log-likelihood is concave and the penalty strictly convex), so the starting point does not change the answer). Every fit converged (largest gradient entry below $10^{-12}$ per position), and in every fit the 65 class vectors sum to zero to within $10^{-11}$, as Theorem 4 requires. Medians over the 30 models:

Head Training loss, 16,384 positions Validation loss Length of $B$
Trained 1.717 1.874 10.0
Refit, $\lambda = 10^{-3}$ 1.626 1.891 9.7
Refit, $\lambda = 10^{-5}$ 1.578 2.088 35.9

The refit lowers the loss on the positions it was fitted to and raises it on the validation text, in 30 of 30 models at $\lambda = 10^{-3}$ and 30 of 30 at $\lambda = 10^{-5}$. The result is consistent with overfitting: the head has $4{,}225 - 129 = 4{,}096$ identified parameters, one for every four of the 16,384 positions, while the trained head was shaped by 2,560,000 positions (2,500 batches of 32 windows of 32 characters), drawn at random at every step. The design does not separate that difference in sample from the other difference, a head refitted alone on frozen features against one trained jointly with them. And because the experiment refits on a small sample only, it does not show whether the exact maximum on the whole training split would be better or worse than the trained head. As $\lambda$ falls, the coefficients grow: the length $\lVert B\rVert_F$ rises from 9.7 to 35.9, and the largest single coefficient from 0.58 to 3.56. Without any penalty the coefficients of the four characters that never occur would have no finite maximum (the first half of the proof of Theorem 8).

These are observations of 30 runs of one small model trained one way. They show what the theorems predict for any softmax output layer (the gradient, the free shift, the null directions, the bound) and what they do not decide (how close training comes to the maximum, and whether the exact maximum is worth having).

What is proved, what is cited, what the experiments show

Proved here: the categorical distribution as an exponential family, with the softmax as the gradient of the log-partition function and the covariance $\operatorname{diag}(\boldsymbol\pi) - \boldsymbol\pi\boldsymbol\pi^{\mathsf T}$ of rank $K - 1$ (Theorem 1); the Gumbel-max rule and the Gumbel law of the maximum (Theorem 2); identifiability up to a common shift (Theorem 3); conservation of the sum of the class vectors under gradient descent, and the sum-zero representative under an L2 penalty (Theorem 4); the score $X^{\mathsf T}(Y - \Pi)$, the gradient $\boldsymbol\pi - \mathbf{y}$ and the Hessian, with observed equal to expected information (Theorem 5); concavity, strict concavity under full rank and the null directions (Theorem 6), and the $K - 1$ further null directions that a final layer normalization creates; Böhning's bound and the safe gradient step (Theorem 7); the existence theorem for the maximum likelihood estimate in terms of separating directions (Theorem 8); maximum likelihood as conditional maximum entropy (Theorem 9); and, in the problems, the inverse of the intercept-only information and the saturated grouped model.

Proved on linked pages: the general exponential-family identities and the canonical-link facts (Exponential Families, Link Functions); Newton's method and Fisher scoring (Iteratively Reweighted Least Squares); the cross-entropy identity and Gibbs' inequality (Cross-Entropy and Kullback–Leibler Divergence); the large-sample theory behind standard errors and likelihood ratio tests (Asymptotics of the Maximum Likelihood Estimator, Deviance and Inference for Generalized Linear Models).

Cited: the history of the random-utility derivation as Train (2009) gives it, and the logistic law of a difference of two Gumbel variables; Böhning's (1992) use of the bound in an algorithm; the general feature form of the maximum entropy duality and its limit statement (Berger, Della Pietra and Della Pietra, 1996); the name "soft max" and the gradient remark (Bridle, 1990); the softmax output of the Transformer (Vaswani et al., 2017); the patterns of separation in multinomial data (Albert and Anderson, 1984; Santner and Duffy, 1986); the cumulative logit model for ordered classes (McCullagh, 1980; Agresti, 2013).

What the experiments show: on NHANES, a strictly concave fit with a unique maximum, Wald and likelihood ratio results for the three inputs and the checks of Theorems 6, 7 and 9, for this sample and these inputs. On the GPT, observations of 30 training runs of one small architecture with one optimizer, at reduced size: they show what happened in those runs and are not general statements about language models.

Worked problems

These problems are posed for this article, on the NHANES data and on small exact cases. The script tools/experiments/statistics/multinomial-and-softmax-regression.py checks every number.

Problem 1 (the intercept-only model by hand). Fit the model with an intercept only to the 5,171 answers, with "excellent" as the reference class. Show that $\hat\beta_k = \ln(n_k/n_{\text{ref}})$ and that its standard error is $\sqrt{1/n_k + 1/n_{\text{ref}}}$, and give a 95% interval for the odds of "poor" against "excellent".

Solution. The interval for the odds is $(0.286, 0.394)$, around the estimate $200/596 = 0.336$. With only an intercept, every observation has the same probabilities $\boldsymbol\pi$, and the score equation with an intercept says $n\pi_k = n_k$ for every class. So $\hat\pi_k = n_k/n$ and $\hat\beta_k = \ln(\hat\pi_k/\hat\pi_{\text{ref}}) = \ln(n_k/n_{\text{ref}})$: 0.830, 1.176, 0.591 and −1.092 for very good, good, fair and poor. By Theorem 6 this is the only maximum.

For the standard errors, write $\tilde{\boldsymbol\pi}$ for the probabilities of the four non-reference classes and $\pi_r$ for the reference class. With $\mathbf{x}_i = 1$, Theorem 5 gives the information $\mathcal{I} = n\big(\operatorname{diag}(\tilde{\boldsymbol\pi}) - \tilde{\boldsymbol\pi}\tilde{\boldsymbol\pi}^{\mathsf T}\big)$. Its inverse is $\frac1n\big(\operatorname{diag}(1/\tilde{\boldsymbol\pi}) + \frac{1}{\pi_r}\mathbf{1}\mathbf{1}^{\mathsf T}\big)$. To check, multiply, using $\operatorname{diag}(\tilde{\boldsymbol\pi})\mathbf{1} = \tilde{\boldsymbol\pi}$ and $\tilde{\boldsymbol\pi}^{\mathsf T}\mathbf{1} = 1 - \pi_r$:

$$\big(\operatorname{diag}(\tilde{\boldsymbol\pi}) - \tilde{\boldsymbol\pi}\tilde{\boldsymbol\pi}^{\mathsf T}\big)\Big(\operatorname{diag}(1/\tilde{\boldsymbol\pi}) + \tfrac{1}{\pi_r}\mathbf{1}\mathbf{1}^{\mathsf T}\Big) = I + \tilde{\boldsymbol\pi}\mathbf{1}^{\mathsf T}\Big[\frac{1}{\pi_r} - 1 - \frac{1 - \pi_r}{\pi_r}\Big] = I.$$

The diagonal entry for class $k$ is $\frac1n\big(\frac{1}{\pi_k} + \frac{1}{\pi_r}\big)$, which at the estimates is $\frac{1}{n_k} + \frac{1}{n_r}$. These are the familiar standard errors of a log odds and agree with the standard errors from the information matrix of the fitted intercept-only model: 0.049, 0.047, 0.051 and 0.082. For "poor" against "excellent", $\hat\beta = \ln(200/596) = -1.092$ with standard error $\sqrt{1/200 + 1/596} = 0.082$. The interval $-1.092 \pm 1.96 \times 0.082$, exponentiated, is $(0.286, 0.394)$.

Problem 2 (the saturated age-group model). Classify the 5,242 adults who answered by age group (18–39, 40–59, 60 and over) and fit the model with an intercept and indicators for the two older groups. Show that the fitted probabilities are the observed shares within each group, that the likelihood ratio statistic against the intercept-only model is the $G^2$ statistic of the 3 × 5 table, and read off the coefficient of "60 and over" for "poor" against "excellent".

Solution. The statistic is $G^2 = 177.88$ on 8 degrees of freedom, and the coefficient is 1.967, a log odds ratio. The table (rows: age groups; columns: excellent to poor) is

Age Excellent Very good Good Fair Poor
18–39 288 527 637 256 32
40–59 174 397 589 354 65
60 and over 141 452 733 485 112

The design has three columns, and every observation in group $g$ has the same input vector, so the same probabilities $\boldsymbol\pi_g$. The design's columns span the three group indicators, so the score equations are equivalent to $\sum_{i \in g}(\mathbf{y}_i - \boldsymbol\pi_g) = \mathbf{0}$ for each group: $n_g\pi_{gk} = n_{gk}$, the count of class $k$ in group $g$. So $\hat\pi_{gk} = n_{gk}/n_g$. The model has $3 \times 4 = 12$ parameters for $3 \times 4$ free probabilities; it is saturated.

The maximized log-likelihoods are $\sum_{g,k} n_{gk}\ln(n_{gk}/n_g)$ for this model and $\sum_{g,k} n_{gk}\ln(n_{+k}/n)$ for the intercept-only model (as in Problem 1) fitted to the same 5,242 answers, where $n_{+k}$ is the column total. Twice the difference is

$$2\sum_{g,k} n_{gk}\ln\frac{n_{gk}\,n}{n_g\,n_{+k}} = 2\sum_{g,k} n_{gk}\ln\frac{n_{gk}}{E_{gk}}, \qquad E_{gk} = \frac{n_g\,n_{+k}}{n},$$

the likelihood ratio statistic $G^2$ of the test of independence (The Chi-Square Test of Independence). It equals 177.88 here, on $12 - 4 = 8$ degrees of freedom, with a p-value of $3 \times 10^{-34}$: self-rated health depends on age group. With the youngest group as the baseline, the intercept for "poor" is $\ln(32/288) = -2.197$, and the coefficient of the oldest group is the log of the ratio of the odds of "poor" against "excellent" in the two groups, $\ln\big[(112/141)/(32/288)\big] = 1.967$. The odds of "poor" rather than "excellent" are $e^{1.967} = 7.15$ times as high in the oldest group as in the youngest.

Problem 3 (separation in three classes). Six observations have one input $x$ and an intercept: class 1 at $x = 1, 2$, class 2 at $x = 3, 4$, class 3 at $x = 5, 6$. Show that the maximum likelihood estimate does not exist. Then add a seventh observation, of class 1 at $x = 6$, and show that it does.

Solution. For the six observations, take the direction with class scores $f_1(x) = 0$, $f_2(x) = 2x - 5$ and $f_3(x) = 4x - 14$, that is $\mathbf{d}_1 = (0, 0)$, $\mathbf{d}_2 = (-5, 2)$, $\mathbf{d}_3 = (-14, 4)$ on (intercept, $x$). At $x = 1, \ldots, 6$ the three scores are $(0, -3, -10)$, $(0, -1, -6)$, $(0, 1, -2)$, $(0, 3, 2)$, $(0, 5, 6)$ and $(0, 7, 10)$. Each observation's own class has the strictly largest score, so the data are completely separated, and by Theorem 8 the supremum of the log-likelihood is 0 and is not attained. Along the ray $tD$ the total loss $-\ell$ is 1.425 at $t = 1$, 0.517 at $t = 2$ and 0.027 at $t = 5$, falling toward 0.

With the seventh observation, suppose $D$ is separating, with scores $f_k(x) = \mathbf{x}^{\mathsf T}\mathbf{d}_k$, each a linear function of $x$. Class 1 and class 3 both occur at $x = 6$, so $f_1(6) \ge f_3(6)$ and $f_3(6) \ge f_1(6)$: the linear function $f_3 - f_1$ is zero at 6. It is at least 0 at $x = 5$ (class 3 observed there) and at most 0 at $x = 1$ (class 1 observed there). A linear function that is zero at 6 and nonnegative at 5 has slope at most 0, so it is nonnegative everywhere left of 6, and with the value at 1 it is zero at 1. Zero at two points, it is identically zero: $f_3 = f_1$. Next, $f_2 - f_1$ is at least 0 at $x = 3$ and 4 (class 2) and at most 0 at $x = 2$ and 6 (class 1). A linear function at most 0 at 2 and at 6 is at most 0 on the whole interval between, so it is zero at 3 and 4, hence identically zero. So $f_1 = f_2 = f_3$, which means $\mathbf{d}_1 = \mathbf{d}_2 = \mathbf{d}_3$ ($X$ has full column rank) and $D = \mathbf{d}_1\mathbf{1}^{\mathsf T}$, which is not separating. By Theorem 8 the estimate exists and is unique. Newton's method finds it in 8 steps, with class 1 as the reference: $\ln(\hat\pi_2/\hat\pi_1) = -0.998 + 0.182x$ and $\ln(\hat\pi_3/\hat\pi_1) = -6.103 + 1.266x$, at a maximized log-likelihood of −6.032. The script also confirms by linear programming that every direction satisfying the separation inequalities is zero in the reference parametrization. One observation in the wrong place is enough to turn a supremum that is never reached into a finite maximum.

Problem 4 (sampling by Gumbel noise). For the scores $(0, 1, 2)$, compute the softmax and check Theorem 2 by drawing 10,000 sets of three standard Gumbel variables, adding them to the scores and counting which class has the largest sum. Repeat with 30 seeds.

Solution. The softmax is $(0.0900, 0.2447, 0.6652)$, the values of Activation Functions: $e^0, e^1, e^2$ are $1, 2.7183, 7.3891$, with sum $11.1073$. Over seeds 1 to 30 (NumPy's default_rng(seed).gumbel), the median share of draws won by each class is 0.0889, 0.2455 and 0.6665, with interquartile ranges 0.0876 to 0.0910, 0.2412 to 0.2478 and 0.6638 to 0.6680. Each range contains the corresponding softmax probability, and the medians differ from the probabilities by at most 0.0012. That is well within the sampling error of one run: a share of 10,000 independent draws with probability 0.6652 has standard deviation $\sqrt{0.6652 \times 0.3348/10{,}000} = 0.0047$. Theorem 2 also places the maximum at $\ln 11.1073 = 2.4076$ plus a standard Gumbel variable. The location $\ln\sum_j e^{\eta_j}$ always lies between the largest score and the largest score plus $\ln K$, because the sum is at least its largest term and at most $K$ times it; here it lies between 2 and $2 + \ln 3 = 3.0986$. That is why the log-sum-exp is called a smooth maximum.

Summary

  • One categorical observation is an exponential family with natural parameters $\ln(\pi_k/\pi_K)$; the gradient of its log-partition function is the softmax and its covariance is $\operatorname{diag}(\boldsymbol\pi) - \boldsymbol\pi\boldsymbol\pi^{\mathsf T}$, of rank $K - 1$ (Theorem 1). The canonical link gives the baseline-category logit model, which is softmax regression.
  • The softmax is also the law of the largest of $K$ scores perturbed by independent Gumbel noise, and the log-sum-exp is the location of that largest score (Theorem 2).
  • The coefficients are identified only up to adding one vector to every class (Theorem 3). A reference class removes the freedom; gradient descent conserves the sum of the class vectors; an L2 penalty picks the representative whose class vectors sum to zero (Theorem 4). A final layer normalization leaves at least $K - 1$ more directions unidentified, even with a reference class.
  • The score is $X^{\mathsf T}(Y - \Pi)$, so the gradient of the loss with respect to the scores is $\boldsymbol\pi - \mathbf{y}$; the Hessian is $-\sum_i\Sigma(\boldsymbol\pi_i)\otimes\mathbf{x}_i\mathbf{x}_i^{\mathsf T}$, free of $Y$, so Newton's method is Fisher scoring (Theorem 5).
  • The log-likelihood is concave, strictly so with a reference class and full column rank (Theorem 6), and its curvature never exceeds $\frac12\lambda_{\max}(X^{\mathsf T}X)$, so a gradient step of $1/L$ always lowers the loss (Theorem 7).
  • The maximum exists exactly when no direction separates the classes (Theorem 8). Self-rated health in NHANES has a unique maximum; the bigram table, with 2,845 unseen pairs, has none.
  • At the maximum the model matches, class by class, the totals of every input, and among all conditional distributions that do so it has the greatest total entropy (Theorem 9).
  • On NHANES, BMI and age are strongly associated with self-rated health at fixed other inputs and sex is not (likelihood ratio statistics 305.72, 145.37 and 2.34 on 4 degrees of freedom). On 30 small GPTs the theorems' predictions for the head hold, the trained heads are not at their own maximum, and a lightly penalized refit of the head alone on 16,384 positions fits those positions better and the validation text worse, which is consistent with overfitting.

What we have learned

The output layer of a language model is a generalized linear model with a vector response. Its distribution is the categorical, an exponential family whose natural parameters are log-ratios against a reference class and whose mean map is the softmax; its link is canonical; its likelihood is the cross-entropy loss. The canonical link gives the score in the form observed minus fitted, $X^{\mathsf T}(Y - \Pi)$, which is the gradient $\boldsymbol\pi - \mathbf{y}$ that every training loop computes, and a Hessian that does not depend on the data's labels, so that Newton's method is Fisher scoring. The coefficients are identified only up to a common shift, which a reference class removes, an L2 penalty resolves symmetrically and gradient descent leaves where it started. The likelihood is concave, strictly so in the reference parametrization, and its curvature is bounded by half the largest eigenvalue of $X^{\mathsf T}X$. It has a maximum exactly when no direction of the coefficients separates the classes, a test the self-rated health data pass and the bigram table fails. At the maximum the model is the conditional distribution of greatest entropy among those that reproduce, class by class, the observed totals of every input.

That completes the Generalized Linear Models unit. A fitted model like the one for self-rated health invites many tests at once, one per coefficient and class. The next unit, Multiple Testing, is about what such a collection of p-values can support. It begins with The False Discovery Rate and the Benjamini–Hochberg Procedure.

References

  • Agresti, A. (2013). Categorical Data Analysis (3rd ed.). Wiley. Chapter 8, "Models for Multinomial Responses" (Section 8.1, baseline-category logit models; Section 8.2, cumulative logit models). record
  • Albert, A., and Anderson, J. A. (1984). On the existence of maximum likelihood estimates in logistic regression models. Biometrika, 71(1), 1–10. https://doi.org/10.1093/biomet/71.1.1 record · 2 pages
  • Berger, A. L., Della Pietra, S. A., and Della Pietra, V. J. (1996). A maximum entropy approach to natural language processing. Computational Linguistics, 22(1), 39–71. record · 2 pages
  • Böhning, D. (1992). Multinomial logistic regression algorithm. Annals of the Institute of Statistical Mathematics, 44(1), 197–200. https://doi.org/10.1007/BF00048682 record
  • Bridle, J. S. (1990). Training stochastic model recognition algorithms as networks can lead to maximum mutual information estimation of parameters. In Advances in Neural Information Processing Systems 2, 211–217. record
  • Karpathy, A. (2015). char-rnn [Software and data]. https://github.com/karpathy/char-rnn (the file data/tinyshakespeare/input.txt). record · 4 pages
  • Kingma, D. P., and Ba, J. (2015). Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR 2015). arXiv:1412.6980. record · 3 pages
  • McCullagh, P. (1980). Regression models for ordinal data. Journal of the Royal Statistical Society, Series B, 42(2), 109–127. https://doi.org/10.1111/j.2517-6161.1980.tb01109.x record
  • McCullagh, P., and Nelder, J. A. (1989). Generalized Linear Models (2nd ed.). Chapman and Hall. Chapter 5, "Models for Polytomous Data". record · 2 pages
  • McFadden, D. (1974). Conditional logit analysis of qualitative choice behavior. In P. Zarembka (Ed.), Frontiers in Econometrics, 105–142. Academic Press. record
  • National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: Demographic Variables and Sample Weights (DEMO_J), Body Measures (BMX_J) and Hospital Utilization & Access to Care (HUQ_J) data files (variable HUQ010: https://wwwn.cdc.gov/Nchs/Data/Nhanes/Public/2017/DataFiles/HUQ_J.htm). Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 95 pages
  • Santner, T. J., and Duffy, D. E. (1986). A note on A. Albert and J. A. Anderson's conditions for the existence of maximum likelihood estimates in logistic regression models. Biometrika, 73(3), 755–758. https://doi.org/10.1093/biomet/73.3.755 record · 2 pages
  • Theil, H. (1969). A multinomial extension of the linear logit model. International Economic Review, 10(3), 251–259. https://doi.org/10.2307/2525642 record
  • Train, K. E. (2009). Discrete Choice Methods with Simulation (2nd ed.). Cambridge University Press. Chapter 3, "Logit" (Sections 3.1 and 3.5). record
  • Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017). Attention is all you need. In Advances in Neural Information Processing Systems 30 (NIPS 2017). arXiv:1706.03762. record · 8 pages