[Next] [Up] [Previous]
Next: Soundness of the Q-DAG Up: Generating Query DAGs Previous: Computational Complexity of Q-DAG

## Other Generation Algorithms

The polytree algorithm is a special case of the clustering algorithm as shown in [Shachter, Andersen, SzolovitsShachter et al.1994]. Therefore, the polytree algorithm can also be modified as suggested above to compute Q-DAGs. This also means that cutset conditioning can be easily modified to compute Q-DAGs: for each instantiation of the cutset , we compute a Q-DAG node for using the polytree algorithm and then take the -sum of the resulting nodes.

Most algorithms for exact inference in belief networks can be adapted to generate Q-DAGs. In general, an algorithm must satisfy a key condition to be adaptable for computing Q-DAGs as we suggested above. The condition is that the behavior of the algorithm should never depend on the specific evidence obtained, but should only depend on the variables about which evidence is collected. That is, whether variable is instantiated to value or value should not affect the complexity of the algorithm. Only whether variable is instantiated or not should matter.

Most belief networks algorithms that we are aware of satisfy this property. The reason for this seems to be the notion of probabilistic independence on which these algorithms are based. Specifically, what is read from the topology of a belief network is a relation , stating that variables and are independent given variables . That is,

for all instantiations of these variables. It is possible, however, for this not to hold for all instantiations of but only for specific ones. Most standard algorithms we are aware of do not take advantage of this instantiation-specific notion of independence.[+] Therefore, they cannot attach any computational significance to the specific value to which a variable is instantiated. This property of existing algorithms is what makes them easily adaptable to the generation of Q-DAGs.

[Next] [Up] [Previous]
Next: Soundness of the Q-DAG Up: Generating Query DAGs Previous: Computational Complexity of Q-DAG

Darwiche&Provan