next up previous
Next: Incompleteness in NEOCLASSIC Up: NeoClassic User's GuideVersion 1.0 Previous: Updates

Subsections

Inference in NEOCLASSIC

  In each knowledge base NEOCLASSIC creates a taxonomy of concepts and individuals, based on the subsumption relationship, so it has to be able to (efficiently) answer subsumption questions. Determining subsumption in NEOCLASSIC is a two-part process, consisting first of normalization, and then of checking whether one normalized concept is more general than another.

To perform normalization, NEOCLASSIC takes the input (told) information about a concept or individual, and computes an inferred (derived) version. The derived version contains information from several sources, including rule-firings and propagations (for individuals), and from inheritance, classification, and combining information in a number of ways (for both concepts and individuals). The derived version contains all the information that could be deduced about the concept or individual. Functions that retrieve information about concepts and individuals come in two varieties: one that retrieves told information and one that retrieves derived information.

NEOCLASSIC is normally only concerned with the normalized (derived) version of a concept or individual, except when performing retraction--as only told information can be retracted, and in explanation--where told information is the root cause of all information.

This section presents an informal discussion of the normalization and subsumption process so that users can understand how NEOCLASSIC makes certain inferences. It is not necessary to fully understand this section (especially the parts on classification) in order to be able to use NEOCLASSIC.

Concepts

Normalization

 

The normalization of concepts includes :

For example, suppose a HealthyVegetarian is defined as

where Person, HealthyThing, and Plant are all primitive concepts. Then the normalized form of HealthyVegetarian isThe all restrictions on the food role were combined, and the embedded and, which was redundant, was removed.

Now define an OldHealthyVegetarian as

Then the normalized form of OldHealthyVegetarian isIt inherits the primitive superconcept Person, as well as the all restriction on food.

Suppose concept C is defined as

where evenp is a HOST test function that recognizes even integers. The normalized form of C isNote that, since 25 is not an even integer, it has been filtered out.

The last part of normalization checks concepts for consistency. Examples of inconsistent concepts are:

where Male and Female are two disjoint primitive concepts of the same disjoint grouping; since Jack is not a member of the set (oneOf Mary Sue);andsince 17 is inconsistent with the specified interval.

Subsumption

 

A concept C1 subsumes another concept C2 if C1 is an equivalent concept to C2, or C1 is a more general concept than C2. Once two concepts have been normalized, NEOCLASSIC can easily determine whether one concept subsumes the other. Basically, in order for C1 to subsume C2, for each description on C1 there must be an equivalent or more specific description on C2.

For example, there are the primitive concepts Mammal and Plant under the concept ClassicThing, the primitive concept Person under Mammal, and the primitive concept Fruit under Plant. Now define the concept VegetarianMammal as

and the concept FruitEatingPerson asVegetarianMammal subsumes (is more general than) FruitEatingPerson, because:

The Classification Process

Classification of a concept involves finding the parents, children, and direct instances of the concept, and firing any rules with this concept as antecedent on all instances of the concept. NEOCLASSIC finds the parents (most specific subsumers) of C as follows: First start at the top of the concept hierarchy (with either ClassicThing or HostThing, depending on the realm of C--assume it is a CLASSIC concept for the sake of this example). For each concept Ci that is known to subsume C (starting with ClassicThing), check each of its children Cj to see if Cj subsumes C. The lowest such set of concepts in the concept hierarchy are C's parents.

To find C's children (most general subsumees), start with the parents you have just found for C, and for each child of the parents, see if C subsumes it. If so, you have found a child; if not, try its children until you have found a child of C, or a concept has no children.

To find C's instances (direct instances, not descendant instances), look at each individual which is a descendant instance of one of C's parents, but is not a descendant instance of one of C's children. If C subsumes it (see Section 9.2.3), it is an instance of C.


  
Figure 2: Hierarchy for individual subsumption example.
\begin{figure*}
\hbox to \linewidth{
\hfill{\vbox to 1.5in{\vfill
\epsfxsize=4.5in \epsfbox{hierarchy2-subsumption.eps}
\vfill}}
\hfill}\end{figure*}

Now any rules with C as antecedent are fired on C's instances (descendant instances, i.e., all instances), and these individuals are reclassified (see Section 9.2.4 below).

Individuals

Normalization

 

The normalization of an individual includes all the steps involved in the normalization of a concept. In addition, it involves running any test functions on the individual (for checking its consistency), and propagating information to other individuals when new facts are implied by all restrictions.

After inheriting information from all its parents, an individual is checked for consistency. The examples of inconsistent concepts from Section 9.1.1 would also cause inconsistent individuals. The following are some additional examples of inconsistent individuals:

Propagation

Whenever an individual, i, that has fillers for any role is normalized. These fillers are then given the value restriction for this role on i. This process is referred to as propagation, since information has been propagated from i to the filler.

For example, consider:

When MrsCasey is normalized, NEOCLASSIC recognizes that MrsCasey has a child filler, Ben, and that all child fillers must be Doctor. Therefore, NEOCLASSIC propagates Doctor to Ben. If it turned out that Ben had other information that was contradictory to Doctor, then an error would be generated due to the contradiction, and the entire operation would be cancelled.

Propagation only occurs on individuals that have a value restriction and a filler(s) on the same rule, and not on concepts that have a value restriction and a filler(s) on the same role. For example, suppose that Doctor and Bum were defined as disjoint primitive concepts:

Now define two concepts, ProudParentOfBen and EmbarrassedParentOfBen, that would cause Ben to be a Doctor and a Bum respectively.While these two concept definitions seem to be contradictory, they are both legal and allowed to exist at the same time. However, once an individual is defined to be an instance of one of the above two concepts, no individual could be defined as an instance of the other. For example, suppose one tried to define the following two individuals:Then following the first creation, NEOCLASSIC would propagate Doctor to Ben. Following the second creation, NEOCLASSIC would attempt to propagate Bum to Ben, which would generate an error since Bum and Doctor are disjoint concepts. As a result, MrCasey would not be added to the knowledge base.

Subsumption

  An individual I is subsumed by, or satisfies, or is an instance of a concept C if I is described by C, i.e., if I satisfies every description on C. Once an individual has been normalized, NEOCLASSIC can easily determine whether or not it is subsumed by, or satisfies, a concept. Basically, in order for concept C to subsume a normalized individual I, each description on C must be satisfied by I, either because there is an equivalent or more specific description on I, or because the description on C can be derived from the descriptions, fillers, and closed roles on I.

For example, suppose there are the primitive concepts Person and Alcoholic-Beverage under the concept ClassicThing, the primitive concepts Woman and Doctor under the concept Person, and the primitive concept Wine under the concept Alcoholic-Beverage (see Figure 2).

Now define the concept C1 as a Person with at least 1 child, all of whose children are Doctors, and all of whose friends drink only Alcoholic-Beverages:

Suppose that Fran is a Woman with exactly 2 children, Jack and Barbara, both of whom have been previously asserted to be Doctors; all her friends drink only wine; and Susy is one of her friends: Then C1 subsumes Fran, because each description on C1 is satisfied by Fran: The extra fact known about Fran--that Susy is her friend--does not affect this question of subsumption.

The Classification Process

 

Classification of an individual involves finding the parents of the individual, propagating any information from that individual to other individuals and reclassifying them, and firing any appropriate rules on the individual. The parents of an individual are found in the same way as the parents of a concept, using the subsumption check for individuals described above (an individual has no children, and of course, no instances).

If the individual has any new parents as a result of being classified, all rules with the new parents or their ancestors as antecedents are fired on the individual, and the individual is reclassified. For example, if Mary is classified as a VegetarianPerson, then any rules with VegetarianPerson or Person as antecedents are fired.

Information may be propagated from this individual to other individuals (see the example in Section 9.2.1 above, where Jim's favorite food was inferred to be Lasagne). Any affected individuals are reclassified.


next up previous
Next: Incompleteness in NEOCLASSIC Up: NeoClassic User's GuideVersion 1.0 Previous: Updates
Peter F. Patel-Schneider
7/15/1998