Figure: A simple belief network for car diagnosis.
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.