...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:
displaymath1700
It is clear that the subexpression corresponding to the message tex2html_wrap1672 from tex2html_wrap1256 to tex2html_wrap1015 is independent of the evidence on tex2html_wrap1015.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....
More precisely, they correspond to the expression tex2html_wrap1682.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Darwiche&Provan