Multiclass and multilabel classification

Every classifier so far in this section, from logistic regression to the kernel SVM, separates two classes. Most real problems have more: ten digits, a few dozen product categories, a vocabulary of tens of thousands of words for a language model. Others attach several labels to the same object: a news article can be about both politics and the economy. This note covers the three ways to handle $K \gt 2$ classes with linear models: split the problem into binary ones, or extend logistic regression to a single model with $K$ outputs, the softmax, which is the output layer of nearly every neural classifier. It then adapts the metrics of the classification metrics note to many classes, and treats the case of several labels per example.

Notation. Classes $1, \dots, K$; a training set $(x_i, y_i)$, $i = 1, \dots, n$, with $x_i \in \mathbb R^d$ and $y_i \in \{1, \dots, K\}$. The one-hot vector of a label is $\mathbf y \in \{0, 1\}^K$ with a single 1 in position $y$. A linear multiclass model has a weight matrix $W$ with rows $w_1, \dots, w_K$ and biases $b_k$; the scores (logits) are $z_k = \langle w_k, x\rangle + b_k$, and $p = (p_1, \dots, p_K)$ is the vector of predicted class probabilities. In the multilabel case the target is a vector $\mathbf y \in \{0, 1\}^K$ with any number of ones. $\mathrm{TP}_k$, $\mathrm{FP}_k$ and $\mathrm{FN}_k$ count the true positives, false positives and false negatives of class $k$ against the rest.

Reducing to binary problems#

One-vs-rest#

Train $K$ binary classifiers; classifier $k$ separates class $k$ (label $+1$) from all the others (label $-1$) and outputs a score $f_k(x)$. Predict the class with the highest score, $\hat y = \arg\max_k f_k(x)$. The cost is $K$ binary trainings on all $n$ examples. Taking the sign of each classifier instead of the argmax leaves regions where no classifier, or several, claim the point (Bishop, 2006, §4.1.2); the argmax removes the ambiguity but brings its own problems:

• Scores on different scales. Each classifier is trained alone, so nothing makes $f_3(x) = 2$ comparable with $f_7(x) = 2$. For SVMs, whose scores are not probabilities, this is a real concern; calibrated probabilities help.
• Imbalance by construction. With ten balanced classes every binary problem is 1 against 9.
• A class between others. A linear score for “class $k$ against the rest” cannot be high in a band and low on both sides of it, so the binary model of a middle class is misspecified. The argmax of several linear scores can still carve out the band; the trouble is that each score is fitted alone, to its own binary problem.

The last pitfall is not a matter of data size. Take three classes on a line, with $x$ normal of variance 1 around $-2$, $0$ and $2$, and fit both approaches to the distribution itself:

Figure

One-vs-rest against softmax on three classes

The best linear logit for the middle class is constant, so its one-vs-rest model predicts $1/3$ everywhere, and class 2 wins only where both outer models fall below $1/3$, for $\lvert x\rvert \lt 0.70$ instead of the optimal $\lvert x\rvert \lt 1$. Its recall drops from $0.68$ to $0.51$, and the accuracy from the optimal $0.788$ to $0.774$. In high dimension such configurations are less common, and with well-regularized binary classifiers one-vs-rest is often as accurate as anything else (Rifkin and Klautau, 2004); but the example shows what the reduction gets wrong. It is not a matter of representation: the argmax of the one-vs-rest scores does form a band, and the same family of three linear scores contains the optimal rule, since the argmax of $(-2x - 2,\ 0,\ 2x - 2)$ picks class 2 exactly for $\lvert x\rvert \lt 1$. What fails is the training. Each binary logistic model is fitted alone to a posterior that is not logistic in $x$ (for the middle class it rises and falls), and the three misspecified fits do not combine into the optimal boundaries.

One-vs-one#

Train a classifier for every pair of classes, $K(K-1)/2$ of them, each on the examples of its two classes only; predict by majority vote, with ties broken by summed scores. Each problem is small and balanced, about $2n/K$ examples for balanced classes. If training on $m$ examples costs $m^a$, one-vs-rest costs $K n^a$ and one-vs-one costs $\tfrac{K(K-1)}{2}(2n/K)^a$. For a linear-time learner, $a = 1$, both cost about $Kn$; for kernel SVMs, with $a$ around 2, one-vs-one costs about $2n^2$ against $Kn^2$, five times less for ten classes. This is why LIBSVM, and scikit-learn’s SVC on top of it, use one-vs-one (Hsu and Lin, 2002). The price is at prediction time, $K(K-1)/2$ evaluations, 45 for ten classes, and each pairwise classifier also votes on points from the other $K - 2$ classes, which it never saw.

On the ten digits of scikit-learn (1,797 images of $8 \times 8$ pixels, half for testing) with L2-regularized logistic regression as the binary learner, one-vs-rest with 10 models reaches a test accuracy of $0.953$ and one-vs-one with 45 models $0.966$. A single multinomial model, the subject of the next section, reaches $0.963$. Reductions are not limited to these two schemes: error-correcting output codes assign each class a binary code word and train one classifier per bit (Dietterich and Bakiri, 1995), and joint formulations such as the multiclass SVM of Crammer and Singer (2001) train all $K$ score functions in one optimization problem.

Multinomial logistic regression#

One model with $K$ linear scores, turned into a probability distribution, avoids all three pitfalls: the scores are trained together, on one scale, against one likelihood.

Why a softmax of linear functions. Bayes’ formula gives the form of the posterior. Suppose the classes have prior probabilities $\pi_k$ and Gaussian class-conditional densities $N(\mu_k, \Sigma)$ with a shared covariance. By Bayes’ formula, $P(y = k \mid x) \propto \pi_k \exp\big(-\tfrac12 (x - \mu_k)^\top \Sigma^{-1} (x - \mu_k)\big)$. Expanding the quadratic form, the term $-\tfrac12 x^\top \Sigma^{-1} x$ is the same for every class and cancels in the normalization, which leaves

$$P(y = k \mid x) = \frac{e^{z_k}}{\sum_{j} e^{z_j}}, \qquad z_k = \langle \Sigma^{-1}\mu_k,\ x\rangle - \tfrac12 \mu_k^\top \Sigma^{-1}\mu_k + \log \pi_k ,$$

a normalized exponential of linear functions of $x$ (see the multivariate Gaussian; Bishop, 2006, §4.2). Multinomial logistic regression keeps this form and fits the weights directly, without assuming Gaussians. For the three classes of the figure, $z_k = \mu_k x - \mu_k^2/2 = (-2x - 2,\ 0,\ 2x - 2)$, and the fitted model reproduces exactly this posterior.

The model and its loss. The softmax maps a score vector to a probability vector:

$$p_k = \operatorname{softmax}(z)_k = \frac{e^{z_k}}{\sum_{j=1}^K e^{z_j}} .$$

The exponential makes every entry positive and the division makes them sum to 1; the largest score gets the largest probability, and a score far above the others takes almost all of it, hence the name, a soft version of the argmax. The model is fitted by maximum likelihood under a categorical distribution: the negative log-likelihood of one example is

$$L = -\log p_{y} = -\sum_{k} \mathbf y_k \log p_k = -z_y + \log \sum_{j} e^{z_j} ,$$

the cross-entropy between the one-hot label and the predicted distribution, in the sense of the entropy note of the generative models course. For $K = 2$ it is the logistic loss.

Figure

Softmax, cross-entropy and the gradient p − y

1. The linear layer gives one score per class: with $x = (2, 1)$ and the weights of the figure, $z = (2.0, 1.0, 0.1)$.
2. The softmax: $e^{z} = (7.389, 2.718, 1.105)$, which sum to $11.212$, so $p = (0.659, 0.242, 0.099)$.
3. The true class is 1, and the loss is $-\log 0.659 = 0.417$.
4. The gradient with respect to the scores is $p - \mathbf y = (-0.341, 0.242, 0.099)$.

The gradient $p - \mathbf y$. Differentiate $L = -z_y + \log\sum_j e^{z_j}$ with respect to $z_k$: the first term gives $-[k = y]$, the second $e^{z_k}/\sum_j e^{z_j} = p_k$. So

$$\frac{\partial L}{\partial z} = p - \mathbf y, \qquad \frac{\partial L}{\partial W} = (p - \mathbf y)\, x^\top, \qquad \frac{\partial L}{\partial b} = p - \mathbf y ,$$

where the second form follows from $z = Wx + b$ by the chain rule. The gradient is “predicted minus observed”, the same pattern as the residual of least squares and the $p - y$ of binary logistic regression. A gradient step raises the score of the true class in proportion to $1 - p_y$ and lowers every other score in proportion to its probability; an example the model already gets right with confidence contributes almost nothing.

The loss is convex in the scores. The second derivatives are $\partial p_k / \partial z_j = p_k([k = j] - p_j)$, so the Hessian is $H = \operatorname{diag}(p) - pp^\top$, and for any vector $v$

$$v^\top H v = \sum_k p_k v_k^2 - \Big(\sum_k p_k v_k\Big)^2 = \operatorname{Var}(v_Y), \qquad Y \sim \text{Categorical}(p) ,$$

a variance, hence non-negative. The scores are linear in $W$ and $b$, so the training loss is convex in the parameters too, and gradient descent or Newton’s method finds its minimum.

Invariance to shifting the scores. The Hessian has one direction of zero curvature: $v = (1, \dots, 1)$, for which $v_Y = 1$ always and the variance is 0. Adding the same constant $c$ to every score multiplies numerator and denominator of the softmax by $e^c$:

$$\operatorname{softmax}(z + c\mathbf 1) = \operatorname{softmax}(z) .$$

Three consequences follow. First, the parameters are not identifiable: adding the same vector $v$ to every $w_k$ and the same number to every $b_k$ shifts all scores by $\langle v, x\rangle + c$ and changes no probability. One class can therefore serve as a reference with $w_K = 0$, $b_K = 0$; for $K = 2$ this gives $p_1 = e^{z_1}/(e^{z_1} + e^{z_2}) = \sigma(z_1 - z_2)$, binary logistic regression. With an L2 penalty the weights become unique: of all equivalent weight sets, the penalty picks the one with the smallest norm, in which the class weights sum to zero. scikit-learn does not penalize the intercepts, so they remain defined only up to a common shift, and its solvers return the representative whose intercepts sum to zero: L-BFGS starts from zero, and the gradient with respect to the intercepts, a sum of vectors $p - \mathbf y$ over the examples, always has components summing to zero, so the iterates never leave that set. That is why the fitted intercepts of the figure are $(-0.667, 1.333, -0.667)$ rather than $(-2, 0, -2)$: the same posterior, shifted by $4/3$. Second, the shift is the standard numerical safeguard. For $z = (1000, 999)$, $e^{1000}$ overflows and the naive formula returns undefined values; subtracting the maximum first gives $\operatorname{softmax}(0, -1) = (0.731, 0.269)$, and the loss is computed as $-z_y + \max_j z_j + \log\sum_j e^{z_j - \max_j z_j}$. Third, only differences of scores matter, which is why the Gaussian term $x^\top\Sigma^{-1}x$ could be dropped above.

Softmax regression is the output layer of neural classifiers and of language models. A language model is a classifier whose $K$ classes are the tokens of the vocabulary: the n-gram language models note estimates the next-token probabilities by counting, and word2vec computes them with this softmax over dot products, where $K$ in the hundreds of thousands makes the normalization the bottleneck.

Multiclass metrics: micro and macro averages#

Precision, recall and $F_1$ are defined for one class against the rest. With $K$ classes there are $K$ such tables, and two ways to combine them (Manning, Raghavan and Schütze, 2008, §13.6):

• Macro averaging computes the metric per class and averages the $K$ numbers: every class counts equally, however rare.
• Micro averaging sums $\mathrm{TP}_k$, $\mathrm{FP}_k$ and $\mathrm{FN}_k$ over the classes and computes the metric once from the totals: every example counts equally.
• Weighted averaging averages the per-class metrics with weights proportional to the class sizes.

For single-label classification, micro averaging adds nothing: every wrong prediction is one false positive (for the predicted class) and one false negative (for the true class), so $\sum_k \mathrm{FP}_k = \sum_k \mathrm{FN}_k$ equals the number of errors and $\sum_k \mathrm{TP}_k$ the number of correct answers. Micro precision, micro recall and micro $F_1$ all equal the accuracy.

Worked example. A toy classifier on 100 examples with classes of 80, 15 and 5 (rows: true class, columns: prediction):

true \ predicted	A	B	C
A (80)	76	3	1
B (15)	6	9	0
C (5)	3	0	2

The accuracy, and so the micro $F_1$, is $87/100 = 0.87$. Per class, $F_1 = 2\mathrm{TP}/(2\mathrm{TP} + \mathrm{FP} + \mathrm{FN})$ is $152/165 = 0.921$ for A, $18/27 = 0.667$ for B and $4/8 = 0.5$ for C. The macro $F_1$ is $(0.921 + 0.667 + 0.5)/3 = 0.696$; the weighted $F_1$, $0.8 \cdot 0.921 + 0.15 \cdot 0.667 + 0.05 \cdot 0.5 = 0.862$, sits close to the accuracy because the large class dominates both. Which number to report is a question about the task: if finding the 5 examples of class C matters as much as the 80 of class A, the macro average says the classifier is mediocre, and the micro average hides it. The NLP evaluation note works through a three-topic text example of the same effect. Ranking metrics generalize too: a ROC curve and its AUC can be computed per class against the rest and macro-averaged.

Multilabel classification#

In multilabel problems each example carries a set of labels: the tags of a photo, the topics of an article, the diagnoses of a patient. The standard model treats each label as its own binary problem with its own sigmoid:

$$P(\mathbf y \mid x) = \prod_{k=1}^K p_k^{\mathbf y_k} (1 - p_k)^{1 - \mathbf y_k}, \qquad p_k = \sigma(\langle w_k, x\rangle + b_k) .$$

The product says that the labels are conditionally independent given $x$, and its negative logarithm is the sum of $K$ binary cross-entropies, one per label. The difference from the multiclass model is the normalization: the softmax makes the classes compete for one unit of probability, while independent sigmoids let any number of labels be likely at once, or none. Each label gets its own decision threshold, tuned on validation data to the metric that matters, because a label present in 2% of examples rarely deserves the default threshold of 0.5. This approach is called binary relevance. It still reflects labels that co-occur because they depend on the same features of $x$, but it ignores any dependence that remains once $x$ is known (“economy” making “politics” more likely for the same article). Classifier chains feed the predictions for the first labels as extra features into the classifiers for the next ones (Read et al., 2011); a network with a shared hidden layer and $K$ sigmoid outputs shares a representation between the labels, which helps when they depend on the same features (Zhang and Zhou, 2014). Its output is still the product above, so given $x$ the labels remain independent; dependence that remains given $x$ needs chains or a model of the joint distribution of the label vector.

Multilabel metrics compare a predicted set with a true set. With true sets $Y_i$ and predicted sets $Z_i$:

• Hamming loss: the share of wrong label decisions, $\frac{1}{nK}\sum_i \lvert Y_i \,\triangle\, Z_i\rvert$, where $\triangle$ is the symmetric difference;
• subset accuracy (exact match): the share of examples whose whole set is right, a harsh metric for large $K$;
• example-based metrics, averaged over examples: the Jaccard index $\lvert Y_i \cap Z_i\rvert / \lvert Y_i \cup Z_i\rvert$, or $F_1$ per example;
• micro and macro averages over labels, as in the multiclass case. Micro $F_1$ no longer equals any accuracy, since one example can contribute several true positives.

Worked example. Four examples and three labels, with true sets $\{1, 3\}, \{2\}, \{1, 2\}, \{3\}$ and predicted sets $\{1\}, \{2\}, \{1, 2, 3\}, \{2, 3\}$. Three of the 12 label decisions are wrong, so the Hamming loss is $0.25$; only the second example is exactly right, so the subset accuracy is $0.25$ too. The Jaccard indices are $1/2, 1, 2/3, 1/2$, with mean $0.667$. Summed over labels, $\mathrm{TP} = 5$, $\mathrm{FP} = 2$, $\mathrm{FN} = 1$, so micro $F_1 = 10/13 = 0.769$; per label $F_1$ is $1$, $0.8$ and $0.5$, and the macro average is $0.767$. On a synthetic problem with 5 labels, about two per example, independent logistic regressions have a Hamming loss of $0.216$ but get the whole label set right for only $0.351$ of the test examples: the two metrics measure very different things.

The text classification note of the NLP course lists the binary, multiclass and multilabel variants side by side with their losses.

Hierarchical and extreme classification#

Hierarchical classification. Classes often form a taxonomy: product categories, the topics of a library catalogue, biological species. A flat classifier ignores the tree; a top-down approach trains a classifier at each internal node to choose among its children, which keeps each problem small but propagates an error at the top to everything below it. Errors can be weighted by their distance in the tree, so that confusing two breeds of dog costs less than confusing a dog with a car (Silla and Freitas, 2011). The same tree gives a fast softmax: if the classes are leaves of a binary tree, the probability of a leaf is the product of the binary decisions on its path, which costs $\log_2 K$ sigmoids instead of a sum over $K$ classes. This hierarchical softmax was introduced for language models (Morin and Bengio, 2005) and is used by word2vec.

Extreme classification. When $K$ reaches $10^5$ to $10^7$ (all Wikipedia categories, all products of a shop, all tokens of a vocabulary), the softmax costs $O(Kd)$ per example for both the scores and the gradient, and most labels have only a handful of examples. Training then approximates the normalization by sampling a few negative classes per example (sampled softmax, Jean et al., 2015; negative sampling in the word2vec note) or uses label trees, and evaluation switches to ranking metrics such as precision at $k$: the share of correct labels among the $k$ top-scored ones.

What changed#

	Binary classification	Multiclass and multilabel
Output	one score, its sign	$K$ scores: an argmax, or a set of labels
Probability model	Bernoulli, $\sigma(z)$	categorical, $\operatorname{softmax}(z)$; or $K$ independent Bernoullis
Loss	logistic loss	cross-entropy $-\log p_y$; or a sum of $K$ binary cross-entropies
Gradient in the scores	$p - y$	$p - \mathbf y$, a vector
Reductions	none needed	one-vs-rest ($K$ models), one-vs-one ($K(K-1)/2$ models)
Identifiability	unique weights	scores defined up to a common shift; fix a reference class or use L2
Metrics	precision, recall, $F_1$	per class, then micro, macro or weighted averages; Hamming loss and exact match for label sets

Limitations#

• Reductions do not see the whole problem. One-vs-rest fits each linear score alone, so a class between others gets a misspecified binary model and suboptimal boundaries, even though the argmax can still form a band; one-vs-one asks classifiers about classes they never saw. Their scores are not calibrated probabilities.
• The softmax forces a choice. Probabilities sum to 1 over the known classes, so an input from none of them is still spread over them. The output may be overconfident, or close to uniform: being forced to choose a known class and being confident are different things; detecting such inputs is the subject of the anomaly detection note.
• Independent sigmoids ignore label dependence given $x$, even with a shared hidden layer, and exact-match accuracy falls quickly as the number of labels grows.
• Cost grows with $K$. Scores and gradients cost $O(Kd)$ per example; for very large $K$ the normalization must be approximated.
• Still linear. Every score $z_k$ is linear in $x$, so the decision regions are convex polytopes; a class made of two separate clusters cannot be one region.

What you should remember#

• One-vs-rest trains $K$ classifiers on all data; one-vs-one trains $K(K-1)/2$ on pairs, cheaper for superlinear learners such as kernel SVMs. Their scores are not on a common scale.
• Multinomial logistic regression: $p = \operatorname{softmax}(Wx + b)$, loss $-\log p_y$, the categorical negative log-likelihood. It is the exact posterior for Gaussian classes with a shared covariance.
• The gradient in the scores is $p - \mathbf y$, and in the weights $(p - \mathbf y)x^\top$. The Hessian $\operatorname{diag}(p) - pp^\top$ is a covariance matrix, so the loss is convex.
• Adding a constant to all scores changes nothing: fix a reference class or regularize, and subtract the maximum score before exponentiating.
• Single-label micro $F_1$ equals accuracy; macro averages weight classes equally and expose rare classes. Multilabel: independent sigmoids, per-label thresholds, Hamming loss, exact match, micro and macro $F_1$.

Code#

The softmax and its gradient, one-vs-rest against the multinomial model on three classes, the three strategies on the digits, and the multiclass and multilabel metrics:

import numpy as np
from scipy.stats import norm
from sklearn.datasets import load_digits, make_multilabel_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression
from sklearn.multiclass import OneVsRestClassifier, OneVsOneClassifier
from sklearn.metrics import f1_score, accuracy_score, hamming_loss, jaccard_score

# softmax, cross-entropy and its gradient for the scores z = (2, 1, 0.1), true class 1
def softmax(z):
    e = np.exp(z - z.max())            # subtracting the maximum changes nothing and prevents overflow
    return e / e.sum()
z = np.array([2.0, 1.0, 0.1]); y = np.array([1, 0, 0])
p = softmax(z)
print(p.round(3), round(-np.log(p[0]), 3), (p - y).round(3))   # [0.659 0.242 0.099] 0.417 [-0.341  0.242  0.099]
print(softmax(z + 100).round(3))                                # [0.659 0.242 0.099]: adding a constant changes nothing
with np.errstate(over='ignore', invalid='ignore'):
    big = np.array([1000.0, 999.0])
    print(np.exp(big) / np.exp(big).sum(), softmax(big).round(3))   # [nan nan] [0.731 0.269]
eps = 1e-6; L = lambda z: -np.log(softmax(z)[0])
print(np.array([(L(z + eps * np.eye(3)[k]) - L(z - eps * np.eye(3)[k])) / (2 * eps) for k in range(3)]).round(3))   # [-0.341  0.242  0.099]

# three classes on a line, N(-2, 1), N(0, 1), N(2, 1): one-vs-rest and multinomial fitted to the population (a fine weighted grid)
x = np.arange(-8, 8.0001, 0.01); X = np.tile(x, 3)[:, None]; c = np.repeat([0, 1, 2], len(x))
w = np.concatenate([norm.pdf(x, m) for m in (-2, 0, 2)])
fit = lambda target: LogisticRegression(C=1e8, tol=1e-12, max_iter=10000).fit(X, target, sample_weight=w)
ovr = [fit((c == k).astype(int)) for k in range(3)]
print([(round(float(m.coef_[0, 0]), 3), round(float(m.intercept_[0]), 3)) for m in ovr])   # [(-2.114, -2.169), (0.0, -0.693), (2.114, -2.169)]
t = (np.log(1 / 2) - ovr[0].intercept_[0]) / ovr[0].coef_[0, 0]            # where the left model drops to 1/3
print(round(-t, 3), round((2 * norm.cdf(2 + t) + 2 * norm.cdf(-t) - 1) / 3, 3), round(2 * norm.cdf(-t) - 1, 3))   # 0.698 0.774 0.515
mn = fit(c)
print(mn.coef_.ravel().round(3), mn.intercept_.round(3), round((4 * norm.cdf(1) - 1) / 3, 3), round(2 * norm.cdf(1) - 1, 3))
# [-2.  0.  2.] [-0.667  1.333 -0.667] 0.788 0.683: the Bayes posterior, shifted so that the intercepts sum to zero

# ten digits: one-vs-rest, one-vs-one and multinomial logistic regression
Xd, yd = load_digits(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(Xd, yd, test_size=0.5, random_state=0, stratify=yd)
sc = StandardScaler().fit(Xtr); Xtr, Xte = sc.transform(Xtr), sc.transform(Xte)
base = LogisticRegression(C=0.1, max_iter=5000)
for name, m in (('ovr', OneVsRestClassifier(base)), ('ovo', OneVsOneClassifier(base)), ('multinomial', base)):
    m.fit(Xtr, ytr)
    n_models = len(m.estimators_) if hasattr(m, 'estimators_') else 1
    print(name, n_models, round(m.score(Xte, yte), 3))
# ovr 10 0.953 | ovo 45 0.966 | multinomial 1 0.963
print(np.abs(base.coef_.sum(axis=0)).max() < 1e-6)   # True: with an L2 penalty the class weights sum to zero

# micro and macro averages: 100 examples, classes of 80, 15 and 5
cm = np.array([[76, 3, 1], [6, 9, 0], [3, 0, 2]])     # rows: true class, columns: prediction
yt = np.repeat(np.repeat([0, 1, 2], 3), cm.ravel()); yp = np.tile([0, 1, 2], 3).repeat(cm.ravel())
print(accuracy_score(yt, yp), f1_score(yt, yp, average=None).round(3), [round(f1_score(yt, yp, average=a), 3) for a in ('micro', 'macro', 'weighted')])
# 0.87 [0.921 0.667 0.5  ] [0.87, 0.696, 0.862]

# multilabel: four examples, three labels
Yt = np.array([[1, 0, 1], [0, 1, 0], [1, 1, 0], [0, 0, 1]]); Yp = np.array([[1, 0, 0], [0, 1, 0], [1, 1, 1], [0, 1, 1]])
print(hamming_loss(Yt, Yp), accuracy_score(Yt, Yp), round(jaccard_score(Yt, Yp, average='samples'), 3),
      [round(f1_score(Yt, Yp, average=a), 3) for a in ('micro', 'macro')], f1_score(Yt, Yp, average=None).round(3))
# 0.25 0.25 0.667 [0.769, 0.767] [1.  0.8 0.5]

# independent sigmoids on a synthetic multilabel problem (5 labels)
Xm, Ym = make_multilabel_classification(n_samples=2000, n_features=20, n_classes=5, n_labels=2, random_state=0)
Xtr, Xte, Ytr, Yte = train_test_split(Xm, Ym, test_size=0.5, random_state=0)
P = OneVsRestClassifier(LogisticRegression(max_iter=5000)).fit(Xtr, Ytr).predict_proba(Xte)
Yhat = (P >= 0.5).astype(int)
print(Ytr.mean(axis=0).round(2), round(hamming_loss(Yte, Yhat), 3), round(accuracy_score(Yte, Yhat), 3),
      [round(f1_score(Yte, Yhat, average=a), 3) for a in ('micro', 'macro')], round(f1_score(Yte, Yhat, average='samples', zero_division=0), 3))
# [0.38 0.43 0.39 0.36 0.33] 0.216 0.351 [0.695, 0.695] 0.619: label shares, Hamming loss, exact match, micro, macro and per-example F1

Next#

Every model of this section, binary or multiclass, scores an input by a linear function of its features, or of features fixed in advance by a kernel. A linear score cannot express interactions on its own: if a loan is risky when the income is low and the debt is high, but not when only one of them holds, the effect of income depends on debt, and no weighted sum of the two captures it. The next section starts from models that are built out of such conditions. The decision trees note splits the feature space by a sequence of yes-or-no questions, handles any number of classes at its leaves directly, and needs no scaling of the features.

References#

• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. §4.1.2 (multiple classes and the ambiguous regions of one-vs-rest and one-vs-one), §4.2 (generative models with Gaussian class-conditionals give a softmax of linear functions), §4.3.4 (multiclass logistic regression), §7.1.3 (multiclass SVMs).
• R. Rifkin, A. Klautau. In Defense of One-Vs-All Classification. JMLR, 5, pp. 101–141, 2004.
• C.-W. Hsu, C.-J. Lin. A Comparison of Methods for Multiclass Support Vector Machines. IEEE Transactions on Neural Networks, 13(2), pp. 415–425, 2002.
• T. G. Dietterich, G. Bakiri. Solving Multiclass Learning Problems via Error-Correcting Output Codes. Journal of Artificial Intelligence Research, 2, pp. 263–286, 1995.
• K. Crammer, Y. Singer. On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines. JMLR, 2, pp. 265–292, 2001.
• C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. §13.6 (evaluation of text classification: macro- and microaveraging).
• J. Read, B. Pfahringer, G. Holmes, E. Frank. Classifier Chains for Multi-label Classification. Machine Learning, 85(3), pp. 333–359, 2011.
• M.-L. Zhang, Z.-H. Zhou. A Review on Multi-Label Learning Algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8), pp. 1819–1837, 2014.
• C. N. Silla Jr., A. A. Freitas. A Survey of Hierarchical Classification across Different Application Domains. Data Mining and Knowledge Discovery, 22(1–2), pp. 31–72, 2011.
• F. Morin, Y. Bengio. Hierarchical Probabilistic Neural Network Language Model. AISTATS, 2005. Hierarchical softmax.
• S. Jean, K. Cho, R. Memisevic, Y. Bengio. On Using Very Large Target Vocabulary for Neural Machine Translation. ACL, 2015. Sampled softmax over a large vocabulary.
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. §4.2 (masking of a middle class by linear regression of indicators), §4.4 (multiclass logistic regression).
• E. Sokolov et al. Машинное обучение (HSE), lecture notes: lecture 6 (multiclass classification, one-vs-all and all-vs-all, multinomial logistic regression, micro and macro averages, multilabel classification and its metrics).