\documentstyle[/home/darwiche/latex/adnan-aaai,/home/darwiche/latex/jair,twoside,/home/darwiche/latex/theapa,epsf,11pt]{article}

\jairheading{6}{1997}{147-176}{6/96}{5/97}
\ShortHeadings{A Practical Paradigm for Implementing Belief-Network Inference}
{Darwiche \& Provan}
\firstpageno{147}

\def\eq{\!\!=\!\!}

\def\E{{\bf E}}
\def\Q{{\bf Q}}


\def\qn{n}
\def\esn(#1,#2){{\qn(#1,#2)}}

\def\qdq{{\cal Q}}
\def\dag{{\cal D}}
\def\evars{{\cal V}}
\def\qvars{{\cal Z}}
\def\valf{{\cal I}}
\def\unk{\diamond}
\def\qdevd{{\cal E}}
\def\qneval{{\cal M}_\qdevd}
\def\qdeval{{\cal M}_\qdevd}
\def\qdpr{{Qnode}}

\def\qd{(\evars,\unk,\valf,\dag,\qvars)}

\def\on{{\it ON}}
\def\off{{\it OFF}}

\def\pr{{\it Pr}}
\def\epr{{\it Pr^\prime}}
\def\k{\kappa}
\def\ek{\kappa^\prime}

\def\X{{\bf X}}
\def\Y{{\bf Y}}
\def\Z{{\bf Z}}
\def\x{{\bf x}}
\def\y{{\bf y}}
\def\z{{\bf z}}

\def\a{{\bf a}}
\def\A{{\bf A}}
\def\b{{\bf b}}
\def\B{{\bf B}}
\def\c{{\bf c}}
\def\C{{\bf C}}

\def\false{{\it false}}
\def\true{{\it true}}

\def\definedas{=}
\def\definedas{=_{\it def}}

\def\u{{\bf u}}

\def\evd{{\bf e}}

\def\arc(#1,#2){#1 \rightarrow #2}

\def\cnets{{\sc CNETS}}
\def\bel{{\it BEL}}

\def\pr{{\it Pr}}



\def\q{Q-DAG }
\def\m{{\qdeval}}
\def\o{\odot}
\def\ot{\otimes}
\def\t{\times}


\begin{document}


\title{Query DAGs: A Practical Paradigm for Implementing 
Belief-Network Inference}

\author{\name {Adnan Darwiche}
        \email darwiche@aub.edu.lb \\
        \addr Department of Mathematics \\
              American University of Beirut \\
              PO Box 11 - 236, Beirut, Lebanon
        \AND
        \name Gregory Provan \email provan@risc.rockwell.com \\
        \addr Rockwell Science Center \\
              1049 Camino Dos Rios \\
              Thousand Oaks, CA 91360}


\maketitle

\begin{abstract}
We describe a new paradigm for implementing inference in belief networks, 
which consists of two steps:
(1) compiling a belief network into an arithmetic expression called 
a Query DAG (Q-DAG);
and (2) answering queries using a simple evaluation algorithm.
Each node of a Q-DAG represents a numeric 
operation, a number, or a symbol for evidence. Each leaf node of a Q-DAG 
represents the answer to a network query, that is, the probability of some event
of interest. It appears that Q-DAGs can be generated using any of the 
standard algorithms
for exact inference in belief networks --- we show how they can be generated
using clustering and conditioning algorithms. The time and space complexity of a
Q-DAG {\em generation} algorithm is no worse than the time complexity of the 
inference algorithm on which it is based. The complexity of a Q-DAG {\em
evaluation} algorithm is linear in the size of the Q-DAG, and such
inference amounts to a standard evaluation of the arithmetic expression it 
represents. The intended value of Q-DAGs 
is in reducing the software and hardware resources required to utilize belief 
networks in on-line, real-world applications. The proposed framework also 
facilitates the development of on-line inference on different software 
and hardware platforms due to the simplicity of the Q-DAG evaluation algorithm.
Interestingly enough, Q-DAGs were found to serve other purposes: simple 
techniques for reducing Q-DAGs tend to subsume relatively complex
optimization techniques for belief-network inference, such as
network-pruning and computation-caching.
\end{abstract}

\section{Introduction}

Consider designing a car to have a self-diagnostic system that can alert
the driver to a range of problems. 
Figure~\ref{car-fig} shows a simplistic belief network that could 
provide a ranked set of diagnoses
for  car troubleshooting, given input from sensors hooked up to the
battery, alternator, fuel-tank and oil-system.

\begin{figure}
\centerline{\epsfxsize=85mm \leavevmode 
\epsffile{car.eps}}
\caption{A simple belief network for car diagnosis.
\label{car-fig}}
\end{figure}

The standard approach to building such a diagnostic system is to put
this belief network, along with inference code, onto the
car's computer; see Figure~\ref{fig:comparison}. 
We have encountered a number of difficulties when using this 
approach to embody belief network technology in industrial applications. 
First, we were asked to provide the technology on multiple platforms. For 
some applications, the technology had to be implemented in ADA to pass certain 
certification procedures. In others, it had to be implemented on 
domain-specific hardware that only supports very primitive programming 
languages. Second, memory was limited  to keep the cost of 
a unit below a certain threshold to maintain product profitability.
The dilemma was the following:  belief network algorithms are 
not trivial to implement, especially when optimization is crucial,
and porting these algorithms to multiple platforms and languages
would have been prohibitively expensive, time-consuming and demanding
of qualified manpower.

\begin{figure}[tb]
\centerline{\epsfxsize=110mm \leavevmode 
\epsffile{comparison.eps}}
\caption{This figure compares the traditional approach to exact belief-network 
inference
(shown on the left) with our new compiled approach (shown on the right) in the
context of diagnostic reasoning.
In the traditional approach, the belief network and sensor values are used 
{\em on-line} to compute the probability distributions over fault variables; in
the compiled approach, the belief network, fault variables and sensor variables
are compiled {\em off-line} to produce a Q-DAG, which is then evaluated {\em
on-line} using sensor values to compute the required distributions.
\label{fig:comparison}}
\end{figure}

\begin{figure}[tb]
\begin{center}
\mbox{\epsfxsize=75mm \leavevmode 
\epsffile{ccomp-soln.eps}}
\caption{The proposed framework for implementing belief-network inference.
\label{fig:soln}}
\end{center}
\end{figure}

To overcome these difficulties, we have devised a very flexible approach 
for implementing belief network systems, which is based on the following
observation. Almost all the work performed by standard algorithms for belief
networks is independent of the specific evidence gathered about variables.
For example, if we run an algorithm with the battery-sensor set to 
{\it low} and then
run it later with the variable set to {\it dead}, 
we find almost no algorithmic 
difference between the two runs. That is, the algorithm will not branch 
differently on any of the key decisions it makes, and the only difference
between the two runs is the specific arguments to the invoked numeric
operations. Therefore, one can apply a standard inference algorithm on a 
network with evidence being a {\it parameter} instead of being a specific value. 
The result returned by the algorithm will then be an arithmetic expression 
with some parameters that depend on specific evidence. This parameterized 
expression is what we call a Query DAG, an example of which is shown in 
Figure~\ref{fig:cn-1}.\footnote{The sharing of subexpressions is what makes
this a Directed Acyclic Graph instead of a tree.}

\begin{figure*}[htb]
\begin{center}
\mbox{\epsfxsize=140mm \leavevmode 
\epsffile{ccomp-cn-qd.eps}}
\caption{A belief network (a); and its corresponding Query-DAG (b).
Here, \(C\) is an evidence variable, 
and we are interested in the probability of variable \(B\).
\label{fig:cn-1}}
\end{center}
\end{figure*}

The approach we are proposing consists of two steps. 
First, given a belief 
network, a set of variables about which evidence may be collected (evidence
variables), and a set of variables for which we need to compute probability
distributions  (query variables), a Q-DAG is compiled off-line, as shown in 
Figure~\ref{fig:soln}. The compilation is typically done on a sophisticated
software/hardware platform, using a traditional belief network inference
algorithm in conjunction with the Q-DAG compilation method.
This part of the process is far and away the most costly computationally.

Second, an on-line system composed from the 
generated Q-DAG and an evaluator specific to the given platform
is used to evaluate the Q-DAG.
Given evidence, the parameterized arithmetic expression 
is evaluated in a straightforward manner using simple arithmetic
operations rather than complicated belief network inference.
The computational work needed to perform this on-line 
evaluation is so straightforward that it lends itself to easy implementations 
on different software and hardware 
platforms.

This approach shares some commonality with other methods that 
symbolically manipulate probability expressions, like SPI
\cite{spi94b,spi90}; it differs from SPI on the objective of
such manipulations and, hence, on the  results obtained. 
SPI explicates the notion of an arithmetic expression
to state that belief-network inference can be viewed as an 
expression-factoring operation. This allows results from optimization 
theory to be utilized in belief-network inference. On the other hand,
we define an arithmetic expression
to explicate and formalize the boundaries between on-line and off-line
inference, with the goal of identifying the minimal piece of software that 
is required on-line. Our results are therefore oriented towards this purpose and 
they include: (a) a formal definition of a Q-DAG and its evaluator; 
(b) a method for generating Q-DAGs using standard inference algorithms --- 
an algorithm need not subscribe to the inference-as-factoring view 
to be used for Q-DAG generation; and
(c) computational guarantees on the size of Q-DAGs in terms of the 
computational guarantees of the inference algorithm used to generate them.
Although the SPI framework is positioned to formulate related results, it has
not been pursued in this direction.

It is important to stress the following properties of the proposed approach.
First, declaring an evidence variable in the compilation process does {\em not}
mean that evidence must be collected about that variable on-line---this is 
important because some evidence values, e.g., from sensors, may be lost 
in practice---it only means 
that evidence {\em may} be collected.
 Therefore, one can declare all variables to
be evidence if one wishes. Second, a variable can be declared to be both 
evidence and query. This allows one to perform value-of-information 
computations to decide whether it is worth collecting evidence about a 
specific variable. Third, the space complexity of a Q-DAG in terms of the 
number of evidence variables is no worse than the time complexity of its
underlying inference algorithm; therefore, this is not a simple 
enumerate-all-possible-cases approach. Finally, the time and space complexity 
for generating a Q-DAG is no worse than the time complexity of the standard 
belief-network algorithm used in its  generation. Therefore, if a network can 
be solved using a standard inference algorithm,
and if the time complexity of this algorithm is no worse than its space 
complexity,\footnote{Algorithms based on join trees have this property.}
then we can construct a Q-DAG for that network.

The following section explains the concept of a Q-DAG with a concrete example 
and provides formal definitions.  Section~\ref{sec:generating-qds} is dedicated 
to the generation of Q-DAGs and their computational complexity, showing that
any standard belief-network inference algorithm can be used to compile a Q-DAG 
as long as it meets some general conditions. Section~\ref{sec:reducing-qds}
discusses the reduction of a Q-DAG
after it has been generated, showing that such reduction  subsumes key
optimizations that are typically implemented in belief network algorithms.
Section~\ref{sec:example} contains a detailed example on the application
of this framework to diagnostic reasoning.
Finally, Section~\ref{sec:conclusion} closes with some concluding remarks.


\section{Query DAGs} \label{sec:q-dags}

This section starts our treatment of Q-DAGs with a concrete example. 
We will consider a particular belief network, define a set of queries
of interest, and then show a Q-DAG that can be used to answer such
queries. We will not discuss how the Q-DAG is generated; only how it 
can be used. This will allow a concrete introduction to Q-DAGs and 
will help us ground some of the formal definitions to follow.

The belief network we will consider is the one in Figure~\ref{fig:cn-1}(a). 
The class of queries we are interested in is \(\pr(B\mid C)\), that is,
the probability that variable \(B\) takes some value given some known
(or unknown) value of \(C\). Figure~\ref{fig:cn-1}(b) depicts a Q-DAG for 
answering such queries, which is essentially a parameterized arithmetic 
expression where the values of parameters depend on the evidence obtained.
This Q-DAG will actually answer queries of the form
\(\pr(B,C)\), but we can use normalization to compute 
\(\pr(B\mid C)\).

First, a number of observations about the Q-DAG in Figure~\ref{fig:cn-1}(b):
\begin{itemize}
\item The Q-DAG has two leaf nodes labeled \(\pr(B\eq\on,c)\) and \(\pr(B\eq\off,c)\).
These are called {\em query nodes} because their values represent 
answers to the queries \(\pr(B\eq\on,c)\) and \(\pr(B\eq\off,c)\).

\item The Q-DAG has two root nodes labeled \((C,\on)\) and \((C,\off)\).
These are called {\em Evidence Specific Nodes (ESNs)} since their values
depend on the evidence collected about variable \(C\) on-line. 
\end{itemize}

According to the semantics of Q-DAGs, the value of node \((V,v)\) is 1 if 
variable \(V\) is observed to be \(v\) or is unknown, and 0 otherwise. 
Once the values of ESNs are determined, we evaluate the remaining nodes 
of a Q-DAG using numeric multiplication and addition. The numbers that 
get assigned to query nodes as a result of this evaluation are the answers 
to queries represented by these nodes.

For example, suppose that the evidence we have is \(C\eq\on\). Then ESN
\((C,\on)\) is evaluated to 1 and ESN \((C,\off)\) is evaluated to 0. 
The Q-DAG in Figure~\ref{fig:cn-1}(b) is then evaluated as given in 
Figure~\ref{fig:qd-2}(a), thus leading to
\[ \pr(B\eq\on, C\eq\on) = .3475, \]
and
\[ \pr(B\eq\off, C\eq\on) = .2725,\]
from which we conclude that \(\pr(C\eq\on) = .62\). We can then compute the
conditional probabilities 
\(\pr(B\eq\on \mid C\eq\on)\) and 
\(\pr(B\eq\off \mid C\eq\on)\) using:
\[ \pr(B\eq\on \mid C\eq\on) = 
   \pr(B\eq\on, C\eq\on) / \pr(C\eq\on), \]
\[ \pr(B\eq\off \mid C\eq\on) = 
   \pr(B\eq\off, C\eq\on) / \pr(C\eq\on). \]

If the evidence we have is \(C\eq\off\), however,
then \((C,\on)\) evaluates to 0 and 
\((C,\off)\) evaluates to 1. The Q-DAG in Figure~\ref{fig:cn-1}(b) will then be 
evaluated as given in Figure~\ref{fig:qd-2}(b), thus leading to
\[ \pr(B\eq\on, C\eq\off) = .2875, \]
and
\[ \pr(B\eq\off, C\eq\off) = .0925.\]

\begin{figure}[t]
\begin{center}
\mbox{\epsfxsize=140mm \leavevmode 
\epsffile{ccomp-qd-2ab.eps}}
\caption{Evaluating the Q-DAG in Figure~\protect{\ref{fig:cn-1}} with 
respect to two pieces of evidence: (a) \protect{\(C\eq\on\)} and 
(b) \protect{\(C\eq\off\)}.
\label{fig:qd-2}}
\end{center}
\end{figure}

We will use the following notation for denoting variables and their values. 
Variables are denoted using uppercase letters, such as \(A, B, C\), and variable 
values are denoted by lowercase letters, such as \(a, b, c\). Sets of variables
are denoted by boldface uppercase letters, such as \(\A, \B, \C\), and their
instantiations are denoted by boldface lowercase letters, such as 
\(\a, \b, \c\). 
We use \(\E\) to denote the set of variables about which we have evidence.
Therefore, we use \(\evd\) to denote an instantiation of these variables that 
represents evidence. Finally, the {\em family}
of a variable is the set containing
the variable and its parents in a directed acyclic graph.

Following is the formal definition of a Q-DAG.
\begin{definition}
A Q-DAG is a tuple \(\qd\) where
\begin{enumerate}
\item \(\evars\) is a distinguished set of symbols (called \underline{evidence variables})
\item \(\unk\) is a symbol (called \underline{unknown value})
\item \(\valf\) maps each variable in \(\evars\) into a set of symbols
(called \underline{variable values}) different from \(\unk\).
\item \(\dag\) is a directed acyclic graph where
\begin{enumerate}\itemsep -1.5mm
\item [-] each non-root node is labeled with either $+$ or $*$
\item [-] each root node is labeled with either
\begin{itemize}
\item [-] a number in \([0,1]\) or 
\item [-] a pair \((V,v)\) where \(V\) is an evidence variable and \(v\) is a value
\end{itemize}
\end{enumerate}
\item \(\qvars\) is a distinguished set of nodes in \(\dag\) (called \underline{query nodes})
\end{enumerate}
\end{definition}
Evidence variables \(\evars\) correspond to network variables about which we
expect to collect evidence on-line. 
For example, in Figure~\ref{fig:qd-2}, $C$ is the evidence variable.
Each one of these variables has a set of 
possible values that are captured by the function \(\valf\). 
For example, in Figure~\ref{fig:qd-2}, the evidence variable $C$ has values
$\on$ and $\off$.
The special value 
\(\unk\) is used when the value of a variable is not known. For example, we may 
have a sensor variable with values ``low,'' ``medium,'' and ``high,'' but then
lose the sensor value during on-line reasoning. In this case, we set the sensor
value to \(\unk\).\footnote{This is also useful in cases where a variable will
be measured only if its value of information justifies that.} 
Query nodes are those representing answers to user queries.
For example, in Figure~\ref{fig:qd-2}, $B$ is the query variable, and 
leads to query nodes $Pr(B\eq\on,c)$ and $Pr(B\eq\off,c)$.

An important notion is that of evidence:
\begin{definition}
For a given Q-DAG \(\qd\), \underline{evidence} is defined as a function 
\(\qdevd\) that maps each variable \(V\) in \(\evars\) into the set of values 
\(\valf(V) \cup \{\unk\}\).
\end{definition}
When a variable \(V\) is mapped into \(v \in \valf(V)\), then evidence tells
us that \(V\) is instantiated to value \(v\). When \(V\) is mapped into
\(\unk\), then evidence does not tell us anything about the value of \(V\).


We can now state formally how to evaluate a Q-DAG given some evidence. But 
first we need some more notation:
\begin{enumerate}
\item {\em Numeric-Node:} 
\(\qn(p)\) denotes a node labeled with a number \(p \in [0,1]\);
\item {\em ESN:} 
\(\esn(V,v)\) denotes a node labeled with \((V,v)\);
\item {\em Operation-Node:}
\(n_1 \otimes \ldots \otimes n_i\) denotes a node labeled with $*$ and
having parents \(n_1, \ldots, n_i\);
\item {\em Operation-Node:}
\(n_1 \oplus \ldots \oplus n_i\) denotes a node labeled with $+$ and
having parents \(n_1, \ldots, n_i\).
\end{enumerate}

The following definition tells us how to evaluate a Q-DAG by evaluating each of
its nodes. It is a recursive definition according to which the value assigned to
a node is a function of the values assigned to its parents. The first two cases
are boundary conditions, assigning values to root nodes. The last two cases are
the recursive ones.

\begin{definition} \label{def:neval}
For a Q-DAG \(\qd\) and evidence \(\qdevd\), the \underline{node evaluator}
is defined as a function \(\qneval\) that maps each node in \(\dag\)
into a number \([0,1]\) such that:
\begin{enumerate}
\item \(\qneval[\qn(p)] = p\) \\
(The value of a node labeled with a number is the number itself.)

\item \(\qneval[\qn(V,v)] = 
\left\{
\begin{array}{ll}
1, & \mbox{if \(\qdevd(V) = v\) or \(\qdevd(V) = \unk\);} \\
0, & \mbox{otherwise} \\
\end{array}
\right.
\) \\
(The value of an evidence-specific node depends on the available
evidence: it is 1 if \(v\) is consistent with the evidence and 0 otherwise.)

\item \(\qneval[n_1 \otimes \ldots \otimes n_i] = \qneval(n_1) * \ldots *
\qneval(n_i)\) \\
(The value of a node labeled with $*$ is the product of the values 
of its parent nodes.)

\item \(\qneval[n_1 \oplus \ldots \oplus n_i] = \qneval(n_1) + \ldots +
\qneval(n_i)\) \\
(The value of a node labeled with $+$ is the sum of the values of its parent nodes.)
\end{enumerate}
\end{definition}

One is typically not interested in the values of all nodes in a Q-DAG since most
of these nodes represent intermediate results that are of no interest to
the user. It is the query nodes of a Q-DAG that represent answers to user
queries and it is the values of these nodes that one seeks when constructing 
a Q-DAG. The values of these queries are captured by the notion of a Q-DAG
output.

\begin{definition}
The node evaluator \(\qneval\) is extended to Q-DAGs as follows:
\[ \qneval(\qd) = \{(n,\qneval(n)) \mid n \in \qvars\}. \]
The set \(\qneval(\qd)\) is called the Q-DAG \underline{output.} 
\end{definition}
This output is what one seeks from a Q-DAG. Each element in this output
represents a probabilistic query and its answer. 

Let us consider a few evaluations of the Q-DAG shown in Figure~\ref{fig:cn-1},
which are shown in Figure~\ref{fig:qd-2}. Given evidence \(\qdevd(C)\eq\on\), 
and assuming that \(\qdpr(B\eq\on)\) and \(\qdpr(B\eq\off)\) stand for the 
Q-DAG nodes labeled \(\pr(B\eq\on,c)\) and \(\pr(B\eq\off,c)\), 
respectively, we have 
\begin{eqnarray*}
\qdeval[\esn(C,\on)] & = & 1, \\
\qdeval[\esn(C,\off)] & = & 0, \\
\qdeval[\qdpr(B\eq\on)] 
& = & .075 * (.9*1 + .1*0) + .56 * (1*.5 + .5*0 ) = .3475, \\
\qdeval[\qdpr(B\eq\off)] 
& = & (.9*1 + .1*0) * .225 + (1*.5 + .5*0) * .14 = .2725, 
\end{eqnarray*}
meaning that \(\pr(B\eq\on, C\eq\on) = .3475\) 
and \(\pr(B\eq\off, C\eq\on) = .2725\).
If instead the evidence were \(\qdevd(C)\eq\off\), a set of
analogous computations can be done.

It is also possible that evidence tells us nothing about the value of variable
\(C\), that is, \(\qdevd(C) = \unk\). In this case, we would have 
\begin{eqnarray*}
\qdeval[\esn(C,\on)] & = & 1, \\
\qdeval[\esn(C,\off)] & = & 1, \\
\qdeval[\qdpr(B\eq\on)] 
& = &  .075 * (.9*1 + .1*1) + .56 * (1*.5 + .5*1 )  = .635, \\
\qdeval[\qdpr(B\eq\off)] 
& = &  (.9*1 + .1*1) * .225 + (1*.5 + .5*1) * .14 = .365,
\end{eqnarray*}
meaning that \(\pr(B\eq\on) = .635\) and \(\pr(B\eq\off) = .365\).


\subsection{Implementing a Q-DAG Evaluator}

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 {\em 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.\footnote{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.}


\subsection{The Availability of Evidence} 

The construction of a Q-DAG requires the identification of query and evidence
variables. This may give an incorrect impression that we must know up front
which variables are observed and which are not. This could be problematic in 
(1) applications where one may lose a sensor reading, thus changing the status
of a variable from being observed to being unobserved; and (2) applications
where some variable may be expensive to observe, leading to an on-line 
decision on whether to observe it or not (using some value-of-information
computation).

\begin{figure}
\begin{center}
\mbox{\epsfxsize=70mm \leavevmode 
\epsffile{voi-example-net.eps}}
\mbox{\epsfxsize=120mm \leavevmode 
\epsffile{voi-example.eps}}
\caption{A belief network and its corresponding Q-DAG in which 
variable \(B\) is declared to be both query and evidence.
\label{voi1}}
\end{center}
\end{figure}

Both of these situations can be dealt with in a Q-DAG framework. First, as 
we mentioned earlier, Q-DAGs allow us to handle missing evidence 
through the use of the \(\unk\) notation which denotes an unknown value of
a variable. Therefore, Q-DAGs can handle missing sensor readings.
Second, a variable can be declared to be both query and evidence. 
This means that we can incorporate evidence about this variable when it is
available, and also compute the probability distribution of the variable 
in case evidence is not available. Figure~\ref{voi1} depicts a Q-DAG in 
which variable \(A\) is declared to be a query variable, while variable
\(B\) is declared to be both an evidence and a query variable (both variables 
have \(\true\) and \(\false\) as their values). In this case, we have two ESNs 
for variable \(B\) and also two query nodes
(see  Figure~\ref{voi1}).
This Q-DAG can be used in two ways:

\begin{enumerate}
\item To compute the probability distributions of variables \(A\) and
\(B\) when no evidence is available about \(B\). Under this situation,
the values of \(\esn(B,\true)\) and \(\esn(B,\false)\) are set to 1, and we have
\begin{eqnarray*}
\pr(A=\true) & = & .3*.1+.3*.9 = .3 \\
\pr(A=\false) & = & .8*.7+.7*.2 = .7 \\
\pr(B=\true) & = & .3*.1+.8*.7 = .59 \\
\pr(B=\false) & = & .3*.9+.7*.2 = .41 
\end{eqnarray*}

\item To compute the probability of variable \(A\) when evidence is available
about \(B\). For example, suppose that we observe \(B\) to be \(\false\). 
The value of \(\esn(B,\true)\) will then be set to 0 and the value of 
\(\esn(B,\false)\) will be set to 1, and we have
\begin{eqnarray*}
\pr(A=\true,B=\false) & = & .3*.9 = .27 \\
\pr(A=\false,B=\false) & = & .7*.2 = .14
\end{eqnarray*}
\end{enumerate}

\def\ut{{\it Utility\_Of\_Observing}}

The ability to declare a variable as both an evidence and a query 
variable seems to be essential in applications where 
(1) a decision may need to be made on whether to collect evidence about 
some variable \(B\); and
(2) making the decision requires knowing the probability distribution of
variable \(B\).
For example, suppose that we are using the following formula 
\cite[Page 313]{pearl88b} to compute the utility of observing variable 
\(B\):
\[
\ut(B) = \sum_b Pr(B=b| {\bf e})~U(B=b), 
\]
where \(U(B=b)\) is the utility for the decision maker of finding that 
variable \(B\) has value \(b\). Suppose that \(U(B=\true)= \$2.5\) and 
\(U(B=\false)=-\$3\). We can use the Q-DAG to compute the probability
distribution of \(B\) and use it to evaluate \(\ut(B)\):
\[
\ut(B) = (\$2.5*.59) + (-\$3*.41) = \$0.24,
\]
which leads us to observe variable \(B\). Observing \(B\), we find that
its value is \(\false\). We can then accommodate this evidence into the Q-DAG 
and continue with our analysis. 

\section{Generating Query DAGs} \label{sec:generating-qds}

This section shows how Q-DAGs can be generated using traditional algorithms for 
exact belief-network inference. In particular, we will show how Q-DAGs can be
generated using the clustering (join tree, Jensen, LS) algorithm
\cite{jensen90,shachter94,shenoy86}, the polytree algorithm, and cutset conditioning
\cite{pearl88b,peot91}.
We will also outline properties that must be satisfied by other belief network 
algorithms in order to adapt them for generating Q-DAGs as we propose.


\subsection{The Clustering Algorithm}

We provide a sketch of the clustering algorithm in this section. Readers
interested in more details are
referred to \cite{shachter94,jensen90,shenoy86}.

According to the clustering method, we start by:
\begin{enumerate}
\item constructing a join tree of the given belief network;\footnote{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.} 
\item assigning the matrix of each variable in the belief network to some cluster
that contains the variable's family.
\end{enumerate}
The join tree is a secondary structure on which the inference algorithm
operates. We need the following notation to state this algorithm:
\begin{itemize}
\item [-] \(S_1, \ldots, S_n\) are the clusters, where each cluster corresponds
to a set of variables in the original belief network.

\item [-] \(\Psi_i\) is the {\em potential function} over cluster \(S_i\), which
is a mapping from instantiations of variables in \(S_i\) into real numbers.

\item [-] \(P_i\) is the {\em posterior probability distribution} over cluster
\(S_i\),  which is a mapping from instantiations of variables in \(S_i\) into real numbers.

\item [-] \(M_{ij}\) is the message sent from cluster \(S_i\) to cluster \(S_j\),
which is a mapping from instantiations of variables in \(S_i \cap S_j\) into
real numbers.

\item [-] \(\evd\) is the given evidence, that is, an instantiation of evidence
variables \(\E\).
\end{itemize}
We also assume the standard multiplication and marginalization operations on
potentials.

Our goal now is to compute the potential \(\pr(X,\evd)\) which maps each 
instantiation \(x\) of variable \(X\) in the belief network into the 
probability \(\pr(x,\evd)\). Given this notation, we can state the algorithm 
as follows:
\begin{itemize}
\item Potential functions are initialized using
\[ \Psi_i = \prod_X \pr_X \lambda_X,\]
where 
\begin{itemize}
\item \(X\) is a variable whose matrix is assigned to cluster \(S_i\);
\item \(\pr_X\) is the matrix for variable \(X\): a mapping from
instantiations of the family of \(X\) into conditional probabilities; 
and 
\item \(\lambda_X\) is the likelihood vector for variable \(X\):
\(\lambda_X(x)\) is 1 if \(x\) is consistent with given evidence \(\evd\) 
and 0 otherwise.
\end{itemize}

\item Posterior distributions are computed using
\[P_i = \Psi_i \prod_k M_{ki}, \]
where \(S_k\) are the clusters adjacent to cluster \(S_i\). 

\item Messages are computed using
\[ M_{ij} = \sum_{S_i \setminus S_j} 
          \Psi_i \prod_{k \neq j} M_{ki}, \]
where \(S_k\) are the clusters adjacent to cluster \(S_i\). 

\item The potential \(\pr(X,\evd)\) is computed using
\[ \pr(X, \evd) = \sum_{S_i \setminus \{X\}} P_i, \]
where \(S_i\) is a cluster to which \(X\) belongs.
\end{itemize}

These equations are used as follows.
To compute the probability of a variable, we must compute the posterior
distribution of a cluster containing the variable. 
To compute the posterior distribution
of a cluster, we collect messages from neighboring clusters. A message from
cluster \(S_i\) to \(S_j\) is computed by collecting messages from all clusters 
adjacent to \(S_i\) except for \(S_j\). 

This statement of the join tree algorithm is appropriate for situations where
the evidence is not changing frequently since it involves computing initial
potentials each time the evidence changes. This is not necessary in general and
one can provide more optimized versions of the algorithm. This issue,
however, is irrelevant in the context of generating Q-DAGs because updating 
probabilities in face of evidence changes will take place at the Q-DAG level,
which includes its own optimization technique that we discuss later.

\subsection{Generating Q-DAGs}

To generate Q-DAGs using the clustering method, we have to go through two steps. 
First, we have to modify the initialization of potential functions so that 
the join tree is quantified using Q-DAG nodes instead of numeric probabilities. 
Second, we have to replace numeric addition and multiplication in the algorithm
by analogous functions that operate on Q-DAG nodes. In particular:
\begin{enumerate}
\item Numeric multiplication $*$ is replaced by an operation \(\otimes\) that 
takes Q-DAG nodes \(n_1, \ldots, n_i\) as arguments, constructs and returns a 
new node \(n\) with label \(*\) and parents \(n_1, \ldots, n_i\). 

\item Numeric addition $+$ is replaced by an operation \(\oplus\) that 
takes Q-DAG nodes \(n_1, \ldots, n_i\) as arguments, constructs and returns 
a new node \(n\) with label \(+\) and parents \(n_1, \ldots, n_i\). 
\end{enumerate}
Therefore, instead of numeric operations, we have Q-DAG-node constructors. And
instead of returning a number as a computation result, we now return a Q-DAG node. 

Before we state the Q-DAG clustering algorithm, realize that we now do not have 
evidence \(\evd\), but instead we have a set of evidence variables \(\E\) for
which we will collect evidence. Therefore, the Q-DAG algorithm will not compute an
answer to a query \(\pr(x, \evd)\), but instead will compute a Q-DAG node that
evaluates to \(\pr(x, \evd)\) under the instantiation \(\evd\) of variables 
\(\E\).

In the following equations,
potentials are mappings from variable instantiations to Q-DAG nodes 
(instead of numbers). For example, the matrix for variable \(X\) will map 
each instantiation of \(X\)'s family into a Q-DAG node \(\qn(p)\) instead
of mapping it into the number \(p\). 
The Q-DAG operations \(\otimes\) and \(\oplus\) are extended to 
operate on these new potentials in the same way that \(*\) and \(+\) are 
extended in the clustering algorithm.

The new set of equations is:
\begin{itemize}
\item Potential functions are initialized using
\[ \Psi_i = 
\bigotimes_X \qn(\pr_X) \otimes \bigotimes_{E} \qn(\lambda_E), \]
where 
\begin{itemize}
\item \(X\) is a variable whose matrix is assigned to cluster \(S_i\);
\item \(\qn(\pr_X)\) is the Q-DAG matrix for \(X\): a mapping from
instantiations of \(X\)'s family into Q-DAG nodes representing conditional 
probabilities; 
\item \(E\) is an evidence variable whose matrix is assigned to cluster 
\(S_i\); and 
\item \(\qn(\lambda_E)\) is the Q-DAG likelihood vector of 
variable \(E\): \(\qn(\lambda_E)(e) = \esn(E,e)\), which means that node
\(\qn(\lambda_E)(e)\) evaluates to 1 if \(e\) is consistent with given evidence
and 0 otherwise.
\end{itemize}

\item Posterior distributions are computed using
\[ P_i = \Psi_i \bigotimes_k M_{ki}, \]
where \(S_k\) are the clusters adjacent to cluster \(S_i\). 

\item Messages are computed using
\[ M_{ij} = 
\bigoplus_{S_i \setminus S_j} \Psi_i \bigotimes_{k \neq j} M_{ki}, \]
where \(S_k\) are the clusters adjacent to cluster \(S_i\). 

\item The Q-DAG nodes for answering queries of the form 
\(\pr(x, \evd)\) are computed using
\[ \qdpr(X) = \bigoplus_{S_i \setminus \{X\}} P_i, \]
where \(S_i\) is a cluster to which \(X\) belongs.
\end{itemize}
Here \(\qdpr(X)\) is a potential that maps each instantiation
\(x\) of variable \(X\) into the Q-DAG node \(\qdpr(X)(x)\) which 
evaluates to \(\pr(x, \evd)\) for any given instantiation \(\evd\) of variables 
\(\E\). 

Hence, the only modifications we made to the clustering algorithm are 
(a) changing the initialization of potential functions and 
(b) replacing multiplication and addition with Q-DAG constructors of 
multiplication and addition nodes. 

\subsection{An Example}

We now show how the proposed Q-DAG algorithm can be used to generate a Q-DAG for the
belief network in Figure~\ref{fig:cn-1}(a).

\begin{figure}
\begin{center}
\mbox{\epsfxsize=150mm \leavevmode 
\epsffile{ccomp-jt-composite.eps}}
\caption{A join tree quantified with numbers (a), and
with Q-DAG nodes (b).
\label{fig:jt-cn-1a}}
\end{center}
\end{figure}

We have only one evidence variable in this example, \(C\). And we are interested
in generating a Q-DAG for answering queries about variable \(B\), that is,
queries of the form \(\pr(b,\evd)\).
Figure~\ref{fig:jt-cn-1a}(a) shows the join tree for the belief network in 
Figure~\ref{fig:cn-1}(a), where the tables contain the potential functions 
needed for the probabilistic clustering algorithm. 
Figure~\ref{fig:jt-cn-1a}(b) shows the join tree again, but the tables 
contain the potential functions needed by the Q-DAG clustering algorithm. 
Note that the tables are filled with Q-DAGs instead of numbers.

We now apply the Q-DAG algorithm. To compute the Q-DAG nodes that will evaluate
to \(\pr(b,\evd)\), we must compute the posterior distribution \(P_2\) over cluster
\(S_2\) since this is a cluster to which variable \(B\) belongs. We can then 
sum the distribution over variable \(A\) to obtain what we want. To compute
the distribution \(P_2\) we must first compute the message \(M_{12}\) from
cluster \(S_1\) to cluster \(S_2\).

The message \(M_{12}\) is computed by summing the potential function
\(\Psi_1\) of cluster \(S_1\) over all possible values of variable \(C\), i.e.,
\(\displaystyle M_{12} = \bigoplus_C \Psi_1, \)
which leads to: 
\[ M_{12}(A\eq\on) = [\qn(.9) \otimes \esn(C,\on)] \oplus [\qn(.1) \otimes \esn(C,\off)], \]
 
\[ M_{12}(A\eq\off) = [\qn(.5) \otimes \esn(C,\on)] \oplus [\qn(.5) \otimes \esn(C,\off)]. \]

The posterior distribution over cluster \(S_2\), \(P_2\), is computed using
\(\displaystyle P_2 = \Psi_2 \otimes M_{12}, \)
which leads to
\begin{eqnarray*}
P_2(A\eq\on,B\eq\on) & = & 
\qn(.075) \otimes [[\qn(.9) \otimes \esn(C,\on)] \oplus 
[\qn(.1) \otimes \esn(C,\off)]] \\
P_2(A\eq\on,B\eq\off) & = & 
\qn(.225) \otimes [[\qn(.9) \otimes \esn(C,\on)] \oplus 
[\qn(.1) \otimes \esn(C,\off)]] \\
P_2(A\eq\off,B\eq\on) & = & 
\qn(.56) \otimes [[\qn(.5) \otimes \esn(C,\on)] \oplus 
[\qn(.5) \otimes \esn(C,\off)]] \\
P_2(A\eq\off,B\eq\off) & = & 
\qn(.14) \otimes [[\qn(.5) \otimes \esn(C,\on)] \oplus 
[\qn(.5) \otimes \esn(C,\off)]].
\end{eqnarray*}

The Q-DAG node \(\qdpr(b)\) for answering queries of the form \(\pr(b,\evd)\) is
computed by summing the posterior \(P_2\) over variable \(A\),
\(\displaystyle \qdpr = \bigoplus_{S_2 \setminus \{B\}} P_2, \)
leading to
\begin{eqnarray*}
\qdpr(B\eq\on) & = & 
[\qn(.075) \otimes [[\qn(.9) \otimes \esn(C,\on)] \oplus 
[\qn(.1) \otimes \esn(C,\off)]]] \oplus \\
& & [\qn(.56) \otimes [[\qn(.5) \otimes \esn(C,\on)] \oplus 
[\qn(.5) \otimes \esn(C,\off)]]] \\
\qdpr(B\eq\off) & = & 
[\qn(.225) \otimes [[\qn(.9) \otimes \esn(C,\on)] \oplus 
[\qn(.1) \otimes \esn(C,\off)]]] \oplus \\
& & [\qn(.14) \otimes [[\qn(.5) \otimes \esn(C,\on)] \oplus 
[\qn(.5) \otimes \esn(C,\off)]]],
\end{eqnarray*}
which is the Q-DAG depicted in Figure~\ref{fig:cn-1}(b).
Therefore, the result of applying the algorithm is two Q-DAG nodes, one
will evaluate to \(\pr(B\eq\on,\evd)\) and the other will evaluate to
\(\pr(B\eq\off,\evd)\) under any instantiation \(\evd\) of evidence 
variables \(\E\).

\subsection{Computational Complexity of Q-DAG Generation}

The computational complexity of the algorithm for generating Q-DAGs is 
determined by the computational complexity of the clustering algorithm. 
In particular, the proposed algorithm applies a \(\oplus\)-operation
precisely when the clustering algorithm applies an addition-operation.
Similarly, it applies a \(\otimes\)-operation
precisely when the clustering algorithm applies a multiplication-operation.
Therefore, if we assume that \(\oplus\) and \(\otimes\) take 
constant time, then both algorithms have the same time complexity. 

Each application of \(\oplus\) or \(\otimes\) ends up adding
a new node to the Q-DAG. And this is the only way a new node can be added
to the Q-DAG. Moreover, the number of parents of each added node is equal
to the number of arguments that the corresponding arithmetic operation 
is invoked on in the clustering algorithm. Therefore, the space complexity
of a Q-DAG is the same as the time complexity of the clustering algorithm.

In particular, this means that the space complexity of Q-DAGs in terms of the number 
of evidence variables is the same as the time complexity of the clustering 
algorithm in those terms. Moreover, each evidence variable \(E\) will  
add only \(m\) evidence-specific nodes to the Q-DAG, where \(m\) is the number of 
values that variable \(E\) can take. 
This is important to stress because without this complexity guarantee 
it may be hard to distinguish between the proposed approach and a 
brute-force approach that builds a big table containing all possible 
instantiations of evidence variables together with their corresponding 
distributions of query variables.


\subsection{Other Generation Algorithms}

The polytree algorithm is a special case of the clustering algorithm as 
shown in
\cite{shachter94}. Therefore, the polytree algorithm can also be modified as
suggested above to compute Q-DAGs. This also means that cutset conditioning can 
be easily modified to compute Q-DAGs: for each instantiation \(\c\) of the
cutset \(\C\), we compute a Q-DAG node for \(\pr(x,\c,\evd)\) using the polytree 
algorithm and then take the \(\oplus\)-sum of the resulting nodes. 

Most algorithms for exact inference in belief networks can be adapted to
generate Q-DAGs. In general, an algorithm must satisfy a key condition
to be adaptable for computing Q-DAGs as we suggested above. The condition is
that the behavior of the algorithm should never depend on the 
specific evidence obtained, but should only depend on the variables about which 
evidence is collected. That is, whether variable \(E\) is instantiated to value
\(v_1\) or value \(v_2\) should not affect the complexity of 
the algorithm. Only whether variable \(E\) is instantiated or not should matter.

Most belief networks algorithms that we are aware of satisfy this property. The
reason for this seems to be the notion of probabilistic independence on which 
these algorithms are based. Specifically, what is read from the topology of a
belief network is a relation \(I(\X,\Z,\Y)\), stating that variables \(\X\) and
\(\Y\) are independent given variables \(\Z\). That is, 
\[ \pr(\x, \y \mid \z) = \pr(\x \mid \z) \pr(\y \mid \z) \]
for all instantiations \(\x, \y, \z\) of these variables. It is possible,
however, for this not to hold for all instantiations of \(\z\) but only for 
specific ones. Most standard algorithms we are aware of do not take advantage 
of this instantiation--specific notion of independence.\footnote{Some 
algorithms for two--level binary networks (BN20 networks),
and some versions of the SPI algorithm do take advantage of these 
independences.} Therefore, they cannot attach any computational significance 
to the specific value to which a variable is instantiated. This property of 
existing algorithms is what makes them easily adaptable to the generation of 
Q-DAGs.


\subsection{Soundness of the Q-DAG Clustering Algorithm}

\label{sec:sound}

The soundness of the proposed algorithm is stated below. 
The proof is given in Appendix~\ref{app:proof}.

\begin{theorem} \label{theo:soundness}
Suppose that \(\qdpr(X)\) is a Q-DAG potential generated by the Q-DAG clustering 
algorithm for query variable \(X\) and evidence variables \(\E\).
Let \(\evd'\) be an instantiation of some variables in \(\E\), and let Q-DAG
evidence \(\qdevd\) be defined as follows:
\[ \qdevd(E) = \left\{
\begin{array}{ll}
e, & \mbox{if evidence \(\evd'\) sets variable \(E\) to value \(e\);} \\
\unk, & \mbox{otherwise.}
\end{array}
\right.\]
then 
\[ \qneval(\qdpr(X)(x)) = \pr(x,\evd'). \]
\end{theorem}
That is, the theorem guarantees that the Q-DAG nodes generated by the 
algorithm will always evaluate to their corresponding probabilities under 
any partial or full instantiation of evidence variables.

\section{Reducing Query DAGs}
\label{sec:reducing-qds}

This section is focused on reducing Q-DAGs after they have been generated.
The main motivation behind this reduction is twofold: faster evaluation of
Q-DAGs and less space to store them. Interestingly enough, we have 
observed that a few, simple reduction techniques tend in certain cases
to subsume optimization techniques that have been influential in practical 
implementations of belief-network inference. Therefore, reducing Q-DAGs 
can be very important practically. 

This section is structured as follows. First, we start by discussing four 
simple reduction operations in the form of rewrite rules. We then show 
examples in which these reductions subsume two key optimization techniques 
known as network-pruning and computation-caching.


\subsection{Reductions}

\begin{figure}[tb]
\centerline{\epsfxsize=95mm \leavevmode 
\epsffile{simplify.eps}}
\caption{The four main methods for Q-DAG reduction. 
\label{fig:simplify-fig}}
\end{figure}

The goal of Q-DAG reduction is to reduce the size of a Q-DAG while
maintaining the arithmetic expression it represents.
In describing the equivalence of arithmetic expressions,
we define the notion of Q-DAG equivalence:
\begin{definition}
Two Q-DAGs are \underline{equivalent} iff they have the same set of 
evidence-specific nodes and they have the same output for all possible 
Q-DAG evidence.
\end{definition}

Figure~\ref{fig:simplify-fig} shows four basic reduction operations that 
we have experimented with: 
\begin{enumerate}
\item {\em Identity elimination:} eliminates a numeric node if it is an 
identity element of its child operation node.

\item {\em Numeric reduction:} replaces an operation node with a numeric node 
if all its parents are numeric nodes.

\item {\em Associative merging:} eliminates an operation node
using operation associativity.

\item {\em Commutative merging:} eliminates an operation node
using operation commutativity.
\end{enumerate}
These rules can be applied successively and in different order until no
more applications are possible. 
 
We have proven that these operations are sound in \cite{qdag-tr}.
Based on an analysis of network structure and preliminary 
empirical results, we have observed that
many factors govern the effectives of these operations.
The degree to which reduction operations, numeric reduction in particular, 
can reduce the size of the Q-DAG depends on the topology of the given belief
network and the set of evidence and query variables.
For example, if all root
nodes are evidence variables of the belief network, and if all leaf nodes are
query variables, then numeric reduction will lead to little Q-DAG reduction. 

We now focus on numeric reduction, showing how it sometimes subsumes
two optimization techniques that have been influential in belief network 
algorithms. For both optimizations, we show examples where an unoptimized 
algorithm that employs numeric reduction yields the same Q-DAG as an 
optimized algorithm. The major implication is that
optimizations can be done uniformly at the Q-DAG level, freeing the underlying
belief network algorithms from such implementational complications. 

The following examples assume that we are applying the polytree algorithm
to singly-connected networks.

\subsection{Network Pruning}

\begin{figure}
\centerline{\epsfxsize=110mm \leavevmode 
\epsffile{example-net2.eps}}
\caption{A simple belief network before pruning (a) and
after pruning (b).
The light-shaded node, \(A\), is a query node, and the
dark-shaded node, \(B\), is an evidence node.
\label{fig:prune}}
\end{figure}

Pruning is the process of deleting irrelevant parts of a belief network before 
invoking inference. Consider the network in Figure~\ref{fig:prune}(a) 
for an example, 
where \(B\) is an evidence variable and \(A\) is a query variable. One can
prune node \(C\) from the network, leading to the network in 
Figure~\ref{fig:prune}(b). Any query of the form \(\pr(a \mid b)\) has
the same value with respect to either network. It should be clear that working
with the smaller network is preferred. In general, pruning can lead to dramatic 
savings since it can reduce a multiply-connected network to a
singly-connected one.


\begin{figure}
\centerline{\epsfxsize=120mm \leavevmode 
\epsffile{example1.eps}}
\caption{A Q-DAG (a) and its reduction (b).
\label{fig:prune-reduction}}
\end{figure}

If we generate a Q-DAG for the network in Figure~\ref{fig:prune}(a) using the
polytree algorithm, we obtain the one in Figure~\ref{fig:prune-reduction}(a).
This Q-DAG corresponds to the following expression,
\[
\pr(A\eq\on,\evd) =  
\pr(A\eq\on) \sum_b \lambda_{B}(b) \pr(b\mid A\eq\on) \sum_c \pr(c \mid b).
\]
If we generate a Q-DAG for the network in Figure~\ref{fig:prune}(b), however,
we obtain the one in Figure~\ref{fig:prune-reduction}(b) which
corresponds to the following expression,
\[
\pr(A\eq\on,\evd) = \pr(A\eq\on) \sum_b \lambda_{B}(b) \pr(b\mid A\eq\on).
\]
As expected, this Q-DAG is smaller than  the Q-DAG in 
Figure~\ref{fig:prune-reduction}(a),
and contains a subset of the nodes in Figure~\ref{fig:prune-reduction}(a).

The key observation, however, is that the optimized Q-DAG in 
Figure~\ref{fig:prune-reduction}(b) can be obtained from the unoptimized one 
in Figure~\ref{fig:prune-reduction}(a) using Q-DAG reduction. In particular, 
the nodes enclosed in dotted lines can be collapsed using numeric reduction 
into a single node with value 1. Identity elimination can then remove the
resulting node, leading to the optimized Q-DAG in 
Figure~\ref{fig:prune-reduction}(b).

The more general observation, however, is that prunable nodes  contribute
identity elements when computing answers to queries. These contributions appear
as Q-DAG nodes that evaluate to identity elements under all instantiations of 
evidence. Such nodes can be easily detected and collapsed into these identity 
elements using numeric reduction. Identity elimination can then remove them 
from the Q-DAG, leading to the same effect as network 
pruning.\footnote{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.} 
Whether Q-DAG reduction can replace all possible pruning operations is an 
open question that is outside the scope of this paper.

\subsection{Computation Caching}

\begin{figure}
\centerline{\epsfxsize=70mm \leavevmode 
\epsffile{example-net.eps}}
\caption{A simple belief network for demonstrating the relationship 
between Q-DAG reduction and computation caching.
The light-shaded node, \(C\), is a query node, and the
dark-shaded node, \(B\), is an evidence node.
\label{fig:cache}}
\end{figure}

Caching computations is another influential technique for optimizing inference
in belief networks. To consider an example, suppose that we are
applying the polytree algorithm to compute \(\pr(c,b)\) in the network of 
Figure~\ref{fig:cache}. Given evidence, say \(B\eq\on\), the algorithm will 
compute \(\pr(c,B\eq\on)\) by passing the messages shown in 
Figure~\ref{fig:msg2}. If the evidence changes to \(B\eq\off\), however, an 
algorithm employing caching will not recompute the message \(\pi_B(a)\) (which
represents the causal support from \(A\) to \(B\) \cite{pearl88b}) since the 
value of this message does not depend on the evidence on \(B\).\footnote{This
can be seen by considering the following expression, which is evaluated
incrementally by the polytree algorithm through its message passes:
\[ \pr(c,\evd) = 
\sum_b \pr(c \mid b) 
\underbrace{\lambda_B(b) 
\sum_a \pr(b \mid a) 
\underbrace{\pr(a)}_{\pi_B(a)}}_{\pi_C(b)}. \]
It is clear that the subexpression
corresponding to the message \(\pi_B(a)\) from \(A\) to \(B\) is independent of 
the evidence on \(B\).}
This kind of optimization is typically implemented by caching the values of 
messages and by keeping track of which messages are affected by what evidence.

\begin{figure}
\centerline{\epsfxsize=35mm \leavevmode 
\epsffile{msg-ex2.eps}}
\caption{Message passing when $C$ is queried and $B$ is observed.}
\label{fig:msg2}
\end{figure}

Now, consider the Q-DAG corresponding to this problem which is shown in 
Figure~\ref{fig:cache-reduction}(a). The nodes enclosed in 
dotted lines correspond to the message from \(A\) to \(B\).\footnote{More
precisely, they correspond to the expression 
\(\sum_a \pr(b \mid a) \pr(a)\).}
These nodes do not have 
evidence-specific nodes in their ancestor set and, therefore, can never change 
values due to evidence changes. In fact, numeric reduction will replace each 
one of these nodes and its ancestors with a single node as shown in  
Figure~\ref{fig:cache-reduction}(b). 

In general, if numeric reduction is applied to a Q-DAG, one is guaranteed the 
following: (a) if a Q-DAG node represents a message that does not depend on
evidence, that node will not be re-evaluated given evidence changes;
and (b) numeric reduction will guarantee this under any Q-DAG evaluation 
method since it will replace the node and its ancestor set with a single root 
node.\footnote{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 {\em depend} on evidence as well.}

\begin{figure}
\centerline{\epsfxsize=135mm \leavevmode 
\epsffile{example2.eps}}
\caption{A Q-DAG (a) and its reduction (b).
\label{fig:cache-reduction}}
\end{figure}

\subsection{Optimization in Belief-Network Inference}

Network pruning and computation caching have proven to be very influential
in practical implementations of belief-network inference. In fact, our own
experience has shown that these optimizations typically make the 
difference between a usable and a non-usable belief-network system.

One problem with these optimizations, however, is their algorithm-specific
implementations although they are based on general principles (e.g., taking 
advantage of network topology). Another problem is that they can make elegant 
algorithms complicated and hard to understand. Moreover, these optimizations 
are often hard to define succinctly, and hence are not well documented within 
the community.

In contrast, belief--network inference can be optimized by generating Q-DAGs 
using unoptimized inference algorithms, and then optimizing the generated
Q-DAG through reduction techniques. We have shown some examples of this
earlier with respect to pruning and caching optimizations.
However, whether this alternate approach to optimization is always feasible
is yet to be known. A positive answer will clearly provide {\em an 
algorithm--independent approach to optimizing belief--network inference}, 
which is practically important for at least two reasons. First, Q-DAG 
reduction techniques seem to be much simpler to understand and implement 
since they deal with graphically represented arithmetic expressions, without 
having to invoke probability or belief network theory. Second, reduction 
operations are applicable to Q-DAGs generated by any belief--network algorithm. 
Therefore, an optimization approach based on Q-DAG reduction would be more 
systematic and accessible to a bigger class of developers.


\section{A Diagnosis Example} \label{sec:example}

This section contains a comprehensive example illustrating the application 
of the Q-DAG framework to diagnostic reasoning.

\begin{figure}
\centerline{\epsfxsize=85mm \leavevmode 
\epsffile{car.eps}}
\caption{A simple belief network for car diagnosis.
\label{car-fig-r}}
\end{figure}

Consider the car troubleshooting example depicted in Figure~\ref{car-fig-r}.
For this simple case we want to determine the probability distribution
for the fault node, given evidence on four sensors:
the battery-, alternator-, fuel- and oil-sensors.
Each sensor provides information about its corresponding system.
The fault node  defines five possible faults:
normal, clogged-fuel-injector, dead-battery, short-circuit, and broken-fuel-pump.

If we denote the fault variable by $F$, and sensor variables by $\E$, then
we want to build a system that can compute the probability $\pr(f,\evd),$ 
for each fault \(f\) and any evidence \(\evd\). These probabilities represent 
an unnormalized probability distribution over the fault variable given 
sensor readings. In a Q-DAG framework, realizing this diagnostic system involves
three steps: Q-DAG generation, reduction, and evaluation. The first two steps
are accomplished off-line, while the final step is performed on-line. We now 
discuss each one of the steps in more detail.

\subsection{Q-DAG Generation}

The first step is to generate the Q-DAG. This is accomplished by applying the
Q-DAG clustering algorithm with the fault as a query variable and the sensors
as evidence variables. The resulting Q-DAG has five query nodes,
\(\qdpr(F= {\it normal}, \evd)\), 
\(\qdpr(F = {\it clogged\_fuel\_injector}, \evd)\), 
\(\qdpr(F = {\it dead\_battery}, \evd)\),
\(\qdpr(F = {\it short\_circuit}, \evd)\), and
\(\qdpr(F = {\it broken\_fuel\_pump}, \evd)\). Each  node
evaluates to the probability of the corresponding fault under any instantiation
of evidence. The probabilities constitute a differential diagnosis that 
tells us which fault is most probable given certain sensor values.

Figure~\ref{car-fig2} shows a stylized description of the Q-DAG restricted to 
two of the five query nodes, corresponding to 
\(\pr(F = {\it broken\_fuel\_pump}, \evd)\) and \(\pr(F= {\it normal}, \evd)\).
The Q-DAG structure is symmetric for each fault value and sensor.

\begin{figure}[tb]
\centerline{\epsfxsize=120mm \leavevmode 
\epsffile{car-dag-temp.eps}}
\caption{A partial Q-DAG for the car example, displaying two of the
five query nodes, {\it broken\_fuel\_pump} and {\it normal}.  
The shaded regions are portions of the Q-DAG that are shared by multiple query
nodes; the values of these nodes are relevant to the value of more than one 
query node. 
\label{car-fig2}}
\end{figure}

Given that the Q-DAG is symmetric for these possible faults, for clarity of
exposition we look at just the subset needed to evaluate node 
\(\pr(F = {\it broken\_fuel\_pump}, \evd)\). Figure~\ref{car-tree} shows a 
stylized version of the Q-DAG produced for this node. Following are some
observations about this Q-DAG. First, there is an evidence-specific node for 
every instantiation of sensor variables, corresponding to all forms of sensor 
measurements possible. Second, all other roots of the Q-DAG are probabilities. 
Third, one of the five parents of the query node 
$Pr(F= {\it broken\_fuel\_pump},\evd)$ is
for the prior on $F = {\it broken\_fuel\_pump}$, and the other four are 
for the contributions of the four sensors. For example, Figure~\ref{car-tree} 
highlights (in dots) that part of the Q-DAG for computing the contribution 
of the battery sensor.

\begin{figure}[tb]
\centerline{\epsfxsize=140mm \leavevmode 
\epsffile{car-tree.eps}}
\caption{A partial Q-DAG for the car example.
\label{car-tree}}
\end{figure}


\subsection{Q-DAG Reduction}

After generating a Q-DAG, one proceeds by reducing it using graph rewrite
rules. Figure~\ref{car-tree} shows an example of such reduction with a
Q-DAG that is restricted to one query node for simplicity. 
To give an idea of the kind of reduction that has been applied, 
consider the partial Q-DAG enclosed by dots in this figure.
Figure~\ref{car-tree1} compares this reduced Q-DAG with
the unreduced one from which it was generated. 
Given our goal of generating Q-DAGs that (a) can be evaluated as efficiently 
as possible and (b) require minimal space to store, it is important to see, 
even in a simple example, how Q-DAG reduction can make a
big difference in their size.

\begin{figure}[t]
\centerline{\epsfxsize=130mm \leavevmode 
\epsffile{battery-sensor.eps}}
\caption{Reduced and unreduced Q-DAGs for the car diagnosis example.
\label{car-tree1}}
\end{figure}


\subsection{Q-DAG Evaluation}

Now that we have a reduced Q-DAG, we can use it to compute answers to diagnostic 
queries. This section presents examples of this evaluation with respect to 
the generated Q-DAG.

Suppose that we obtain the readings dead, normal, ok and full for the 
battery, oil, alternator and fuel sensors, respectively. And let us compute the
probability distribution over the fault variable. This obtained
evidence is formalized as follows:
\begin{itemize}
\item [-] \(\qdevd({\it battery\_sensor}) = {\it dead}\),
\item [-] \(\qdevd({\it oil\_sensor}) = {\it normal}\), 
\item [-] \(\qdevd({\it alternator\_sensor}) = {\it ok}\),
\item [-] \(\qdevd({\it fuel\_sensor}) = {\it full}\).
\end{itemize}
Evidence-specific nodes can now be evaluated according to 
Definition~\ref{def:neval}. For example, we have
\[ \qneval[\esn({\it battery\_sensor}, {\it charged})] = 0,\]
and 
\[ \qneval[\esn({\it battery\_sensor}, {\it dead})] = 1.\]
The evaluation of evidence-specific nodes is shown pictorially in
Figure~\ref{car-tree2}(a). 
Definition~\ref{def:neval} can then be used to evaluate the remaining nodes:
once the values of a node's parents are known, the value of that node can be
determined. Figure~\ref{car-tree2}(b) depicts the results of evaluating other
nodes. The result of interest here is the probability 0.00434 assigned to the 
query node \(\pr({\it fault = broken\_fuel\_pump}, \evd)\).

Suppose now that evidence has changed so that the value of fuel sensor is empty
instead of full. To update the probability assigned to node \(\pr({\it fault =
broken\_fuel\_pump}, \evd)\), a brute force method will re-evaluate the whole
Q-DAG. However, if a forward propagation scheme is used to implement the node 
evaluator, then only four nodes need to be re-evaluated in
Figure~\ref{car-tree2}(b) (those enclosed in circles) instead of thirteen (the
total number of nodes). We stress this point because this refined updating
scheme, which is easy to implement in this framework, is much harder to
achieve when one attempts to embed it in standard belief-network algorithms
based on message passing.

\begin{figure}
\centerline{\epsfxsize=150mm \leavevmode 
\epsffile{car-instantiate.eps}}
\caption{Evaluating the Q-DAG for the car diagnosis example given evidence 
for sensors. The bar in (a) indicates the instantiation of the ESNs.
The shaded numbers in (b) indicate probability values that are computed by the
node evaluator. The circled operations on the left-hand-side of (b) are 
the only ones that need to be updated if evidence for the fuel-system sensor 
is altered, as denoted by the circled ESNs. 
\label{car-tree2}}
\end{figure}


\section{Concluding Remarks}
\label{sec:conclusion}

We have introduced a new paradigm for implementing belief-network inference that
is oriented towards real-world, on-line applications. The proposed framework 
utilizes knowledge of query and evidence variables in an application to compile 
a belief network into an arithmetic expression called a Query DAG (Q-DAG).
Each node of a Q-DAG represents a numeric operation, a number, 
or a symbol that depends on available evidence. Each leaf node of a Q-DAG 
represents the answer to a network query, that is, the probability of some event
of interest. Inference on Q-DAGs is linear in their size and amounts to a
standard evaluation of the arithmetic expressions they represent.

A most important point to stress about the work reported here is that it is {\em not}
proposing a new algorithm for belief-network inference. What we are proposing is a
paradigm for implementing belief-network inference that is orthogonal to 
standard inference algorithms and is engineered to meet the demands of
real-world, on-line applications. 
This class of applications is typically demanding for the following reasons:
\begin{enumerate}
\item It typically requires very short response time, i.e., milliseconds.
\item It requires software to be written in specialized languages, such as ADA,
C++, and assembly before it can pass certification procedures.
\item It imposes severe restrictions on the available software and hardware
resources in order to keep the cost of a ``unit'' (such as an electromechanical
device) as low as possible. 
\end{enumerate}
To address these real-world constraints, we are proposing that one compile a
belief network into a Q-DAG as shown in Figure~\ref{fig:soln} on and use a 
Q-DAG
evaluator for on-line reasoning. This brings down the required memory to that
needed for storing a Q-DAG and its evaluator. It also brings down the required 
software to that needed for implementing a Q-DAG evaluator, which is very
simple as we have seen earlier. 

Our proposed approach still requires a belief-network algorithm to generate a
Q-DAG, but it makes the efficiency of such an algorithm less of a critical 
factor.\footnote{We have shown how clustering and conditioning algorithms can 
be used for Q-DAG generation, but other algorithms such as SPI 
\cite{spi94b,spi90} can be used as well.}
For example, we show that some standard optimizations in belief-network 
inference, such as pruning and caching, become less critical in a Q-DAG 
framework since these optimizations tend to be subsumed by simple Q-DAG 
reduction techniques, such as numeric reduction. 

The work reported in this paper can be extended in at least two ways. First, further
Q-DAG reduction techniques could be explored, some oriented towards reducing the
evaluation time of Q-DAGs, others towards minimizing the memory needed to store
them. Second, we have shown that some optimization techniques that dramatically 
improve belief-network algorithms may become irrelevant to the size of Q-DAGs if
Q-DAG reduction is employed. Further investigation is needed to prove
 formal results and guarantees on the effectiveness of Q-DAG reduction.

We close this section by noting that the framework we proposed is also
applicable to order-of-magnitude (OMP) belief networks, where multiplication 
and addition get replaced by addition and minimization, respectively 
\cite{goldszmidt92a,darwicheUAI94b}. The OMP Q-DAG evaluator, however, is much
more efficient than its probabilistic counterpart since one may evaluate a 
minimization node without having to evaluate all its parents in many cases. 
This can make considerable difference in the performance of a Q-DAG evaluator.

\section*{Acknowledgements}
Most of the work in this paper was carried out while the first author was 
at Rockwell Science Center. Special thanks to Jack Breese, Bruce D'Ambrosio 
and to the anonymous reviewers for their useful comments on earlier drafts 
of this paper.

\appendix

\section{Proof of Theorem~\ref{theo:soundness}}
\label{app:proof}


Without loss of generality, we assume in this proof that all variables
are declared as evidence variables.
To prove this soundness theorem, all we need to show is that each Q-DAG
potential will evaluate to its corresponding probabilistic potential under
all possible evidence. Formally, for any cluster \(S\) and variables \(X\),
the matrices of which are assigned to \(S\), we need to show that
\begin{equation}
\qneval(\bigotimes_X \qn(\pr_X) \otimes \qn(\lambda_X))  = 
\prod_X \pr_X \lambda_X
\label{eq:proof}
\end{equation}
for a given evidence \(\qdevd\).
Once we establish this, we are guaranteed that \(\qdpr(X)(x)\) will
evaluate to the probability \(\pr(x, \evd)\) because the application
of \(\otimes\) and \(\oplus\) in the Q-DAG algorithm is isomorphic to the 
application of $*$ and $+$ in the probabilistic algorithm, respectively.

To prove Equation~\ref{eq:proof}, we will extend the Q-DAG node evaluator 
\(\qneval\) to mappings in the standard way. That is, if \(f\) is a mapping 
from instantiations to Q-DAG nodes, then \(\qneval(f)\) is defined as follows:
\[ \qneval(f)(x) \definedas \qneval(f(x)). \]
That is, we simply apply the Q-DAG node evaluator to the range of mapping \(f\).

Note that \(\qneval(f \otimes g)\) will then be equal to \(\qneval(f) \qneval(g)\). 
Therefore, 
\begin{eqnarray*}
\lefteqn{\qneval(\bigotimes_X \qn(\pr_X) \otimes \qn(\lambda_X))}  \\
& = & \prod_X \qneval(\qn(\pr_X)) \qneval(\qn(\lambda_X))  \\
& = & \prod_X \pr_X \qneval(\qn(\lambda_X)) 
\mbox{    by definition of \(\qn(\pr_X)\)}.
\end{eqnarray*}
Note also that by definition of \(\qn(\lambda_X)\), we have 
that \(\qn(\lambda_X)(x)\) equals \(\esn(X,x)\). Therefore, 
\begin{eqnarray*}
\qneval(\qn(\lambda_X))(x) 
& = & \qneval(\qn(\lambda_X)(x)) \\
& = & \qneval(\esn(X,x)) \\ 
& = & \left\{ 
\begin{array}{ll}
1, & \mbox{if \(\qdevd(X) = x\) or \(\qdevd(X) = \unk\)} \\
0, & \mbox{otherwise}
\end{array} 
\right. \\
& = & \lambda_X(x).
\end{eqnarray*}

Therefore, 
\[ \qneval(\bigotimes_X \qn(\pr_X) \otimes \qn(\lambda_X))  = 
\prod_X \pr_X \lambda_X.~\eproof
\]

\bibliography{/home/darwiche/latex/adam,/home/darwiche/latex/change,/home/darwiche/latex/moises}
\bibliographystyle{/home/darwiche/latex/theapa}




\end{document}







