Consider designing a car to have a self-diagnostic system that can alert the driver to a range of problems. Figure 1 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.

**Figure:** A simple belief network for car diagnosis.

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

**Figure:** 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
*on-line* to compute the probability distributions over fault variables; in
the compiled approach, the belief network, fault variables and sensor variables
are compiled *off-line* to produce a Q-DAG, which is then evaluated *
on-line* using sensor values to compute the required distributions.

**Figure:** The proposed framework for implementing belief-network inference.

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
*low* and then
run it later with the variable set to *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 *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 4.[+]

**Figure:** A belief network (a); and its corresponding Query-DAG (b).
Here, is an evidence variable,
and we are interested in the probability of variable .

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 3. 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 [Li D'AmbrosioLi D'Ambrosio1994, Shachter, D'Ambrosio, del FaveroShachter et al.1990]; 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 *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 *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,[+]
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 [*] 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 [*] 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 5 contains a detailed example on the application of this framework to diagnostic reasoning. Finally, Section 6 closes with some concluding remarks.

[Next] [Up] [Previous]