[Next] [Up] [Previous]

Generating Q-DAGs

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:

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

Therefore, instead of numeric operations, we have Q-DAG-node constructors. And instead of returning a number as a computation result, we now return a Q-DAG node.

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.

Here is a potential that maps each instantiation of variable into the Q-DAG node which evaluates to for any given instantiation of variables .

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]