Algorithms and Applications for the Same-Decision Probability

Suming Jeremiah Chen, Arthur Choi, Adnan DarwicheJAIR 2014 · DOI

TL;DR

This paper introduces the Same-Decision Probability (SDP) as a novel criterion for deciding when to stop gathering information and which information to gather next in decision-making under uncertainty. They propose the first exact algorithm for computing SDP, demonstrating its effectiveness and providing new complexity results, including its NP-hardness for Naive Bayes networks.

What Problem Does This Paper Address?

When making decisions with incomplete information, two critical questions arise: when is it sufficient to commit to a decision (stopping criterion), and if more information is needed, what is the most valuable piece of information to acquire next (selection criterion)? Traditional methods often rely on thresholds or value of information (VOI) measures, but these can sometimes lead to decisions that are not robust to further evidence. The authors address this by proposing and evaluating the Same-Decision Probability (SDP) as a more robust measure of decision confidence.

Methods

The paper introduces and applies the Same-Decision Probability (SDP) as both a stopping and selection criterion.

  • SDP as a Stopping Criterion: A high SDP indicates that the current decision is likely to remain the same even with further observations, suggesting it's safe to stop gathering information. A low SDP suggests the decision is unstable and might change, warranting further investigation.
  • SDP as a Selection Criterion: The authors propose using the SDP gain as a reward function for selecting the next piece of information to observe. This aims to maximize the stability of the decision, rather than just reducing uncertainty or maximizing expected utility.
  • Exact SDP Computation Algorithm: The core technical contribution is the development of the first exact algorithm for computing SDP. This algorithm is generalized from Naive Bayes networks to arbitrary Bayesian networks by leveraging network partitioning and variable elimination techniques. The algorithm uses a search tree with pruning based on lower and upper bounds of evidence weights to efficiently compute the SDP.
  • Complexity Analysis: The paper establishes new complexity results, proving that computing SDP in Naive Bayes networks is NP-hard and that the general SDP computation problem belongs to the PPPP-complete complexity class, similar to non-myopic value of information.

Datasets

The paper evaluates their algorithm on:

  • Real Networks: Datasets from the UCI Machine Learning Repository, HRL Laboratories, and CRESST were used. These were primarily diagnostic networks.
  • Synthetic Networks: Networks with 100 variables and varying treewidth were generated using BNGenerator.

Key Insights and Ideas

  • SDP for Robustness: The SDP provides a measure of decision robustness that goes beyond traditional criteria like simple threshold crossing or entropy reduction. It directly quantifies the probability that the decision will not change with more information.
  • Distinguishing Stable vs. Unstable Decisions: SDP can differentiate between scenarios that appear similar under classical criteria but have vastly different levels of decision stability.
  • Myopic vs. Non-Myopic Selection: While traditional VOI often uses a myopic approach (selecting the best single observation at each step), the SDP gain criterion aims for a more stable decision overall, potentially leading to different selection choices.
  • Computational Hardness: The paper highlights the inherent difficulty of computing SDP, showing it's NP-hard even for simple Naive Bayes structures, underscoring the need for efficient algorithms.

Key Results

  • Algorithm Performance: The proposed exact algorithm for computing SDP significantly outperforms naive brute-force methods and a previously proposed approximate algorithm, especially on larger and more complex networks. It can solve many SDP problems that are out of reach for existing methods.
  • Speedup: The algorithm demonstrates comparable running times to the approximate algorithm and is much faster than the naive brute-force approach. The performance improves with network decomposability (larger partition size 'k').
  • Complexity Results: Computing SDP in Naive Bayes networks is proven to be NP-hard. The general SDP computation problem is shown to be PPPP-complete, placing it in the same class as other complex expectation computation problems like non-myopic VOI.

Limitations and Future Work

  • Computational Intractability: While the proposed algorithm is efficient, SDP computation remains computationally challenging, especially for very large or highly connected networks. The complexity is exponential in treewidth.
  • Generalization to Utility-based Decisions: The paper extends the SDP definition to a generalized setting for utility-based decisions and influence diagrams, suggesting its applicability beyond simple threshold-based decisions.
  • Further Complexity Investigations: The paper suggests that the PPPP-completeness of SDP and related expectation problems warrants further research into efficient algorithms for this class of problems.
  • Non-myopic VOI: The paper connects SDP computation to non-myopic VOI, indicating that advancements in SDP algorithms could benefit the broader field of optimal information gathering.

Summary updated

BibTeX
@article{chen2014algorithms,
  author = {Suming Jeremiah Chen and Arthur Choi and Adnan Darwiche},
  title = {{Algorithms and Applications for the Same-Decision Probability}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4218},
}
Figure