This chapter reviews the classification module: a one-page summary of each classifier, worked examples, and practice problems.
For each classifier in this module (logistic regression, Naive Bayes, kNN, decision trees, the perceptron, SVMs and their kernelized versions), take an empty sheet of paper, title it with the model’s name, and without looking at your notes write down:
Then interrogate what you wrote:
If you can do this for every model, you understand the module.
Consider \(L : \mathbb{R}^3 \to \mathbb{R}\) defined as \[ L(w) = w_1^4 + 2w_2^2 + w_3^2 - w_1 w_2 + 2 w_2 w_3. \] Run one iteration of gradient descent from \(w^{(0)} = (1, 1, 1)\) with \(\eta = 0.05\).
The gradient collects the partial derivatives: \[ \nabla L(w) = \begin{bmatrix} \partial L / \partial w_1 \\ \partial L / \partial w_2 \\ \partial L / \partial w_3 \end{bmatrix} = \begin{bmatrix} 4w_1^3 - w_2 \\ 4w_2 - w_1 + 2w_3 \\ 2w_3 + 2w_2 \end{bmatrix}, \qquad \nabla L(w^{(0)}) = \begin{bmatrix} 3 \\ 5 \\ 4 \end{bmatrix}. \] So \[ w^{(1)} := w^{(0)} - \eta \nabla L(w^{(0)}) = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 0.05 \begin{bmatrix} 3 \\ 5 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.85 \\ 0.75 \\ 0.8 \end{bmatrix}. \] The gradient gives the direction; the learning rate scales how far we travel in it. How to choose a good learning rate, and what happens when \(L\) is not convex, are questions we return to in the deep learning module.
Predict whether a recipient has subscribed after receiving a marketing email, from three binary features.
| personalized? | includes image? | short subject? | subscribed | |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 1 | 1 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 0 | 0 | 1 |
| 7 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 |
Use misclassification error as the impurity \(u\).
Root, emails \(\{1, \dots, 8\}\). Four of eight subscribed, so the root impurity is \(\tfrac12\). The candidate splits:
Split on “includes image?” (\(\tfrac18\) is the smallest). The “yes” branch \(\{1, 2, 3\}\) is pure, so it becomes a leaf with class label 0.
Node \(\{4, 5, 6, 7, 8\}\). Current impurity \(\tfrac15\).
It’s a tie. Misclassification error cannot tell these splits apart, and either is a valid choice. Choose “personalized?”: the “yes” branch \(\{5, 6\}\) becomes a leaf with class label 1.
Node \(\{4, 7, 8\}\). Split on “short subject?”: \(\{4, 7\}\) becomes a leaf with class label 1, and \(\{8\}\) becomes a leaf with class label 0. Every leaf is now pure, so we stop.
The final tree:
includes image?
├── yes → {1, 2, 3}: label 0
└── no → personalized?
├── yes → {5, 6}: label 1
└── no → short subject?
├── yes → {4, 7}: label 1
└── no → {8}: label 0
Popular choices of \(K : \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}\):
| kernel | \(K(x_i, x_j)\) | implicit \(\phi\) |
|---|---|---|
| quadratic | \((1 + x_i \cdot x_j)^2\) | quadratic terms in \(x\); \(\phi : \mathbb{R}^d \to \mathbb{R}^{O(d^2)}\) |
| RBF | \(\exp(-\|x_i - x_j\|^2)\) | similarity pattern of \(x\) with every point in \(\mathbb{R}^d\); \(\phi : \mathbb{R}^d \to \mathbb{R}^\infty\) |
Kernels have two advantages over explicit feature transformations. For suitable \(\phi\), the dot product is much faster to compute than \(\phi\) itself. And kernels allow transformations that are impossible to compute explicitly, like the infinite-dimensional one behind the RBF kernel.
It helps to see the kernelized SVM as the last of four steps.
The same idea works for the perceptron, as you derived in Homework 2.2.
Notice that every perceptron update adds \(y_i x_i\) for some misclassified point. Starting from \(w^{(0)} = 0\), after \(T\) steps, \[ w^{(T)} = \sum_{i=1}^n \alpha_i y_i x_i, \qquad \text{where } \alpha_i \text{ is the number of times we make a mistake on } (x_i, y_i). \] So we can keep track of the counts \(\alpha \in \mathbb{R}^n\) instead of \(w\):
Everything is now a dot product, so we can kernelize by replacing each \(x_j \cdot x\) with \(K(x_j, x)\): \[ f(x) := \text{sign}\Big(\sum_{i=1}^n \alpha_i y_i K(x_i, x)\Big), \qquad \text{update: } \alpha_i \leftarrow \alpha_i + 1 \text{ when } \text{sign}\Big(\sum_j \alpha_j y_j K(x_j, x_i)\Big) \neq y_i. \] The kernelized perceptron learns a nonlinear decision boundary. With the quadratic kernel, for example, it can learn XOR, which the ordinary perceptron cannot.
These go beyond direct recall. Several ask you to reason about a model on the spot, as the module assessment will.
With threshold \(t = \tfrac12\), show that logistic regression predicts label 1 exactly when \(w \cdot x > 0\). What shape is its decision boundary?
\(\dfrac{1}{1 + e^{-w \cdot x}} > \tfrac12 \iff 1 + e^{-w \cdot x} < 2 \iff e^{-w \cdot x} < 1 \iff w \cdot x > 0.\)
So the decision boundary is the hyperplane \(w \cdot x = 0\): logistic regression is a linear classifier, like the perceptron and the linear SVM. They differ in how they choose \(w\). Logistic regression maximizes likelihood, the perceptron corrects mistakes until none remain, and the SVM maximizes the margin.
Using the spam model from Chapter 2.2 (class prior \(\text{Bernoulli}(0.4)\); \(X^{(1)} \mid Y = 1 \sim \text{Bernoulli}(0.8)\), \(X^{(2)} \mid Y = 1 \sim \text{Bernoulli}(0.7)\); \(X^{(1)} \mid Y = 0 \sim \text{Bernoulli}(0.4)\), \(X^{(2)} \mid Y = 0 \sim \text{Bernoulli}(0.1)\)), classify “free gift!!”, that is, \(x = (1, 0)\).
\[ \begin{aligned} \mathbb{P}(Y = 1 \mid x) &\propto 0.4 \times 0.8 \times (1 - 0.7) = 0.4 \times 0.8 \times 0.3 = 0.096, \\ \mathbb{P}(Y = 0 \mid x) &\propto 0.6 \times 0.4 \times (1 - 0.1) = 0.6 \times 0.4 \times 0.9 = 0.216. \end{aligned} \] Since \(0.216 > 0.096\), label it not spam. Note the use of \(1 - 0.7\) and \(1 - 0.1\): the email does not contain “win,” and that absence is evidence too.
100%. Each training point’s nearest neighbor is itself.
Larger \(k\) averages over more neighbors, so predictions become smoother and less sensitive to individual noisy points: variance decreases, bias increases. Small \(k\) is flexible (overfitting risk); large \(k\) is rigid (underfitting risk).
Every point has all \(n\) training points as neighbors, so kNN predicts the overall majority class everywhere, regardless of \(x\).
Train a perceptron on the AND function, with inputs \((0,0), (0,1), (1,0), (1,1)\) and outputs \(0, 0, 0, 1\), mapped to labels \(-1, -1, -1, +1\). Lift the bias and start from \(w^{(0)} = (0, 0, 0)\). As in Chapter 2.5, count \(w \cdot x = 0\) as a mistake.
| \(x\) | \(y\) | \(w \cdot x\) | mistake? | \(w\) after |
|---|---|---|---|---|
| \((0,0,1)\) | \(-1\) | \(0\) | yes | \((0, 0, -1)\) |
| \((0,1,1)\) | \(-1\) | \(-1\) | no | \((0, 0, -1)\) |
| \((1,0,1)\) | \(-1\) | \(-1\) | no | \((0, 0, -1)\) |
| \((1,1,1)\) | \(+1\) | \(-1\) | yes | \((1, 1, 0)\) |
You train a hard-margin SVM and find that it has 3 support vectors. You then delete every training point that is not a support vector and retrain. Does the decision boundary change? What if you delete one support vector instead?
Deleting non-support vectors does not change the boundary. \(w^* = \sum_i \alpha_i^* y_i x_i\) depends only on points with \(\alpha_i^* \neq 0\), and those points still satisfy all the constraints of the smaller problem.
Deleting a support vector can change it. That point was holding the margin in place, so without it the margin may widen and the boundary may move.
For \(x, z \in \mathbb{R}^2\), expand \((1 + x \cdot z)^2\) and confirm that it equals \(\phi(x) \cdot \phi(z)\) for \(\phi(x) = (x_1^2,\, x_2^2,\, \sqrt2\, x_1 x_2,\, \sqrt2\, x_1,\, \sqrt2\, x_2,\, 1)\).
Which of the classifiers in this module can be kernelized as written, and why?
\((1 + x_1 z_1 + x_2 z_2)^2 = 1 + x_1^2 z_1^2 + x_2^2 z_2^2 + 2x_1 z_1 + 2x_2 z_2 + 2x_1 x_2 z_1 z_2\). Expanding \(\phi(x) \cdot \phi(z)\) term by term gives \(x_1^2 z_1^2 + x_2^2 z_2^2 + 2x_1x_2z_1z_2 + 2x_1z_1 + 2x_2z_2 + 1\). These are the same.
Algorithms that touch the data only through dot products: the perceptron (in its \(\alpha\) form) and the SVM (in its dual form). kNN with Euclidean distance can also be kernelized, because \(\|x - z\|^2 = x \cdot x - 2\, x \cdot z + z \cdot z\) is made of dot products. Naive Bayes and decision trees work feature by feature, not through dot products, so the kernel trick does not apply to them directly.