A Q-DAG evaluator can be implemented using an event-driven, forward propagation scheme. Whenever the value of a Q-DAG node changes, one updates the value of its children, and so on, until no possible update of values is possible. Another way to implement an evaluator is using a backward propagation scheme where one starts from a query node and updates its value by updating the values of its parent nodes. The specifics of the application will typically determine which method (or combination) will be more appropriate.

It is important that we stress the level of refinement enjoyed by the Q-DAG
propagation scheme and the implications of this on the efficiency of query updates.
Propagation in Q-DAGs is done at the arithmetic-operation level, which is
contrasted with propagation at the message-operation level (used by many
standard algorithms). Such propagation schemes are typically optimized by keeping
validity flags of messages so that only invalid messages are recomputed when new
evidence arrives. This will clearly avoid some unnecessary computations but can never
avoid all unnecessary computations because a message is typically too coarse for
this purpose. For example, if only one entry in a message is invalid, the whole
message is considered invalid. Recomputing such a message will lead to many
unnecessary computations. This problem will be avoided in Q-DAG propagation since
validity flags are attributed to *arithmetic* operations, which are the building
blocks of message operations. Therefore, only the necessary arithmetic
operations will be
recomputed in a Q-DAG propagation scheme, leading to a more detailed level of
optimization.

We also stress that the process of evaluating and updating a Q-DAG is done outside of probability theory and belief network inference. This makes the development of efficient on-line inference software accessible to a larger group of people who may lack strong backgrounds in these areas.[+]

[Next] [Up] [Previous]