classification
Which examples deserve labels?
It is the same labels-are-expensive world, but now you hold the pen: you may choose which thirty of the thirty thousand points get sent to the expert for labeling, and you may choose them adaptively, each new label informing the next request. A point deep inside a cluster teaches you little; a point near the uncertain boundary can be worth dozens of random ones. Design the querying strategy and prove it beats labeling thirty points at random. The guarantee must be provable, not merely plausible. Get it wrong and you spend your tiny, precious label budget on redundant points and learn no faster than blind sampling — when every label costs an expert's hour, choosing the right questions is the entire game, and 'provably better than random' is the bar.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
The problem's bar — 'provably better than random, in a labels-are-money world' — is stated in Valiant's language. PAC learning (1984) is exactly a theory of label cost: sample complexity measures how many labeled examples learning requires, and Valiant's framework is what makes 'beats random sampling' a theorem rather than a slogan. His original paper already went further than passive sampling, endowing learners with oracles including membership queries — the learner asks for the label of a point it chooses — which is this problem's mechanism, formalized at birth; Angluin's query-learning theory and the 1990s-2000s active learning results (query-by-committee's exponential savings, disagreement-based bounds) are all built on his foundations and measured in his currency. He is not the author of the specific 2000s algorithms, but every proof the problem demands lives inside his framework. Top carrier.
Mitchell owns the formal object this problem's entire literature is built on: the version space (1977-1982) — the set of hypotheses consistent with the labels seen so far — and his candidate-elimination analysis showed that the most informative next example is the one that splits the version space, ideally in half. That is the theory of query selection, stated before almost anyone: generalization-as-search makes 'this label is worth dozens of others' a precise claim about how many hypotheses each answer eliminates, and 2000s active learning (query-by-committee, Tong-Koller) explicitly measures query value in version-space volume — his currency. His NELL system (2010) then ran the choose-your-own-supervision loop at web scale. Honest caveat: his original framework was logical and noise-free, and the probabilistic label-complexity theorems came from others. Still, the problem is his idea, industrialized. Top-tier.
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.