Multiclass classification

While many classification algorithms (e.g., decision trees, k-NN, neural networks and multinomial logistic regression) naturally permit the use of more than two classes, some are by nature binary algorithms (e.g., classical binary support vector machine) and require decomposition strategies such as one-vs-all, one-vs-one, or ECOC to solve multiclass problems.

Multiclass classification should not be confused with multi-label classification, where multiple labels are to be predicted for each instance (e.g., predicting that an image contains both an apple and an orange, in the previous example).

Better-than-random multiclass models

From the confusion matrix of a multiclass model, we can determine whether a model does better than chance. Let ${\displaystyle K\ge 3}$ be the number of classes, ${\displaystyle \mathcal{O}}$ a set of observations, ${\displaystyle \hat{y}:\mathcal{O}\to \{1,...,K\}}$ a model of the target variable ${\displaystyle y:\mathcal{O}\to \{1,...,K\}}$ and ${\displaystyle n_{i,j}}$ be the number of observations in the set ${\displaystyle \{y=i\}\cap \{\hat{y}=j\}}$. We note ${\displaystyle n_{i.}=\sum _j{n}_{i,j}}$, ${\displaystyle n_{.j}=\sum _i{n}_{i,j}}$, ${\displaystyle n=\sum _j{n}_{.j}=\sum _i{n}_{i.}}$, ${\displaystyle {\lambda }_i=\frac{n_{i.}}{n}}$ and ${\displaystyle {\mu }_j=\frac{n_{.j}}{n}}$. It is assumed that the confusion matrix ${\displaystyle (n_{i,j}{)}_{i,j}}$ contains at least one non-zero entry in each row, that is ${\displaystyle {\lambda }_i>0}$ for any ${\displaystyle i}$. Finally we call "normalized confusion matrix" the matrix of conditional probabilities ${\displaystyle (\mathbb{P}(\hat{y}=j\mid y=i){)}_{i,j}={\left(\frac{n_{i,j}}{n_{i.}}\right)}_{i,j}}$.

Intuitive explanation

The lift is a way of measuring the deviation from independence of two events ${\displaystyle A}$ and ${\displaystyle B}$ :

${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(A,B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(A)\mathbb{P}(B)}=\frac{\mathbb{P}(A\mid B)}{\mathbb{P}(A)}=\frac{\mathbb{P}(B\mid A)}{\mathbb{P}(B)}}$

We have ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(A,B)>1}$ if and only if events ${\displaystyle A}$ and ${\displaystyle B}$ occur simultaneously with a greater probability than if they were independent. In other words, if one of the two events occurs, the probability of observing the other event increases.

A first condition to satisfy is to have ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=i,\hat{y}=i)\ge 1}$ for any ${\displaystyle i}$. And the quality of a model (better or worse than chance) does not change if we over- or undersample the dataset, that is if we multiply each row ${\displaystyle R_i}$ of the confusion matrix by a constant ${\displaystyle c_i}$. Thus the second condition is that the necessary and sufficient conditions for doing better than chance need only depend on the normalized confusion matrix.

The condition on lifts can be reformulated with One versus Rest binary models : for any ${\displaystyle i}$, we define the binary target variable ${\displaystyle y_i}$ which is the indicator of event ${\displaystyle \{y=i\}}$, and the binary model ${\displaystyle {\hat{y}}_i}$ of ${\displaystyle y_i}$ which is the indicator of event ${\displaystyle \{\hat{y}=i\}}$. Each of the ${\displaystyle {\hat{y}}_i}$ models is a "One versus Rest" model. ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=i,\hat{y}=i)}$ only depends on the events ${\displaystyle \{y=i\}}$ and ${\displaystyle \{\hat{y}=i\}}$, so merging or not merging the other classes doesn't change its value. We therefore have ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=i,\hat{y}=i)=\mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y_i=1,{\hat{y}}_i=1)}$ and the first condition is that all binary One versus Rest models are better than chance.

Example

If ${\displaystyle K=2}$ and 2 is the class of interest , the normalized confusion matrix is ${\displaystyle \left(\begin{array}{cc}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{t}\mathrm{y}& 1-\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{t}\mathrm{y}\\ 1-\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}& \mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}\end{array}\right)}$ and we have ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=1,\hat{y}=1)-1=\frac{\mathbb{P}(y=\hat{y}=1)}{{\lambda }_1{\mu }_1}-1=\frac{n_{1,1}n}{n_{1.}{n}_{.1}}-1}$ ${\displaystyle =\frac{n_{1,1}(n_{1,1}+n_{1,2}+n_{2,1}+n_{2,2})-(n_{1,1}+n_{1,2})(n_{1,1}+n_{2,1})}{n_{1.}{n}_{.1}}=\frac{n_{1,1}{n}_{2,2}-n_{1,2}{n}_{2,1}}{n_{1.}{n}_{.1}}}$. Thus ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=1,\hat{y}=1)\ge 1⟺n_{1,1}{n}_{2,2}-n_{1,2}{n}_{2,1}\ge 0}$. Similarly, by swapping the roles of 1 and 2, we find that ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=2,\hat{y}=2)\ge 1⟺n_{1,1}{n}_{2,2}-n_{1,2}{n}_{2,1}\ge 0}$. Dividing by ${\displaystyle n_{1.}{n}_{2.}}$ we find that the necessary and sufficient condition on the normalized confusion matrix is ${\displaystyle \mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{t}\mathrm{y}-(1-\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y})(1-\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{t}\mathrm{y})\ge 0⟺\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{t}\mathrm{y}+\mathrm{s}\mathrm{p}\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{c}\mathrm{i}\mathrm{t}\mathrm{y}-1\ge 0⟺J\ge 0}$. This brings us back to the classical binary condition: Youden's J must be positive (or zero for random models).

Random models

A random model is a model that is independent of the target variable. This property is easily reformulated with the confusion matrix.

Proposition—The model ${\displaystyle \hat{y}}$ of ${\displaystyle y}$ is random if and only if the confusion matrix is of rank 1.

Proof

${\displaystyle \hat{y}}$ is a random model of ${\displaystyle y}$ if and only if we have ${\displaystyle \mathbb{P}(\{y=i\}\cap \{\hat{y}=j\})=\mathbb{P}(y=i)\mathbb{P}(\hat{y}=j)}$ for any ${\displaystyle i}$ and ${\displaystyle j}$, which is equivalent to ${\displaystyle n_{i,j}n=n_{i.}{n}_{.j}}$ for any ${\displaystyle i}$ and ${\displaystyle j}$. All the columns of the confusion matrix are then proportional to the non-zero vector ${\displaystyle (n_{i.}{)}_i}$ , which implies that the confusion matrix is of rank 1.

Conversely, if this matrix is of rank 1, the non-zero columns of the matrix are proportional to each other, and therefore proportional to their sum ${\displaystyle (n_{i.}{)}_i}$. So there exists a family of numbers ${\displaystyle ({\beta }_j{)}_j}$ such that ${\displaystyle n_{i,j}=n_{i.}{\beta }_j}$ for any ${\displaystyle i}$ and ${\displaystyle j}$. Summing this equations over ${\displaystyle i}$ gives ${\displaystyle n_{.j}={\beta }_{j}n}$, hence ${\displaystyle n_{i,j}n=n_{i.}{n}_{.j}}$ for any ${\displaystyle i}$ and ${\displaystyle j}$.

This proposition shows that the model ${\displaystyle \hat{y}}$ of ${\displaystyle y}$ is uninformative if and only if there are two families of numbers ${\displaystyle ({\alpha }_i{)}_i}$ and ${\displaystyle ({\beta }_j{)}_j}$ such that ${\displaystyle \mathbb{P}(\{y=i\}\cap \{\hat{y}=j\})={\alpha }_i{\beta }_j}$ for any ${\displaystyle i}$ and ${\displaystyle j}$.

Multiclass likelihood ratios and diagnostic odds ratios

We define generalized likelihood ratios calculated from the normalized confusion matrix: for any ${\displaystyle i}$ and ${\displaystyle j\ne i}$, let ${\displaystyle {\mathrm{L}\mathrm{R}}_{i,j}=\frac{\mathbb{P}(\hat{y}=j\mid y=j)}{\mathbb{P}(\hat{y}=j\mid y=i)}}$. When ${\displaystyle K=2}$, if 2 is the class of interest,, we find the classical likelihood ratios ${\displaystyle {\mathrm{L}\mathrm{R}}_{1,2}={\mathrm{L}\mathrm{R}}_{+}}$ and ${\displaystyle {\mathrm{L}\mathrm{R}}_{2,1}=\frac{1}{{\mathrm{L}\mathrm{R}}_{-}}}$. Multiclass diagnostic odds ratios can also be defined using the formula ${\displaystyle {\mathrm{D}\mathrm{O}\mathrm{R}}_{i,j}={\mathrm{D}\mathrm{O}\mathrm{R}}_{j,i}={\mathrm{L}\mathrm{R}}_{i,j}{\mathrm{L}\mathrm{R}}_{j,i}=\frac{n_{i,i}{n}_{j,j}}{n_{i,j}{n}_{j,i}}=\frac{\mathbb{P}(\hat{y}=j\mid y=j)/\mathbb{P}(\hat{y}=i\mid y=j)}{\mathbb{P}(\hat{y}=j\mid y=i)/\mathbb{P}(\hat{y}=i\mid y=i)}}$

Theorem—For any ${\displaystyle j}$,

${\displaystyle \mathbb{P}(\hat{y}=j\mid y=j)-{\mu }_j=\sum _i{\lambda }_i(\mathbb{P}(\hat{y}=j\mid y=j)-\mathbb{P}(\hat{y}=j\mid y=i))}$

Equivalently, if all ${\displaystyle n_{i,j}}$ are non-zero:

${\displaystyle \frac{1}{\mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=j,\hat{y}=j)}=\sum _i\frac{{\lambda }_i}{{\mathrm{L}\mathrm{R}}_{i,j}}}$

Proof

${\displaystyle \mathbb{P}(\hat{y}=j\mid y=j)-\mathbb{P}(\hat{y}=j)=\mathbb{P}(\hat{y}=j\mid y=j)-\sum _i{\lambda }_i\mathbb{P}(\hat{y}=j\mid y=i)}$ ${\displaystyle =\sum _i{\lambda }_i(\mathbb{P}(\hat{y}=j\mid y=j)-\mathbb{P}(\hat{y}=j\mid y=i))}$. By dividing by ${\displaystyle \mathbb{P}(\hat{y}=j\mid y=j)}$ and subtracting 1, we deduce the second formulation.

Corollary—If all probabilities ${\displaystyle \mathbb{P}(\hat{y}=k\mid y=l)}$ are fixed, for any ${\displaystyle i}$ and ${\displaystyle j}$ we have

${\displaystyle \underset{{\lambda }_i\to 1}{lim}(\mathbb{P}(\hat{y}=j\mid y=j)-{\mu }_j)=\mathbb{P}(\hat{y}=j\mid y=j)-\mathbb{P}(\hat{y}=j\mid y=i)}$

Equivalently, if all ${\displaystyle n_{i,j}}$ are non-zero:

${\displaystyle \underset{{\lambda }_i\to 1}{lim}\mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=j,\hat{y}=j)={\mathrm{L}\mathrm{R}}_{i,j}}$

We saw above that a better-than-chance model (or a random model) must verify ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=i,\hat{y}=i)\ge 1}$ for any ${\displaystyle i}$ and ${\displaystyle {\lambda }_i}$. According to the previous corollary, likelihood ratios are thus greater than or equal to 1. Conversely, if the likelihood ratios are greater than or equal to 1, the theorem shows that we have ${\displaystyle \mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=i,\hat{y}=i)\ge 1}$ for any ${\displaystyle i}$ and ${\displaystyle {\lambda }_i}$.

Definition of better-than-chance multiclass models

A model ${\displaystyle \hat{y}}$ of ${\displaystyle y}$ outperforms chance if the following conditions are met:

• For any ${\displaystyle j}$, we have ${\displaystyle \underset{i}{max}\mathbb{P}(\hat{y}=j\mid y=i)=\mathbb{P}(\hat{y}=j\mid y=j)}$.
• There are i and j distinct such that ${\displaystyle \mathbb{P}(\hat{y}=j\mid y=i)<\mathbb{P}(\hat{y}=j\mid y=j)}$.

If all the entries of the confusion matrix are non-zero, this means that all the likelihood ratios are greater than or equal to 1, and at least one of these inegalities is strict. A model that satisfies the first condition but not the second is random, since we then have ${\displaystyle \mathbb{P}(\{\hat{y}=j\}\cap \{y=i\})=\mathbb{P}(y=i)\mathbb{P}(\hat{y}=j\mid y=i)=\mathbb{P}(y=i)\mathbb{P}(\hat{y}=j\mid y=j)={\alpha }_i{\beta }_j}$ for any ${\displaystyle i}$ and ${\displaystyle j}$.

We can rewrite the first condition in a more familiar way, noting ${\displaystyle x}$ the observed value of ${\displaystyle \hat{y}}$, ${\displaystyle \theta }$ the value to be estimated of ${\displaystyle y}$ and ${\displaystyle \hat{\theta }(x)}$ the set ${\displaystyle argma{x}_{\theta }\mathbb{P}(x\mid \theta )}$: for any ${\displaystyle x}$ we have ${\displaystyle x\in \hat{\theta }(x)}$. We deduce that a model is better-than-random or random if and only if it is a maximum likelihood estimator of the target variable.

Applications

Multiclass balanced accuracy

The performance of a better-than-chance model can be estimated using multiclass versions of metrics such as balanced accuracy or Youden's ${\displaystyle J}$.

Definition—${\displaystyle \mathrm{B}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}=\frac{1}{K}\sum _i\mathbb{P}(\hat{y}=i\mid y=i)}$ ${\displaystyle \mathrm{J}=\frac{1}{K-1}(K\mathrm{b}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}-1)=\frac{1}{K-1}\sum _i{\mu }_i(\mathrm{L}\mathrm{i}\mathrm{f}\mathrm{t}(y=i,\hat{y}=i)-1)}$

If ${\displaystyle \mathrm{b}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}=1}$, in other words ${\displaystyle J=1}$, the model is perfect. And for any random model, we have ${\displaystyle \mathrm{b}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}=\frac{1}{K}}$ (if, for example, we draw a uniform random number from the ${\displaystyle K}$ labels, we have exactly one chance in ${\displaystyle K}$ of predicting the correct value of the target variable).

On a balanced data set (${\displaystyle {\lambda }_i=\frac{1}{K}}$ for any ${\displaystyle i}$), balanced accuracy is equal to the rate of well-classified observations. On any data set, if a model does better than chance, we have ${\displaystyle J\ge 0}$ and ${\displaystyle \mathrm{b}\mathrm{a}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}\ge \frac{1}{K}}$. But the converse is not true when ${\displaystyle K>2}$, as we can see from this example: the confusion matrix ${\displaystyle \left(\begin{array}{ccc}0& 3& 0\\ 1& 2& 0\\ 0& 0& 3\end{array}\right)}$ is that of a bad model (=worse than chance) since ${\displaystyle {\mathrm{L}\mathrm{R}}_{2,1}=0}$. However, 5 of the 9 observations are correctly classified. This also shows that poor model performance on one of the modalities is not compensated for by good performance on the other modalities.

ROC space

The set of normalized confusion matrices is called the ROC space, a subspace of ${\displaystyle [0,1{]}^{m^2}}$. If ${\displaystyle E}$ denotes the subset of the ROC space made up of random models or models that do better than chance, one can show that the topological boundary of ${\displaystyle E}$ is the set of elements of ${\displaystyle E}$ for which at least one of the likelihood ratios is equal to 1. And random models are those models whose likelihood ratios are all equal to 1. When ${\displaystyle K=2}$, the boundary between models that do better than chance and bad models is equal to the set of random models (see article on the roc curve for more details), but it is strictly larger as soon as ${\displaystyle K>2}$. And if ${\displaystyle K=3}$, we can calculate the volume occupied by bad models in the ROC space: they occupy 90% of this space, whereas it's only 50% when ${\displaystyle K=2}$.