Multiclass Classification and Softmax

Definition Multiclass classification is a classification task with $K \ge 3$ classes in which every example belongs to exactly one class. The classes must be mutually exclusive and, for the cases the model is meant to handle, together cover every case. The label is coded as an index $y$ in $\{1, \dots, K\}$ or as a one-hot vector $\mathbf{y}$ in $\{0, 1\}^K$ with a single $1$ at the true class. A linear multiclass model computes one score per class,

where $\mathbf{x}$ in $\mathbb{R}^p$ holds the $p$ features, $W$ is a $K \times p$ weight matrix and $\mathbf{b}$ is in $\mathbb{R}^K$. The score of class $k$ is $z_k = b_k + \mathbf{w}_k^{\top}\mathbf{x}$, where $\mathbf{w}_k^{\top}$ is row $k$ of $W$. With $K = 2$ the task is binary classification.

Definition Multilabel classification is a task with $L$ binary labels per example, any number of which can equal $1$ at the same time, so the target is a vector $\mathbf{y}$ in $\{0, 1\}^L$ that may contain several ones or none. A common model gives each label its own probability, $P(Y_l = 1 \mid \mathbf{x}) = \sigma(z_l)$ for $l = 1, \dots, L$, and is trained with the sum or mean of the $L$ binary cross-entropies. These probabilities need not add to $1$. Multiplying $\sigma(z_l)$ or $1 - \sigma(z_l)$ across the labels to get the probability of a whole label vector additionally assumes that the labels are conditionally independent given $\mathbf{x}$, which may be false.

Definition The softmax function maps a score vector $\mathbf{z}$ in $\mathbb{R}^K$ to the vector $\mathbf{p} = \operatorname{softmax}(\mathbf{z})$ whose entries, for $k = 1, \dots, K$, are

The result is a class probability vector, a vector $\mathbf{p}$ in $\mathbb{R}^K$ with $p_k \ge 0$ for every $k$ and $p_1 + \cdots + p_K = 1$. In a model $p_k$ is the modeled probability $P(Y = k \mid \mathbf{x})$. For finite scores every softmax entry is strictly positive, so with $K \ge 2$ each entry lies strictly between $0$ and $1$. Adding the same constant $c$ to every score leaves the output unchanged, because the factor $e^{c}$ cancels. The ratio of two entries is $p_j / p_k = e^{z_j - z_k}$, and for $K = 2$ the first entry is $\sigma(z_1 - z_2)$. Multiplying all scores by a positive constant other than $1$ keeps the order of the entries but changes their values unless all scores are equal. When every wrong class costs the same and a correct class costs nothing, predicting a class with the largest $p_k$ minimizes the modeled probability of error.

Because of the shift invariance, adding the same vector to every row of $W$ and the same number to every entry of $\mathbf{b}$ leaves all the probabilities of a linear softmax model unchanged. Its parameters are therefore determined only up to such a shift unless one class is fixed as a reference with scores $0$.

Definition The log-sum-exp of a score vector $\mathbf{z}$ in $\mathbb{R}^K$ is $\operatorname{LSE}(\mathbf{z}) = \ln \sum_{j} e^{z_j}$, and the logarithms of the softmax probabilities are $\ln p_k = z_k - \operatorname{LSE}(\mathbf{z})$. Let $m = \max_j z_j$ be the largest score and

the sum of the shifted exponentials. Since $\sum_j e^{z_j} = e^{m} S$, the trick computes both quantities as

The shifted scores $z_j - m$ are all at most $0$, with at least one equal to $0$, so every shifted exponential lies in $(0, 1]$ and $S$ lies in $[1, K]$. It follows that $m \le \operatorname{LSE}(\mathbf{z}) \le m + \ln K$, and the partial derivative of $\operatorname{LSE}$ with respect to $z_k$ is $p_k$.

Definition For one example with true class $t$, one-hot target $\mathbf{y}$ and softmax probabilities $\mathbf{p} = \operatorname{softmax}(\mathbf{z})$, the multiclass cross-entropy is

Its gradient with respect to the scores has entries $p_k - y_k$, because the derivative of $\operatorname{LSE}(\mathbf{z})$ with respect to $z_k$ is $p_k$ and the derivative of $z_t$ with respect to $z_k$ is $1$ for $k = t$ and $0$ otherwise. Training minimizes the average $\hat{R} = \frac{1}{n}\sum_{i} L(\mathbf{z}_i, \mathbf{y}_i)$ over the $n$ training examples, often plus a penalty. If the labels are conditionally independent given their features and the parameters, this average is the categorical negative log likelihood divided by $n$, so minimizing it is maximum likelihood. For $K = 2$ it is the binary cross-entropy of the previous lesson.

Definition One-vs-rest, also called one-vs-all, reduces a $K$-class problem to $K$ binary problems. For each class $k$ a separate binary classifier is trained with class $k$ as the positive class and all other classes together as the negative class, and it returns a score or an estimated probability $q_k(\mathbf{x})$. A new case is assigned to a class with the largest of these $K$ outputs, which presumes they are on comparable scales. The $K$ objectives are fitted separately, so the $q_k(\mathbf{x})$ need not add to $1$. Dividing them by their sum afterward gives a vector that adds to $1$, but it does not make the training a softmax cross-entropy fit.