Chapter 9 - Weak Slot-and-Filler Structures

In this chapter, we continue the discussion we began in Chapter 4 of slot-and-filler structures. Recall that we originally introduced them as a device to support property inheritance along isa and instance links. This is an important aspect of these structures. Monotonic inheritance can be performed substantially more efficiently with such structures than with pure logic, and nonmonotonic inheritance is easily supported. The reason that inheritance is easy is that the knowledge in slot-and-filler systems is structured as a set of entities and their attributes. This structure tums out to be a useful one for other reasons besides the support of inheritance, though, including:

We describe two views of this kind of structure: semantic nets and frames. We talk about the representations themselves and about techniques for reasoning with them. We do not say much, though, about the specific knowledge that the structures should contain. We call these "knowledge-poor" structures "weak," by analogy with the weak methods for problem solving that we discussed in Chapter 3. In the next chapter, we expand this discussion to include "strong" slot-and-filler structures, in which specific commitments to the content of the representation are made.

9.1 Semantic Nets

The main idea behind semantic nets is that the meaning of a concept comes from the ways in which it is connected to other concepts. In a semantic net, information is represented as a set of nodes connected to each other by a set of labeled arcs, which

Figure 9.1: A Semantic Network

represent relationships among the nodes. A fragment of a typical semantic net is shown in Figure 9.1.

This network contains examples of both the isa and instance relations, as well as some other, more domain-specific relations like team and uniform-color. In thisnetwork, we could use inheritance to derive the additional relation

has-part(Pee-Wee-Reese, Nose)

9.1.1 Intersection Search

One of the early ways that semantic nets were used was to find relationships among objects by spreading activation out from each of two nodes and seeing where the activation met. This process is called intersection search [Quillian,1968]. Using this process, it is possible to use the network of Figure 9.1 to answer questions such as "What is the connection between the Brooklyn Dodgers and blue?" [Footnote: Actually, to do this we need to assume that the inverses of the links we have shown also exist.] This kind of reasoning exploits one of the important advantages that slot-and-filler structures have over purely logical representations because it takes advantage of the entity-based organization of knowledge that slot-and-filler representations provide.

To answer more structured questions, however, requires networks that are themselves more highly structured. In the next few sections we expand and refine our notion of a network in order to support more sophisticated reasoning.

9.1.2 Representing Nonbinary Predicates

Semantic nets are a natural way to represent relationships that would appear as ground instances of binary predicates in predicate logic. For example, some of the ares from Figure 9.1 could be represented in logic as

Figure 9.2: A Semantic Net for an n-Place Predicate

isa(Person, Mammal)

instance(Pee-Wee-Reese, Person)

team(Pee-Wee-Reese, Brooklyn-Dodgers)

uniform-color(Pee-Wee-Reese, Blue)

But the knowledge expressed by predicates of other arities can also be expressed in semantic nets. We have already seen that many unary predicates in logic can be thought of as binary predicates using some very general-purpose predicates, such as isa and instancte. So, for example,

man(Marcus)

could be rewritten as

instance(Marcus, Man)

thereby making it easy to represent in a semantic net.

Three or more place predicates can also be converted to a binary form by creating one new object representing the entire predicate statement and then introducing binary predicates to describe the relationship to this new object ofeach ofthe original arguments. For example, suppose we know that

score(Cubs,Dodgers,5-3)

This can be represented in a semantic net by creating a node to representthe specific game and then relating each of the three pieces of information to it. Doing this produces the network shown in Figure 9.2.

This technique is particularly useful for representing the contents of a typicul declarative sentence that describes several aspects of a particular event. The sentence

John gave the book to Mary.

Figure 9.3: A Semantic Net Representing a Sentence

could be represented by the network shown in Figure 9.3. [Footnote: The node laheled BK23 represents the particular book that was referred to by the phrase "the book." Discovering which particular book was meant by that phrase is similar to the problem of deciding on the correct referent for a pronoun, and it can he a very hard problem. These issues are discussed in Section 15.4.] In fact, several of the earliest uses of semantic nets were in English-understanding programs.

9.1.3 Making Some Important Distinctions

In the networks we have described so far, we have glossed over some distinctions that are impottant in reasoning. For example, there should be a difference between a link that defines a new entity and one that relates two existing entities. Consider the net

Both nodes represent objects that exist independently of their relationship to each other. But now suppose we want to represent the fact that John is taller than Bill, using the net

The nodes H1 and H2 are new concepts representing John's height and Bill's height, respectively. They are defined by their relationships to the nodes John and Bill. Using these delined concepts, it is possible to represent such facts as that John's height increased, which we could not do before. (The number 72 increased?)

Sometimes it is useful to introduce the arc value to make this distinction clear. Thus we might use the following net to represent the fact that John is 6 feet tall and that he is taller than Bill:

The procedures that operate on nets such as this can exploit the fact that some ares, such as height, define new entities, while others, such as greater-than and value, merely describe relationships among existing entities.

Another example of an important distinction we have missed is the difference between the properties of a node itself and the properties that a node simply holds and passes on to its instances. For example, it is a property of the node Person that it is a subclass of the node Mammal. But the node Person does not have as one of its parts a nose. Instances of the node Person do, and we want them to inherit it.

It is difficult to capture these distinctions without assigning more structure to our notions of node, link, and value. In the next section, when we talk about frame systems, we do that. But first, we discuss a network-oriented solution to a simpler problem; this solution illustrates what can be done in the network model but at what price in complexity.

9.1.4 Partitioned Semantic Nets

Suppose we want to represent simple quantified expressions in semantic nets. One way to do this is to partition the semantic net into a hierarehical set of spares, each of which corresponds to the scope of one or more variables [Hendrix,1977]. To see how this works, consider first the simple net shown in Figure 9.4(a). This net corresponds to the statement

The nodes Dogs, Bite, and Mail-Carrier represent the classes of dogs, bitings, and mail carriers, respectively, while the nodes d, b, and m represent a particular dog, a particular biting, and a particular mail carrier. This fact can easily be represented by a single net with no partitioning.

But now suppose that we want to represent the fact

or, in logic:

Figure 9.4: Using Partitioned Semantic Nets

&every;x : Dog(x) -> &exists;y : Mail-Carrier(y) ^ Bite(x, y)

To represent this fact, it is necessary to encode the scope of the universally quantified variable x. This can be done using partitioning as shown in Figure 9.4(b). The node g stands for the assertion given above. Node g is an instance of the special class GS of general statements about the world (i.e., those with universal quantifiers). Every element of GS has at least two attributes: a form, which states the relation that is being asserted. and one or more b connections, one for each of the universally quantified variables. In this example, there is only one such variable d, which can stand for any element of the class Dogs. The other two variables in the form, b and m, are understood to be existentially quantified. In other words, for every dog d, there exists a biting event b, and a mail carrier m, such that d is the assailant of M and m is the victim.

To see how partitioning makes variable quantification explicit, consider next the similar sentence:

The representation of this sentence is shown in Figure 9.4(c). In this net, the node c representing the victim lies outside the form of the general statement. Thus it is not viewed as an existentially quantified variabk whose value may depend on the value of d. Instead it is interprcted ae cfanding for a specific ontity (in this case, a particular constable), just as do other nodes in a standard, nonpartitioned net.

Figure 9.4(d) shows how yet another similar sentence:

would be represented. In this case, g has two &every; links, one pointing to d, which represents any dog, and one pointing to m, representing any mail carrier.

The spaces of a partitioned semantic net are related to each other by an inclusion hierarchy. For example, in Figure 9.4(d), space S1 is included in space SA. Whenever a search process operates in a partitioned semantic net, it can explore nodes and arcs in the space from which it starts and in other spaces that contain the starting point, but it cannot go downward, except in special circumstances, such as when a form arc is being traversed. So, returning to Figure 9.4(d), from node d it can be determined that d must be a dog. But if we were to start at the node Dogs and search for all known instances of dogs by traversing isa links, we would not find d since it and the link to it are in the space S1, which is at a lower level than space SA, which contains Dogs. This is important, since d does not stand for a particular dog; it is merely a variable that can be instantiated with a value that represents a dog.

9.1.5 The Evolution into Frames

The idea of a semantic net started out simply as a way to represent labeled connections among entities. But, as we have just seen, as we expand the range of problem-solving tasks that the representation must support, the representation itself necessarily begins to become more complex. In particular, it becomes useful to assign more structure to nodes as well as to links. Although there is no clear distinction between a semantic net and a frame system, the more structure the system has, the more likely it is to be termed a frame system. In the next section we continue our discussion of structured slot-and-filler representations by describing some of the most imponant capabilities that frame systems offer.

9.2 Frames

A frame is a collection of attributes (usually called slots) and associated values (and possibly constraints on vafues) that describe some entity in the world. Sometimes a frame describes an entity in some absolute sense; sometimes it represents the entity from a particular point of view (as it did in the vision system proposal [Minsky, 1975] in which the term frame was first introduced). A single frame taken alone is rarely useful. Instead, we build frame systems out of collections of frames that are connected to each other by virtue of the fact that the value of an attribute of one frame may be another frame. In the rest of this section, we expand on this simple definition and explore ways that frame systems can be used to encode knowledge and support reasoning.

9.2.1 Frames as Sets and Instances

Set theory provides a good basis for understanding frame systems. Although not all frame systems are defined this way, we do so here. In this view, each frame represents either a class (a set) or an instance (an element of a class). To see how this works, consider the frame system shown in Figure 9.5, which is a slightly modified form of the network we showed in Figure 4.5. In this example, the frames Person, Adult-Male, ML-Baseball-Player (corresponding to major league baseball players), Pitcher, and ML-Baseball-Team (for major league baseball team) are all classes. The frames Pee-Wee-Reese and Brooklyn-Dodgers are instances.

The isa relation that we have been using without a precise definition is in fact the subset relation. The set of adult males is a subset of the set of people. liie set of major league baseball players is a subset of the set of adult males, and so forth. Our instance relation corresponds to the relation element-of. Pee Wee Reese is an element of the set of fielders. Thus he is also an element of all of the supersets of fielders, including major league baseball players and people. The transitivity of isa that we have taken for granted in our description of property inheritance follows dinectly from the transitivity of the subset relation.

Both the isa and instance relations have inverse attributes, which we call subclasses and all-instances. We do not bother to write them explicitly in our examples unless we need to refer to them. We assume that the frame system maintains them automatically, either explicitly or by computing them if necessary.

Because a class represents a set, there are two kinds of attributes that can be associated with it. There are attributes about the set itself, and there are attributes that are to be inherited by each element of the set. We indicate the difference between these two by prefixing the latter with an asterisk (*). For example, consider the class ML-Baseball-Player. We have shown only two properties of it as a set: It is a subset of the set of adult males. And it has cardinality 624 (i.e., there are 624 major league baseball players). We have Iisted five properties that aIl major league baseball players have (height, bats, batting-average, team, and uniform-color), and we have specified default values for the first three of them. By providing both kinds of slots, we allow a class both to define a set of objects and to describe a prototypical object of the set.

Sometimes, the distinction between a set and an individual instance may not seem clear. For example, the team Brooklyn-Dodgers, which we have described as an instance of the class of major league baseball teams, could be thought of as a set of players. In fact, notice that the value of the slot ployers is a set. Suppose, instead, that we want to represent the Dodgers as a class instead of an instance. Then its instances would be the individual players. It cannot stay where it is in the isa hierarchy; it cannot be a subclass of ML-Baseball-Team, because if it were, then its elements, namely the players, would also, by the transitivity ofsubclass, be elements of ML-Baseball-Team, which is not what we want to say. We have to put it somewhere else in tho isa hierarchy. For example, we could make it a subclass of major league baseball players. Then its elements, the players, are also elements of ML-Baseball-Pluyer, Adult-Male, and Person. That is acceptable. But if we do that, we lose the ability to inherit properties of the Dodgers from general information about baseball teams. We can still inherit attributes for the elements of the team, but we cannot inherit properties of tho team as a whole, i.o., of the set of players. For example. we might like to know what the dofault sizz of tho team is,

Figure 9.5: A Simplified Frame System

that it has a manager, and so on. The easiest way to allow for this is to go back to the idea of the Dodgers as an instance of ML-Baseball-Team, with the set of players given as a slot value.

But what we have encountered here is an example of a more general problem. A class is a set, and we want to be able to talk about properties that its elements possess. We want to use inheritance to infer those properties from general knowledge about the set. But a class is also an entity in itself. It may possess properties that belong not to the individual instances but rather to the class as a whole. In the case of Brooklyn-Dodgers, such properties included team size and the existence of a manager. We may even want to inherit some of these properties fcom a more general kind of set. For example, the Dodgers can inherit a default team size from the set of all major league baseball teams. To support this. we need to view a class as two things simultaneously: a subset (isa) of a larger class that also contains its elements and an instance (instance) of a class of sets, from which it inherits its set-level properties.

To make this distinction clear, it is useful to distinguish between regular classes, whose elements are individual entities, and metaclasses, which are special classes whose elements are themselves classes. A class is now an element of (instance) some class (or classes) as well as a subclass (isa) of one or more classes. A class inherits properties from the class of which it is an instance, just as any instance does. In addition, a class passes inheritable properties down from its superclasses to its instances.

Let's consider an example. Figure 9.6 shows how we could represent teams as classes using this distinction. Figure 9.7 shows a graphic view ofthe same classes. The most basic metaclass is the class Class. It represents the set of all classes. All classes are instances of it, either directly or through one of its subclasses. In the example, Team is a subclass (subset) of Class and ML-Baseball-Team is a subclass of Team. The class Class introduces the attribute cardinality, which is to be inherited by all instances of Class (including itself). This makes sense since all the instances of Class are sets and all sets have a cardinality.

Team represents a subset of the set of all sets, namely those whose elements are sets of players on a team. It inherits the property of having a cardinality from Class. Team introduces the attribute team-size, which all its elements possess. Notice that team-size is like cardinality in that it measures the size of a set. But it applies to something different; cardinality applies to sets of sets and is inherited by all elements of Class. The slot team-size applies to the elements of those sets that happen to be teams. Those elements are sets of individuals.

ML-Baseball-Team is also an instance of Class, since it is a set. It inherits the properly of having a cardinality from the set of which it is an instance, namely Class. But it is a subset of Team. All of its instances will have the property of having a team-size since they are also instances of the superclass Team. We have added at this level the additional fact that the default team size is 24, so all instances of ML-Baseball-Team will inherit that as well. In addition, we have added the inheritable slot manager.

Brooklyn-Dodgers is an instance of a ML-Baseball-Team. It is not an instance of Class because its elements are individuals, not sets. Brooklyn-Dodgers is a subclass of ML-Baseball-Player since all of its elements are also elements of that set. Since it is an instance of a ML-Baseball-Team, it inherits the properties team-size and manager, as well as their default values. It specifies a new attribute uniform-color, which is to be inherited by all of its instances (who will be individual players).

Figure 9.6: Representing the Class of All Teams as a Metaclass

Figure 9.7: Classes and Metaclasses

Finally, Pee-Wee-Reese is an instance of Brooklyn-Dodgers. That makes him also, by transitivity up isa links, an instance of ML-Baseball-Player. But recall that in our earlier example we also used the class Fielder, to which we attached the fact that fielders have above-average batting averages. To allow that here, we simply make Pee Wee an instance of Fielder as well. He will thus inherit properties from both Brooklyn-Dodgers and from Fielder, as well as from the classes above these. We need to guarantee that when multiple inheritance occurs, as it does here, that it works correctly. Specifically, in this case, we need to assure that batting-average gets inherited from Fielder and not from ML-Baseball-Player through Brooklyn-Dodgers. We return to this issue in Section correspond.

In all the frame systems we illustrate, all classes are instances of the metaclass Class. As a result, they all have the attribute cardinality. We leave the class Class, the isa links to it, and the attribute cardinality out of our descriptions of our examples, though, unless there is some particular reason to include them.

Every class is a set. But not every set should be described as a class. A class describes a set of entities that share significant properties. In particular, the default information associated with a class can be used as a basis for inferring values for the properties of its individual elements. So there is an advantage to representing as a class those sets for which membership serves as a basis for nonmonotonic inheritance. Typically, these are sets in which membership is not highly ephemeral. Instead, membership is based on somc fundamental structural or funetional properties. To see the difference, consider the following sets:

The first two sets can be advantageously represented as classes, with which a substantial number of inheritable attributes can be associated. The last, though, is different. The only properties that all the elements ofthat set probably share are the definition of the set itself and some other properties that follow from the definition (e.g., they are being transported from one place to another). A simple set, with some associated assertions, is adequate to represent these facts; nonmonotonic inheritance is not necessary.

9.2.2 Other Ways of Relating Classes to Each Other

We have talked up to this point about two ways in which classes (sets) can be related to each other. Class1 can be a subset of Class2. Or, if Class2 is a metaclass, then Class1 can be an instance of Class2. But there are other ways that classes can be related to each other, corresponding to ways that sets of objects in the world can be related.

One such relationship is mutually-disjoint-with, which relates a class to one or more other classes that are guaranteed to have no elements in common with it. Another important relationship is is-covered-by, which relates a class to a set of subclasses, the union of which is equal to it. If a class is-covered-by a set S of mutually disjoint classes, then S is called a partition of the class.

For examples of these relationships, consider the classes shown in Figure 9.8, which represent two orthogonal ways of decomposing the class of major league baseball players. Everyone is either a pitcher, a catcher, or a fielder (and no one is more than one of these). In addition, everyone plays in either the National League or the American League, but not both.

9.2.3 Slots as Full-Fledged Objects

So far, we have provided a way to describe sets of objects and individual objects, both in terms of attributes and values. Thus we have made extensive use of attributes, which we have represented as slots attached to frames. But it tums out that there are several reasons why we would like to be able to represent attributes explicitly and describe their properties. Some of the properties we would like to be able to represent and use in reasoning include:

In order to be able to represent these attributes of attributes, we need to describe attributes (slots) as frames. These frames will be organized into an isa hierarehy, just as any other frames are, and that hierarehy can then be used to support inheritance of values for attributes of slots. Before we can describe such a hierarehy in detail, we need to formalize our notion of a slot.

A slot is a relation. It maps from elements of its domain (the classes for which it makes sense) to elements of its range (its possible values). A relation is a set of ordered pairs. Thus it makes sense to say that one relation (R1) is a subset of another (R2). In that case, R1 is a specialization of R2, so in our terminology isa(R1, R2). Since a slot is a set, the set of all slots, which we will call Slot, is a metaclass. Its instances are slots, which may have subslots.

Figures 9.9 and 9.10 illustrate several examples of slots represented as frames. Slot is a metaclass. Its instances are slots (each of which is a set ofordered pairs). Associated with the metaclass are attributes that each instance (i.e., each actual slot) will inherit. Each slot, since it is a relation, has a domain and a range. We represent the domain in the slot labeled domain. We break up the representation of the range into two parts: range gives the class of which elements of the range must be elements; range-constraint contains a logical expression that further constrains the range to be elements of range that also satisfy the constraint. If range-constraint is absent, it is taken to be TRUE. The advantage to breaking the description apart into these two pieces is that type checking is much cheaper than is arbitrary constraint checking, so it is useful to be able to do it separately and early during some reasoning processes.

The other slots do what you would expect from their names. If there is a value for definition, it must be propagated to all instances of the slot. Ifthere is a value for default, that value is inherited to all instances of the slot unless there is an overriding value. The attribute transfers-through lists other slots from which values for this slot can be derived through inheritance. The to-compute slot contains a procedure for deriving its value. The inverse attribute contains the inverse of the slot. Although in principle all slots have inverses, sometimes they are not useful enough in reasoning to be worth representing. And simgle-valued is used to mark the special cases in which the slot is a function and so can have only one value.

Of course, there is no advantage to representing these properties of slots if there is no reasoning mechanism that exploits them. In the rest of our discussion, we assume that the frame-system interpreter knows how to reason with all of these slots of slots as part of its built-in reasoning capability. In particular, we assume that it is capable of performing the following reasoning actions:

There is something slightly counterintuitive about this way of defining slots. We have defined the properties range-constraint and default as pans of a slot. But we often think of them as being properties of a slot associated with a particular class. For example, in Figure 9.5, we listed two defaults for the batting-average slot, one associated with major league baseball players and one associated with fielders. Figure 9.11 shows how this can be represented correctly, by creating a specialization of batting-average that can be associated with a specialization of ML-Baseball-Player to represent the more specific information that is known about the specialized class. This seems cumbersome. It is natural, though, given our definition of a slot as a relation. There are really two relations here, one a specialization of the other. And below we will defioe inheritance so that it looks for values of either the slot it is given or any of that slot's generalizations.

Unfortunately, although this model of slots is simple and it is internally consistent, it is not easy to use. So we introduce some notational shorthand that allows the four most important properties of a slot (domain, range, definition, and default) to be defined implicitly by how the slot is used in the definitions of the classes in its domain. We describe the domain implicitly to be the class where the slot appears. We describe the range and any range constraints with the clause MUST BE, as the value of an inherited slot. Figure 9.12 shows an example of this notation. And we describe the definition and the default, if they are present. by inserting them as the value of the slot when it appears. The two will be distinguished by prefixing a definitional value with an asterisk (*). We then let the underlying bookkeeping of the frame system create the frames that represent slots asthey are needed.

Now let's Iook at examples of how these slots can be used. The slots bats and my-manager illustrate the use of the to-compute attribute of a slot. The variable x will be bound to the frame to which the slot is attached. We use the dot notation to specify the value of a slot of a frame. Specifically, x,y describes the value(s) of the y slot of frame x. So we know that to compute a frame's value for my-manager, it is necessary to find the frame's value for team, then find the resulting team's manager. We have simply composed two slots to form a new one.[Footnote: Notice that since slots are relations rather than functions, their composition may return a net of values.] Computing the value of the bats slot is even simpler. Just go get the value of the handed slot.

Figure 9.11 : Associating Defaults with Slots

Figure 9.12: A Shorthand Notation for Slot-Range Specification

The manager slot illustrates the use of a range constraint. It is stated in terms of a variable x, which is bound to the frame whose manager slot is being described. It requires that any manager be not only a person but someone with baseball experience. It relies on the domain-specific function baseball-experience, which must be defined somewhere in the system.

The slots color and uniform-color illustrate the arrangement of slots in an isa hierarchy. The relation color is a fairly general one that holds between physical objects and colors. The attribute uniform-color is a restricted form of color that applies only between team players and the colors that are allowed for team uniforms (anything but pink). Arranging slots in a hierarchy is useful for the same reason that arranging anything else in a hierarchy is: it supports inheritance. In this example, the general slot color is known to have high visual salience. The more specific slot uniform-color then inherits this property, so it too is known to have high visual salience.

The slot color also illustrates the use of the transfers-through slot, which defines a way of computing a slot's value by retrieving it from the same slot of a related object. In this example, we used transfers-through to capture the fact that if you take an object and chop it up into several top level parts (in other words. parts that are not contained inside each other), then they will all be the same color. For example, the arm of a sofa is the same color as the sofa. Formally, what transfers-through means in this example is

Figure 9.13: Representing Slot-Values

color(x, y) ^ top-level-part-of(z, x) -#&62; color(z, y)

In addition to these domain-independent slot attributes, slots may have domain- specific properties that support probtem solving in a particulardomain. Since these slots are not treated explicitly by the frame-system interpreter, they will be useful precisely to the extent that the domain problem solver exploits them.

9.2.4 Slot-Values as Objects

In the last section, we reified the notion of a slot by making it an explicit object that we could make assertions about. In some sense this was not necessary. A finite relation can be completely described by listing its elements. But in practical knowledge-based systems one often does not have that list. So it can be very important to be able to make assertions about the list without knowing all of its elements. Reification gave us a way to do this.

The next step along this path is to do the same thing to a particular attribute-value (an instance of a relation) that we did to the relation itself. We can reify it and make it an object about which assenions can be made. To see why we might want to do this, let us return to the example of John and Bill's height that we discussed in Section 9. I.3. Figure 9.13 shows a frame-based representation of some of the facts. We could easily record Bill's height if we knew it. Suppose, though, that we do not know it. All we know is that John is taller than Bill. We need a way to make an assertion about the value of a slot without knowing what that value is. To do that, we need to view the slot and its value as an object.

We could attempt to do this the same way we made slots themselves into objects, namely by representing them explicitly as frames. There seems littleadvantage todoing ihat in this case, though, because the main advantage of frames does not apply to slot values: frames are organized into an isa hierarchy and thus support inheritance. There is no basis for such an organization of slot values. So instead, we augment our value representation language to allow the value of a slot to be stated as either or both of:

Figure 9.14: Representing Slot-Values with Lambda Notation

If we do this to the frames of Figure 4.13, then we get the frames of Figure 9.14. We again use the lambda notation as a way to pick up the name of the frame that is being described.

9.2.5 Inheritance Revisited

In Chapter 4, we presented a simple algorithm for inheritance. But that algorithm assumed that the isa hierarchy was a tree. This is often not the case. To support flexible representations of knowledge about the world, it is necessary to allow the hierarchy to be an arbitrary directed acyclic graph (DAG). We know that acyclic graphs are adequate because isa corresponds to the subset relation. Hierarchies that are not trees are called tangled hierarchies. Tangled hierarchies require a new inheritance algorithm. In the rest of this section, we discuss an algorithm for inheriting values for single-valued slots in a iangled hierarchy. We leave the problem of inheriting multivalued slots as an exercise.

Consider the two examples shown in Figure 9.15 (in which we retum to a network notation to make it easy to visualize the isa structure). In Figure 9.I5(u), we want to decide whether Fifi can fly. The correct answer is no. Although birds in general can 8y, the subset of birds, ostriches, does not. Although the class Pet-Bird provides a path from Fifi to Bird and thus to the answer that Fifi can fly, it provides no infomiation that conflicts with the special case knowledge associated with the the class Ostrich, so it should have no affect on the answer. To handle this case conectly, we need an algorithm for traversing the isa hierarchy that guarantees that specific knowledge will always dominate more general facts.

In Figure 9.15(b), we return to a problem we discussed in Section 7.2.1, namely determining whether Dick is a pacifist. Again, we must traverse multiple instance links, and more than one answer can be found along the paths. But in this case, there is no well-founded basis for choosing one answer over the other. The classes that are associated with the candidate answers are incommensurate with each other in the partial ordering that is defined by the DAG formed by the isa hierarchy. Just as we found that in Default L.ogic this theory had two extensions and there was no principled basis for choosing between them, what we need here is an inheritance algorithm that reports the ambiguity; we do not want an algorithm that finds one answer (arbitrarily) and stops without noticing the other.

One possible basis for a new inheritance algorithm is path length. This can be implemented by executing a breadth-first seareh, starting with the frame for which a slot value is needed. Follow its instance links, then follow isa links upward. If a path produces a value, it can be terminated, as can all other paths once their length

Figure 9.15: Tangled Hierarchies

Figure 9.16: More Tangled Hierarchies

exceeds that of the successful path. This algorithm works for both of the examples in Figure 9.15. In (a), it finds a value at Ostrich. It continues the other path to the same length (Pet-Birc!), fails to find any other answers, and then halts. In the case of (b), it finds two competing answers at the same level, so it can report the contradiction.

But now consider the examples shown in Figure 9.16. In the case of (a), our new algorithm reaches Bird (via Pet-Bird) before it reaches Ostrich. So it reports that Fifi can fly. In the case of (b), the algorithm reaches Quaker and stops without noticing a contradiction. The problem is that path length does not always correspond to the level of generality of a class. Sometimes what it really corresponds to is the degree of elaboration of classes in the knowledge base. If some regions of the knowledge base have been elaborated more fully than others, then their paths will tend to be longer. But this should not influence the result of inheritance if no new information about the desired attribute has been added.

The solution to this problem is to base our inheritance algorithm not on path length but on the notion of inferential distance [Toarctzky, 1986], which can be defined as follows:

Notice that inferential distance defines only a partial ordering. Some classes are incommensurate with each other under it.

We can now define the result ofinheritance as follows: The set of competing values for a slot S in a frame F contains all those values that

Notice that under this definition competing values that are derived from incommensurate frames continue to compete.

Using this definition, let us return to our examples. For Figure 9.15(a), we had two candidate classes from which to get an answer. But Ostrich has a shorter inferentiat distance to Fifi than Bird does, so we get the single answer no. For Figure 9.15(b), we get two answers, and neither is closer to Dick than the other so we correctly identify a contradiction. For Figure 9.16(a), we get two answers, but again Ostrich has a shorter inferential distance to Fifi than Bird does. The significant thing about the way we have defined inferential distance is that as long as Ostrich is a subclass of Bird, it will be closer to all its instances than Bird is, no matter how many other classes are added to the system. For Figure 9.16(b), we again get two answers and again neither is closer to Dick than the other.

There are several ways that this definition can be implemented as an inheritance algorithm. We present a simple one. It can be made more efficient by caching paths in the hierarchy, but we do not do that here.

Algorithm: Property Inheritance

To retrieve a value V for slot S of an instance F do:

  1. Set CANDlDATES to empty.
  2. Do breadth-first or depth-first search up the isa hierarchy from F, following all instance and isa links. At each step, see ifa value for S or one of its generalizations is stored.
    1. If a value is found, add it to CANDIDATES and terminate that branch of the search.
    2. If no value is found but there are instance or isa links upward, follow them.
    3. Otherwise, terminate the branch.
  3. For each element C of CANDlDATES do:
    1. See if there is any other element of CANDIDATES that was derived from a class closer to F than the clsss from which C caax.
    2. If there is, then, remove C from CANDIDATES.
  4. Check the cardinality of CANDIDATES:
    1. If it is 0, then report that no value was found.
    2. If it is 1, then return the single element of CANDIDATES as V.
    3. If it is greater than 1, report a contradiction.

This algorithm is guaranteed to terminate because the isa hierarchy is represented as an acyclic graph.

9.2.6 Frame Languages

The idea of a frame system as a way to represent declarative knowledge has been encapsulated in a series of frame-oriented knowledge representation languages, whose features have evolved and been driven by an increased understanding of the sort of representation issues we have been discussing. Examples ofsuch languages include KRL [Bobrow and Winograd,1977], FRL [Roberts and Goldstein, 1977], RLL [Greiner and et al, I980], KL-ONE [Brachman, 1979; Brachman and Schmolze,1985], KRYPTON [Brachman et al., 1985], NIKL [Kaczmarek et al., 1986], CYCL [Lenat and Guha, 1990], conceptual graphs [Sowa,1984), THEO [Mitchell et al.,1989], and FRAMEKIT [Nyberg,1988]. Although not all of these systems support all of the capabilities that we have discussed, the more modern of these systems permit elaborate and efficient representation of many kinds of knowledge. Their reasoning methods include most of the ones described here, plus many more, including subsumption checking, automatic classification, and various methods for consistency maintenance.

9.3 Exercises

  1. Construct semantic net representations for the following:
    1. Pompeian(Maþrus), Blacksmith(Maþrus)
    2. Mary gave the green fiowered vase to her favorite cousin.
  2. Suppose we want to use a semantic net to discover relationships that could help in disambiguating the word "bank" in the sentence John went downtown to deposit his money in the bank. The financial institution meaning for bank should be preferred over the river bank meaning.
    1. Construct a semantic net that contains representations for the relevant concepts.
    2. Show how intersection search could be used to find the connection between the correct meaning for bank and the rest of the sentence motr easily than it ctut find a connection with the incornct meaning.
  3. Construct partitioned semantic net representations for the following:
    1. Every batter hit a ball.
    2. All the batters like the pitcher.
  4. Construct one consistent frame representation of all the baseball knowledge that was described in this chapter. You will need to choose between the two representations for team that we considered.
  5. Modify the property inheritance algorithm of Section 9.2 to work for multiple- valued attributes, such as the attribute believes-in-principles, defined as follows:

    believes-in-principles

    instance : Slot

    domain : Person

    range : Philosophical-Principles

    single-valued : FALSE

  6. Define the value of a multiple-valued slot S of class C to be the union of the values that are found for S and all its generalizations at C and all its generalizations. Modify your technique to allow a class to exclude specific values that are associated with one or more of its superclasses.
  7. Pick a problem area and represent some knowledge about it the way we represented baseball knowledge in this chapter.