classification
Classify with 30 labels and 30,000 unlabeled
It is the 2000s, and labels have become the bottleneck of machine learning: an expert must hand-annotate each one, and experts are slow and expensive, while raw unlabeled data pours in for free. You have thirty labeled points and thirty thousand unlabeled ones. The unlabeled data, though it carries no answers, reveals the shape — the manifold — on which the data lives, and that geometry can pin down the decision boundary far better than thirty labels ever could alone. Exploit it. Get it wrong and you either pay for thousands of labels you didn't need, or ignore the free geometric structure and learn a boundary that slices right through a natural cluster — in a labels-are-money world, the unlabeled cloud is the resource you cannot afford to waste.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
This problem is Niyogi's life's work stated as an exam question. With Belkin he created Laplacian eigenmaps (2001–03), showing that the eigenvectors of a graph Laplacian built on unlabeled points recover the data manifold's intrinsic geometry, with convergence results tying the graph Laplacian to the Laplace-Beltrami operator — the theorem that makes 'the unlabeled cloud reveals the manifold' a mathematical fact rather than a slogan. Manifold regularization (Belkin, Niyogi, Sindhwani, JMLR 2006) then delivered the exact algorithm this scenario calls for: kernel classifiers penalized by the Laplacian so the boundary respects geometry, with a representer theorem, using precisely a-handful-of-labels-plus-thousands-unlabeled experiments. He also studied when unlabeled data provably helps, keeping the claims honest. Era, scale, formulation, and guarantees all match. The problem's own win-list names him first, and the history agrees.
Schölkopf is close to the center of this problem's 2000s answer. He systematized kernel methods (Learning with Kernels, 2002), and his Tübingen group treated semi-supervised learning as a first-class research program: cluster kernels that reshape the feature space using unlabeled data (Chapelle, Weston, Schölkopf, 2002), transductive extensions of SVMs, and ultimately co-editing the field's defining book, Semi-Supervised Learning (Chapelle, Schölkopf, Zien, 2006), which organized the cluster assumption, the manifold assumption, and low-density separation into one framework. The RKHS view he championed is exactly the language in which manifold regularization is written — a Laplacian penalty added to a kernel machine. With thirty labels and thirty thousand unlabeled points he would build a data-dependent kernel and let the geometry do the work. Only the Laplacian eigenmaps line itself is more Niyogi's than 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.