Introduction
In the field of Model-Based Diagnosis (MBD), identifying the root cause of a system failure involves comparing observed behavior against a formal model. When multiple explanations—or "diagnoses"—are possible, additional measurements are required to isolate the actual fault. Because computing the full set of diagnoses is often intractable, practitioners typically rely on sampling. For decades, the "best-first" strategy, which selects the $k$ most probable diagnoses, has been the standard. However, this approach introduces significant statistical bias. This paper investigates whether this "statistical sin" actually hinders diagnostic performance or if it serves as a necessary practical heuristic.
Methodology and Datasets
The study compares six sampling strategies: exact Best-First (bf), exact Random (rd), exact Worst-First (wf), and their approximate counterparts (abf, ard, awf) generated via the Inv-HS-Tree algorithm. These strategies were evaluated on two fronts: Theoretical Representativeness (T-Rep), measuring how well samples estimate population parameters like probability and elimination rate, and Practical Representativeness (P-Rep), measuring real-world diagnostic efficiency.
The evaluation utilized eight real-world knowledge-base (KB) debugging problems, ranging from small university models to large-scale datasets like DBpedia. These KBs were chosen because their complete sets of minimal diagnoses could be precomputed, allowing for a rigorous comparison between samples and the true population.
Key Insights: Probability vs. Elimination
The research reveals a nuanced trade-off between different sampling goals.
The Probability Mass Effect: Contrary to what basic statistics might suggest, "best-first" sampling is superior at estimating the probability of measurement outcomes. In many real-world systems, a small number of diagnoses hold the vast majority of the total probability mass. By capturing these "heavy hitters," best-first sampling provides a more accurate picture of likely outcomes than a uniform random sample.
The Elimination Advantage: Conversely, random sampling is significantly more effective at estimating the elimination rate—the number of diagnoses a measurement is expected to rule out. If the primary goal is to prune the search space as quickly as possible, regardless of the likelihood of the diagnoses being removed, unbiased random sampling is the superior choice.
Performance and Heuristics
The effectiveness of a sampling strategy is heavily dependent on the selection heuristic used to choose the next measurement. For standard information-gain heuristics like ENT (Entropy), best-first sampling performs excellently. However, for heuristics like MPS (Most Probable Singleton), best-first can be disastrous, sometimes doubling the required number of measurements compared to random sampling.
Key Results and Conclusion
The empirical results suggest several practical guidelines for MBD:
- Sample Size Matters: For small samples ($k < 10$), best-first (bf) is generally the most efficient strategy for minimizing measurements. As the sample size grows ($k \ge 20$), random sampling (rd) becomes more robust.
- Efficiency via Approximation: When accounting for total computation time, approximate methods like ard (approximate random) and abf (approximate best-first) often outperform exact methods by providing high-quality samples at a fraction of the computational cost.
- The "Worst" Baseline: Worst-first sampling consistently underperformed, validating that focusing on unlikely faults is a poor diagnostic strategy.
While "best-first" sampling remains a powerful tool due to the skewed probability distributions of real-world faults, this study highlights that it is not a universal solution. The choice between random and best-first sampling should be driven by the specific diagnostic heuristic and the computational constraints of the system. Future research will explore these dynamics in multi-valued measurement scenarios and non-minimal diagnosis sets.
Summary updated