Science1 publisher2 min readPublished Updated
Bristol mathematicians prove random yes-or-no questions can sort millions of classes
Each classifier answers one randomly chosen question and trains in minutes on a laptop; the Bristol team says enough of them can pick one item out of millions, with no coordination between them.
The Scientist · Science desk
What happened
- The method, taken from the childhood game of 20 Questions, chains classifiers that each answer one yes-or-no question and each train in a matter of minutes on a standard laptop.
- The team says it has a mathematical proof, backed by empirical validation, that questions chosen at random can be combined to handle a complex classification task.
- The release puts the conventional alternative at classification models that need tens of thousands of graphics processing units to train, at a cost of millions of dollars.
- The team aims the scheme at systems spread over several devices and at smart devices such as sensors and robots that process data close to where it is generated.
Compiled by The ScientistSomething wrong?How this is made
Why it matters
- capability Because no classifier waits on another's answer, a handful of wrong answers can be absorbed, so classification becomes possible on hardware that fails intermittently or loses contact with a central model.
- cost If the training bill per question is minutes of laptop time, a group with no GPU allocation can build a multiclass classifier itself, and the saving lands on whoever trains rather than whoever buys the cluster.
- constraint The public account gives no accuracy number, no dataset and no classifier count, so a team cannot yet weigh this against a small conventional classifier trained on its own data. For now the compute-floor argument stays theoretical.
Twenty yes-or-no answers separate 1,048,576 possibilities, which is 2 to the 20th power [14]. Sidharth Jaggi's example is a walker who spots an unfamiliar plant and points a phone at it, and he said the classifier behind such an app would likely be designed to carefully separate millions, if not billions, of different types of objects from each other [6]. Separating a billion takes at least 30 questions: 2 to the 29th falls short of a billion, and 2 to the 30th clears it [15]. Perfectly chosen questions are the floor. Random ones cost more, and how much more is what the paper, titled "Fundamental limits of distributed multiclass classification from simple binary decisions," sets out to bound [1].
"The key observation is that no complex coordination of the simple binary classifiers is required. There just need to be enough of them, and that number is surprisingly small," Jaggi said [8]. No coordination means no shared taxonomy across the classifiers: each one is trained on its own random question, and none of them has to be designed with reference to the others [7].
The cost comparison in the release is a training comparison. On one side, tens of thousands of graphics processing units and millions of dollars [5]; on the other, a binary classifier that trains in minutes on a standard laptop [3]. At inference the device has to evaluate every question it asks, so the running cost tracks the number of classifiers. That count is the figure an engineer would size a deployment on. Jaggi said the resulting algorithms have a far lower computational cost, are more robust and are easier to deploy at scale [17].
"Each individual classifier only needs to answer one of these simple questions, but together they can identify from millions of possibilities," said Ioannis Papageorgiou, the lead author, who did the work as a senior research associate at Bristol [11][12]. The work sits in Bristol's Informed AI research hub, which covers mathematics, information theory and AI safety [16], and the paper is an arXiv preprint, presented on Sept. 16 at the Allerton Conference on Communication, Control and Computing in Illinois [1][2].
What to watch
- The arXiv paper's own figures: how many binary classifiers for how many classes, and at what error rate.
- An independent reproduction that puts the random-question ensemble against a small conventional multiclass classifier on the same data.
- Whether the Allerton preprint clears peer review with the bound intact.