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.
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.
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.
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).
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.
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.
It tries the 16 combinations with cross-validation and keeps the one that does best on what it has not seen.