# Uncertainty-Propagation Tree Acquisition

- ID: 1099
- Canonical URL: https://synthcore.org/idea/1099/uncertainty-propagation-tree-acquisition
- API JSON: https://synthcore.org/api/idea/1099.json
- API Markdown: https://synthcore.org/api/idea/1099.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.18089](https://arxiv.org/abs/2607.18089)
- Category: training
- Solves: sample-efficiency, accuracy, scalability
- ML areas: training, optimizer, curriculum
- Math tags: probability, statistics, information-theory, optimization
- Ratings: usefulness 7/10; difficulty 6/10; novelty 6/10

## Idea description

Replace greedy uncertainty sampling with a shallow Monte Carlo Tree Search that plans sequences of neural-network data acquisitions using a propagated uncertainty state. Each hypothetical query reduces uncertainty at nearby or correlated points, so later rewards automatically penalize redundant coverage and include labeling, simulation, or trajectory-transition costs.

## Mathematical statement

For a Gaussian-process model with kernel matrix K, training inputs X, observation-noise variance sigma_n^2, and query x, the posterior variance is v(x)=k(x,x)-k(x,X)[K(X,X)+sigma_n^2 I]^{-1}k(X,x). For a candidate acquisition a, let S(a) be its evaluation points and let v_t(z) be the current variance at evaluation point z. Define weighted integrated variance reduction R(a|v_t)=sum_z w_z[v_t(z)-v_{t+1}^a(z)], where w_z are nonnegative importance weights and v_{t+1}^a is the variance after hypothetically observing S(a). The tree objective is J(a_0,...,a_{H-1})=sum_h gamma^h[R(a_h|v_h)-lambda c(a_{h-1},a_h)], with horizon H, discount gamma, transition or acquisition cost c, and cost coefficient lambda. In a neural implementation, v_t(z) is estimated by an ensemble, Laplace approximation, or linearized neural tangent model; the essential transferable mechanism is propagation of the hypothetical uncertainty state through the search tree.

## Key formulas

- $$v(x)=k(x,x)-k(x,X)\left[K(X,X)+\sigma_n^2I\right]^{-1}k(X,x)$$
- $$R(a\mid v_t)=\sum_{z\in Z}w_z\left[v_t(z)-v_{t+1}^{a}(z)\right]$$
- $$J(a_{0:H-1})=\sum_{h=0}^{H-1}\gamma^h\left[R(a_h\mid v_h)-\lambda c(a_{h-1},a_h)\right]$$

## Implementation notes

Integrate this as an active-learning or data-collection controller around an existing neural predictor. Maintain an ensemble of M networks with identical architecture and different bootstrap samples or random seeds. For every unlabeled candidate batch or simulator trajectory a, evaluate its points S(a), and estimate predictive variance v_t(z) from the ensemble predictions. Build a shallow tree of depth H=2 or 3. At every node, score each candidate using the displayed discounted objective. To estimate v_{t+1}^a cheaply, use a Bayesian linear update on the final layer: compute feature vectors phi(z) from the shared network, update the final-layer covariance with the candidate features, and recompute predictive variance. A more faithful version performs one small gradient update per ensemble member on newly labeled observations and recalculates variance. Use 100-500 random rollouts with UCB child selection, execute only the first action of the best root path, acquire that batch, retrain, and repeat. Compute the weighted variance reduction and transition cost directly; estimate ensemble variance, hypothetical posterior updates, and candidate costs empirically. First experiment on CIFAR-10: start with 1,000 labels, create 20 candidate batches using uncertainty clustering, and compare random sampling, greedy ensemble-variance sampling, and MCTS with H=3. The prediction is that the second greedy batch becomes increasingly redundant, while MCTS improves cumulative weighted variance reduction per label by at least 10% when candidates overlap. The gain should disappear when candidate batches are statistically independent, confirming that propagated posterior state, rather than generic exploration, causes the improvement.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built an exact RBF-GP uncertainty-propagation acquisition prototype with depth-2 exhaustive tree planning, propagated hypothetical posterior variance, transition costs, parameter sweeps, and a random/greedy comparison. Variance non-increase was confirmed (maximum numerical increase -3.05e-9), and the cost-policy crossover matched the analytic prediction 0.55103 versus observed grid midpoint 0.55150. However, the redundancy sweep was not monotonic and the tree matched greedy exactly (cumulative reduction 0.7204 for both), so the proposed acquisition win was not demonstrated.

### Mechanism check

- Verdict: Built an exact RBF-GP uncertainty-propagation acquisition prototype with depth-2 exhaustive tree planning, propagated hypothetical posterior variance, transition costs, parameter sweeps, and a random/greedy comparison. Variance non-increase was confirmed (maximum numerical increase -3.05e-9), and the cost-policy crossover matched the analytic prediction 0.55103 versus observed grid midpoint 0.55150. However, the redundancy sweep was not monotonic and the tree matched greedy exactly (cumulative reduction 0.7204 for both), so the proposed acquisition win was not demonstrated.
- Confidence: 9/10
- Limitations: This is a small one-dimensional exact GP toy, not CIFAR-10 or a neural ensemble. It uses exhaustive depth-2 search rather than Monte Carlo rollouts/UCB, has synthetic spatial batches and costs, tests only three acquisition steps, and does not measure labeling time, FLOPs, calibration, predictive accuracy, or scalability.

## Artifacts

- [experiment.py](https://synthcore.org/code/438/experiment.py)
- [report.md](https://synthcore.org/code/438/report.md)
- [results.json](https://synthcore.org/code/438/results.json)
- [verify.py](https://synthcore.org/code/438/verify.py)
- [Download all files as ZIP](https://synthcore.org/download/438)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.