[Next] [Up] [Previous]

Generating Query DAGs

 

This section shows how Q-DAGs can be generated using traditional algorithms for exact belief-network inference. In particular, we will show how Q-DAGs can be generated using the clustering (join tree, Jensen, LS) algorithm [Jensen, Lauritzen, OlesenJensen et al.1990, Shachter, Andersen, SzolovitsShachter et al.1994, Shenoy ShaferShenoy \ Shafer1986], the polytree algorithm, and cutset conditioning [PearlPearl1988, Peot ShachterPeot Shachter1991]. We will also outline properties that must be satisfied by other belief network algorithms in order to adapt them for generating Q-DAGs as we propose.

 
• The Clustering Algorithm
• Generating Q-DAGs
• An Example
• Computational Complexity of Q-DAG Generation
• Other Generation Algorithms
• Soundness of the Q-DAG Clustering Algorithm