HUGIN - A Shell for Building Bayesian Belief Universes for Expert Systems

1 Introduction

In recent years, focus has been put on the development of expert systems based on a probabilistic scheme where the structure of the domain knowledge is represented in a di­ rected graph. Contrary to earlier probabilistic attempts, this approach makes the domain structure explicit and utilizes the topology of the graph in the control of the inference. The probabilistic scheme has- as opposed to rule based and logic based systems-an intrinsic distinction between so-called 'ex­ pectation evoked' and 'explanation evoked' inference [Pearl,

*HUGIN stands for Handling Uncertainty In General Inference Network. Coincidentally, according to Norse mythology, Hugin and Munin are two ravens, whispering intelligence into the ears of the god Odin. MUNIN is also used as acronym for an expert system for electromyography.

1988]. This knowledge representation has been termed dif­ ferently in the literature: Bayes belief net [Pearl, 1986a], causal probabilistic network [Andreassen et al., 1987], causal networks [Lauritzen and Spiegelhalter, 1988], probabilistic causal network [Cooper, 1984], influence diagrams [Howard and Matheson, 1981] , and so on.

A causal probabilistic network, which is the term we have chosen to use in this paper, is-at a qualitative level-a graph where the nodes represent domain objects and the links be­ tween nodes represent causal relations between these objects. At a quantitative level, the relations expressed by the links are represented by conditional probabilities. Together with methods derived from Bayesian decision theory, this formal­ ism offers a consistent means of handling uncertainty inherent in expert systems [Horvitz et al., 1988].

The key issue of this formalism is the ability to re­ duce the computation to a series of local calculations us­ ing only variables obtainable from one object and its neigh­ bors in a graph structure. Hereby a calculation of the global joint probability distribution is avoided. Furthermore, the graph representation-showing explicit dependencies and independencies- is a powerful tool in the knowledge acquisi­ tion and verification process [Pearl and Paz, 1987].

When the network is singly connected (i.e., at most one path between pairs of nodes is allowed), Kim and Pearl [1983] gives a conceptually simple scheme for passing mes­ sages along links between nodes in the causal probabilistic network. Unfortunately, not all real world problems can be modelled as a singly connected network, and a multiply con­ nected network (i.e., more than one path between pairs of nodes may exist) is required in order to catch the facets of the domain. Several schemes are proposed in the literature such as reasoning by assumption [Pearl, 1986], and value pre­ serving arc-reversing [Shachter, 1988].

This paper outlines the expert system shell HUGIN. This shell provides (1) a set of tools for creation of a causal proba­ bilistic network which simultaneously creates a graphical in­ terface to the domain model, and (2) a set of tools for entering quantitative information about the state of the domain and for propagating this in the network. Behind the scenes, the Algebra of Bayesian Belief Universes is used. This scheme [Andersen et al., 1987, Jensen, 1988a, Jensen et al., 1988, Olesen and Andersen, 1988], which is a substantial simpli­ fication of [Lauritzen and Spiegelhalter, 1988], allows propagation of evidence in acyclic multiply connected networks. The algebra is conceptually as simple as the method of Kim and Pearl [1983] for singly connected causal probabilistic net­ works. This simplicity is achieved by transforming the multi­ ply connected network into a set of belief universes organized as a tree, a junction tree, and by providing the operations for propagation of information between belief universes in the tree. The basic operation is calibration of one belief uni­ verse with another. Calibration is the basis for two oper­ ations: Distrib·uleEvidence and CollectEvidence, which dis­ tributes evidence from one belief universe to all other belief universes, and collects evidence to one belief universe from all other belief universes, respectively. The idea. of a separate representation for propagation purposes is also used in the approaches of Dechtcr tl a!. [1988] and Sltafer and Shenoy [1988].

In order t.o illustrate the HUGIN shell, the next section deals with an example from genetics. The reader is guided through the major steps from specifying the model to mak­ ing it operational, and finally inferring beliefs based on da.ta entered into the model. In Section 3, the use of the algebra of Bayesian belief universes is outlined. Section 4 contains an overview of the HUG IN shell architecture, and finally Sec­ tion 5 discusses problems in applying HUGIN to real world applications, exemplified by MUNIN, an expert system for electromyography.

2 An example: Breeding

We will demonstrate the HUGIN shell by going through an example taken from genetics (inspired by Spiegelhalter [1989]). The example concerns breeding and would typically be found within animal husbandry, but in order to make it more attentive, we state it in terms of human beings:

Florence and Gregory are about to reproduce. How­ ever, Gregory is Florence's nephew, and in the an­ nals of Bartholomew, the father of Florence and grandfather of Gregory, a life-threatening disease has haunted. The disease is caused by a domi­ nant allele A, and appears in a rather late stage of the individual's life-time. Bartholomew married twice, hence Florence and Gregory's mother are half-siblings. Neither Florence nor Gregory, their parents, nor Gregory's grandmother have shown any signs of the disease. What is the risk that their child will inherit the fatal characteristic?

2.1 Qualitative modelling

The first step in a HUG IN session is to formulate the problem in terms of a causal probabilistic network. The genealogical structure of our example is shown in Figure l.

Each individual is represented by name, and parent-child relations are represented by arrows from parent to child. Note that the diagram contains two different paths from Bartholomew to H: via Eliza and Gregory, and via Florence.

In general, we are interested in determining the genotype of the individuals. To each individual, we associate a node labelled with his/her initial and as states the possible geno­ types identified by the combination of alleles. Hence, each individual is of exactly one of the genotypes AA, Aa, or aa.

In our case, where one allele is dominant , this means that the genotypes AA and Aa are carriers of the disea.se, whereas aa is not. \Vhat can be observed is whether the disease is present or not. but this can only be determined when the individual has rea('hf'd a mature age due to the sneaky character of the discasc. 1 In order to be able to enter relevant information on obscn·ed occurrences and ask for expectations of the disease, we add disease nodes to the elder and the coming generation. These nodes, labelled by the individuals initial with index d, have two possible states, yes and no, corresponding to the presence and absence of the disease, respectively.

At this point, the qualitative structure of our problem is determined, and we invoke the HUGIN shell. The shell is menu-driven, and most operations are done by mouse selec­ tion. Figure 2 shows the main screen with the model en­ tered. Here a domain specific window labelled Breeding is created, and the model is constructed: this is done by se­ lecting the Create domain entry on the main menu (attached to the HUGIN icon). All nodes and links are entered, and the corresponding graphical symbols are created. For each node, a display name and the states are typed in. Entering states for the disease nodes is not necessary though, as the states yes and no apply as default. If so desired, the domain model can be saved at any point, for later continuation by reloading.

1 The reader may feel a need for a discussion of temporal relationships appropriate, but this is outside the scope of this paper.

2.2 Quantitative modelling

Let us complete the model by specifying the numeric part of the links. This is done by means of conditional probability tables. For each node, we give a conditional probability for each state given the states of its parents. Thus for the disease nodes, we have tables as specified in Table 1.

For the parent-child relations, we get tables as shown in Table 2, where parents P1 and P2 have offspring C. Since top­ nodes do not have any parents (in our model that is), their ta­ bles degenerate to a priori values for their genotypes. Assume that the conditions for Hardy-Weinberg equilibrium are ful­ filled, and let the frequency of A be p and the frequency of a be q (p + q = 1 ). Then the a priori probabilities for the geno­ type of any individual N is P0 (N) = (p 2 , 2pq, q 2 ). For p = 0.01, we gel P(A) = P(C) = (0.0001,0.0198,0.9801). For Bartholomew, we estimate P(B) = (0.0025,0.2500,0.7475) as his grandmother was known to suffer from the disease.

We will now enter these considerations into HUG IN. Select the Specify table entry from the menu attached to the node H in the Breeding window, and a new dialogue window pops up (Figure 3).

A skeleton for the table is automatically generated, and the numbers are typed in. Now the domain model is com­ plete and a selection of Compile will generate an operational run-time system. Although this last step appears simple, it actually holds the key to the success of the method. What happens is that the state space of the model is factorized in order to allow ·for efficient computations. This is discussed in more detail in Section 3.

2.3 Interactive problem solving

Asking for the belief in node Hd, we see a risk of 10% (Fig­ ure 4) for lf being a victim of the disease. This seems reason­ ably low, and we can give Florence and Gr<:>gory our blessings. Unfortunately, whi le structuring the model, Bartholomew, our young lovers' common ancestor, has caught the disease. To see whcth<:>r this affects our approval of the marriage, let us enter this new fact into our model. Select Set. state on Ed a.nd enter the fact; then update the l)(:'liefs by selecting Prop­ agate.

A request for belief in Hd now yields a risk of 36%, forcing us to implore Florence and Gregory to reconsider their plans.

Suppose that the information about Bartholomew's alleged misfortune was wrong, but that instead Alison showed the disease. We would then Retract the finding on Ed (returning to the a priori belief for B) and follow the described procedure on Ad· Alternatively, we could choose Initialize and repeat as above. In both cases, we find H's risk to be 22%.

At this point other possibilities could be investigated, but we will leave our friends with their worries here and close the section.

3 Behind the scenes

In the example of Section 2, several things happen behind the scenes, but the user does not need to worry about that unless the model has a complexity that requires manual intervention (see Section 5).

In this section, we outline the most important features from behind the scenes. In [Lauritzen and Spiegelhalter, 1988] and in the discussion by Jensen [1988b] , and by Olesen and Andersen [1988] in the same article, an exposition of the methods can be found. A full description of the methods is given in [Jensen et al., 1988] and in [Jensen, 1988a].

3.1 Transformation of the causal network

The inference in a causal network is in HUGIN not done directly in the network. Instead, the domain represented by the network is partitioned into a set of subdomains-called belief universes.

A belief universe U consists of a set of nodes, denoted lUI, and a belief table For reasons to become clear soon, the node sets are called cliques. A belief table is a non-normalized table for the joint probabilities of the belief space.

The construction of a system of belief universes, equivalent to the original domain model, consists of the following steps:

• Form thf moral graph: For each node in the network, add links between all of its parents. Drop the directions.
• Triangulate /II( moral graph: A graph is triangulated if all cycles or length > :3 have a cltord. :\dd links to the moral graph unl i I a t: riangulated graph is obta.i ned.
• Form tin system of bflicf uui1;crses: The node sets are the cliques of the triangulated graph (a clique is a max­ imal set of nodes, all of which are pairwise linked). The initial belief tables are calculated as appropriate prod­ ucts of the condi tiona.! probability tables (described by Lauritzen and Spiegelhalter [1988]).
• Organize the system as a junction t1·ee: Links between belief universes are introduced. This is done such that a tree with the following property results: For all uni­ verses U, V, each belief universe on the unique path be­ tween U and V contains lUI n lVI· In Figures 5 and 6, a junction tree for the domain from Section 2 is given. As proved by Jensen [1988a], a junction tree can be con­ structed by a maximal spanning tree algorithm.

All steps except the second are deterministic: There is only one moral graph, and the set of cliques of a triangulated graph is unique. There may be several junction trees, though, but the differences are not (at this point) essential.

The second step-the triangulation-is not trivial. There is a wide range of literature on triangulation [Rose et al., 1976, Yannakakis, 1981, Tarjan· and Yannakakis, 1984, Kong, 1986], and it is an NP-complete problem to find a trian­ gulation giving the minimal total table size [Gavril, 1977]. In HUGIN, the algorithm used for triangulation is maxi­ mum cardinality search [Tarjan and Yannakakis, 1984]. An algorithm- giving much better results on sparse graphs- has been constructed [Jensen and Kjrerulff, 1989] and will be in­ tegrated into the next version of HUGIN.

3.2 Propagation of evidence

A belief table is a non-normalized assessment of joint prob­ abilities for a clique. Let U be a belief universe with belief table B, and letS C lUI· An assessment of joint probabilities for S' can be obtained from B by summing up all beliefs in B for S. This operation is called marginalization. In particular, the belief i11 a. single node can be obtained by marginalization in the normalized ta.ble of any belief universe containing it.

Evidence is transmitted bet.ween belief universes through the calibration operation. A belief universe U calibrates to another belief universe Vas follows [Jensen et al., 1988]:

1. Calculate the belief table for IU In IV I by marginalizing the belief table of U.
2. Calculate the belief table for the same intersection by marginalizing in V.
3. Multiply the belief table for U by the ratio of the tables achieved by (2) and (1) (i.e., the table achieved by (2) is divided by the table achieved by (1)).

In HUGIN, an object oriented style is used: Each belief universe is an object holding its own data and its own meth­ ods. They communicate only with neighbors in the junction tree.

Calibration is the local propagation method. For a global propagation, the evidence is propagated to all belief universes through the junction tree.

There are two ways of propagating evidence. A forward propagation performed by the operation DistributeEvidence, and a backward propagation performed by the operation Col­ lectEvidence.

DistributeEvidence is used when evidence from a single belief universe must propagate to the entire system: Evi­ dence is transmitted to neighbors, and their DistributeEv­ idence method is called (see Figure 5). CollectEvidence is used when evidence from the entire system must be propa­ gated to a single belief universe: U asks neighbors to Col­ lectEvidence, and then U makes a multiple calibration to them [Jensen et al., 1988] (see Figure 6).

When findings have been entered into more than one belief universe, they can be propagated to the entire system by a call to CollectEvidence, followed by a call to DistributeEvi­ dence from an arbitrary belief universe.

There are other methods for calculation of probabilities in networks with loops [Pearl, 1988, Shachter, 1988]. These methods also contain graph manipulations with a potential for a combinatorial explosion. These manipulations are per­ formed every time evidence is propagated in the causal net­ work. The methods in HUGIN have the advantage that he graph manipulations are performed once and for all when the graph is triangulated. When the junction tree has been con­ structed, an upper limit on time and space requirements for evidence propagation can easily be estimated.

In general, the task of probabilistic inference in causal net­ works is .NP-hard [Cooper, 1987]. The methods in HUGIN makes it unnecessary to solve an .NP-hard problem every time evidence is propagated. Instead the .NP-hard problem is tackled in the construction phase, where much effort can be devoted to finding optimal solutions.

4 Schematic overview of HUGIN

A typical BUGI\' session is divided into three subtasks: (1) Creation of a domain model, (2) generation of a run­ time system. am! (:3) the actual problem solving. These tasks must be performed sequentially, but the session can be sus­ pended at any point, and resumed later. The HUGlN shell is organized in a modular fashion as i11dicatcd in Piguw I .

The graphical interface module does all the necessary book-keeping and provides access to facilities for creation, saving, loading, and deletion of domains. The editor module offers facilities for creating and editing a causal probabilis­ tic network, i.e., creation and deletion of nodes and causal links, creation and editing of conditional probability tables etc. The compiler module creates a junction tree in which all calculations are done ( cf. Section 3.1 ). The inference module maintains a set of current beliefs in all nodes in accordance with entered findings.

The HUGIN shell is implemented in C, and the graphical interface is done in NeWS. 2

5 The MUNIN networks

So far we have illustrated the use of HUG IN only by means of a simple example. In the ESPRIT project P599: "A Knowl­ edge Based Assistant for Electromyography" [Andreassen et al., 1987, Andreassen et al., 1989, Olesen et al., 1989], large networks are being constructed in order to diagnose muscle and nerve diseases. These nets constitute the MUNIN 3 ex­ pert system.

In MUNIN, we are dealing with networks consisting of several hundred nodes. Handling networks on this scale of size raises new problems. The main problem concerns space and- as an implication hereof- time. The automatic trian­ gulation in HUGIN is achieved by the maximum cardinality search algorithm. This method is sufficient for small prob­ lems, but it is inadequate for large networks as it produces unnecessarily large belief universes.

2 NeWS™ is a trademark of Sun Microsysterns , Inc.

3 MUscle and Nerve Inference Network.

As an example, one of the nets in MUNIN consists of .57 nodes, having from 2 to 21 states. In this network, at least one belief universe consisting of 14 nodes is created. This results in a. huge belief table, and hence implies slow and space consuming propagation. The best known cover­ ing of this net consists of two 8-node belief universes and 4:3 other belief universes, giving a total size of about 2.2 million numbers in the belief tables.

6 Conclusion

We ha1-c prcscuted a new expert system shell for modelling dontains by causal probabilistic networks. The main achif'l·c­ ment is the handling o(" lllUitipJy connected networks by t ransfornwlion to a tree structure where t.he inference can be done efficiently. The shell, whi ch employs the newest re­ search results, has proved its capability to handle domain models of non-trivial size as exemplified by the MUNIN ap­ plication.

HUGIN is now a well-suited tool for construction of research-like expert systems. However, much work still needs to be done before a full-size expert system shell is con­ structed. In particular, the following ideas and functional­ ities are under investigation and development:

• detection of conflicting evidence
• explanation facilities
• search for crucial findings
• planning
• learning
• extension to continuous variables

Acknowledgments

We thank David J. Spiegelhalter and in particular Steffen L. Lauritzen for the great inspiration they have given to this work.

V/e are indebted to our colleagues in the MUNIN project, Steen Andreassen, Uffe Kj rerulff, Annelise Rosenfalck, An­ ders R. S(<'lrensen, and Marianne Woldbye, for many valuable discussions.