Other supervised methods: kNN, SVMs and the kernel trick

ML · Chapter 311 min readAsked at Two Sigma, Citadel, QuantCo, DE Shaw

Assumes Trees: bagging, random forests and gradient boosting.

After this lesson you should be able to

  • Say what kNN assumes and why dimension destroys it.
  • Explain the margin and the kernel trick.
  • Distinguish generative from discriminative models.

Beyond trees and linear models, a handful of methods turn up in interviews because each embodies a distinct idea: kNN is pure locality, SVMs are about the margin, and naive Bayes is the generative alternative. Knowing what each assumes is the point, since that is what decides whether it fits your data.

1255000.511−0.9ᵈDimensionsFraction of the cube within 5 per cent of a face
Figure 3.1 · In high dimensions everything is on the edge. By twenty dimensions, seven points in eight are in the outer shell. Nearest-neighbour methods assume there is a neighbourhood; above a few dozen features there is not one, and every point is roughly the same distance from every other.

Proposition 3.2

KNN and its assumption

Predict from the kk nearest training points. The entire assumption is that similar inputs have similar outputs and that "similar" is captured by your distance metric — which is why scaling matters enormously and why an irrelevant feature actively damages the model by distorting every neighbourhood.

Holds when

  • Small kk means low bias and high variance; large kk smooths toward the global mean.
  • Standardise features, or the one with the largest units defines the distance.
  • It degrades fastest of any method as dimension grows, because everything becomes equidistant.

Definition 3.3

Support vector machines

Maximum margin, min⁡12∥w∥2  s.t.  yi(w⊤xi+b)≥1\min \tfrac{1}{2}\|w\|^2 \ \text{ s.t. } \ y_i(w^\top x_i + b) \ge 1 — Among all separating hyperplanes, choose the one furthest from the nearest points. Only those nearest points — the support vectors — determine the solution, so the model is sparse in the data rather than in the features. The soft-margin version adds slack variables so that some points may be misclassified, with a cost parameter controlling the trade.

The kernel trick. The SVM solution depends on the data only through inner products xi⊤xjx_i^\top x_j. So if you want to work in a high-dimensional feature space, you never need to construct it — you only need a function computing inner products in that space, which is the kernel. A polynomial kernel corresponds to all monomials up to some degree; the Gaussian kernel corresponds to an infinite-dimensional space. You get the expressiveness of that space at the cost of evaluating a scalar function, which is why the trick is called a trick.

The rest of this lesson is in Premium

You have read the opening. 10 more sections follow, including 5 worked examples and 3 quick checks.

Start the free 7-day trialSign in

Nothing is charged for 7 days, and you can cancel before then. Or read The law of large numbers and the central limit theorem in full, free.

Other supervised methods: kNN, SVMs and the kernel trick · QuantMax