An Inference Net Compiler for the PROSPECTOR Rule-Based Consultation System

1. Introduction

Typically a rule-based consul t~tion system (which we shall call an expert system) 11 is used in an interactive mode as a consultant: ~ user volunteers information from which conclusions are drawn, or a goal is pursued by the system and appropriate quest ions asked, or there is a combination of both kinds of system interaction. The end result is that the system presents a conclusion about some hypothesis to the user, based on information provided by him.

By contrast, a noninteractive mode for an expert system can also be useful. Noninteractive situations arise when information is presented to the system in Large doses, rather than parceled out piecemeal by an interactive user. Typical applications include data-base screening, in which the system must process a Large number of records; handling map data, in which the system must be run on each of a large number of cells covering the map; and sensitivity analysis of the system, in which answers provided by the user are changed incrementally. These noninteractive applications are characterized by the fact that the type of input is known before the system is run, but the exact values are not. This paper describes a method for compiling a certain type of expert system into an efficient linear form

under these conditions.

2. Exoert Systems

Many expert systems use a production system to encode the knowledge gleaned from experts [ 1, 4 ). Such a production system consists of a uata base of assertions; a set or production rules of the form <antecedent> => <consequent>; a control progr3111 that decides on an inference strategy; and an inference mechanism to propagate the effects of input data. The last two functions are often integrated into a single program called the production system interpreter.

I This research was funded in part by USGS Contract No. 14-08-001-15985 and NSF Grant No. AER77-04499.

II Examples of such systems are (2, 6).

The compilation technique described here developed for a restricted class probabilistic production systems' with following properties: was of the

1. No variables ~re bound in the production rules.
2. There are no inference loops (e.g., A => B, B => C, C =>A).

Given these restrictions, a set of productions can be converted into an inference net with no loops: a portion of this net is illustrated in Figure 1.

Productions are indicated by arrowed lines. At the leaf nodes of the net are input assertions to which the user (or some other input source) can assign probabilities. These probabilities are propagated from the leaf nodes through intermediate hypotheses to the root hypotheses.

3- Ib4 Compilation Teghnigue

A compilation technique for inference nets was developed to take advantage of the noninteractive nature of the input. The assumption of a noninteractive mode has two parts:

· Probabilistic production systems allow

probabilistic inference by attaching probabilities rather than a binary truth value to assertions, and allowing production rules to have varying strengths in updating an assertion. See, e.g. , ( 2), ( 6).

1. "Batch" assumption: all input to the leaf nodes of the inference net is available at the start of the run.
2. Explicit goal assumption: the hypotheses for which results are to be computed are known at the start of the run.

The consequences exploited in the follows: of these assumptions compilation technique are as

Elimination 2! Control Strategy Oyerhead Starting from a set of root goal nodes, the control program normally searches down a path in the inference net to an input leaf node; it then asks the user for a probability for that node. The control strategy is typically goal-directed; it tries to establish a query order for the leaf nodes that is both efficient for hypothesis discrimination and meaningful to the user.

Under the noninteractive assumption of an explicit goal set, it is possible to eliminate the goal-directed strategy entirely. Since the leaf nodes for which the probabilities are known are given in advance, there is no need to search for them in the noninteractive mode. Inferencing becomes data-directed from the input leaf nodes, rather than goa l-direo ted from the hypothesis nodes.

Propagation -- In the interactive mode, the consequences of new in format ion on a leaf node are prop'lgated immediately throughout the net. Obviously, the probability for a hypothesis node may be calculated many times through this procedure; for example, node A may be updated a total of four times once each time the effects of changing the probabilities of nodes E, F, C, and Dare propagated .

If all probabilities on leaf nodes are available at the beginning of propagation, it is poss i ble to devise a propagation scheme in which the probability of each hypothesis node is computed only once, in a single bottom-up pass. Because it has no loops, the inference net defines a partial ordering of nodes from the leaf nodes to the root node. In this ordering, for ·example, the probability of node B must be computed before node C, and both of them before A. The compilation technique converts the partial ordering defined by the net into a linear ordering. In the compiled net, probabilities on hypothesis nodes are computed in this linear order, and the results saved in temporary cells for later calculations .

The input to a compiler embodying this compilation technique is .an inference net of the type described above. Its output is a linear (i.e., loop-free) code sequence that calculat es the probability of the root hypothesis, given a data set for the leaf nodes . This sequence simulates the action of the net interpreter on the net in a noninteractive mode. The amount of time taken to execute the code can be estimated as:

where the c·s are constant for a given machine executing the code, and the N's are defined as :

I NL = number of logical productions

NP = the number of probabilistic productions

4. I1m1o& Results ~ A Compiler Implementation

A compiler for the inference nets of the PROSPECTOR [2] expert system was implemented to test the practicality of the compilation technique. It compiles PROSPECTOR nets into a linear machine code sequence . A short initializing sequence is also included to enable linking of the compiled inference net to any set of inputs; thus the inference net need only be recompiled if the net structure has changed.

The implementation of the compiler follows in a straightforward way from the compilation techniques of the last section. Total compilation time is proportional to the number of productions in the net; a nominal amount of time is spent processing each production.

I Logical productions are logical combinations of assertions, e .g., the AND node in Figure 1.

The compiler W3.S tested using a medium-scale PROSPECTOR inference net comprising some 94 nodes and 105 productions (59 of them were logical productions). This inference net encoded expert knowledge about geological characteristics of a favorable exploration drilling site for a type of copper mineral deposit (3].

In a typical application, dat3. for 13 of the input nodes was extracted from geological maps of an area. The area was partitioned by a 128 x 128 grid into 16,384 map cells, producing input data for 16,384 runs of the compiled model. The resulting probabilities on the root hypothesis were recombined to yield Figure 2.

Note: The brightness of each individu3.l pixel indicates the favorability of the root hypothesis for that pixel. The bright line is · the actual ore body outline. The area is Island Copper in British Columbia, Canada [3].

Timings for this run are given in Table 1. The estimated running time given by equation 1 is also 1 listed, and agrees well with the actual time. These timings indicate typical speeds that we have achieved under the noninteractive assumptions.

For comparison, the inference net interpreter was run using the data set from a single pixel. Timings for a typical interpreted run are also given in Table 1. For this specialized application the compiled version of the net is about four orders of magnitude faster than the net interpreter in the test case.

I CL and CP were estimated to be 6.0 us and 44 us, respeCtively, by looking up machine instruction times in (5]. Experience with many runs indicates that equation 1 is a reliable estimator of running time.

Table 1

5. Conclusions

A compiler for PROSPECTOR-type inference nets has been described. It generates code that is approximately four orders of magnitude faster than the net interpreter. Its efficiency and practicality for noninteractive use has been demonstlrated in an application using digitized map data as input.

As currently conceived and implemented, the compiler suffers from the drawback of not being able to handle production rules containing variables. A compiler that produces linear code is probably inadequate for dealing with arbitrary variables in production rules. However, the use of variables in the productions used by such expert systems as PROSPECTOR and MYCIN is very Limited. We are exploring restrictions on the use of variables in productions that will make compilation techniques for variables feasible.