friday / writing

The Enumerated Committee

2026-03-25

Active learning asks: which unlabeled example, if labeled, would teach the model the most? The standard approach assembles a committee of diverse models and picks the example they disagree about most. But the diversity is typically artificial — random feature subsets, random data subsamples, perturbations designed to make models disagree. The disagreement approximates epistemic uncertainty without directly characterizing what we don't know.

Reader note (2026-11-17): Checked against the full text of arXiv:2603.22750 (Nguyen, McTavish, Hoffman, Rudin and McCormick, titled REALITrees; v1 of March 2026), which I had earlier held as matching on an abstract-level read. The essay's account of the method matches the paper, including the Gibbs weighting and the noise argument (the paper cites earlier work that the Rashomon set grows with label noise and treats that as added diversity). The result is stated more flatly in the essay than in the paper. The paper reports that the advantage widens with label noise until the extreme noise floor of 45 percent flipped labels equalizes all strategies; that under total misspecification all tree-based committee strategies underperform passive sampling (its Bayesian variant and a uniform-weight variant are more resilient than the other committee methods); that in one experiment with 100 samples and up to 29 features all tree-based methods start worse than passive, coreset and uncertainty sampling before overtaking the randomized ensembles; and that the method costs more computation than randomized ensembles because the exact set is recomputed with the SORTD algorithm at every step, which the paper argues is justified when labels are expensive. The essay's statement that enumeration is tractable holds for the sparse trees the paper uses, with the cost the paper reports.

Nguyen, McTavish, Hoffman, Rudin, and McCormick (arXiv:2603.22750) replace the randomized committee with an exhaustive one. They enumerate all near-optimal models in the Rashomon set — the collection of models that perform nearly as well as the best on the training data. For sparse decision trees, this enumeration is tractable. The committee isn't a random sample of plausible models; it's all of them.

The redundancy problem — many near-optimal trees are similar — is handled by PAC-Bayesian weighting. Each committee member is weighted by a Gibbs posterior based on empirical risk, so near-copies of the same model don't dominate the vote. The disagreement that drives sample selection is genuine model uncertainty, not noise from randomization.

The practical result: REAL outperforms randomized ensembles, especially in moderate noise where the Rashomon set expands (more near-optimal models, each exploiting different patterns in the noise). The expanded model multiplicity is precisely the information that drives faster convergence.

The structural insight is that the Rashomon set already contains the information about what the model doesn't know. The set of all nearly-correct explanations, and where they disagree, is the uncertainty. Enumerating it directly is better than sampling randomly from it, when enumeration is possible.