Plausible Inferencing Using Extended Composition

1 Introduction

The construction of a large knowledge base is difficult and requires techniques that can facilitate knowledge ac­ quisition. Rather than requiring that all knowledge in the base be entered explicitly, a system could be provided with a basic set of facts and an inference mechanism for inferring additional facts from these [Baker et al., 1987]. An ideal system would be able to generate all valid and no invalid inferences. One way to approach this ideal is to provide a set of specialized inference procedures that collectively generate a valid set of inferences. In this pa­ per we develop one such procedure, based on an extended composition of semantic relations from a knowledge base. Figure 1 contains examples of this type of composition. The procedure has the effect of constructing new infer­ ence rules, which, when executed, generate extensions to the knowledge base.

2 Extended Composition

A binary relation R consists of a set A (the domain), a set B (the range), and a mapping that specifies the set of tuples (a, b) belonging to R, where a E A and b E B. The mapping may be explicit by listing all the tuples in R or implicit by providing rules for selecting the tuples. In a large frame-based knowledge system, such

Larry M. Stephens

Center for Machine Intelligence University of South Carolina Columbia, South Carolina 29208

as CYC [Lenat et al., 1986, Lenat and Guha, 1988], the mapping for a relation is only partially specified; other tuples for the relation are added as knowledge is entered . The procedure for composing relations outlined in this paper provides a means of inferring additional tuples be­ longing to an implicitly defined relation.

A composite relation results from applying the bi­ nary operation of composition to two binary rela­ tions. This operation has the following definition [Stanat and McAllister, 1977]:

Definition 1 Let R; be a relation from set A to set B and R; be a relation from set B to set C. The composite relation from A to C, denoted R; · R;, is

We define extended composition as follows:

Definition 2 Let R; be a relation from set A to set B and R; be a relation from set C to set V. The extended composite relation from A to V, denoted R; 0 R;, is

If we denote the converse relation of R by Rc, then it can be shown that

Extended composition can also be shown to be associa­ tive and not commutative.

We would like to have an algorithmic way of deter­ mining when R; 0 R; is nonempty and whether it is a subset of R; or R; or neither. Our method for making this determination is based on two premises:

• the domains and ranges of the two relations must be type-compatible, and
• the primitives (defined below) of the relations must combine compatibly.

If the first premise is satisfied by relations R; and R; , then the primitives of the two relations can be combined to yield the primitives of the composed relation, R; 0R;. The primitives of R; 0 R; can then be compared to those of R; and R; to determine if R; 0 R; is a subset of R;, R;, both, or neither.

The type compatibility specified by the first premise results in the following necessary conditions for the ex­ tended composition of relations:

1. The intersection of sets 8 and C must be nonempty; otherwise, the relation R, 0 Rj will be empty.
2. For the derived tuples to be elements of Ri, the intersection of sets 8 and V must be nonempty.
3. For the derived tuples to be elements of Rj, the intersection of sets A and C must be nonempty.

These conditions, represented using Venn diagrams in Figure 2, eliminate many of the possibilities for extended composition. An algebra based ·on primitives of the re­ lations eliminates additional implausible compositions.

3 Primitives for Semantic Relations

The second premise above requires a set of primitives that describe each relation and a set of rules for com­ bining primitives. We have postulated a group of ten primitives, based on a literature survey [Chaffin and Herrmann, 1987, Cohen and Loiselle, 1988, Wierzbic­ ka, 1984, Winston et al., 1987] and an analysis of nu­ merous semantic relations in the CYC knowledge base [Lenat and Guha, 1988]. These primitives are indepen­ dently determinable for each relation and relatively self­ explanatory. They specify a relationship between an el­ ement of the domain and an element of the range of the semantic relation being described. The primitives, de­ scribed next, have values from the set X = { +, 0,-}, where + indicates that the relationship holds, - that it does not, and 0 that it is not applicable.

Composable: Some semantic relations can never be meaningfully composed with other relations due to their fundamental characteristics. For example, at­ tributes are not generally transferable through other relations.

Functional: The domain of a Functional relation is in a specific spatial or temporal position with re­ spect to the range of the relation. For example, in an instance of the componentOf relation, such as Wheel.componentOfCar, the Wheel is in a specific spatial position with respect to the Car. This prop­ erty does not hold for Juror.memberOfJury.

Homeomerous: In each instance of a Homeomerous re­ lation, the element of the domain must be the same kind of thing as the element of the range, e.g., in PieSlice.pieceOfPie, the slice is the same stuff as the pie.

Separable: The domain of a Separable relation can be temporally or spatially separated from the range, and can thus exist independently of the range. For the above component Of example, the Wheel can be separated from the Car and can exist independently. For Wheel.madeO/.Aluminum, the Aluminum cannot be separated from the Wheel if the Wheel is still to exist.

Structural: The domain and range of a Structural re­ lation have a hierarchical relationship in terms of a physical structure. For example, in Wheel.compo­ nentOfCar, the hierarchical structure is from part to whole and the Structural property of compo­ nentOfhas a- value.

Temporal: The domain and range of a Temporal rela­ tion are ordered in regard to a temporal structure. For example, there is no notion of time in the rela­ tion piece Of, indicated by a value of 0 for Temporal; in causedBy, a value of - indicates that the range element precedes the domain element.

Intangible: The domain and range of an Intangible re­ lation have a hierarchical relationship in terms of ownership or mental inclusion. As an example, the relation ownedBy has a value of - for Intangible, because the element owned is intangibly included in the owner's sphere of influence.

(Note: values of the last three primitives for the converse of a relation are opposite to those for the forward relation.)

Near: The domain of a relation with property Near is physically or temporally close to the range.

Connected: The domain of a relation with property Connected is physically or temporally connected to

1 0 b ject. 2 Tangible&lntangibleO b ject.

the range. A connection, which may be indirect, is indicated by +; no connection is denoted by -.

Intrinsic: A semantic relation has the property Intrin­ sic if the relation is an attribute of the stuffiike na­ ture of its domain or range. For example, the re­ lation hasDensity is an intrinsic property of its do­ main, so that if Aluminum.hasDensity.5, then every piece of Aluminum inherits this value for its density.

To test our . hypotheses, we have selected a represen­ tative set of relations (Table 1), including part-whole, subclass, ownership, causal, and attribution relations. For each of these relations, Table 2 shows the values we have assigned to the above primitives. The domains and ranges of the relations, shown in Table 1, are also needed to determine plausibility.

4 Algebra of Relation Primitives

We assume that the results of composing two semantic relations can be determined from the results of combin­ ing their ten relation primitives (the accuracy of this assumption is evaluated below) as follows:

where VR E X 10 , X= {+,0,-}, and o is the combi­ nation operator. That is, for the purposes of relation composition, each relation can be represented solely by a vector of values for its ten relation primitives. It thus becomes necessary to define precisely how two of these vectors combine.

We assume that the primitives are orthogonal and form a linear basis for the set of relations. The combina­ tion operator o can thus be defined in terms of a separate operation table for each primitive, as shown in Table 3. Each operation table is symmetric and has been derived from empirically determined rules for relation composi­ tion, such as the following:

• In order to compose, two relations must have the same hierarchical direction for their Structural, Temporal, and Intangible primitives.
• If R; has the property Connected and Rj does not , then R;0Rj (and Rj0R;) cannot have the property Connected. Therefore, R;0Rj (apd Rj 0R;) is not a subset of R;.
• If R; has the property Separable and Rj does not, then R; 0 Rj (and Rj 0 R;) has the property Sepa­ rable. Therefore, R; 0 Rj (and Rj 0 R;) may be a subset of R; .

The resultant algebra enables the primitives of the composed relation to be derived. If these derived prim­ itives match the primitives of one (or both) of the com­ posing relations, then a tuple of one (or both) of these can be instantiated; else, the knowledge base can be searched to find all relations that match the resultant primitives, and, if not already instantiated, these can be presented to a user as potential new tuples for the knowledge base.

As an example of this inference procedure, assume that a user has entered the assertions Wheel.compo­ nentOfCar and Car.ownedBy.Grover. Combining the primitives from Table 1 for componentOf and ownedBy according to the combining rules in Table 3 yields the following vector of primitives for the resultant relation: VR = (+ - - + 0 0 - 0 +/- +/-). Because this vector matches the primitives of ownedBy and does not match those of componentOf, the inference is that Wheel. ownedBy.Grover.

The plausibility of this result is checked by compar­ ing the types of the domain and range of this rela­ tion instance with the types specified for ownedBy in Table 2. To do this, a taxonomy of types is needed that enables the intersection of domains and ranges to be determined. Such a taxonomy is typically part of frame-based knowledge-representation systems. The types used for our examples are from the CYC on­ tology [Lenat and Guha, 1988]. Using this ontology and Table 2, we find that Wheel is an instance of IndividualObject, Grover is an instance of Tangi­ ble&IntangibleObject, and these match the domain and range of ownedBy. The resultant inference is thus deemed plausible.

5 Results

The above inference procedure was applied to the set of relations shown in Tables 1 and 2. The results, in the form of a composition matrix, are shown in Table 4. Each entry in Table 4 is equivalent to a rule of the form

The results reflect the order of composition, e.g., Rj 0R; as well as R; 0 Rj , which was not addressed in either [Cohen and Loiselle, 1988] or [Winston et al., 1987] . Be­ cause each of the operators for combining primitives is symmetric, the composition matrix is nearly symmet­ ric. The only exceptions result from type compatibility, Note: + f- indicates that the relations compose, but that this primitive does not constrain the composition. P denotes prohibited, indicating that the relations do not compose.

which sometimes excludes a composition from occurring. For example, f 01 C l , but 10 f = 0, because the inter­ section of the range of l with the domain off is empty.

The following are specific examples of plausible infer­ ences predicted by the extended composition of relations (where --+ denotes logical implication):

• ·a 0 pCp Tire . componentDfCar 1\ Car. containedln.Garage --+ Tire .containedln.Garage
• ·p0aCp Refrigerator. containedln.Ki tchen 1\ Kitchen.componentDfHouse --+ Refrigerator. containedln.Hous e
• i 0 eCi

Thunder. causedBy.Lightning 1\ Lightning.subeventDfThunderStorm --+ Thunder . causedBy. ThunderStorm

The technique for relation composition also correctly predicts when neither of the composed relations can be inferred. For example

• p 0 l = 0 Grover. containedln.Car 1\ Car . ownedBy.Ernie -f+ (Grover. containedln.Ernie V Grover.ownedBy.Ernie) .

6 Discussion and Conclusions

The inference procedure and results presented in this paper extend the work of previous researchers . Chaffin and Herrmann [1987] identify a set of relation elements (relation primitives) that can be used to describe and classify relations. Each relation element is a fundamental property that holds between the domain and range of the relation.

Winston et al. (1987) define three independent relation elements, inclusion, connection, and similarity; these are used to describe spatial inclusion, meronymic inclusion, and class inclusion. When any inclusion relation is com­ bined with another, they find that a valid inference can be made and that the resultant relation is the one hav­ ing the fewest relation elements. In addition, Winston et al. identify three dependent elements of connection that explain the transitivity, but not the composability, of six meronymic relations.

Cohen and Loiselle [1988] identify two deep structures for relations: hierarchical and temporal, each having a di­ rection. Each relation is hierarchical, temporal, or both. When two relations are composed, the resultant rela­ tion may have any of several possible deep structures, depending on the properties of the composing relations. They found that inferences are most plausible when ei­ ther the hierarchical or temporal directions of the two composing relations are the same as that in the com­ posed relation. Like Winston et al., they do not consider type consistency in composing relations.

We extend the research efforts cited above by basing relation composition on set theory. On this basis, we conclude that typing of the domain and range elements may restrict composition, independently of any relation attribute restrictions. In addition, we extend the work of (Winston et al., 1987) by explicitly considering the hi­ erarchical nature of the inclusion relations, as suggested by (Cohen and Loiselle, 1988). This leads to a means of defining the primitive attributes of the converse of are­ lation and, consequently, of composing a converse with other relations.

We provide a vector of ten primitives for each of 21 typical relations. This vector representation provides a more powerful basis for ranking and classifying relations than does the linear ordering in [Winston et al., 1987) . Since there are three possible values for each of the ten primitives, our representation provides for 3 10 = 59, 049 different basis vectors that can be used to represent rela­ tions. The number of relations that could be represented is actually much greater because of the large number of types that could be chosen for the domains and ranges.

The inference procedure we developed for relation composition is based on several assumptions. The fore­ most of these is that relation composition is equivalent to a combination of the corresponding vector of primitives. The correctness of this assumption is borne out by the plausibility of the predicted inferences, shown in Table 4. A second assumption is that each relation primitive is orthogonal to the others. This simplifying assumption greatly increases the efficiency of the inference proce­ dure by yielding operation tables (see Table 3) that are independent of each other . Although the validity of the results supports this assumption also, there is some ev­ idence that the chosen primitives are NOT orthogonal. For example, the primitives Connected, Homeomerous, and Intrinsic combine dependently according to the fol­ lowing rule to yield compositions with attribute relations not predicted by our algebra:

(attributeD! .Intrinsic.+) 1\ (Ri .Connected.+) 1\ ( Rj . Homeomerous. +) --+ (attributeD! 0 Rj C attributeD!)

Such a rule would yield the valid inference densi­ tyDJ 0 pieceD! C densityDJ, which does not result from our relation algebra. It could be applied after extended composition and viewed as an additional inference mech­ amsm.

Other valid inferences are missing from Table 4, in­ cluding memberDJ 0 isA C memberDJ and compo­ nentDJ 0 attributeD! C attributeD! However, we feel that these omissions do not diminish the utility of our results, in that our procedure is designed for correctness instead of completeness. In addition, many knowledge­ based systems have other inference mechanisms that could generate these missing inferences. For example, an automatic classifier (Lipkis, 1981] would generate the inference memberDJ 0 isA C memberDf

The potential for generating new inferences in a large knowledge base, such as the one in CYC, is enormous. CYC, currently with >4000 relations, could have approx­ imately sixteen million possible compositions. Of these, 20% are predicted to be plausible, based on the percent­ age of valid entries in Table 4. For all possible values of relation primitives, no more than 31% could be com­ posed validly due to prohibited entries in the operation tables for combining primitives. The one million asser­ tions now in the CYC knowledge base can be combined

Note: the letters in this matrix refer to the relations listed in Tables 1 and 2.

using the predicted compositions to yield many new in­ ferences.

However, there are two major problems with extended composition. First, reason maintenance for the resultant inferences is computationally problematic, because the inferences depend not only on the relations being com­ posed, but also on the relation primitives for all of the relations involved. Second, assigning values for the rela­ tion primitives is conceptually problematic. The values are subjective and must be entered manually for each relation in a knowledge base. The validity of the in­ ferences generated by extended composition are directly dependent on these values.

Nevertheless, we expect that the relation primitives can be used for classifying relations, as well as generat­ ing new inferences, and for suggesting plausible analo­ gies. The procedure for extended composition appears to be a viable technique for increasing the information in an existing knowledge base. Because the procedure has the effect of generating new inference rules and then applying them, it yields plausible inferences that are not within the deductive closure of the original knowledge base.