An Analysis of ATMS-Based Techniques for Computing Dempster-Shafer Belief Functions

1 Introduction

To bridge the gap between the claimed lack of a "logical semantics" in uncertainty calculi and the lack of notions of uncertainty (claimed essential to modeling human rea­ soning) in logic, several attempts have been made to integrate formal logic with an uncertainty calculus. In this paper the relationships between an uncertainty cal­ culus, Dempster Shafer Theory, and propositional logic are shown.

It has been proposed that Dempster Shafer (DS) The­ ory rivals Probability Theory in expressive power and ef­ fectiveness as a calculus for reasoning under uncertainty. However, because of the computational complexity as­ sociated with computing DS Belief functions, only sub­ sets of the full problem domain expressible in DS The­ ory have been implemented, with the exception of recent Assumption-based TMS (ATMS) implementations. The number of subsets of a set of propositions e increases ex­ ponentially with I e I, and given that the DS normalizing function can sum over all of these subsets, computing a single normalization function can be computationally ex­ pensive. The total space necessary to comlute DS belief functions over a set of n propositions is 12 I = 2 2 " in the worst case.

"The author .completed this research with the support of the University of British Columbia Center for Integrated Computer Systems Research, BC Advanced Systems Insti­ tute and NSERC grants to A.K. Mackworth.

Examples of such restricted implementations include work by Shafer and Logan and by d'Ambrosio. Shafer and Logan [1987] have implemented DS Theory re­ stricted to the case of hierarchical evidence, based on proposals by Barnett [1981] and Gordon and Short­ liffe [1985] . D'Ambrosio [1987] has implemented DS theory for the restricted case defined by the Support Logic Programming of Baldwin [1985]. D'Ambrosio at­ taches a simplification of the Dempster-Shafer uncer­ tainty bounds to ATMS labels.

Laskey and Lehner [1988], Provan ([1988b], [1989a]) and Pearl [1988] have independently extended the ATMS with the full DS theory in similar manners. Such an extension represents a synthesis of the symbolic (logic­ theoretic) ATMS representation and the numeric (set­ theoretic) DS Theory representation. However, there has been no analysis of the underlying theoretical foun­ dations or the complexity of this DS theory implemen­ tation.

This paper describes the theoretical and computa­ tional issues raised by extending an ATMS to compute DS Belief functions without significantly compromising the semantic clarity or computational properties of ei­ ther. This extension is motivated by the need to intro­ duce a weighting system into the ATMS, and to improve the poor performance of the ATMS as observed in prac­ tice and predicted by the average-case results of Provan [1989b] . Existing ATMSs cannot rank hypotheses, but the incorporation of DS Theory allows hypotheses to be ranked and offers efficiency improvements, such as the ability of the Problem Solver to prune the search space by identifying and focusing search only on highly likely partial solutions. Using a graph theoretic formulation of the ATMS we show that simply weighting the edges of the graph corresponds to a representation from which DS Belief functions can be computed. Such a graph theoretic formulation provides clear intuitions into the properties of symbolic ATMS-based DS algorithms and their relationship to the computation of network relia­ bility [Agrawal and Barlow, 1984].

The complexity of the problems solved when using the ATMS to compute DS Belief functions is also defined.

Such an analysis ,identifies the sources of intractability in computing OS Belief functions, and explicitly shows why most implementations are of particular restrictions, such as hypertree embeddings [Shenoy and Shafer, 1988], [Shafer and Logan, 1987]. Such theoretical results are supported by empirical evidence (e.g. as pointed out in [Provan, 1986], [Ball, 1986]) which indicates that only moderately-sized problems can be computed efficiently. To counter such intractability, approximation methods for computing the full OS Theory, and not for restric­ tions of the theory are proposed.

This paper is organized as follows. Section 2 re­ views the theoretical basis of OS theory. Section 3 presents three complementary theoretical formulations of the ATMS based on logic, Boolean expression mini­ mization and graph theory. The correspondence between the graph theoretic ATMS formulation and OS theory is shown. Section 4 describes the ATMS-based OS theory algorithm and Section 5 the complexity of the underly­ ing problems. Finally, in Section 6 the conclusions of this study are stated.

2 Dempster-Shafer Theory Review

Many good descriptions of Dempster-Shafer (DS) theory exist, e.g. [Dempster, 1968], [Shafer, 1976]. We assume familiarity with OS theory, state a few basic relation­ ships, and refer the reader to the references.

In OS theory, weights are assigned to subsets as well as elements of a mutually exclusive set of focal propositions a. A mass function u : 2 8 -+ (0, 1) assigns weights to subsets fJ of a subject to the following properties: u(fJ) E [0, 1], E1ce u(fJ) = 1 and u(0) = o.

One measure in OS theory which is derived from this mass function is Belie/, the degree of belief in proposition subsets from which a proposition (} can be proven:

Dempster's Rule of Combination defines an updated mass function for a proposition (} provable in terms of ()i and (Ji, for all fJ,fJi,(Jj ~ e, as:

The Belief function {!' is also denoted as Belt 9 Be/2 · The numerator assumes independence of propositions. Viewed in set-theoretic terms, this is simply "summing'' the mass functions of all sets in which (} is provable. 1 The denominator of Equation 2 is a normalizing term, given that OS Belief is assigned only to non-contradictory sub­ sets.

3 Theoretical ATMS Formalization

The ATMS [de Kleer, 1986] is a database management system which, given a set E of propositional clauses, computes a label, .C(z), for each database literal z . .C(z) summarizes the "proofs" for z in terms of a Boolean for­ mula consisting of assumptions only. The assumptions, which are denoted by .A = {A1, ... ,At}, are a distin­ guished subset of the database literals and are the prim­ itive data representation of the ATMS with which the derivation of all other literals is recorded~

1 DS Theory thus has both underlying set-theoretic and logic-theoretic notions.

The ATMS records contradictions in terms of a con­ junction of assumptions called a nogood. By ensuring null intersections of all labels with the set of nogoods, the ATMS maintains a consistent assignment of labels to database literals. The ATMS can incrementally up­ date the database labeling following the introduction of new clauses. It does this by storing the entire label and nogood set to avoid computing them every time they are needed.

A typical problem for which an ATMS is used is cir­ cuit diagnosis, such as that done by GDE [de Kleer and Williams, 1987]. The circuit analyzed in [de Kleer and Williams, 1987] consists of multipliers M11 M2 and M3 and adders A1 and A2, as shown in Figure 1. Assumptions can be: (1) each component is working,

where W A; signifies that adder Ai is functioning cor­ rectly, and WM, signifies that multiplier Mi is function­ ing correctly; or (2) input data, e.g. A = 3, B = 2, etc. In the course of diagnosis, an assumption like WM 2 , i.e. "M2 is working", may be proved incorrect. For the circuit in Figure 1, the output at F is 10 instead of 12, implying that some combination(s) of M1, M2, Ms, A1 and A2 is(are) faulty. In GDE, the ATMS identifies hy­ pothesized sets of circuit components whose faulty be­ havior could cause discrepancies between predicted and observed circuit measurements. Taking observations at points like X, Y or Z narrows the set of diagnoses con­ sistent with the observations and guides future decisions about where to make further readings. A solution con­ sists of a set of faulty multipliers and adders which ex­ plains all the observations.

Given the set of input clauses and assumptions, the ATMS computes what de Kleer and Williams call minimal conflict sets, which are the labels for circuit malfunctions. The two conflict sets are represented logically as -.(WA 1 1\ WM 1 1\ WM,) and -.(WA 1 A WA, A WM 1 A WM 3 ). Hence, the malfunction­ ing of the circuit shown in Figure 1 can be explained by the simultaneous malfunctioning of A1, M1 and M2, or that of A1, A2, M1 and Ms.

We now present three complementary methods of viewing the problems solved by the ATMS. We first con­ sider the two frameworks traditionally used to formal­ ize the ATMS, namely propositional logic and Boolean algebra. We then show the equivalence of a graphical framework.

3.1 Logic Formulation

The input alphabet (using terminology introduced in [Reiter and de Kleer, 1987]) is represented by a set x = { Zl, ... , Zn} of propositional symbols. A proposi­ tional literal is a propositional symbol or its negation. A propositional clause consists of a finite disjunction of propositional literals with no literal repeated, e.g. z1 V z2 V zs V ... V z~c V z, k 2: 0. 2 z1, z2, ... , z~c are called the antecedents of z, ant(z), in keeping with ATMS ter­ minology.

We define an environment E to be a set of assumptions and a context C to be the set of literals derivable from the assumptions in E given the clauses.

The input consists of a set E = {E1, ... ,E1} of Horn clauses, referred to in [de Kleer, 1986] as justifications. A Horn clause is a clause with at most one unnegated literal.

The ATMS's operation consists of two distinct phases, label manipulation and interpretation construction, which is described below.

Label Manipulation: In the label manipulation phase, for each htera:I the ATMS maintains a label, which is a set of environments in which the literal can be proven. A typical label is {{Al,As,At},{As,A6}}, showing two environments. In logical terms, the Boolean expression for the label is (A1/\ As/\ At) V (As/\ A6), or the disjunction of the environments. Each environment in the label for Xi is defined in terms of a minimal sup­ port clause~· for Xi, and is given by C = {1\AjE.A Aj I (V AjE.A Aj) is a minimal support clause of E}. ~ is a support clause for Xi with respect to E if E ~ ~. Xi U ~ does not contain a complementary pair of literals (i.e. both Xj and Xj), and E f= Xi U ~. C is a minimal sup­ port clause for Xi with respect to E if no proper subset of e is a support clause for Xi with respect to E. A closely related type of clause, a prime implicate,s is defined as follows: a prime implicate of a set E of clauses is a clause 1r such that (1) E f= 1r, and (2) for no proper subset 1r 1 of 1r does E f= 1r 1 · The relationship between the label (minimal support clause) for a literal x and a prime im­ plicate for Horn clauses is given as follows [Reiter and de Kleer, 1987]: ~is a minimal support clause for x with respect to E iff there is a prime implicate 1r for E such that z E 1r and~= 1r-x. The ATMS thus computes the set II(E) of prime implicates and assigns as a label for each literal the disjunction of support clauses (restricted to assumptions) for that literal.

:l Any clause can be represented as either x; :J x; or x;Vx;. The latter method is used by convention.

3 The dual to prime implicate (in Boolean algebra) is called a prime implicant. We use the prime implicate terminology to avoid confusion between the dual representations.

If a new clause x1 V x2 V · · · V x is added such that the antecendents of x already have labels, or if (z) must be updated due to database updating, label updating must take place. An updated label is assigned to a literal x by taking the conjunction of the labels of the antecedents of z: .C(z) = /\1:;Eant(1:) .C(z,). Labels are always repre­ sented minimally with respect to set inclusion.

The process of determining solutions, called Interpre­ tation Construction in ATMS terminology, can be· de­ scribed in this logical framework in terms of a CNF to DNF conversion, but is more intuitively described within the Boolean expression framework, in terms of well-known set covering algorithms. We discuss Inter­ pretation Construction in the next section.

3.2 Boolean Algebra Formulation

This formulation uses the same terminology as the logi­ cal formulation. The conjunction of the E,'s is called a Boolean expression 4 F, i.e. F = 1\i=l, ... ,l E,.

As in the previous formulation, the ATMS label gen­ eration algorithm computes the prime implicates for E, II(E) = {7rl, ... ,7rm}· The derivation of the prime im­ plicates enables the expression F to be represented in terms of the prime implicates, i.e. Frr = 1\, 'Tri, such that Frr computes F. A expression F' computes F if F'(x) = F(x) for every instantiation of x. We note that there may be many other expressions F' which also com­ pute F.

The ATMS then derives the minimal or irredundant expression :F for F. By assigning a unit cost to each support clause e,, the cost ofF can be defined as the sum of the costs of the support clauses ei in F. 5 A minimal expression :F is an expression such that :F computes F and no expression computing F has cost smaller than :F.

Interpretation construction derives an irredundant (or minimal) set of prime implicates, where a prime impli­ cate 1r is redundant if it can be removed from the set II of prime implicates to form a set II' such that II' still com­ putes F. The ATMS uses a set covering algorithm for interpretation construction, but other algorithms may be used, such as the Quine-McCluskey algorithm [Mc­ Cluskey, 1956], or the hitting set algorithm used by Re­ iter [1987] for a diagnostic reasoning application. The minimal Boolean expression corresponds in ATMS ter­ minology to an interpretation, which de Kleer [1986] de­ fines as the smallest set of assumptions from which all literals in the context are derivable.

For the circuit in Figure 1, a minimal DNF expression :F is (WA 1 )V(WM 1 )V(WA 2 AWM 2 )V(WM 2 AWM 3 ), which is what de Kleer and Williams call a minimal diagnosis.

3.3 Graph Theoretic Formulation

In describing this formulation, we introduce some graph­ theoretic notation, which is used to show the equivalence of the graph-theoretic and logic-theoretic descriptions of the problem.

'This is standard conjunctive normal form (CNF), the dual representation of traditional disjunctive normal form (DNF) Boolean expressions.

5 There are many ways to define such a cost function. For example, the cost of each support clause {; can be assigned as the number of assumptions in {;.

We can consider a Boolean expression F as definin~ a graph Q(V, E) composed of vertices V and edges E. More precisely, a Boolean literal Xi corresponds to an edge Ei, and a logical connective (v, t\) corresponds to a vertex that joins two or more edges between the cor­ responding components as follows: a t\ connecting two literals (or clauses) corresponds to an edge connecting two vertices (or vertex sets) in series, and a V connecting two literals (or clauses) corresponds to an edge connect­ ing two vertices (or vertex sets) in parallel. The direction of the edges corresponds to the direction of implication for the clauses.

A path consists of a connected sequence of distinct edges. We call E a path between vertices s and t in the event that all edges in the path are functioning. A minimal path is a path the deletion of any edge of which renders the path disconnected. A subgraph Q' (V', E') of Q(V, E) is a graph such that V' ~ V and E' ~ E. A connected graph has at least one path between every pair of vertices. A cutset of a graph Q is a subgraph of Q the removal of any edge (or vertex) of which renders Q disconnected.

Using the correspondence between the Boolean expres­ sion and graph theoretic formulations for the ATMS, we outline the graph-theoretic equivalent of the ATMS la­ bels. But instead of the label, we will use the prime implicate 1r, since a label is just another means of repre­ senting 1r, as shown earlier.

Lemma 1 The set of prime implicates II(E) for a CNF Boolean expression F defines a set of paths through the corresponding graph Q.

IfF is expressed in DNF, then we obtain

Lemma 2 The set of prime implicates II(E) for a DNF Boolean expression F defines the cut sets of the corre­ sponding graph Q.

The graph corresponding to the irredundant CNF ex­ pression for the circuit diagnosis example is shown in Figure 2(a). The graph corresponding to the irredundant DNF expression is shown in Figure 2(b) which showns the minimal paths derived from the example. We em­ phasize that these graphs are interconvertible. By find­ ing the edge cuts containing the minimum number of edges for the graph shown in Figure 2(a), we can obtain a minimal cut representation shown in Figure 2(b ). Note the graph theoretic relationships between the diagnostic notions of minimal conflict sets (minimal cut sets) and minimal candidates (minimal paths).

Computing the pathsets or cutsets of a graph Q is one means of computing the network reliability of Q, which we now show is analogous to using the ATMS label set to calculate DS Belief function assignments for the corresponding Boolean expression F.

6 There a.re many ways of defining a graph from a Boolean expression. We present one method here, and outline other methods in [Provan, 1989a].

4 Correspondence between the ATMS and Dempster-Shafer Belief Functions

4.1 Extension of ATMS Graph

We now show how the simple assignment of weights to the underlying ATMS graph Q enables the computation of DS Belief functions from the very same graph. Assume each edge of Q is associated with a statistically indepen­ dent random variable with only two possible states, func­ tioning or not functioning. For each DS proposition () there is an associated ATMS literal x and an antecedent set ant(x) containing at least one assumption, such as '%3 v A2 v x. An event is a state assignment to literals, such as { x1, x2, ... , Xn-1} functioning and Zn not func­ tioning. There are 2" possible events . . ~ign to each edge a (0, 1] weight, e : E -+ (0, 1], whtch 18 the pro?­ ability that the edge functions properly. Each edge m Q corresponds to an ATMS assumption, and the edge weight corresponds to a weight assigned to the ATMS assumption.

The reliability R(s, t) of a graph g with respect to .t~o distinguished vertices s and t is defined as the probabiltty that an s - t path exists. The s - t reliability problem is defined as follows:

R(s, t): Given a graph Q(V, E) and a probability as­ signment e to E, compute the pr?b~bili~y that a .func­ tioning path exists between two dtstmgulShed vertices s and t.

R(s, t) can be computed by su~g the proba.bilities of the disjoint s - t path set. A d18Jomt path set 18 a set of paths such that no pair of paths has a common edge. Any pathset, cutset or equivalent Boolean expression for computing R(s,t) must be disjoint.

We summarize the results of [Provan, 1989a] as fol­ lows:

Lemma 3 The label assigned to a literal x is a symbolic (and not nec~ssarily disjoint) rel!resentation of .the DS Belief assigned to the correspondmg DS proposataon 0.

There is an ATMS corollary to DS information pooling (equation 2):

Lemma 4 The ATMS label updating for a literal x, .C(x) - A ( ) .C(xi) is a symbolic ATMS analog - I \:z:;Eont :z: '

to the DS Belief updating formula for the corresponding proposition 0, Bel(O) = ffi; Bel;(O).

Numeric assignments of Bel can be calculated as given by:

Lemma 5 The DS Belief assigned to a literal can be computed using an ATMS by converting the weighted ATMS label set to its graphical representation and com­ puting the probability that an s - t path exists in the subgraph formed from the label assigned to the literal.

Hence calculating DS belief functions for an underly­ ing Boolean expression F is identical to computing the network reliability for the graph corresponding to F.

Moreover, there is an analog in the ATMS to Demp­ ster's rule of Conditioning. Dempster's Rule of Condi­ tioning is as follows:

Lemma 6 If Bel and Bel' are two combinable Belief functions, 7 let Bel( ·I02) denote Bel ffi Bel'. Then

for all 01 c e.

If we call the set of nogoods 'Ill, then the ATMS's sym­ bolic representation of equation 3 is, for all x E x,

4.2 Dempster-Shafer Belief Function Algorithm

DS Belief functions can be computed from ATMS labels as follows. To each ATMS assumption A; assign a DS mass function e(A;). Then use the ATMS to symboli­ cally compute the labels for all the literals. Similar to the ATMS's removal of nogoods from all contexts as an es­ sential part of its processing, DS theory can assign belief only to non-contradictory subsets, i.e. it "removes" mass assigned to contradictory subsets because 0 is not prov­ able for subsets which have a non-null intersection with contradictory subsets. In the ATMS implementation, nogoods must be explicitly accounted for in computing DS Belief functions. This is done by: (1) assigning be­ lief in the numerator of equation 2 only to subsets with null intersections with nogoods (i.e. conditioning on the consistent sets); and (2) using a normalization function, the denominator of equation 2, to renormalize all Belief assignments given that no mass is assigned to nogoods. Hence, the Belief assigned to any proposition (literal) can be computed as follows:

1. Compute a Boolean expression from the label, as described in Section 3.1.
2. Account for nogoods, using equation 4, or the equiv­ alent form

1. Convert the Boolean expression (4) or (5) into a disjoint form.

7 d. [Shafer, 1976], p.67 for a. definition of conditions for combina.bility.

1. Substitute mass functions for the A; 's to calculate the Belief function for x, using Table 1.

Note that in Steps 1 to 3 we manipulate Boolean ex­ pressions. We refer to steps 3 and 4 as a Network Reli­ ability computation.

There are many methods for symbolically computing the disjoint form of an arbitrary Boolean expression, some of which are reviewed in [Agrawal and Barlow, 1984]. The methods applicable to this application are those based on pathsets and cutsets, such as the Sum of Disjoint Products and Inclusion-Exclusion methods.

5 Complexity of ATMS-based Dempster-Shafer Belief Function Computation

This extension of the ATMS was originally proposed as a means of improving the efficiency of the ATMS by focusing search only on the portions of the search space in which solutions were most likely to be found. This need arose from the poor performance of the ATMS in practice, and the theoretical evidence ([Provan, 1988a], [Provan, 1989b]) which suggests that (1) for almost all Boolean expressions 8 the problem of label generation is of complexity exponential in the number of literals; and (2) the interpretation construction problem is NP-hard.

However, the efficiency gains from direct ATMS imple­ mentation of DS Theory may not be cost-effective. Using the ATMS to compute DS Belief functions from ATMS labels is intractable in the worst case, a computational barrier similar to that which has previously prevented implementation of the full DS theory.

Lemma 7 Given the set of ATMS labels for a set x of literals and an assignment of weights to the ATMS as­ sumption set A, computing the DS Belief assigned to x either from the ATMS label set :=:· or from a minimal expression :F is of complexity exponential in the number of literals in the Boolean expression F, in the worst case.

If the ATMS label set is used as a starting point, the size of the label set is exponential in the number of liter­ als or clauses [Provan, 1989b], just as the number of s-t pathsetsfcutsets is an exponential function of I V I and I E I [Agrawal and Barlow, 1984]. The minimal expres­ sion :F may also be used as a starting point, but even though cost(.r) < cost(Fn), it is unknown whether the savings introduced will be worth computing .r from Fn.

8 A property is sa.id to hold for almost a.ll the functions of the algebra. of logic if the proportion of functions of n variables which do not satisfy this property (among a.ll the functions of n variables) tends to zero when n --+ oo.

If truth maintenance facilities and numeric assign­ ments of weights to proposition sets are required, this method may be useful, depending on the tradeoff be­ tween the cost of computing the DS Belief functions and the search space which can be saved by more focused search. The graphical framework suggests more efficient methods of computing ATMS labels and DS belief func­ tions by exploiting the topology of the underlying graph. Further efficiency improvements may be obtained by us­ ing one of the many R(s, t) approximation algorithms applicable to computing DS Belieffunctions from ATMS labels. In [Provan, 1989a] we describe network reliability approximation algorithms which avoid the intractability associated with deriving exact solutions. Such algo­ rithms may remove the necessity to restrict the problem domain to a subset such as that of hierarchical evidence [Shafer and Logan, 1987] due to intractability otherwise.

6 Conclusions

The theoretical basis underlying methods of computing DS Belief functions from ATMS label sets have been dis­ cussed. These computations are done using an ATMS which incorporates the full DS theory in a semanti­ cally clear and efficient manner, as shown by the graph­ theoretic equivalence of the ATMS and DS theory. In addition, computing DS Belief functions from ATMS la­ bels was shown to be intractable in the worst case.

The use of the ATMS to compute DS Belieffunctions is a promising research area, as it is a means of blending logic with an uncertainty representation in a semanti­ cally correct manner. However, we argue that the com­ putational cost of computing exact DS Belief functions may be prohibitive for large problems, and approxima­ tion methods may have to be used.

Acknowledgements: Discussions with Judea Pearl have helped refine my understanding of the corre­ spondence of the semantics of the ATMS and DS theory, and the use of network reliability algorithms.