Text & documents
Numbers & maths
Data & formats
Security
Development & DevOps
Artificial Intelligence
Finance
Health & Wellness
Productivity
Games & Entertainment
Multimedia & design
Business
How to use
kNN: the neighbours vote

A point's class is the one that appears most among its k nearest neighbours. It learns nothing when training: it just keeps the data. With k = 1 it learns everything by heart, noise included (it gets 100 % of its own data right and quite a bit less outside); with a very large k, the boundary flattens until it tells nothing apart.

SVM: the widest margin

The support vector machine looks for the boundary that leaves the widest margin between the two classes. Only the points right on the margin decide it: the support vectors (circled in the drawing). C says how much it penalises points on the wrong side: with a small C it forgives a lot and the margin is wide; with a large C, it bends so as not to miss any.

The kernel trick

A straight boundary cannot separate two rings. The kernel changes how the similarity between two points is measured, and with that the SVM draws curved boundaries without computing any new feature. The polynomial one measures (x·y/4 + 1)^degree; the RBF, exp(−γ·distance²): with a large γ each point only resembles very close ones (a very wiggly boundary); with a small γ, almost all of them (an almost straight boundary).

Cross-validation and curves

Accuracy on the training data is misleading: k = 1 always gets 100 %. 5-fold cross-validation splits the data into 5 chunks, trains on 4 and measures on the remaining one, 5 times. The validation curve shows training and validation as a hyperparameter moves: where they part, it overfits. The learning curve, as data is added: if both meet low down, the model lacks capacity; if a gap remains between them, it lacks data.

How much can it learn? VC dimension and PAC

In the How much can it learn? view: the VC dimension of a family of classifiers is the largest number of points that, well placed, it separates with ANY labelling (it «shatters» them). A line in the plane: 3 (with 4 some labelling always fails, like the XOR one). The larger it is, the more it can learn… and memorise. PAC («probably approximately correct»): how many examples guarantee that the error exceeds ε at most in a fraction δ of the times. For a rectangle, m ≥ (4/ε)·ln(4/δ); the simulation shows that the bound is pessimistic but holds.

ClassifierskNN, SVM and kernels with cross-validation
ClassifierskNN, SVM and kernels with cross-validation

How many ways can it separate? The VC dimension

Place n points and look at the 2ⁿ possible labellings (blue: positive; orange: negative). If the family separates ALL of them, that placement is «shattered». The VC dimension is the largest n for which some placement manages it: it measures how much the family can learn (and memorise).

This labelling can be separated (the blue area is what the classifier takes as positive).

It separates all 8 labellings: this placement of 3 points is shattered.The VC dimension of this family is 3.

How many examples are needed? PAC learning

A rectangle (green) has to be learnt from m random points. The learner keeps the tightest box around the positives (blue); its error is the green area left outside. PAC promises: with m ≥ (4/ε)·ln(4/δ) examples, the error exceeds ε at most in a fraction δ of the times.

In this trial the error is 0.099 (does not exceed ε).

Of 300 trials with m = 50, the error exceeds ε in 18.7 % (the promise with δ = 0.10: at most 10 %).

δbound102050100200400800100 %0

The bound is pessimistic on purpose: it holds for any rectangle and any way of spreading the points. In practice far fewer examples are enough, but the bound GUARANTEES it.

● class A▲ class B✕ misclassified

Grid search: C × γ (SVM with RBF)

It tries the 16 combinations with cross-validation and keeps the one that does best on what it has not seen.