Multi-label Classification
Binary relevance, classifier chains, label powerset, and Hamming loss.
On this page
Beginner: section 2.4.4 was about picking exactly ONE label out of K — a photo is a cat, a dog, or a bird, never more than one at a time. Multi-label classification throws that assumption out: each example can carry ANY subset of L labels at once. A news article can be tagged politics AND economy simultaneously; a photo can contain a dog AND a frisbee AND a park all at once. The output space isn't "choose 1 of K" anymore — it's "choose any subset of L labels," and there are 2^L possible subsets to choose from.
Intermediate: this lesson covers three different strategies for turning the binary/probabilistic classifiers already built in this module (logistic regression, section 2.4.1) into multi-label predictors. Binary Relevance trains one independent classifier per label — simple, fast, but blind to correlations between labels. Classifier Chains trains the same L classifiers in sequence, each one allowed to see the previously predicted labels as extra input — this captures correlations Binary Relevance misses, at the cost of depending on the order the labels are chained in. Label Powerset sidesteps both by treating every observed label COMBINATION as its own class and reducing straight back to the ordinary multi-class machinery of section 2.4.4 — exact, but combinatorially expensive.
Advanced: the three strategies are really three different answers to "how do I approximate P(y₁,…,y_L∣x) using machinery built for a single label?" Binary Relevance assumes the labels are conditionally independent given x — a factorization that is convenient but generally FALSE. Classifier Chains uses the exact chain-rule factorization of probability — never an approximation in principle — but pays for exactness with sequential, order-dependent, error-propagating training. Label Powerset is also exact, but its class count grows as 2^L, bounded in practice only by how many distinct combinations happen to appear in the training set. This lesson also introduces Hamming loss, the standard way to score any of the three, since ordinary classification accuracy doesn't make sense once a "prediction" is a whole label SET rather than a single label.
Binary Relevance — the (generally wrong) independence assumption:
Classifier Chains — the exact chain rule of probability:
Hamming loss — the average per-label mismatch rate:
All three build directly on the binary classifier derived in section 2.4.1 — nothing here requires a new base model, only new ways of composing and evaluating it.
Binary Relevance (BR) is the simplest possible reduction: train L completely independent binary classifiers, one per label, each solving exactly the logistic regression problem from section 2.4.1 with that label as the target and x as the only input:
Multiplying these L independent probabilities together gives an implied joint distribution over the whole label vector:
This factorization is only exactly correct if the labels are conditionally independent given x — and in most real multi-label problems, they aren't. Consider a tiny numeric example: suppose P(rain=1)=0.30 and P(umbrella=1)=0.35 marginally. If BR's independence assumption held, the implied joint probability of BOTH being 1 would be 0.30 × 0.35 = 0.105. But in the real world, people who see rain coming actually grab an umbrella — the true observed co-occurrence rate might be P(rain=1, umbrella=1) = 0.28, nearly 2.7× higher than independence predicts. BR's per-label classifiers each fit their OWN marginal rule against x and never see each other's outputs, so this entire correlation is structurally invisible to them — not a matter of more data or a better optimizer, but a direct consequence of the factorization itself.
Classifier Chains (CC) starts from the one factorization of a joint distribution that is always exactly true, with no independence assumption anywhere — the chain rule of probability, applied to the L binary labels in some fixed order:
Each factor is turned into an ordinary binary classifier, exactly as in BR, except the l-th classifier's input is x AUGMENTED with the earlier labels y_1,…,y_{l-1}. At TRAINING time those earlier labels are the true, observed ones (teacher forcing); at INFERENCE time — since the true labels aren't available yet — each classifier is fed the PREDICTED labels produced by the earlier classifiers in the chain, in the same order:
This is exactly why CC captures the correlation the numeric example above showed BR missing: the umbrella classifier's input literally contains the (predicted) rain label, so it can learn "predict umbrella ≈ predicted rain" directly, rather than trying to reconstruct that correlation purely from x.
The real practical caveat is right there in the formula: the factorization is exact only if every one of the L classifiers is perfect. In practice they aren't, so two things follow. First, chain order matters — the labels chained early only ever condition on x, exactly like BR, while labels chained late get to condition on everything before them, so which labels end up "early" vs. "late" changes what correlations each classifier can exploit (the second diagram below makes this concrete). Second, errors propagate forward: if an early classifier predicts a label wrong, every downstream classifier trained on that (predicted, possibly wrong) label inherits the mistake. In practice this motivates training an ENSEMBLE of chains with several random label orders and averaging their predictions — Ensembled Classifier Chains (ECC) — rather than committing to one fixed order (more on this below).
Label Powerset (LP) takes a different route entirely: instead of decomposing y = (y_1,…,y_L) into L separate binary problems, treat the whole vector as a SINGLE meta-label:
This turns multi-label classification directly back into the ordinary multi-class problem of section 2.4.4 — one-vs-rest, one-vs-one, softmax, or ECOC can all be applied unchanged, just with each "class" now standing for one entire label combination rather than one label.
The cost is combinatorial. With L binary labels there are, in principle, up to 2^L distinct combinations:
For L=10 labels that's already 1{,}024 possible classes; for L=20 it's over a million. In practice |𝒴| is bounded by however many DISTINCT combinations were actually observed in the training set, which is typically far smaller than 2^L — but that's exactly LP's real weakness, not a saving grace. Two problems follow directly: LP structurally CANNOT predict any label combination that never appeared during training (there is no such class to output, no matter how confident the model is about the individual labels involved), and combinations that appeared only a handful of times get almost no training signal, producing poorly calibrated, high-variance predictions for exactly the rarer — often most interesting — tag combinations.
Once predictions are label SETS rather than single labels, "accuracy" is ambiguous — there needs to be an explicit choice of how partial credit is handled. The standard metric is Hamming loss: the fraction of individual (example, label) cells that are wrong, averaged over every example and every label:
Equivalently, this is just the average of the L per-label binary misclassification rates — decompose the double sum by label and each inner sum \tfrac{1}{N}\sum_i \mathbb{1}[\hat y_{il}\neq y_{il}] is exactly the ordinary 0/1 error rate of the l-th binary classifier on its own.
Contrast this with SUBSET ACCURACY (exact match), the far stricter alternative:
Subset accuracy counts an example as correct ONLY if every one of its L predicted labels matches exactly — getting L−1 out of L labels right scores identically to getting zero right. A small example makes the gap concrete: with L=5 labels, an example predicted correctly on 4 out of 5 contributes 1/(N·5) to the Hamming loss numerator (a small, proportionate penalty for a near miss) but contributes a full wrong example to subset accuracy's numerator (zero credit at all). Hamming loss is far more forgiving of near-misses — which is usually the right behavior for tagging-style problems, but not always: an application that genuinely needs the WHOLE combination right (e.g. a set of mutually required regulatory codes) should report subset accuracy instead, or alongside it.
8 toy examples, 3 labels. Umbrella is built to closely track rain (with one deliberately noisy exception, so the comparison stays honest). Binary Relevance's independently-fit umbrella threshold misses the correlation; Classifier Chains' umbrella prediction directly copies its own predicted rain and gets those cases right. Toggle strategies to watch the mismatch rings (and the Hamming loss readout) change on the Umbrella column only — Rain and Sunglasses are identical either way.
The same document, the same four label affinities, chained in two different orders. In Order A, Politics is predicted first and its 1 boosts Economy's affinity past 0.5 -- Economy is predicted. In Order B, Economy is predicted BEFORE Politics is known, so it never gets that boost and stays below threshold. Same base classifiers, same data, different final label SET -- purely from chain order. Replay to watch a run unfold, or switch orders to compare final predictions.
#include <cmath>
#include <iostream>
#include <vector>
double sigmoid(double z) { return 1.0 / (1.0 + std::exp(-z)); }
// Trains a simple logistic regression by gradient descent (section 2.4.1). Rows of X may
// already be augmented with previously predicted/true labels as extra columns -- that single
// difference is what turns this one routine into either a Binary Relevance or a Classifier
// Chains base classifier, depending on what the caller passes in.
std::vector<double> trainLogistic(const std::vector<std::vector<double>>& X,
const std::vector<int>& y, int epochs = 800, double lr = 0.3) {
int n = X.size(), d = X[0].size();
std::vector<double> w(d, 0.0);
for (int e = 0; e < epochs; ++e) {
std::vector<double> grad(d, 0.0);
for (int i = 0; i < n; ++i) {
double z = 0.0;
for (int j = 0; j < d; ++j) z += w[j] * X[i][j];
double p = sigmoid(z);
for (int j = 0; j < d; ++j) grad[j] += (p - y[i]) * X[i][j];
}
for (int j = 0; j < d; ++j) w[j] -= lr * grad[j] / n;
}
return w;
}
std::vector<int> predict(const std::vector<std::vector<double>>& X, const std::vector<double>& w) {
std::vector<int> preds;
for (const auto& row : X) {
double z = 0.0;
for (size_t j = 0; j < w.size(); ++j) z += w[j] * row[j];
preds.push_back(sigmoid(z) >= 0.5 ? 1 : 0);
}
return preds;
}
int main() {
// Bias column plus one feature; three labels, "umbrella" built to correlate with "rain".
std::vector<std::vector<double>> X = {{1, -2}, {1, -1}, {1, 0.5}, {1, 1}, {1, 2}, {1, 2.5}};
std::vector<int> rain = {0, 0, 1, 1, 1, 1};
std::vector<int> umbrella = {0, 1, 1, 1, 0, 1}; // mostly follows rain, one flip each way
// Binary Relevance: umbrella's classifier sees only X, never the rain label.
auto wUmbrellaBR = trainLogistic(X, umbrella);
auto predUmbrellaBR = predict(X, wUmbrellaBR);
// Classifier Chains: rain -> umbrella, umbrella's input augmented with rain.
auto wRainCC = trainLogistic(X, rain);
auto predRainCC = predict(X, wRainCC);
std::vector<std::vector<double>> XPlusTrueRain = X;
for (size_t i = 0; i < X.size(); ++i) XPlusTrueRain[i].push_back(rain[i]); // teacher forcing
auto wUmbrellaCC = trainLogistic(XPlusTrueRain, umbrella);
std::vector<std::vector<double>> XPlusPredRain = X;
for (size_t i = 0; i < X.size(); ++i) XPlusPredRain[i].push_back(predRainCC[i]); // inference
auto predUmbrellaCC = predict(XPlusPredRain, wUmbrellaCC);
std::cout << "True umbrella: ";
for (int y : umbrella) std::cout << y << " ";
std::cout << "\nBinary Relevance predicts: ";
for (int p : predUmbrellaBR) std::cout << p << " ";
std::cout << "\nClassifier Chain predicts: ";
for (int p : predUmbrellaCC) std::cout << p << " ";
std::cout << "\n";
return 0;
}- Document / article tagging — a news article tagged both "politics" and "economy," a support ticket tagged both "billing" and "urgent."
- Image scene tagging — a single photo containing multiple objects at once ("dog," "frisbee," "park"), unlike single-object image classification.
- Gene function prediction — a single gene product can be annotated with multiple simultaneous biological functions (e.g. multiple Gene Ontology terms), not just one.
- Playlist / content genre labeling — a track tagged both "acoustic" and "rock," a movie tagged both "comedy" and "romance."
- Medical coding — a single patient encounter can carry several co-occurring diagnosis codes simultaneously, not a single diagnosis.
- Defaulting to Binary Relevance without checking whether the labels are actually correlated — it's the simplest option, but on a dataset like the umbrella/rain example above it silently throws away real, exploitable signal.
- Treating Classifier Chains as order-independent — it isn't. A poorly chosen order can propagate an early mistake through the whole chain and, on some runs, do no better than Binary Relevance; validate the order, or train an ensemble of random-order chains (ECC) instead of committing to one.
- Reaching for Label Powerset on a label set with many rare combinations — at test time it can only output combinations it saw during training, and combinations it saw only once or twice get almost no usable training signal.
- Reporting plain accuracy (or Hamming loss) as if it always means "the model got it right" — Hamming loss gives partial credit for near-misses, which is appropriate for most tagging problems but wrong for problems where the entire label set genuinely needs to match; report subset accuracy too when that distinction matters.
Going deeper
Order-sensitivity isn't usually fixed by hand-picking a single "best" chain order — it's fixed by not picking one at all. Ensembled Classifier Chains (ECC) trains several chains, each with an independently randomized label order, and averages their per-label predicted probabilities (or votes on the binary outputs). Any one chain's order-dependent quirks tend to wash out in the average, at the cost of training M chains instead of one. More broadly, Classifier Chains is a first, concrete example of a much bigger idea: decomposing a joint prediction over a structured output (here, a label vector with internal correlations) into a sequence of simpler conditional predictions. That same move — conditioning each prediction on the ones already made — reappears in far more general form in graphical models and sequence-labeling methods later in this course; Classifier Chains is the simplest possible instance of it.
Binary Relevance and Classifier Chains are both built from exactly the same base binary classifier (logistic regression). So why can Classifier Chains outperform Binary Relevance if the underlying model class is identical?
The difference isn't in the base classifier at all -- it's in what each one is allowed to CONDITION ON. Binary Relevance's l-th classifier only ever sees x, so it can only exploit correlation between label l and other labels to the extent that correlation happens to be mediated through x. Classifier Chains' l-th classifier sees x AND the earlier labels y_1..y_{l-1} directly, so it can exploit label correlations that exist for reasons x doesn't capture at all -- like two tags that co-occur for editorial or structural reasons unrelated to the raw input features. The chain-rule factorization is exact only if every classifier in the chain is perfect; in practice it trades that theoretical exactness for genuinely more information at each step, which is exactly why it can win even with an identical model class.
Multi-label classification handles one specific way labels can be structured — an unordered SUBSET rather than a single choice. The next lesson, section 2.4.6, Ordinal Regression / Classification, handles yet another distinct structure that neither multi-class (2.4.4) nor multi-label (this lesson) methods get right on their own: categories that carry a natural ORDER, like poor/fair/good/excellent, where predicting one step off should be penalized far less than predicting the opposite extreme.