FRAMES AND INHERITANCE

Although the scheme above incorporates the most frequently used link types, it can never incorporate all possible types. Any two-place predicate or relation could be made into a link type, for example: "is the father of", "is greater than", "sits to the left of". (More generally, it is well-known that any n-place predicate can be reduced to a collection of typed links.) This freedom will quickly overburden any semantic network representation. Another AI representation scheme, a "frame" (Minsky, 1975), extends the semantic network representation by allowing custom-made relations to be associated with different types of concepts. A frame consists of a central concept, which is related to other concepts by "attribute-value" pairs (also called "slots and fillers"). For example, the concept car has attributes (slots) such as color, brand, model, and year. A particular instance of that concept, such as my own car, will have particular values (fillers) for these respective attributes, such as grey, Honda, Civic and 1992. The values of an attribute are in general concepts themselves and thus the attribute plays the role of a typed link connecting nodes in a semantic network.

The unrestricted proliferation of attribute-value pairs is kept in check by the mechanism of inheritance: concepts inherit most of their attributes (and sometimes also values) from the concepts higher up in the "is a" hierarchy, that is, from the classes to which they belong as subclasses or as instances. For example, a car is a vehicle, and therefore car will inherit a number of attributes such as number of wheels or type of fuel from the vehicle category. Vehicle itself will inherit attributes such as size and weight from the object category. This has the advantage that each attribute only needs to be represented once, in the concept situated at the highest level of the hierarchy where it is needed. Thus, the number of attributes or link types is controlled by associating each of them with one or a few high level concepts.

Such a "frame-like" knowledge representation can be easily expressed in an entailment net. Suppose I wish to express the fact that my car, which is an instance of the class car, has the value grey for its attribute color. Fig. 7 shows how this typical attribute-value pair can be represented with untyped entailment links between nodes typed through the categorical distinctions introduced earlier. The "is a" link between my car and car is obviously an entailment between an object and a class (see Fig. 5). The statement that every car has an attribute color is equivalent to the statement that the class car is a subclass of, and therefore entails, the class of colored things. Thus, the entailment link goes from car to color. Similarly my car, which is an object, belongs to the class of grey things which is itself a subclass of the class of colored things. Thus, the scheme linking an instance to its class and to an attribute-value pair can be reduced in essence to an entailment graph with two times two parallel arrows, in a configuration resembling what is called a "commutative diagram" in mathematics.

Fig. 7: representation of a frame (car) with attribute (color) and value (grey) for an instance (my car), as a commutative diagram (thick arrows) in an entailment network.

Since "if...then" entailments are supposed to be transitive, inheritance of attributes comes automatically. Whether my car gets its attribute number of wheels through the class car or through the higher class vehicle should not make a difference. In both cases, a commutative diagram can be drawn, with an entailment path running from my car to number of wheels, either through car or through vehicle. The inheritance of values in a frame has a more subtle feature, though, the default mechanism: a concept inherits its values from the class to which it belongs, unless there are values that are directly attached to the concept. The values filling the slots at the level of the concept override those filling the same slots at the higher levels from which it normally inherits. Inheritance of values only takes place if the values are not specified at the level of the concept itself.

The traditional example of inheritance by default is the concept of "penguin", which belongs to the class of birds, from which it inherits properties such as being warm-blooded, and laying eggs. However, by default the class of birds also has the property of being able to fly, which the penguin does not have. This is represented by having a specific attribute-value pair (can_fly?, false) attached to the concept penguin), while other subclasses of the bird class, such as robins or sparrows simply inherit their attribute value pair (can_fly?, true) from the parent class. This can be represented in an entailment net by the following simple graph (Fig. 8):

Fig. 8: representation by means of entailment links of a default inheritance (birds can fly) being overwritten for the exceptional case of "penguin" .

In order to interpret this entailment network correctly, the requirement of transitivity for the entailment relation must be relaxed, so that the direct entailment penguin -> cannot fly can override the indirect path penguin -> bird, bird -> can fly. The general rule could be that if two entailment paths from the same node lead to contradictory results, the shortest path is to be preferred.

This somewhat ad hoc interpretation may be justified if we consider a more general interpretation of an entailment a -> b, where it expresses a kind of "expectation" of b, given a, rather than "certitude" of b, given a. Expectations can come with different "strengths" or degrees of certainty. These may be expressed as a kind of conditional probability of b, given a: P(b| a). If we assume that typical entailment links have a strength of 1 or slightly less, paths of entailments will have a strength that is the product of the strengths of the individual links. This will be lower than or equal to the strength of the weakest link. Therefore, if the link from penguin to bird has maximal strength, P(bird| penguin) = 1, while P(can fly| bird) = 0.9, the combined path P(can fly | penguin) = 0.9, which is overridden by the stronger connection P (cannot fly| penguin) = 1. We will here not go into further detail about such calculations, but discuss an application of entailment nets which uses link strengths in a more general way.

Learning Webs