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

An Example

We now show how the proposed Q-DAG algorithm can be used to generate a Q-DAG for the belief network in Figure 4(a).

 figure236
Figure: A join tree quantified with numbers (a), and with Q-DAG nodes (b).  

We have only one evidence variable in this example, tex2html_wrap1014. And we are interested in generating a Q-DAG for answering queries about variable tex2html_wrap1015, that is, queries of the form tex2html_wrap1518. Figure [*](a) shows the join tree for the belief network in Figure 4(a), where the tables contain the potential functions needed for the probabilistic clustering algorithm. Figure [*](b) shows the join tree again, but the tables contain the potential functions needed by the Q-DAG clustering algorithm. Note that the tables are filled with Q-DAGs instead of numbers.

We now apply the Q-DAG algorithm. To compute the Q-DAG nodes that will evaluate to tex2html_wrap1518, we must compute the posterior distribution tex2html_wrap1520 over cluster tex2html_wrap1521 since this is a cluster to which variable tex2html_wrap1015 belongs. We can then sum the distribution over variable tex2html_wrap1256 to obtain what we want. To compute the distribution tex2html_wrap1520 we must first compute the message tex2html_wrap1525 from cluster tex2html_wrap1526 to cluster tex2html_wrap1521.

The message tex2html_wrap1525 is computed by summing the potential function tex2html_wrap1529 of cluster tex2html_wrap1526 over all possible values of variable tex2html_wrap1014, i.e., tex2html_wrap1532 which leads to:
displaymath1574


displaymath1575

The posterior distribution over cluster tex2html_wrap1521, tex2html_wrap1520, is computed using tex2html_wrap1535 which leads to
eqnarray251

The Q-DAG node tex2html_wrap1536 for answering queries of the form tex2html_wrap1518 is computed by summing the posterior tex2html_wrap1520 over variable tex2html_wrap1256, tex2html_wrap1540 leading to
eqnarray254
which is the Q-DAG depicted in Figure 4(b). Therefore, the result of applying the algorithm is two Q-DAG nodes, one will evaluate to tex2html_wrap1541 and the other will evaluate to tex2html_wrap1542 under any instantiation tex2html_wrap1049 of evidence variables tex2html_wrap1048.


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

Darwiche&Provan