Two Procedures for Compiling Influence Diagrams

Paul E. Lehner, Azar SadighUAI 1993

TL;DR

This paper introduces two algorithms for compiling complex Bayesian decision networks (influence diagrams) into simpler, human-executable decision rules. This compilation is crucial for applying these powerful reasoning systems to time-constrained, real-world problems where human decision-makers need clear, actionable guidance.

What Problem Does This Paper Address?

Modern decision-making, especially in fields like command and control, often involves complex scenarios with uncertain information and tight deadlines. Bayesian decision theory offers a robust framework for handling such uncertainty by constructing "influence diagrams" (or decision networks) that model probabilities and utilities. However, directly executing these networks can be computationally prohibitive, especially under time pressure. Furthermore, delegating life-or-death decisions entirely to machines is often undesirable. The challenge, therefore, is to bridge the gap between the theoretical power of influence diagrams and the practical need for rapid, human-understandable decision procedures. This paper tackles this by developing methods to "compile" these complex networks into simple, step-by-step decision rules that humans can readily follow.

Methods

The core contribution lies in the development of two algorithms for compiling influence diagrams into "default trees" (Dtrees). A Dtree represents a decision procedure as a tree structure where nodes are either decisions or evidence items to be examined.

  • Default Trees (Dtrees): These trees are composed of decision nodes (Dnodes) and evidence nodes (Enodes). Each Enode specifies an evidence item to check and a decision to make if that evidence is observed. The goal is to create a Dtree that "DT-compiles" a decision network, meaning every possible evidence state leads to a decision node.
  • Algorithm DD (Greedy Expansion): This algorithm iteratively builds a Dtree by selecting the open decision node that, when expanded with a new evidence item, yields the greatest increase in the expected utility of the Dtree. It's a greedy approach, focusing on the locally optimal expansion at each step.
  • Algorithm DDn (n-step Greedy Expansion): This is an extension of Algorithm DD that looks ahead up to 'n' steps to find the expansion subtree that maximizes the average increase in expected utility. This allows for a more conservative approach, considering longer-term consequences of decisions.

The paper also introduces concepts like "evoiDT" (increase in expected utility from examining an evidence item) and "eu-expandDT" (increase in expected utility from expanding a node) to guide the greedy selection process.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Theory and Practice: The paper highlights the critical need to translate computationally intensive theoretical models (influence diagrams) into practical, human-executable procedures.
  • Greedy Optimality: While not guaranteeing global optimality, the greedy expansion algorithms (DD and DDn) offer a practical way to derive near-optimal decision procedures. The intuition is that focusing on the immediate best expansion is often a good heuristic.
  • E-descending Constraint: The concept of "E-descending" trees is introduced as a condition that helps characterize the optimality properties of the generated Dtrees. Violations of this constraint are considered unlikely and typically involve only short evidence chains.
  • Adaptability: The Dtree formulation inherently supports adaptation to time and workload constraints. If time runs out, a default decision can be made, or the procedure can be adapted to prioritize time-sensitive evidence.

Key Results

The paper presents two algorithms (DD and DDn) for compiling influence diagrams into Dtrees. While not guaranteeing global optimality, these algorithms are shown to produce locally optimal expansions. Algorithm DDn offers a way to control the conservativeness of the compilation process by looking 'n' steps ahead. The paper theoretically analyzes the properties of these algorithms, suggesting that they are effective in generating human-executable, near-optimal decision procedures.

Limitations and Future Work

  • Global Optimality: The authors acknowledge that their greedy algorithms do not guarantee global optimality. They note that while Dtrees converge to the same value, greedy expansions might be redundant and not always lead to the absolute best outcome.
  • Dtree Size: An open empirical question is the expected size of a near-optimal Dtree.
  • Time-Varying Information Value: The current formulation doesn't account for situations where the value of information changes over time.
  • Adaptive Decision Making: The paper suggests that while Dtrees handle time stress well, they need further development to adapt to other types of problems, such as sensor failures.
  • Team Allocation: A significant future direction is partitioning the derived Dtrees into decision procedures that can be allocated to different team members.

Summary updated

BibTeX
@inproceedings{lehner1993two,
  author = {Paul E. Lehner and Azar Sadigh},
  title = {{Two Procedures for Compiling Influence Diagrams}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1993},
}
Figure