Classification

The decision-theoretic core#

Classification is a decision problem, not an estimation problem. Separating the two stages clarifies most practical disputes.

Stage one, estimate. Model the posterior P(y = k | x). Stage two, decide. Choose an action minimising expected loss.

For a loss matrix L(k, j) — the cost of predicting j when the truth is k — the optimal rule is:

h(x) = argmin_j  SUM_k  L(k, j) * P(y = k | x)

• L(k, j) — cost incurred by answering j when the true class is k
• P(y = k | x) — posterior probability of class k given features x

Under 0-1 loss, L(k, j) = 1[k != j], and this collapses to argmax_k P(y = k | x), the Bayes classifier. Its risk is the Bayes error, an irreducible floor set by genuine class overlap.

The binary asymmetric case gives the threshold directly:

predict 1  iff  P(y = 1 | x)  >  L(0,1) / ( L(0,1) + L(1,0) )

• L(0,1) — cost of a false positive, L(1,0) — cost of a false negative

The default threshold of 0.5 is therefore the correct choice only when the two errors cost the same. Elkan (2001) shows that for cost-sensitive problems, adjusting the threshold on a calibrated probability dominates retraining with resampled data. Rebalancing the training set and then thresholding at 0.5 is a strictly worse-conditioned way to reach the same place.

Discriminative versus generative#

Discriminative:  model P(y | x) directly       logistic regression, SVM, trees
Generative:      model P(x | y) and P(y),      naive Bayes, LDA, QDA
                 then apply Bayes' rule

Ng and Jordan (2001) give the definitive comparison. The generative model carries higher asymptotic error when its assumptions are wrong, but converges at O(log d / n) rather than O(d / n). The curves cross. Naive Bayes wins in the small-sample, high-dimension regime; logistic regression wins once n is large.

Generative models also handle missing features and novel classes more gracefully, because they carry a density over x. Discriminative models have no notion of whether an input was plausible at all.

Reductions from multi-class to binary#

ECOC is under-appreciated. Assign each class a binary codeword of length L, train one binary classifier per bit, and decode by minimum Hamming distance. With a code of good minimum distance, the ensemble corrects individual classifier errors. It reduces both bias and variance relative to one-vs-rest.

Softmax is the right default for probability quality. One-vs-one is competitive when per-fit cost is superlinear in n, since each of its many fits sees only two classes' worth of data — this is why SVC uses it.

Multi-label#

Let Y be a subset of 2^K rather than an element of {1..K}.

Binary relevance:   K independent binary models. Ignores label correlation.
Classifier chains:  model k conditions on predictions 1..k-1. Order matters.
Label powerset:     treat each observed label set as one class. Up to 2^K classes.

Read et al. (2011) introduced ensembles of classifier chains with randomised orderings, which remains a strong baseline. Binary relevance is optimal for Hamming loss but not for subset-0/1 loss — Dembczyński et al. (2012) prove that the loss function determines whether modelling label dependence can help at all. This is the key theoretical result in the area and it is routinely overlooked.

Evaluation needs multi-label-specific measures: Hamming loss, subset accuracy, micro- and macro-averaged F1. Note that micro-averaging weights by label frequency and macro-averaging does not, so the two can rank systems differently.

Class imbalance#

The literature is larger than the effect. van den Goorbergh et al. (2022) show that resampling degrades calibration while leaving discrimination roughly unchanged, and argue against it as a default in clinical prediction.

Ordered by evidence:

1. Change the threshold, using a calibrated model. Nearly always sufficient.
2. Cost-sensitive weighting in the loss, via class_weight. Equivalent to threshold shifting for many models, but interacts with regularisation.
3. Resampling. SMOTE (Chawla et al., 2002) synthesises minority points along segments between neighbours. Widely used; it distorts the posterior and requires recalibration afterwards.

If resampling is applied, it must live inside the cross-validation loop, applied to training folds only. Oversampling before splitting places near-duplicates on both sides and inflates every score. imblearn.pipeline.Pipeline enforces this; the scikit-learn one does not.

Open-set recognition#

The closed-world assumption — every test input belongs to one of the K training classes — is false in nearly every deployment.

Scheirer et al. (2013) formalised open-set recognition and introduced open space risk. Softmax outputs are unsuitable as novelty scores because they are normalised over known classes only; an input unlike anything seen still produces one large probability.

Practical approaches: OpenMax (Bendale & Boult, 2016) fits an extreme-value model to per-class activation distances; energy-based scores (Liu et al., 2020) outperform maximum-softmax baselines; deep ensembles remain a strong uncertainty baseline (Lakshminarayanan et al., 2017). None is solved. Treat any deployed classifier as needing a separate rejection mechanism.

Calibration and thresholds under shift#

Prior shift — P(y) changes while P(x | y) does not — is the common case in fraud, disease and demand. Saerens et al. (2002) give an EM procedure that corrects the posterior using only unlabelled test data:

P_new(y = k | x)  ∝  P_old(y = k | x) * ( pi_new(k) / pi_old(k) )

• pi_old(k), pi_new(k) — class priors in the training and deployment distributions

Only the intercept requires adjustment for a logistic model, which is why prior shift is far more tractable than covariate shift.

Key references#

• Dietterich, T. & Bakiri, G. (1995). Solving Multiclass Learning Problems via Error-Correcting Output Codes. JAIR 2.
• Elkan, C. (2001). The Foundations of Cost-Sensitive Learning. IJCAI.
• Ng, A. & Jordan, M. (2001). On Discriminative vs. Generative Classifiers. NeurIPS 14.
• Saerens, M., Latinne, P. & Decaestecker, C. (2002). Adjusting the Outputs of a Classifier to New a Priori Probabilities. Neural Computation 14(1).
• Chawla, N. et al. (2002). SMOTE: Synthetic Minority Over-sampling Technique. JAIR 16.
• Read, J. et al. (2011). Classifier Chains for Multi-label Classification. Machine Learning 85(3).
• Dembczyński, K. et al. (2012). On Label Dependence and Loss Minimization in Multi-label Classification. Machine Learning 88(1).
• Scheirer, W. et al. (2013). Toward Open Set Recognition. IEEE TPAMI 35(7).
• Lakshminarayanan, B., Pritzel, A. & Blundell, C. (2017). Simple and Scalable Predictive Uncertainty Estimation Using Deep Ensembles. NeurIPS.
• van den Goorbergh, R. et al. (2022). The Harm of Class Imbalance Corrections for Risk Prediction Models. JAMIA 29(9).

Current state#

For tabular classification, gradient-boosted trees remain the strongest default. Grinsztajn et al. (2022) analyse why neural networks still trail on tabular data: rotational invariance is the wrong inductive bias when features are individually meaningful, and trees handle irregular target functions and uninformative features better.

For perceptual inputs, the pipeline has inverted. Rather than training a classifier end to end, the standard approach is to take a pretrained representation and fit a light head on it, or to skip fitting entirely and use a zero-shot model such as CLIP (Radford et al., 2021), which classifies against arbitrary text labels supplied at prediction time. That relaxes the closed-set constraint at the interface, though not the underlying problem.

The unresolved issues are not accuracy. They are calibrated uncertainty, subgroup performance disparity, and knowing when to abstain.

What to learn next#

• Decision trees — how the staircase boundary gets built, one question at a time.
• Model evaluation — why the accuracy on this page's first map was meaningless.
• Train, test and validation splits — measuring a classifier on data it has not memorised.