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.[+]