...HREF=#figcn1#89>.

The sharing of subexpressions is what makes this a Directed Acyclic Graph instead of a tree.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...complexity,

Algorithms based on join trees have this property.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....

This is also useful in cases where a variable will be measured only if its value of information justifies that.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...areas.

In fact, it appears that a background in compiler theory may be more relevant to generating an efficient evaluator than a background in belief network theory.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...network;

A join tree is a tree of clusters that satisfies the following property: the intersection of any two clusters belongs to all clusters on the path connecting them.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...independence.

Some algorithms for two-level binary networks (BN20 networks), and some versions of the SPI algorithm do take advantage of these independences.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...pruning.

Note, however, that Q-DAG reduction will not reduce the computational complexity of generating a Q-DAG, although network pruning may. For example, a multiply-connected network may become singly-connected after pruning, thereby, reducing the complexity of generating a Q-DAG. But using Q-DAG reduction, we still have to generate a Q-DAG by working with a multiply-connected network.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....

This can be seen by considering the following expression, which is evaluated incrementally by the polytree algorithm through its message passes:

It is clear that the subexpression corresponding to the message from to is independent of the evidence on .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....

More precisely, they correspond to the expression .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...node.

Note that Q-DAGs lead to a very refined caching mechanism if the Q-DAG evaluator (1) caches the value of each Q-DAG node and (2) updates these cached values only when there is need to (that is, when the value of a parent node changes). Such a refined mechanism allows caching the values of messages that depend on evidence as well.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...factor.

We have shown how clustering and conditioning algorithms can be used for Q-DAG generation, but other algorithms such as SPI [Li D'AmbrosioLi D'Ambrosio1994, Shachter, D'Ambrosio, del FaveroShachter et al.1990] can be used as well.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.