4.2 Classification

4.2.1 Fundamentals

Let us now turn to classification problems. Like regression, we assume we get IID observations \(z_n = (\mathbf {x}_n, y_n)\), but now with the difference that \(y\) takes one of a set of unordered distinct values, which I will call \(\mathcal {Y}\). The simplest case is where \(y\) takes one of two values, which I will sometimes call “binary classification”. As before, we wish to use \(\mathbf {x}\) to guess what \(y\) is. As we will see shortly, there are more choices to what \(f\) should even be for classification than there are for regression.

Ultimately, we need a mapping \(\mathbf {x} \mapsto \mathcal {Y}\), so we might take \(\hat {y}(\mathbf {x}) \in \mathcal {Y}\). Necessarily, the loss function must take in two values in \(\mathcal {Y}\)—the guess and the truth—and return a real number. Formally, \(\mathscr {L}: \mathcal {Y} \times \mathcal {Y} \mapsto \mathbb {R}\), which can be fully represented as a \(|\mathcal {Y}| \times |\mathcal {Y}|\) matrix. The simplest case of this is called “zero–one” loss: \[ \mathscr {L}_{\text {ZO}}(\hat {y}, y) = \mathrm {I}(\hat {y} \neq y) = \sum _{c \in \mathcal {Y}} \mathrm {I}(\hat {y} = c)\, \mathrm {I}(y \neq c). \] Note that the maximizer of the zero–one loss has a closed form: \begin{align*} \mathbb {E}_{\mathbb {P}(\mathbf {x},y)}\left [\mathscr {L}_{\text {ZO}}(\hat {y}, y)\right ] &= \sum _{c \in \mathcal {Y}} \mathrm {I}(\hat {y} = c)\, \mathbb {E}_{\mathbb {P}(\mathbf {x},y)}\left [\mathrm {I}(y \neq c)\right ] \\ &= \sum _{c \in \mathcal {Y}} \mathrm {I}(\hat {y} = c)\bigl (1 - \mathbb {P}(y = c, \mathbf {x})\bigr ) \\ &= 1 - \sum _{c \in \mathcal {Y}} \mathrm {I}(\hat {y} = c)\bigl (1 - \mathbb {P}(y = c \mid \mathbf {x})\bigr )\mathbb {P}(\mathbf {x}). \end{align*}

Since \(\mathbb {P}(\mathbf {x})\) does not depend on \(c\), the best choice for \(\hat {y}\) is \begin{equation*} \hat {y}^*(\mathbf {x}) = \operatorname *{argmax}_{c \in \mathcal {Y}} \mathbb {P}(y = c \mid \mathbf {x}). \end{equation*}

The natural generalization of zero–one loss and functions that return categories is a function that returns a probability. For binary regression with \(y \in \{0, 1\}\), we can take \(\pi (\mathbf {x})\) to approximate \(\mathbb {P}(y = 1 \mid \mathbf {x})\), and so take \(\pi : \mathbf {x} \mapsto [0, 1]\).

Cross Entropy Loss If \(\pi (\mathbf {x}) \in (0, 1)\) then we can in fact use other losses. One common choice is the negative log likelihood: \begin{align*} \mathscr {L}_{\text {CE}}(\pi , y) &= -\log \mathbb {P}(y \mid \pi ) \\ &= -\log \pi ^{y}(1 - \pi )^{1-y} \\ &= -y \log \pi - (1-y) \log (1 - \pi ) \\ &= -y \log \frac {\pi }{1 - \pi } - \log (1 - \pi ). \end{align*}

This is also known as the “cross-entropy loss,” since the maximum likelihood estimator is also the minimizer of the Kullback–Liebler divergence.

Logistic Regression Suppose we have \(f \in \mathbb {R}\). Then \begin{equation*} \pi (f) = \frac {\exp (f)}{1 + \exp (f)} =: \operatorname {Expit}(f). \end{equation*} You can readily see that \(\operatorname {Expit}(f) \in (0, 1)\). The expit function is invertible with inverse sometimes called the “logit”: \begin{equation*} \operatorname {Logit}(\pi ) := \log \frac {\pi }{1 - \pi }. \end{equation*} Note that if you plug this formula into the cross-entropy loss, \begin{align*} \mathscr {L}_{\text {CE}}(\operatorname {Expit}(f), y) &= -y \operatorname {Logit}(\operatorname {Expit}(f)) + \log (1 - \operatorname {Expit}(f)) \\ &= -y f + \log \!\left (1 - \frac {\exp (f)}{1 + \exp (f)}\right ) \\ &= -y f - \log (1 + \exp (f)), \end{align*}

And if we further take \(f(\mathbf {x}) = \mathbf {\beta }^{\top } \mathbf {x}\), we get \begin{equation*} \mathscr {L}_{\text {CE}}(\operatorname {Expit}(\mathbf {\beta }^{\top }\mathbf {x}), y) = -y \mathbf {\beta }^{\top } \mathbf {x} - \log (1 + \exp (\mathbf {\beta }^{\top }\mathbf {x})), \end{equation*} which is logistic regression.

Generative modeling We have noted that the optimal classifier takes the form of the maximum of \(\mathbb {P}(y = c \mid \mathbf {x})\mathbb {P}(\mathbf {x})\). In our reasoning above we ignored \(\mathbb {P}(\mathbf {x})\) since it does not depend on \(c\), and modeled \(\mathbb {P}(y = c \mid \mathbf {x})\), e.g. using the expit function and linear models. However, we could condition in the other direction to write \begin{equation*} \hat {y} = \operatorname *{argmax}_{c} \mathbb {P}(y = c \mid \mathbf {x})\mathbb {P}(\mathbf {x}) = \operatorname *{argmax}_{c} \mathbb {P}(\mathbf {x} \mid y = c)\mathbb {P}(y = c). \end{equation*} When we have many more data than categories, \(\mathbb {P}(y = c)\) is easy to estimate: \begin{equation*} \mathbb {P}(y = c) \approx \frac {1}{N} \sum _{n=1}^{N} \mathrm {I}(y_n = c). \end{equation*} We can then attempt to model the conditional density \(\mathbb {P}(\mathbf {x} \mid y = c)\) by forming density estimates the sets of points \(\mathcal {X}_c := \{\mathbf {x}_n : y_n = c\}\). Density estimation is difficult in high dimensions—arguably more difficult than estimating good decision boundaries—but generative modeling can be particularly effective in low dimensions, or when something special is known about the structure of \(\mathbb {P}(\mathbf {x} \mid y = c)\).

Note that the estimation \(\mathbb {P}(\mathbf {x} \mid y = c)\) does not admit a ready formulation as a direct minimization of classification error. Estimation of densities is typically considered an “unsupervised learning” problem for this reason, even though here we would use the unsupervised learning estimate in service of a supervised learning problem.

4.2.2 Support Vector Machines

Suppose we have binary classification data \((\mathbf {x}_1, y_1), \ldots , (\mathbf {x}_N, y_N)\), where \(y_n \in \{-1, 1\}\), and we want to find a linear decision boundary: \begin{equation*} \hat {y}_n = \operatorname {sign}(\mathbf {x}_n^{T} \hat {\mathbf {\beta }}). \end{equation*} Such a vector \(\hat {\mathbf {\beta }}\) would be normal to a hyperplane that separates our predictions. Support Vector Machines add three layers on top of this:

• Regularization: find the separating hyperplane with maximum margin.
• Soft margin: allow for margin mistakes (e.g. not linearly separable).
• Kernel: expressive (possibly infinite) feature mapping.

For finite data that are linearly separable, there always are infinitely many separating hyperplanes. Which one does perceptron converge to? If it does, con implicit, so let’s make it implicit and ask for a particular one. As a form of regularization, we’ll ask for the one with maximum margin: \begin{equation*} \hat {\mathbf {\beta }}_{\text {hard}} = \operatorname *{argmax}_{\|\mathbf {\beta }\|_2 = 1,\, \gamma } \gamma \quad \text {subject to} \quad y_n \mathbf {x}_n^{T} \mathbf {\beta } \geq \gamma \quad \forall n = 1, \ldots , N. \end{equation*}

Soft Margin SVM The hard margin SVM is restricted to linearly separable data. We now introduce a soft margin (linear) SVM, which trades separability with \(\|\mathbf {\beta }\|_2\): \begin{equation*} \hat {\mathbf {\beta }}_{\text {soft}}(\lambda ) = \operatorname *{argmin}_{\mathbf {\beta }} \sum _{n=1}^{N} \max (1 - y_n \mathbf {x}_n^{T} \mathbf {\beta },\, 0) + \lambda \|\mathbf {\beta }\|_2^2. \end{equation*} This way, we may allow classification (or margin) mistakes for the purpose of reducing \(\|\mathbf {\beta }\|_2^2\). This brings us to the familiar form of minimizing loss plus penalty.

Connection to hard margin SVM To see how soft margin SVM relates to hard margin, add slack variable \(\xi _n \geq \max (1 - y_n \mathbf {x}_n^{T} \mathbf {\beta },\, 0)\) and observe that \begin{equation*} \hat {\mathbf {\beta }}_{\text {soft}}(\lambda ) = \operatorname *{argmin}_{\mathbf {\beta }} \|\mathbf {\beta }\|_2^2 + \frac {1}{\lambda } \sum _{n=1}^{N} \xi _n \quad \text {subject to} \quad y_n \mathbf {x}_n^{T} \mathbf {\beta } \geq 1 - \xi _n,\; \xi _n \geq 0 \quad \forall n = 1, \ldots , N. \end{equation*}

We also divided by \(\lambda \). From this point we may intuitively believe that, for linearly separable data, \(\hat {\mathbf {\beta }}_{\text {hard}}\) is obtained as the limit of \(\hat {\mathbf {\beta }}_{\text {soft}}(\lambda )\) as \(\lambda \to 0^{+}\), since the slack variables \(\xi _1, \ldots , \xi _N\) are pushed to zero.

Interpretation as penalty for margin mistakes The slack variable \(\xi _n\) is nonzero if we make a margin mistake on \((\mathbf {x}_n, y_n)\). It is greater than one if we make a classification mistake. The sum \(\sum _{n=1}^{N} \xi _n\) quantifies the total over all margin mistakes, which we can control by adjusting the penalty \(\lambda \).

Kernels Using convex optimization theory, one may show that the soft margin SVM solution will satisfy \begin{equation*} \hat {\mathbf {\beta }}_{\text {soft}} = \sum _{n=1}^{N} \alpha _n y_n \mathbf {x}_n \quad ; \quad \text {where} \quad \alpha _n \neq 0 \text { if and only if } y_n \mathbf {x}_n^{T} \hat {\mathbf {\beta }}_{\text {soft}} \leq 1. \end{equation*} If we used an expressive feature transformation \(\varphi (\mathbf {x}_n) \in \mathbb {R}^{Q}\), the soft margin SVM \(\hat {\mathbf {\beta }}_{\text {kernel}} \in \mathbb {R}^{Q}\) would satisfy \begin{equation*} \hat {\mathbf {\beta }}_{\text {kernel}} = \sum _{n=1}^{N} \alpha _n y_n \varphi (\mathbf {x}_n). \end{equation*} The prediction on a new observation would be \begin{equation*} y = \operatorname {sign}\!\left (\varphi (\mathbf {x})^{T} \hat {\mathbf {\beta }}_{\text {kernel}}\right ) = \sum _{n=1}^{N} \alpha _n y_n \varphi (\mathbf {x})^{T} \varphi (\mathbf {x}_n)=: \sum _{n=1}^{N} \alpha _n y_n k(\mathbf {x},\mathbf {x}_n). \end{equation*}