2.8 Classification Recap

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:

  1. the model: what the classifier looks like; and
  2. the learning algorithm: how its parameters are learned from data.

Then interrogate what you wrote:

If you can do this for every model, you understand the module.

2.1 Logistic regression

Example: gradient descent

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.

2.2 Naive Bayes

2.3 kNN

2.4 Decision trees

Example: building a decision tree

Predict whether a recipient has subscribed after receiving a marketing email, from three binary features.

email 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

2.5 Perceptron

2.6 Support vector machines

2.7 Kernelization

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.

Example: kernelized SVM

It helps to see the kernelized SVM as the last of four steps.

  1. Linear SVM, primal. Solve the problem above. Classifier: \(\hat f(x) := \text{sign}(w^* \cdot x + b^*)\).
  2. Primal with transformed inputs. Replace \(x_i\) with \(\phi(x_i)\): the constraints become \(y_i(w \cdot \phi(x_i) + b) \geq 1 - \varepsilon_i\), and the classifier is \(\text{sign}(w^* \cdot \phi(x) + b^*)\). This works, but we need to explicitly compute \(\phi(x_i)\).
  3. Dual with transformed inputs. \[ \max_\alpha \sum_{i=1}^n \alpha_i - \frac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j \big(\phi(x_i) \cdot \phi(x_j)\big) \quad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0, \;\; 0 \leq \alpha_i \leq C, \] with classifier \(\text{sign}\big(\sum_i \alpha_i^* y_i\, (\phi(x_i) \cdot \phi(x)) + b^*\big)\). We still compute \(\phi\), but now \(\phi\) appears only inside dot products.
  4. Kernelized SVM. Replace each \(\phi(x_i) \cdot \phi(x_j)\) with \(K(x_i, x_j)\): \[ \max_\alpha \sum_{i=1}^n \alpha_i - \frac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j K(x_i, x_j) \quad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0, \;\; 0 \leq \alpha_i \leq C, \] with classifier \(\hat f(x) := \text{sign}\big(\sum_i \alpha_i^* y_i K(x_i, x) + b^*\big)\).

Example: kernelized perceptron

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.

Practice problems

These go beyond direct recall. Several ask you to reason about a model on the spot, as the module assessment will.

Problem 1: Logistic regression’s decision boundary

With threshold \(t = \tfrac12\), show that logistic regression predicts label 1 exactly when \(w \cdot x > 0\). What shape is its decision boundary?

Solution

\(\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.

Problem 2: Naive Bayes by hand

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)\).

Solution

\[ \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.

Problem 3: kNN and the choice of \(k\)

  1. What is the training accuracy of 1-NN, assuming no two training points are identical? (b) In terms of bias and variance, what happens as \(k\) increases? (c) What does kNN predict when \(k = n\)?
Solution
  1. 100%. Each training point’s nearest neighbor is itself.

  2. 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).

  3. Every point has all \(n\) training points as neighbors, so kNN predicts the overall majority class everywhere, regardless of \(x\).

Problem 4: The perceptron on AND

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.

  1. Make one pass through the data in this order, and record each update. (b) Will the algorithm eventually terminate? Justify your answer without running it to the end.
Solution
  1. The lifted inputs are \((0,0,1), (0,1,1), (1,0,1), (1,1,1)\).
\(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)\)
  1. Yes. AND is linearly separable: for example, the line \(x_1 + x_2 = 1.5\), i.e. \(w = (1, 1, -1.5)\), separates it. By the perceptron convergence theorem, the algorithm terminates. (Running it out, it stops after 18 updates at \(w = (3, 2, -4)\), which gives scores \(-4, -2, -1, +1\): all correct.) Contrast this with XOR in Chapter 2.5, which is not linearly separable, so the perceptron never stops.

Problem 5: Support vectors

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?

Solution

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.

Problem 6: Kernels

  1. 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)\).

  2. Which of the classifiers in this module can be kernelized as written, and why?

Solution
  1. \((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.

  2. 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.