classification
The line between two clouds
It is the 1990s, and two point clouds sit in thirty-dimensional space, perfectly separable by a hyperplane — but infinitely many hyperplanes separate them, and all score zero errors on the data you have. Zero training error is not the goal; the goal is the future. Find the classifier that best guarantees low error on examples not yet seen, which means reasoning about the margin — the width of the buffer between the classes — rather than merely fitting the training points. The generalization guarantee is a theorem, not an empirical hope. Get it wrong and you ship a boundary that aces the test set and fails in the wild, while looking perfect on paper — fitting the past is trivial; the margin buys the future.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
This problem is essentially a restatement of Vapnik's life work. With Chervonenkis he built the theory of uniform convergence and VC dimension in the 1960s-70s, and by the early 1990s at Bell Labs he turned it into the support vector machine: among all separating hyperplanes, choose the one maximizing the margin, because the generalization bound depends on the margin-to-radius ratio rather than the raw dimension. The problem's insistence that the guarantee be a theorem, not an empirical hope, is precisely his structural risk minimization program — order hypothesis classes by capacity and pick the class the data can support. Thirty dimensions, separable clouds, 1990s setting: this is the exact regime in which the optimal-margin classifier of Boser, Guyon, and Vapnik (1992) was formulated. No one else on this list matches the problem this exactly.
Chervonenkis co-authored the 1971 theorem on uniform convergence of relative frequencies that makes this problem answerable at all: it says when zero training error can be trusted, as a function of the capacity of the hypothesis class, not the number of parameters. The VC dimension — half his name — is the quantity that lets you prove a distribution-free generalization bound for hyperplanes, and the growth-function machinery he and Vapnik developed is the engine under every margin bound of the 1990s. He worked in Moscow on pattern recognition from the 1960s onward, including applied geological prediction, so separable point clouds were his daily material. He scores just below Vapnik only because the specific margin-maximizing algorithm and its 1990s SVM form were carried further by his collaborator; the theorem the problem demands is his.
Fought here
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.