To generate Q-DAGs using the clustering method, we have to go through two steps. First, we have to modify the initialization of potential functions so that the join tree is quantified using Q-DAG nodes instead of numeric probabilities. Second, we have to replace numeric addition and multiplication in the algorithm by analogous functions that operate on Q-DAG nodes. In particular:

- Numeric multiplication * is replaced by an operation that takes Q-DAG nodes as arguments, constructs and returns a new node with label and parents .
- Numeric addition + is replaced by an operation that takes Q-DAG nodes as arguments, constructs and returns a new node with label and parents .

Before we state the Q-DAG clustering algorithm, realize that we now do not have evidence , but instead we have a set of evidence variables for which we will collect evidence. Therefore, the Q-DAG algorithm will not compute an answer to a query , but instead will compute a Q-DAG node that evaluates to under the instantiation of variables .

In the following equations, potentials are mappings from variable instantiations to Q-DAG nodes (instead of numbers). For example, the matrix for variable will map each instantiation of 's family into a Q-DAG node instead of mapping it into the number . The Q-DAG operations and are extended to operate on these new potentials in the same way that and are extended in the clustering algorithm.

The new set of equations is:

- Potential functions are initialized using

where- is a variable whose matrix is assigned to cluster ;
- is the Q-DAG matrix for : a mapping from instantiations of 's family into Q-DAG nodes representing conditional probabilities;
- is an evidence variable whose matrix is assigned to cluster ; and
- is the Q-DAG likelihood vector of variable : , which means that node evaluates to 1 if is consistent with given evidence and 0 otherwise.

- Posterior distributions are computed using

where are the clusters adjacent to cluster . - Messages are computed using

where are the clusters adjacent to cluster . - The Q-DAG nodes for answering queries of the form
are computed using

where is a cluster to which belongs.

Hence, the only modifications we made to the clustering algorithm are (a) changing the initialization of potential functions and (b) replacing multiplication and addition with Q-DAG constructors of multiplication and addition nodes.

[Next] [Up] [Previous]