Learning to Acquire Information

Yewen Pu, Leslie Pack Kaelbling, Armando Solar-Lezama

Abstract

Active diagnosis involves selecting the most informative queries to identify a hidden state, a task often hindered by computationally intractable hypothesis spaces. We present a method that bypasses the hypothesis space by leveraging a "uniform observation entropy" assumption. By training a neural network to model the relationships between observations directly, we can efficiently select queries that maximize information gain. Our approach is evaluated on Battleship, preference ranking, and network fault localization, demonstrating superior performance and robustness compared to standard heuristics and random sampling.

Introduction

Active diagnosis—the process of choosing the most informative next question to uncover a hidden state—is a fundamental challenge in fields ranging from medical diagnostics to network troubleshooting. Traditionally, this requires computing information gain over a hypothesis space that is often massive and computationally intractable. For instance, in a game of Battleship, there are up to $2^{38}$ possible board configurations, making it impossible to evaluate every potential query in real-time.

This paper introduces a novel framework that bypasses the hypothesis space entirely. By assuming "uniform observation entropy" (UOE), we prove that maximizing mutual information is equivalent to maximizing the conditional entropy of the next observation. This allows an agent to select queries based solely on the relationships between observations, modeled by a neural network.

Methodology

The core of our approach is the decoupling of Observation Collection (OC) from Hypothesis Delivery.

The Implication Model

Instead of modeling the hidden state, we train an "implication model"—a neural network designed to predict the probability of unseen observations given a set of past observations, $P(O' | O^-)$. This model is trained using input sparsification, similar to a denoising autoencoder. During training, the network receives a complete set of observations with a random subset masked as unknown. It learns to reconstruct the full set, thereby capturing the underlying dependencies between different queries.

Active Selection

During execution, the agent uses the implication model to evaluate all available queries. It greedily selects the query for which the model is most uncertain (i.e., the prediction is closest to 0.5). This process continues until a query budget is reached, at which point a separate algorithm delivers the final hypothesis.

The progression of active diagnosis on a Battleship board, showing how the model's belief (heatmap) and selected observations (dots) evolve over time.

Results

We evaluated our method on three benchmarks: Battleship, Sushi preference ranking, and network fault localization.

In the Battleship task, our OC algorithm significantly outperformed random sampling and standard heuristics. As shown in the performance curves, the OC variants (oc_0, oc_1, oc_cnn) achieve a higher fraction of correct guesses with fewer observations than the "sink" heuristic or random selection.

Performance comparison of different observation collection strategies on the Battleship task.

In the Sushi dataset, the model learned to infer a user's full ranking in just 26 pairwise queries, compared to 40 for QuickSort. By leveraging learned preference distributions, it achieved significant predictive power even before the first query. In Network fault localization, the algorithm reached 99.5% accuracy within 60 observations, effectively utilizing the network's structural dependencies.

Discussion

The primary insight of this work is that one does not need to know what they are looking for to know which question to ask. By modeling implications between observations directly, we reduce computational complexity and enable training on unlabeled data.

However, the approach relies on the UOE assumption, which may not hold if sensors have non-uniform noise profiles. Additionally, while the greedy strategy is efficient, it may be sub-optimal in complex scenarios where multiple hidden states interact. Future work will explore training the implication model on the specific observation traces generated during active collection to further specialize its performance.

Summary updated

Abstract

We consider the problem of diagnosis where a set of simple observations are used to infer a potentially complex hidden hypothesis. Finding the optimal subset of observations is intractable in general, thus we focus on the problem of active diagnosis, where the agent selects the next most-informative observation based on the results of previous observations. We show that under the assumption of uniform observation entropy, one can build an implication model which directly predicts the outcome of the potential next observation conditioned on the results of past observations, and selects the observation with the maximum entropy. This approach enjoys reduced computation complexity by bypassing the complicated hypothesis space, and can be trained on observation data alone, learning how to query without knowledge of the hidden hypothesis.
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