Evidential Reasoning in Semantic Networks: A Formal Theory

I. Introduction

The computational cost of gathering, processing and storing information about a complex and constantly changing environment makes it impossible to maintain complete knowledge. However, the need to act on available information compels an agent to make decisions (inferences) based on incomplete knowledge. This underlines the importance of formalizing inference -; tructures that can deal with incompleteness and uncertainty. as is well recognized in AI [Do, Fo, HM, Jo, l_d , MD, McD, \tlo, Ni, Re].

This paper presents an evidential approach based on the principle of maximum entropy to deal with incomplete knowledge. Evidential reasoning permits the association of numeric quantities with assertions to indicate their degree of belief and has long been used in expert system design [Po, Sho, DHN]. This paper demonstrates that it is possible to adopt an evidential approach in solving some well known problems in knowledge representation. It focuses on a restricted representation language - similar in expressive power to semantic network formalisms, and develops a formal theory of evidential inheritance within this language. The resulting theory has an efficient parallel implementation.

A way to fonnalize these distinctions is to treat statements like Sl and S2 as evidential assertions and to associate a numeric quantity with each assertion to indicate its evidential import. If one could assign meaning to these numbers and explain how they may be extracted from world knowledge and also specify a fonnal calculus for computing the combined effect of evidential assertions, then one would be able to handle situations such as the quaker example more satisfactorily. Deciding whether Dick is a pacifist or a non-pacifist need not be based on arbitrary choices, but instead, be resolved by a fonnally specified theory of evidential reasoning.

One may handle interactions between default rules by enumerating the possible cases of interactions and specifying the correct inference in each case [RC]. However, having a fonnal calculus for computing the effects of interactions between default rules in a justifiable manner seems more desirable to us than having to explicitly list the outcome of every possible interaction.

Recently, Touretzky [To], has suggested a non­ evidential theory of inheritance based on the principle of inferential distance ordering which states that: if A inherits P from B, and -P from C, then "if A has an inheritance path via B to C and not vice versa, then conclude P; if A has an inheritance path via C to B and not vice versa, then conclude -P; otherwise report an ambiguity." In effect, his fonnalism treats all rules at the same inferential distance as having !he same import and this forces him to report an ambiguity in situations such as the quaker example.

Rich [Ri], has proposed that default reasoning be treated as likelihood reasoning. However, she does not offer a fonnal theory of evidential reasoning; she concludes " ... the introduction of likelihoods poses new questions such as how to best assign (certainty factors) when there are conflicts ... these questions ... should be addressed."

This paper specifies a formal theory of evidential reasoning with respect to a restricted representation language. The theory can handle a limited, but we think interesting, class of multiple inheritance situations, including those that involve exceptions and multiple inheritance (analogous to multiple extensions). The theory may be realized in tenns of a highly parallel network that can solve inheritance problems in time proportional to the depth of the conceptual hierarchy.

Section 2 specifies the representation language, section 3 derives the evidence combination rule and discusses its relation to the Dempster-Shafer evidence theory [Sha, GLF, Ba, Gi], Section 4 develops the theory of evidential inheritance and section 5 discusses related issues.

2 Representation language

We will be dealing with the problem of evidential reasoning in the context of a restricted knowledge representation language that is similar to semantic network fonnalisms such as [Fa, Br, BW] and may be viewed as an evidential extension of inheritance hterarchies with exceptions [ER]. An outline of the language follows.

An agent's apriori knowledge consists of the quintuple:

<C is the set of concepts, <I> is the set of properties, A is a mapping from <C to the power set of <I>, ~ is a set of distributions and ~ is a partial ordering defined on <C . These terms are explained below.

A concept can be a Token or a Type. Tokens denote instances or individuals while Types are abstractions defined over Tokens.

If Cis a Token then #C = l, and if Cis a Type then #C = the number of instances of C observed by the agent.

An agent describes concepts and defines abstractions over concepts using properties and their values. Examples of properties are has-color (with values such as RED, GREEN, BLUE etc.) and has-taste. Properties such as has­ taste and has-color are distinct from concepts such as TASTE and COLOR.

A concept may have multiple values for the same property. For example, if there exist red apples as well as green apples then the concept APPLE will have the values RED as well as GREEN for the property has-color.

Values are also concepts. If V is a value of some property P then # V is defined to be equal to the number of instances that possess this value. Thus, #RED equals the number of red colored entities in the domain.

For each C E <C, A( C) is the subset of <I> that consists of exactly those properties that are applicable to C. For example, A(APPLE) may be {has-color has-taste has-shape}

Given a concept C and a property P E A(C),

#C<P,V> = the number of instances of C that are observed to have the value V for property P

Thus, # APPLE<has-color, RED> equals the number of red apples observed by the agent. Similarly,

the number of instances of C, observed to have the value V1 for property P1, value V2 for property P2 .... and value V n for property Pn.

Each distribution 8(C,P) E ~ (where C E <C and P E A(C)), specifies how instances of C are distributed with respect to the values of property P. 8(C,P) may be expressed in terms of #C<P,V>'s. For example, 8(APPLE, has-color) may be expressed as:

{ # APPLE(has-color, RED) = 60, # APPLE(has-color, GREEN)= 40}

indicating that 60 apples are red and 40 are green.

An agent need not know all possible distributions. An agent acquires and stores only those distributions that are useful to him. Thus, the agent may not know ll(C,P) even !hough P may belong to .\(C).

Although we have used absolute numbers to specify the distributions and the size of concepts, it is shown in section 4.5 that an agent need only deal with relative information and rational numbers that lie in the interval [0,1].

The relation ~ structures the concepts in <C into a partially ordered set and corresponds to the subtype relation employed in semantic networks. In this formulation, ~ relates Types to other Types as well as to Tokens.

The ordering induced by ~ on <C may be compactly represented in the form of an ordering graph. Figure l depicts an ordering graph for a specified ~ - Each node in the graph denotes a concept. A directed link connects ai to every node aj, (ai * aj) such that ai ~ aj and there exists no ak (other than ai and aj) such that ai ~ ak ~ aj. If there is a direct link from ai to aj then aj is referred to as a parent of ai.

Given a set of concepts S, where S = {sl s2 ... sn}, if aj is such that for all si E S, Si ~ aj, and there is no ak (other than aj) such that for all si E S, si ~ ak ~ aj, then aj IS a reference concept for S. For mstance, in figure l, b is the reference concept for { c e f}.

2.1 An Example

An agent's knowledge about a hypothetical domain may comprise:

TASTE, SWEET, SOUR} <1> = {has-taste, has-color}

.\(FRUIT) , .\(APPLE), .\(GRAPE) = {has-taste, has-color} .\(COLOR), .\(TASTE), .\(RED), .\(GREEN), .\(SWEET), .\(SOUR) = 0

fj, encodes the following:

#APPLE = 100 # APPLE<has-color, RED> = 60, # APPLE<has-color, GREEN> = 40 # APPLE<has-taste, SWEET> = 70, # APPLE<has-taste, SOUR> = 30 #GRAPE = 50 #GRAPE<has-color, RED> = 5, # GRAPE<has-color, GREEN> = 45 # GRAPE<has-taste, SWEET> = 30,

~ is given by:

# GRAPE<has-taste, SOUR> = 20 (APPLE ~ FRUIT) , (GRAPE ~ FRUIT) , (RED ~ COLOR) , (GREEN ~ COLOR), (SWEET ~ TASTE) , (SOUR ~ TASTE)

The agent's domain knowledge may be expressed in a network form as shown in figure 2.

3. A theory of evidence

In its simplest form, the problem of evidential reasoning may be stated as a decision problem illustrated by the following example:

Suppose an agent is required to choose between APPLE(x) (to be read as "x is an apple") and· GRAPE(x) given that RED(x) AND SWEET(x). How should he make the choice on the basis of his knowledge that consists of the values of:

E(APPLE(x) I SWEET(x)) and E(GRAPE(x) I SWEET(x)).

• *where E(AIB) means "the evidence provided by B to A"

In solving decision problems such as the one above, a theory of evidential reasoning should strive to ascertain the following:

"Given the state of the agent's knowledge i.e. , taking into account what the agent knows, which choice is most probably correct".

The theory developed below is based on the notion of maximum entropy, a notion that is fundamentally related to information theory and statistical mechanics, [Ja1, Ja2, Ch].

3.1 Problem formulation

Given the knowledge in section 2.1, a rational agent would have no difficulty in guessing the most probable identity of an object given one of its property values. For example, he would guess that a red object is probably an apple because there are 60 instances of red apples as against 5 of red grapes.

Our goal is to suggest how a rational agent should decide the most probable identity of an object given a description specifying multiple property values such as "red and sweet".

The information about apples and grapes in section 2.1 may be expressed in the form of matrices as shown in figure 3. The rows of the two matrices correspond to the different values of the property has-taste while the columns correspond to the different values of the property has-color. The numbers at the end of each row (column) represent the number of instances of the concept that have the appropriate value of taste (color).

45 - COLUMN SUMS

FIGURE3

In general, an agent's knowledge about a concept A may be represented as an n-dimensional matrix where n = I .\(A) 1. Each dimension of the matrix corresponds to an applicable property and the extent of a dimension is given by the number of distinct values the property may have. The # A<P,V>'s appear as marginals or the sums of hyper-rows and hyper-columns.

The internal matrix elements may be used to specify the number of instances of the concept that have the appropriate combination of property values. For instance, the top left element of the APPLE (GRAPE) matrix in figure 3 indicates the number of instances of apples (grapes) that are both red in color and sweet in taste.

To guess the identity of a red and sweet object would be trivial if the agent knew the internal matrix elements. He could simply compare the top left elements of the two matrices in figure 3 and choose the concept that has the higher value.

However, if the agent does not know the internal matrix elements the best that he can do is find the most probable estimates of these on the basis of the available information and use the estimates to reason about the world In the remainder of this section we show how the most probable estimate may be found.

3.2 Computing the most probable configuration

The general 2-dimensional case. may be represented as shown in figure 4.

The matrix represents the concept A, and

R· I # A<property l, ith value of property l>

c­ J # A<property 2, jth value of property 2>

a-­ IJ # A<property 1, ith value of property 1> <property 2. jth value of property 2>

i.e. the number of instances of A having the ith value for property 1 and the jth value for property 2.

Let a configuration be a specification of all the aij's. Our goal is to find the most probable configuration indicated by the following in formation :

The problem of finding the most probable configuration may be recast as follows:

Consider distributing N distinct objects into a 2dimensional array of cells.

Let a placement be the complete specification of the result of such a distribution That is, for each cell a placement specifies the objects that are placed in the cell.

Let the number of objects located in the ijth cell be given by aij. Then, it follows that there is a many to one mapping from the space of placements to the space of con figurations.

Let a placement be termed feasible if it satisfies the constraints imposed by row sums and column sums. Then:

Given his knowledge, an agent has no basis for assuming that a particular feasible placement is more probable than some other feasible placement and the only rational assumption he can make is that all feasible * placements are equally probable.

In view of the above assumption the most probable configuration will be that which results from the greatest number of feasible placements.

If w denotes the number of placements resulting in a configuration then w is given by:

{number of ways of dividing N distinct objects into n*m groups of au. an 000 anm each.}

One may now maximize w subject to the constraints:

tn order to find the most probable configuration.

It may be shown that for the above maximization problem:

* This is in essence the principle of indifference or the principle of insufficient reason first stated by Bernou11i in 1713.

satisfies the condition of maximality.

The above derivation involves taking the logarithm of w and using the Stirling's approximation to eliminate the factorials. The maximization is performed by setting the derivative of the resulting expression with respect to aij 's to zero: the constraints being incorporated as Lagrange multipliers.

The above result can be extended to higher dimensions. The result is analogous to the result for 2dimensions and is given by:

where N equals the total number of objects, n equals the number of dimensions in the array. Ai, Bjo Ck 000 denote the sums of hyper-rows or hyper-columns and aijkoo. is the most probable number of objects in the ijkoo. th cell of the array.

The above result will be referred to as the best estimate rule and may be restated as follows. Based on the knowledge of:

is giVen by:

Referring back to the example about apples and grapes - the result derived above implies that a rational agent would believe that the most probable way in which the instances of apples and grapes could be distributed is given by the matrices shown in figure 5. Thus, he will identify a "red and sweet" object to be an apple as there are probably 42 apples meeting this description as against only 3 grapes.

3.3 Relation to the Dempster·Shafer theory

The Dempster-Shafer (OS) evidence theory [Sha, GLF, Ba], suggests an evidence combination rule that is cu'rrently in vogue in aritificial intelligence. One can show that a straight forward application of the DS rule for evidence combination does not produce the correct results - for the kinds of problems we wish to solve. It is shown that the DS result agrees with the best estimate rule if one assumes that the frequency (i.e. the prior probability) of all concepts is the same.

A simple example illustrates the point. Consider the information about apples and grapes as given in section 2.1.

If one wishes to use the DS rule to decide whether a green and sour object is an apple or a grape one would essentially proceed as follows:

One would treat each property value as a source of evidence. The evidence provided by green and sour will be:

Applying the OS rule for evidence combination we get:

{The above is a simplified account of the actual steps using OS theory. We have focused on the essentials. In particular, we have not normalized the quantities because we are only interested in a relative measure.}.

Comparing the evidence for Apples and Grapes we have

E(Apple I green & sour) : E(Grape I green & sour) equals,

and the decision is in favor of Apple.

However, on the basis of the given information, the best (most probable) estimate of the number of green and sour Apples is 12 and that of green and sour Grapes is 18. (See figure 5). Hence the appropriate ratio is:

and the decision is in favor of Grapes!

It is not difficult to locate the reason for this discrepency. Given that one is only interested in making comparisons, the ratio of the relative likelihood of two concepts A and B using the OS rule is given by:

However, the best estimate rule gives the ratio as:

which may be restated as:

If one were to assume #A = # B, or in effect that all concepts have the same prior probability, then the OS rule and the best estimate rule become equivalent.

One might suggest that by including an additional source that provides evidence about the prior probabilities of apples and grapes, one might be able to correct the DS result. However, an examination of Eq-I will indicate that the problem is more complex. In order to make the DSratio the same as that obtained by the best estimate result one will have to multiply it by the factor:

But, introducing an evidential source to account for the prior probability only introduces the factor #A/# B, which acts in the wrong direction.

3.4 Relation to Bayes's rule

The best estimate rule is consistent with the use of Bayes's rule if one assumes that the properties are independent. The maximum entropy approach simply determines the most probable configuration on the basis of all the available information. If there is nothing in the information to suggest a dependence or (correlation) then none is assumed. If additional information suggesting dependence is available, it is incorporated in the derivation of the most probable configuration as an additional constraint. For example, if the agent knows one of the matrix elements (say the number of red and sweet apples), then the most likely configuration is as follows:

Without loss of generality, let the agent know that au = a. Then,

However, the above computations get complex if many internal elements are known: the implications of this are discussed in section 5.

4. Evidential inheritance

This section develops an evidential theory of inheritance based on the result derived in section 3.2. The inheritance problem may be defined as follows:

Find: The best value of property P for concept C, i.e. find V* such that for all possible Vi's, the best estimate of #C<P.V*> > the best estimate of #C<P.Vi>· -

The section begins by considering the simplest case of inheritance (direct inheritance) and progressively considers more complex cases that require combining evidence from multiple sources (multiple inheritance).

4.1 Direct inheritance

Given two concepts A and B, and a property P such that: A ~ B, «'J(A,P) ~ ~ but S(B,P) E ~. then in the absence of any other information, # A<P, V>'s are best estimated by:

A proof easily follows from an application of the best estimate rule [Shas].

For example, if 30% of fruits are red, then in the absence of any other information, except that apples are a subtype of fruits, the best estimate of the percentage of red apples is 30%.

4.2 Principle of relevance

Given a concept A and a property P E A(A), a concept B is relevant to A with respect to P, if and only if:

1. A ~ B,
2. ii) «S(B,P) E ~ and
3. iii) there exists no concept C (distinct from A and
4. such that «S(C.P) E ~ and A ~ C ~ B.

The principle of relevance states that:

Given a concept A and a property P such that P E A( A) and «'J(A,P) ~ ~. then, if there is only one concept (say B) that is relevant to A with respect to property P, then the best estimate of «'J(A,P) may be directly inherited from B.

Example: Suppose an agent knows that apples are a subtype of fruits, delicious is a subtype of apples, 45% fruits are red and 60% apples are red. Given this information, the best estimate of the percentage of red delicious is 60%, based on the more specific information about apples.

The principle of relevance solves the problem of exceptions. Suppose an agent knows that penguins are a subtype of birds, most birds fly, and penguins do not fly. If the agent is told that Tweety is a bird, and asked to choose between "Tweety flies" and "Tweety does not fly", he will make the choice based on his knowledge of birds ("most birds fl y" hence "tweety flies"). However. if the agent is also told that Tweety is a penguin, then the principle of relevance prescribes that he make the choice based on his knowledge of penguins ("penguins do not fly" hence "Tweety does not fly").

The principle of relevance appears as the reference class problem in statistical inference [Ky] and also corresponds to the inferential distance ordering in [To].

4.3 Multiple inheritance

This section presents a solution to a restricted class of the multiple inheritance problem. The existence of multiple relevant concepts requires that evidence from many sources be combined. For the ensuing discussion, we introduce two definitions.

Given a concept C and a property P E A(C):

i) r(C,P) refers to the set of concepts that are relevant to C with respect to P.

ii) <C/C,P, the projection of <C with respect to C and P, is defined as follows :

4.3.1 Multiple inheritance: the simple case

Let e = <<C. <t>, A, t:., -<> be the conceptual structure of an agent. If the ordering induced on <C/C.P by ~ is such that their exists a unique reference concept (say fl) for r(C,P) that is also the parent of all members ofr(C,P), then the best estimate of #C<P. vp I #C<P,V q> is given by:

In the above expressions, Vj and V q are any two values of property P for concept C and B(s are ' the members of r(C,P).

In other words, if an estimate of #C<P,Yj> is required solely for the purpose of comparing it with estimates of other #C<P,Vq>'s, then it suffices to compute:

Proof Outline: The above result is proved by first establishing the following result:

Given a set V, and n sets S1, S2···· Sn, each Sk <;;; V; let w denote nk=l.n sk

Then, the best estimate of #W is given by:

The problem of estimating #W is a special case of determining the most probable configuration. Each Sk may be treated as a 2-valued property applicable to V. For each v E V, if v E Sk then the value of the property sk for v equals "1" otherwise it equals "0". Hence, finding the best estimate of # W is identical to finding the best estimate of #Y<S1,"l"> <S2,"l"> ... <Sn,"l">. 111 follows from the result of section 3.2 and III in turn leads to II, [Shas].

4.3.2 Multiple inheritance: the more complex case

This section deals with a more complex multiple inheritance situation. The result of this section states that:

If the ordering induced on <CIC,P by ~ is such that there exists a unique reference concept Q for r(C,P) and there is a unique path from each Bi E r(C,P) to Q (in other words, the ordering results in a graph that includes a tree with Bi's as its leaves and Q as its root), then the best estimate of

IS computed by the following algorithm:

The function BEST-ESTIMATE(~. cp, v) operates on the tree induced by ~ on <CIC,P and is as follows:

Function BEST-ESTIMATE (~ . cp , v) : returns real

{~ is a concept, cp is a Property and v is a value}

If ~ E r(C,P) then BEST-ESTIMATE : = # ~(cp,v)

else BEST-ESTIMATE : =

#~(cp,v) * 0 (BEST- ESTIMATE(~i,cp , v) l#~(cp,v))

{The product is taken over all the sons (i.e. the ~i ' s) of ~}

EJq>lanation: The evidence provided by the ~ i ·s is progressively combined from bottom up by repeated application of the result derived in section 4.3.1. till Q is reached.

4.4 Evidential inheritance: a summary

Problem statement:

Given: e = <<C, <!>, .\, !:1 , ~> and C E <C and P E .\(C),

Find: The best value of property P for concept C, i.e. find V* such that for all possible Vi's, the best estimate of #C<P.Y*> > the best estimate of #C<P ,Yi>- -

Solution:

1. Find r(C,P)
2. ii) If there exists a unique reference concept Q for r(C,P) and there is a unique path from each y E r(C,P) to Q in the ordering diagram defined by ~ and <CIC,P then :

Find V* such that for all i BEST-ESTIMATE(Q, C, V*) I BEST-ESTIMATE(Q, C, Vj) ~ 1 (Direct inheritance and the case where o(C,P) E t1 are special cases of the above result).

The condition specified in step ii is not unduly restrictive. An interesting conceptual organization that satisfies the condition is the one in which the Type structure defined over Tokens consists of several distinct taxonomies. In such an organization, each Token may have several parents, and hence, multiple relevant concepts.

In particular, condition ii does NOT require all concepts in <C to be organized as a tree; if this were the case, multiple inheritance situations would not even arise. Figure 6 shows an example in which the property P may be inherited for concepts C1 as well as C2. For instance, C1 , o, F, H, I, and J could represent Dick, Quakers, Republicans, Religious groups, Poilitical groups, and People respectively, and P could be the property has-belief with values such as Pacifism, Non-pacifism, Nationalism etc. The question of Dick's pacifism would be resolved by combining evidence from the concepts "Quaker" and "Republican" at the reference concept "People".

o(x,P) E !:1 for nodes x drawn in black. Both C1 and C2 have two relevant concepts with respect to P.

• J is the reference concept.

FIGURE 6

4.5 The role of numbers in the theory

The representation language specified in section 2 required the specification of absolute numbers. However, an important characterstic of the theory of inheritance developed above is that none of the calculations require the knowledge or ab_solute numbers. All the necessary numenc mformat1on IS embodied in the following ratios each of which lies in the interval [0,1]:

1. For all C and P such that o(C,P) E !:1, ratios of the form

where, D is a parent of C in the ordering induced by ~ on <C/C,P and Vi's are possible values of P.

1. For all pairs of concepts C and D such that D is a parent of C in the ordering induced by ~ on <C. the ratios: #CI#D

4.6 Parallel implementation

It is possible to encode e as a highly parallel (connectionist) network made up of active elements connected via weighted links. The network can perform the computations required to solve the inheritance problem in only O(d) time, where d is the length of the longest path in the ordering defined on <C by ~- The weights on links encode the ratios discussed above.

An interesting property of the parallel implementation is that the weights on links can be computed on the basis of purely local information. Thus, the weight on a link from node A to node B, is a function of the activities of nodes A and B alone.

For a description of the parallel implementation see [Shas]; the connectionist paradigm is described in [FB]. An earlier parallel implementation, along with some extensions of this work is described in [SF].

5. Discussion

This paper has developed an evidential framework based on the principle of maximum entropy and has applied it to the problem of inheritance. The evidential treatment solves the problem of exceptions and a class of multiple inheritance problems. By combining information from multiple ancestors in a formally justifiable manner, it allows the result to be based on relevant information, and not just on an arbitrarily chosen subset of information. (Recall the quaker example in section 1).

The formalism presented here has an efficient parallel implementation (section 4.6), though the results apply only to a restricted representation language. We believe that work in AI on representation and inference should not ignore the issue of tractability (a.k.a. performance, effeciency). A formalism that has limited expressiveness but that is computationally tractable seems at least as relevant to AI as one that is extremely expressive but hopelessly intractable [Le2]. We feel that our formalism lies at a significant point on a metaphorical "curve" that might describe the tradeoff between expressiveness and tractability.

This formulation demonstrates that as long as the knowledge about concepts and their property values is in the form of #C<P,V>'s, there exists an efficient way of utilizing this knowledge. In section 3.4 we saw how a "limited" amount of knowledge outside this form could be incorporated. However, the computations soon become too complex. This suggests that the goal of a concept formation (learning) mechanism should be to create concepts - and the ensuing Type structure, such that most of the distribution information may be expressed in terms of #C<P,V>'s of existing concepts.

The evidential formulation is extendable to the recognition problem (given a description consisting of property value pairs, find the concept that is best indicated by the description). The extension is described in [Shas].

6. Conclusion

This paper demonstrates that certain problems in knowledge representation and reasoning have elegant solutions within an evidential framework. We hope that this work provides a point of contact between researchers who adopt various non-monotonic logics and researchers who adopt an evidential approach to deal with partial and uncertain knowledge. We further hope that this will lead to a greater interaction between the two groups.

Acknowledgment

This research was sponsored by the National Science Foundation, in part under Grant No. IST8210564, in part under Grant No. DCR-8405720, and in part under Grant No. IST-8208571.