- ...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.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .