Softmax Coupling versus One-vs-Rest Probabilities

With three or more classes there are two natural ways to reduce the problem to binary decisions, and they estimate different quantities. Multinomial logistic regression, usually called softmax, fits one joint model whose outputs are normalised to sum to one and are consistent with a single generative story. One-vs-rest fits one independent binary model per class and combines the outputs afterwards. The difference shows up in the fitted coefficients, in whether the probabilities sum to one, and in whether a class that was rare in training can ever be predicted.

The normalising constant is the constraint

For $K$ classes with weight vectors $\beta_1, \dots, \beta_K$, the softmax model is

$$P(y = k \mid x) = \frac{e^{x^\top \beta_k}}{\sum_{j=1}^{K} e^{x^\top \beta_j}} .$$

The denominator adds a constraint that no binary model has: the scores are not free parameters but ratios. Adding a constant vector $c$ to every $\beta_k$ leaves every probability unchanged, because $e^{x^\top(\beta_k + c)}$ scales numerator and denominator by the same factor. The parameterisation therefore has an unidentifiable direction of dimension $p$, and the Hessian is singular along it. The standard resolution is to fix one class as the reference by setting its weight vector to zero, leaving $(K-1)p$ free parameters, with the reference class’s probability as the residual. Prediction is unaffected by the choice of reference; the coefficients are not, and a coefficient from a softmax model is always an effect relative to the chosen baseline.

The exponential also imposes a bound on relative scores that is easy to miss. A score difference of $d$ between two classes corresponds to a probability ratio of $e^{d}$. A model that has learned coefficients large enough to produce a score gap of 30, which is plausible with unstandardised features measured in thousands, predicts a probability for the leading class within $10^{-13}$ of one, and for the trailing class within the same distance of zero. In single precision, with its 24-bit significand, such a probability can round to exactly 1.0 and the gradient for that observation vanishes.

Evaluating the normaliser needs the max-subtraction trick for the same reason as the binary case: subtract the largest score before exponentiating, since $\log\sum_j e^{s_j} = m + \log\sum_j e^{s_j - m}$ with $m = \max_j s_j$. The shifted scores are all non-positive, so no exponential overflows, and at least one term equals one, so the sum is at least one and the logarithm is well conditioned.

import numpy as np

def softmax(S):
    S = S - S.max(axis=1, keepdims=True)     # largest score becomes 0
    E = np.exp(S)
    return E / E.sum(axis=1, keepdims=True)

The maximum is taken per row, not over the whole matrix, because the scores for one observation are the only ones being normalised together. Taking a global maximum would still be stable but would underflow every row whose top score is far below the global maximum.

One-vs-rest estimates a different quantity

The one-vs-rest construction trains $K$ independent models, each distinguishing class $k$ from the union of the others. Each model returns $\sigma(x^\top\gamma_k)$, a probability under the assumption that the observation is either class $k$ or not, with the class frequencies of that binary problem. These are not conditional probabilities over the $K$ classes. If the class prior is uniform, $\sum_k \sigma(x^\top\gamma_k)$ is around 1 for well-fitted models on typical data, but the sum is not constrained and is generally not exactly 1 for any particular observation.

Normalising the scores by dividing each by their sum is the usual repair, and the result is not the same as softmax. Softmax’s denominator is a function of the features through every class’s score; the one-vs-rest normalisation takes the product structure that the separate fits assumed and imposes a different functional form on it. The normalisation also destroys the calibration of each individual score, so a threshold derived for one class’s probability no longer carries its original meaning after division.

Training cost is the sharpest practical difference. One-vs-rest fits $K$ models of $p$ parameters on $n$ observations each, so the work scales as $K$ times a single binary fit. Softmax fits $Kp$ parameters jointly, so forming its Hessian costs $O(nKp^2)$ and solving costs $O((Kp)^3)$ per Newton iteration. For $K = 10$ and $p = 100$ the difference is a $10\times$-ish factor in the Hessian work and a $1000\times$ factor in the solve; for $K = 1000$ the joint solve is out of reach without a sparse or iterative solver, while the per-class fits remain independent and parallel.

One-vs-rest also parallelises trivially across classes, which in distributed settings matters more than the constant factor. Each binary problem reads the same design matrix and produces a separate weight vector, and there is no shared normaliser to synchronise.

Behaviour under class imbalance and within-class structure

A softmax model’s estimates are driven by the relative frequencies of the classes because the likelihood is a proper likelihood for the multinomial distribution. A class with 0.1 percent of the data has a score that must beat every alternative for the corresponding region of feature space, and the loss on that class’s observations is weighted by their frequency. The model can still learn it if the region is separable, but the gradient signal is proportional to the count.

One-vs-rest reframes each class as half of a balanced-by-construction binary problem if the negative class is subsampled, which is why it is sometimes described as less sensitive to imbalance. The claim is only partly right: the negative class in each binary problem contains every other class, so its composition varies across the $K$ fits, and a majority class that dominates the negatives will dominate every model that excludes it. Subsampling the negatives changes the implied prior and reintroduces the intercept-shift problem treated in class imbalance and cost-sensitive thresholds.

The two approaches also differ in what they can express. Softmax forces the log-odds between any two classes to be linear in the features, since

$$\log \frac{P(y=j\mid x)}{P(y=k\mid x)} = x^\top(\beta_j - \beta_k),$$

a difference of two linear functions. One-vs-rest imposes linearity on each class-versus-rest log-odds instead. A dataset on which the pairwise log-odds are linear but the versus-rest log-odds are not favours softmax; the reverse favours one-vs-rest. In practice the difference is small on smooth problems and large when one class is a union of disjoint clusters, because a versus-rest boundary has to enclose all of them while a pairwise boundary does not.

import numpy as np

def ovr_normalised(S):
    """Normalise independent per-class scores; not equivalent to a joint model."""
    S = S - S.max(axis=1, keepdims=True)
    E = np.exp(S)
    return E / E.sum(axis=1, keepdims=True)

When only the predicted class is needed, the normalising constant can be skipped entirely: the argmax of the softmax equals the argmax of the raw scores, since dividing by a positive row sum preserves the ordering. A model trained for accuracy alone can therefore drop the exponentials and the division at inference. The normaliser matters precisely when the output is consumed as a probability.

Hierarchical structure defeats the flat model

When the classes have a nested structure such as vehicle, car, sedan, neither flat parameterisation uses it. A softmax over all leaves allocates $Kp$ parameters and must learn that the sedan-versus-motorcycle distinction is easier than sedan-versus-coupe, with nothing in the model to share evidence between related classes. One-vs-rest has the same problem in a worse form, since every model re-learns the same coarse distinctions.

A hierarchical decomposition fixes this by fitting a small softmax at each internal node: whether the observation is a vehicle at all, then which kind, then which subtype. The total parameter count is the sum over nodes of (children count) times the dimensionality, which is generally far less than $Kp$ when the tree is deep, and the conditional probabilities at each node multiply into a valid joint probability over the leaves by the chain rule. The cost is that an error at a high node is unrecoverable downstream, and the per-node fits have smaller and less balanced samples than a flat fit.

The conditional structure also gives a way to trade accuracy for abstention. A path that reaches a node with a low probability can stop and return the coarse label, which is what makes hierarchical classifiers useful for taxonomy with uneven depth. This connects to the more general question of whether predicted probabilities are usable as probabilities, which is the subject of proper scoring rules for probability forecasts.

Two implementation details recur in both parameterisations. First, the reference class in softmax must be chosen once and documented, since refitting with a different reference silently changes every coefficient. Second, one-vs-rest requires a tie-breaking rule for the argmax, and the rule interacts with the class order in the input encoding; a tie that is broken by index systematically favours the earlier classes when the scores are quantised, which is common with integer-valued features.

A third option is worth naming because it competes with both. Fitting one margin-based classifier per class with the objective described in hinge loss and maximum margin avoids the exponential entirely and gives a sparse solution supported on near-boundary points, at the cost of producing scores with no probabilistic interpretation. Choosing between the three comes down to whether the output must be a probability, an argmax, or a sparse decision function, and only the first of those requires the normalising constant.