[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 tex2html_wrap1598 of the cutset tex2html_wrap1014, we compute a Q-DAG node for tex2html_wrap1600 using the polytree algorithm and then take the tex2html_wrap1409-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 tex2html_wrap1048 is instantiated to value tex2html_wrap1603 or value tex2html_wrap1604 should not affect the complexity of the algorithm. Only whether variable tex2html_wrap1048 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 tex2html_wrap1606, stating that variables tex2html_wrap1335 and tex2html_wrap1608 are independent given variables tex2html_wrap1609. That is,
displaymath1626
for all instantiations tex2html_wrap1610 of these variables. It is possible, however, for this not to hold for all instantiations of tex2html_wrap1611 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