Learning to Acquire Information

Yewen Pu, Leslie Pack Kaelbling, Armando Solar-Lezama

Introduction

Active diagnosis—the process of selecting a sequence of informative observations to identify a hidden state—is a fundamental challenge in fields ranging from medical diagnostics to network troubleshooting. Traditionally, the optimal strategy involves maximizing Information Gain. However, this approach is often computationally prohibitive because it requires a search through the entire hypothesis space. For instance, in a network with $M$ links, there are $2^M$ possible failure configurations, making real-time calculation impossible for large-scale systems.

This paper introduces a novel framework that bypasses the hypothesis space entirely. Instead of modeling the relationship between observations and hidden states, the authors propose an "implication model" that learns the statistical dependencies between observations themselves.

The Implication Model

The core of this approach is the Uniform Observation Entropy (UOE) assumption. The researchers demonstrate that if every observation is assumed to be equally noisy given a specific hypothesis, the most informative next observation is simply the one with the maximum entropy conditioned on previous results. In other words, the best question to ask is the one the model is most uncertain about.

To implement this, the authors utilize a neural network architecture trained as a sparsifying auto-encoder. The network takes a vector of past observations as input (with unobserved values marked as unknown) and predicts the probabilities of missing values.

The Implication Model architecture uses a feed-forward neural network to predict the probabilities of unobserved values based on a sparse set of past observations.

At runtime, the agent selects the test where the network's output probability is closest to a 50/50 split, representing maximum entropy. This "Confused Oracle" approach allows the system to identify highly informative tests without ever explicitly considering the underlying hypothesis.

Experimental Evaluation

The proposed method was evaluated across three distinct domains:

  1. Battleship: A 10x10 grid game where the agent must locate ships within a hypothesis space of approximately $2^{38}$ configurations.
  2. Sushi Preference: A real-world dataset where the model infers a user's full ranking of 10 sushi types through pairwise comparisons.
  3. Network Fault Localization: A simulated 100-node tree network where the agent uses connectivity queries to identify broken links.

Key Results and Discussion

The implication model demonstrated significant efficiency and accuracy gains across all benchmarks. In the Sushi task, the model required only 26 queries to infer full rankings, compared to 40 for standard algorithms like QuickSort. In the network task, it achieved 99.5% accuracy with just 60 observations by leveraging complex path dependencies.

Performance comparison on the Battleship task shows that the Observation Collection (OC) models reach perfect board reconstruction significantly faster than random sampling or the heuristic 'sink' algorithm.

As shown in the Battleship results, the "OC" (Observation Collection) models outperformed both random and heuristic baselines. Furthermore, the model proved robust to noise, maintaining high accuracy even with a 10% observation error rate. A major advantage of this approach is its ability to learn from unlabeled data; since the model only predicts observations from other observations, it can be trained on raw data traces without needing ground truth labels for the underlying hypotheses.

Conclusion

By shifting the focus from hypothesis modeling to observation implications, this framework provides a scalable and efficient solution for active diagnosis. While the current implementation focuses on discrete observations and relies on the UOE assumption, it opens new avenues for learning information acquisition strategies in complex, high-dimensional domains.

Summary updated

BibTeX
@inproceedings{pu2017learning,
  author = {Yewen Pu and Leslie Pack Kaelbling and Armando Solar-Lezama},
  title = {{Learning to Acquire Information}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=Y8KTl5KM2jx},
}
Figure