Binary logistic regression models one probability through one linear score. Many classification problems have unordered classes. Softmax regression generalizes the binary model by giving each class its own linear score and turning the vector of scores into a probability vector. This note develops the model carefully. We cover the likelihood and its cross-entropy form, the gradient and Hessian, numerically careful evaluation, the identifiability problem caused by shared shifts, the existence of minimizers, and the connection between fitted probabilities and the evaluation of classifiers.
The model and its likelihood
Fix classes and observations , , with , and . Collect the feature vectors as the rows of a design matrix . A parameter matrix has one column per class. The scores are
Definition 5.3.1
(Softmax probabilities)
Given scores for row , the softmax probabilities are
Every exponential is strictly positive, so . Because the numerators add up to the denominator, . Since and every other class also has positive probability, we in fact have for every finite .
The statistical model treats as conditionally independent given the features, with . The conditional likelihood is , and in the notation below.
Definition 5.3.2
(Log-sum-exp and the mean negative log-likelihood)
For , . The mean negative log-likelihood of is
The name cross-entropy comes from the following identity. Encode the label as the one-hot vector . The cross-entropy of relative to is , which is exactly the -th term above. Because , every term is strictly positive. Hence for every finite . This simple fact matters later.
Gradient and Hessian
Theorem 5.3.3
(Gradient and directional second derivative)
For each class ,
equivalently , where and is the one-hot label matrix. Let be a direction and put . Then
Consequently is convex on .
Proof
(Differentiating along a line)
Fix one row . Along , the scores are . Define
and let be the softmax of the moving scores. Differentiating the log of a sum gives .
By the quotient rule,
Therefore
The linear term contributes nothing to the second derivative.
At , . This is the inner product of with the matrix whose -th column is , so that matrix is the gradient of the -th term. Averaging over gives both formulas.
At , let . Expanding the square shows
So each bracket is the variance of under the probability weights , and a variance is nonnegative. A twice continuously differentiable function whose second derivative along every line is nonnegative is convex on every line, and is therefore convex.
Two features of the gradient deserve comment. First, it is a residual-weighted sum: class is pushed toward feature vectors whose predicted probability falls short of the observed indicator. Second, . As the section on shared shifts and gauges explains, this zero sum reflects a symmetry of the model.
Worked example 5.3.4
(Probabilities and gradients for two rows)
Let and . Take with , and with . Use the columns , and . Compute the probabilities, , every class gradient and the predictions.
The scores are and .
Row 1: the exponentials are with sum , so . The loss is , and the residual vector is .
Row 2: the exponentials are with sum , so . The loss is , and the residual vector is .
The mean loss is .
The class gradients are , where is the -th entry of row 's residual vector:
- ;
- ;
- .
The gradients sum to , as the remark above predicts.
Predictions: row 1 has largest probability in class 1, but its label is 3. Row 2 has largest probability in class 3, but its label is 1. The training accuracy is .
Evaluating log-sum-exp stably
Theorem 5.3.5
(Max-shifted log-sum-exp)
For with ,
and .
Proof
(Factor out the largest exponential)
Factor out of the sum: . Taking logarithms gives the first identity.
Every exponent is at most , so every term is at most , and the sum is at most . At least one index attains the maximum, and its term is , so the sum is at least . The log-probability formula follows by substituting the identity into .
This rewriting removes overflow caused by exponentiating large positive scores. It does not make arithmetic exact. Very negative shifted exponents can still underflow to zero. The sum retains a term equal to , but tiny contributions may be lost and affect rounding; even subtracting extreme finite scores may overflow. Rounding error remains. When scores are large in magnitude, the difference can lose relative accuracy through cancellation. Stability here means avoiding unnecessary failure in floating point. It is not a guarantee of any particular accuracy or running time.
Concept lensAnalytic
Log-sum-exp as a smooth maximum
The bounds in the theorem say , and the gradient of is the softmax vector . So is a convex, differentiable replacement for the maximum, and each loss term satisfies
Up to , the loss is the amount by which the largest score exceeds the score of the true class. Exactly, it equals , which tends to zero only when every other score falls infinitely far behind.
Common mistake
(Taking the logarithm of a computed probability)
A probability formed as a ratio can round to , and taking its logarithm then gives , although the exact loss is finite. Evaluate log-probabilities with the formula in the theorem, , not as the logarithm of a computed probability.
Worked example 5.3.6
(Scores )
The exponentials are , which sum to . The probabilities are therefore .
With label , the loss is , which equals . The gradient with respect to the scores is , and its entries sum to zero.
The stable route gives the same answer. Here , the shifted scores are , and their exponentials sum to . Hence .
Adding any constant to all three scores multiplies every exponential by . The probabilities do not change. The loss becomes , so it does not change either. If these scores belong to a feature vector in a dataset of size , that row contributes to .
Quick check
(Evaluate to four decimal places without overflow.)
Factor out the largest exponential first.
Solution · Answer
Here and the shifted exponentials are . The last one underflows to and is negligible, so the sum is . Hence . Computing directly would overflow.
Shared shifts and gauges
Definition 5.3.7
(Equivalent parameters and gauges)
Parameter matrices and are equivalent if for some , that is, if every column is shifted by the same vector. The reference-class gauge is the condition ; the sum-to-zero gauge is the condition .
Theorem 5.3.8
(Common-shift invariance and gauge representatives)
For any , replacing every by leaves every probability unchanged, for every . In particular it leaves unchanged. Each equivalence class contains exactly one matrix in the reference-class gauge and exactly one in the sum-to-zero gauge.
Proof
(Shift, then pick a representative)
The shift changes every score at by the same amount, . The softmax is unchanged by adding a constant to all scores, and the loss term changes by .
For the reference gauge, take ; this gives a representative with . If and both have last column zero, then , so the representative is unique.
For the sum-to-zero gauge, take , where ; the new columns sum to zero. If both and have zero column sum, then , so .
The equivalence relation captures exactly the parameter matrices that give the same probabilities at every . Suppose and give identical softmax outputs for all . Since , the difference cannot depend on . Writing for this common difference, we get for every . Subtracting the equation gives for all . Hence for every , which is a common shift.
This failure of identifiability holds even when has full column rank. It is a property of the parameterization, not of the data.
The data can add further ambiguity. If the training rows do not span , there is a nonzero with for all . Adding to a single column changes no training score, so it leaves unchanged. It can, however, change predictions at new points outside the span of the training rows.
Worked example 5.3.9
(Gauge representatives and an invisible change)
Let , and . Find both gauge representatives, check that they agree at , and give the prediction. Then suppose every training row is a multiple of . Exhibit a change in parameters that is invisible on the training data.
Reference gauge: subtract to get , and .
Sum-to-zero gauge: the column average is . Subtracting it gives , and , which sum to zero. The two representatives differ by the common vector in every column.
At , the original scores are , the reference scores are , and the sum-to-zero scores are . Each set is a shift of the original by a constant ( and respectively). All three give
Classes 1 and 3 tie. Under a smallest-index rule fixed in advance, the prediction is class 1.
For the training-only ambiguity, take . It is orthogonal to , so it is orthogonal to every training row. Replace by . No training score changes, but the class-2 score at rises by .
Theorem 5.3.10
(Positive definiteness in the sum-to-zero gauge)
Suppose span . Then at every finite , the quadratic form in the gradient-and-Hessian section is strictly positive for every nonzero direction with . Hence restricted to is strictly convex.
Proof
(Zero variance forces zero direction)
Suppose the form vanishes. Each row contributes a nonnegative variance, so every row variance is zero. Since every , this forces for all .
Sum over : , so for all and . Because the rows span , each is orthogonal to all of , so . Thus .
The same argument works in the reference gauge, where gives and hence directly. A positive definite Hessian along every segment of the gauge subspace yields strict convexity on that subspace.
Proof X-ray
Three hypotheses, three separate jobs
The proof starts from the variance decomposition in the gradient-and-Hessian section, so the only question is when every row variance can vanish. Each hypothesis removes one way for that to happen.
Finiteness of gives for every class. That is what turns a zero weighted variance into for all ; if some probability were , the corresponding would be unconstrained. The positivity is not uniform: along a path to infinity some probabilities tend to and the curvature can tend to , which is how the next section can have strict convexity without a minimizer.
The gauge constraint removes the common-shift direction. Without it, for every gives constant and zero variance, which is the invariance of the previous theorem. The constraint enters through one line: summing over turns into .
The span hypothesis converts for all training rows into . The third direction in the example below shows that it cannot be dropped.
Strict convexity gives at most one minimizer. It does not say that a minimizer exists.
Worked example 5.3.11
(The variance form in three directions)
Take one row with , as in row 1 of the two-row example. Evaluate the directional second derivative for a common shift, for a nonconstant direction, and for a direction orthogonal to .
(a) Common shift: for all gives for every . The weighted variance of a constant is , consistent with invariance under shared shifts.
(b) Nonconstant direction: take , and . These sum to zero, and . Then and , so the variance is .
As a check, the score Hessian is
and .
(c) Direction orthogonal to : take , and . These sum to zero and are nonzero, yet , so the form vanishes. A single row does not span , so the span hypothesis of the theorem is necessary.
Existence of minimizers
Counterexample mode
Strictly convex, bounded below, no minimum
Take , , , and . In the reference gauge set , and . The scores are and
This decreases strictly to as . The opening section on the model and its likelihood showed that at every finite parameter, because . Hence the infimum is not attained.
The single row spans , so the previous theorem applies: the loss is strictly convex in the gauge, and yet it has no minimizer. The same conclusion holds over the full two-dimensional gauge , since the infimum there is also .
The failure comes from the data being perfectly fit in the limit. No general claim is made here that a finite optimum exists for every dataset that is not separable. Such statements need their own proof. A penalty, by contrast, does give existence.
Theorem 5.3.12
(Full ridge penalty gives a unique finite minimizer)
For , the function on the full space , with every coefficient penalized, has exactly one minimizer. That minimizer satisfies .
Proof
(Coercivity, compactness, strict convexity)
Since , we have . At all probabilities equal , so . The sublevel set is therefore bounded, it is closed by continuity, and it is nonempty. A continuous function attains its minimum on a nonempty compact set, and that point minimizes globally.
The second directional derivative of is the variance form plus , which is positive for . So is strictly convex and the minimizer is unique.
Finally, , while is unchanged by the shift. If , subtracting the column average would strictly lower . So the minimizer has .
The penalty changes the objective. Its minimizer need not minimize , and is no longer invariant under raw common shifts.
Common mistake
(Expecting existence with an unpenalized intercept)
The theorem needs every coefficient penalized. If an intercept or some coefficients are left unpenalized, no blanket existence result holds. In the counterexample above, treat as an unpenalized intercept. Then , and no minimizer exists.
The binary case
With , impose the reference gauge , so . Then
Write . The loss term is . This equals , which is the binary logistic loss. The gradient is the familiar logistic gradient. Without a gauge, , so the data inform only the difference .
From scores to decisions and evaluation
Holding the other scores fixed, increasing strictly increases , because
It strictly decreases each for , while leaving the ratios among those other classes unchanged. A common shift of all scores changes nothing. Changing one coefficient of moves by an amount whose sign depends on . Coefficients therefore act through scores, not uniformly.
A prediction is a decision, distinct from the probability vector. Because softmax is strictly increasing in each score relative to the others, . Ties are possible and need a rule fixed in advance, such as choosing the smallest index.
Quick check
(For scores , give the softmax probabilities and the prediction under the smallest-index tie rule.)
The probabilities depend only on score differences.
Solution · Answer
With , the probabilities are . Classes and tie for the largest score, so the smallest-index rule predicts class . The tie is a property of the decision rule, not of the probabilities, which are well defined.
A different cost structure may justify a different rule, for example minimizing expected misclassification cost.
Computing probabilities stably says nothing about whether they are calibrated, that is, whether events predicted with probability occur about of the time. Calibration must be assessed on held-out data.
The mapping from labels to indices must be fixed before held-out evaluation and used identically for training and test data. Held-out mean cross-entropy, accuracy and the confusion matrix are all computed under that mapping.
Low training loss alone does not imply good performance on new data. Generalization claims need assumptions such as sampling from a common distribution. Standard errors and other inferential statements also require identifiability and model assumptions. Fitted coefficients describe associations; they do not support causal conclusions without further design or assumptions.
Exercises
Exercise 5.3.13
(Let and , with , , and , . Put . Reduce to a function of , show that no minimizer exists, and find the minimizer of the full ridge objective for . What changes if one fixes and penalizes only ?)
Core
Solution(5)
- 1
Reduce to one parameter
Row 1 contributes . Row 2 contributes . Hence . With , and scores , this matches the binary logistic loss in the section on the binary case.
- 2
Show nonattainment
, so there is no stationary point, and as . The data are separated: any classifies both points correctly, and rescaling upward always lowers the loss.
- 3
Solve the full-penalty stationarity equations
Key step
and give , hence and . For , works because .
- 4
Identify the minimizer
, , with fitted at .
Because: is strictly convex, so a stationary point is the unique minimizer.
- 5
Compare with a gauge-fixed penalty
With and only penalized, the condition becomes . At the right side equals , so the minimizer differs. Applying the same naive penalty formula to different gauge representatives can change the fitted model.