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.
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.
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