[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). Figure: A join tree quantified with numbers (a), and with Q-DAG nodes (b).

We have only one evidence variable in this example, . And we are interested in generating a Q-DAG for answering queries about variable , that is, queries of the form . 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 , we must compute the posterior distribution over cluster since this is a cluster to which variable belongs. We can then sum the distribution over variable to obtain what we want. To compute the distribution we must first compute the message from cluster to cluster .

The message is computed by summing the potential function of cluster over all possible values of variable , i.e., which leads to:  The posterior distribution over cluster , , is computed using which leads to The Q-DAG node for answering queries of the form is computed by summing the posterior over variable , leading to 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 and the other will evaluate to under any instantiation of evidence variables .

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

Darwiche&Provan