Chapter 7 Introduction to Classification

Classification is a supervised learning task whose goal is to predict a categorical outcome from a set of input features. Unlike regression, where the response is continuous, the labels here are discrete—for example, “spam” versus “not spam,” or “diseased” versus “healthy.” We learn a rule that maps features to a class, typically by estimating class probabilities or by constructing a decision boundary. Methods range from relatively simple models such as logistic regression and discriminant analysis to more flexible ones such as trees, support vector machines, neural networks, and ensembles. As in the rest of statistical learning, the central tension is between flexibility and overfitting: we want a rule that predicts well on new observations, not only on the training sample.

Classification Framework

We start with training data \(\mathcal{D}_n = \{(x_i, y_i)\}_{i=1}^{n}\), where \(x_i \in \mathbb{R}^p\) is a \(p\)-dimensional feature vector. For now we focus on the binary case, with response \(y_i \in \{0, 1\}\). The particular coding of the two classes is not essential; \(\{-1, +1\}\) is equally common.

The goal is to find a classifier \(f: \mathbb{R}^p \rightarrow \{0, 1\}\), that is, a map from feature space to the label set. To score a prediction \(f(x)\) when the true label is \(y\), we use the 0-1 loss, also called the misclassification error: \[ L\bigl(f(x), y\bigr) = \begin{cases} 0, & \text{if } y = f(x),\\ 1, & \text{otherwise}. \end{cases} \] The training (empirical) risk of \(f\) is then \[ \widehat{R}_n[f] = \frac{1}{n} \sum_{i=1}^{n} L\bigl(f(x_i), y_i\bigr). \] Minimizing \(\widehat{R}_n[f]\) over all functions \(f\) is not a useful recipe by itself: the minimizer can interpolate the training labels and still fail on future data. What we actually want is a rule with small expected error on a new pair \((X, Y)\).

The Optimal Classifier

If we knew the data-generating distribution \(P\), or if we had infinitely many samples, the empirical risk would converge to the expected risk, \[ \widehat{R}_n[f] \longrightarrow R[f] := E_{X,Y}\, L\bigl(f(X), Y\bigr). \]

Optimal classifier

The optimal classifier minimizes expected 0-1 risk: \[ f^* = \arg\min_f \, R[f], \qquad R[f] = E_{X,Y}\, L\bigl(f(X), Y\bigr). \]

Suppose we may use any function \(f\). What is \(f^*\)?

Write \(p(x)\) for the marginal density of \(X\), \(p(y \mid x)\) for the conditional distribution of \(Y\) given \(X = x\), and \(p(x,y) = p(x)\,p(y \mid x)\) for the joint distribution. Then \[\begin{align*} R[f] &= E_{X,Y}\, L\bigl(f(X), Y\bigr) \\ &= \int_{\mathcal{X}} \sum_{y \in \{0,1\}} L\bigl(f(x), y\bigr)\, p(y \mid x)\, p(x)\, dx \\ &= \int_{\mathcal{X}} \Biggl[ \sum_{y \in \{0,1\}} L\bigl(f(x), y\bigr)\, p(y \mid x) \Biggr] p(x)\, dx. \end{align*}\] Because \(p(x) \ge 0\), it is enough to minimize the inner sum separately at each \(x\): \[ f^*(x) = \arg\min_{a \in \{0,1\}} \sum_{y \in \{0,1\}} L(a, y)\, p(y \mid x). \]

Let \(\eta(x) := P(Y = 1 \mid X = x)\). Then \(Y \mid X = x\) is Bernoulli, and the inner risk is just the conditional probability of a mistake: \[\begin{align*} \sum_{y} L\bigl(f(x), y\bigr)\, p(y \mid x) &= \begin{cases} 1 - \eta(x), & \text{if } f(x) = 1,\\ \eta(x), & \text{if } f(x) = 0. \end{cases} \end{align*}\] Hence \[ f^*(x) = \begin{cases} 1, & \text{if } \eta(x) \ge 1/2,\\ 0, & \text{if } \eta(x) < 1/2. \end{cases} \] (The assignment at the tie \(\eta(x) = 1/2\) is arbitrary.) This \(f^*\) is the Bayes classifier (or Bayes rule). Its risk \(R[f^*]\) is the Bayes risk, also called the Bayes error. No other classifier can beat it in expected 0-1 loss; in practice we never know \(\eta(x)\), so every method is an attempt to approximate \(f^*\).

How about multi-class classification?

The same argument extends immediately to \(K\) classes, \(y \in \{1, \ldots, K\}\). The Bayes rule is \[ f^*(x) = \arg\max_{k \in \{1,\ldots,K\}} P(Y = k \mid X = x). \] A classifier partitions \(\mathbb{R}^p\) into labeled regions. We often describe the decision boundary (the interface between regions) rather than \(f\) itself. A linear classifier is one whose decision boundaries are hyperplanes.