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 :

• inheriting information from parent concepts,
• combining descriptions on the same role,
• eliminating embedded and operators,
• deducing fillers when they are implied by all restrictions,
• deducing fillers when they are restricted to Integers, and they are implied by a fully-specified interval (minimum and maximum restrictions are both specified),
• inheriting and combining role restrictions up and down role hierarchies,
• checking the consistency of descriptions, disjoint primitive concepts, etc.,
• combining oneOf descriptions (taking their intersection),
• filtering oneOf descriptions which are restricted to HOST individuals, by all applicable test descriptions, since the properties of HOST individuals cannot change (this is not done for CLASSIC individuals since their properties can change).

For example, suppose a HealthyVegetarian is defined as

• []

  
  (and Person (all food HealthyThing)
  		(all food Plant)),
  

where Person, HealthyThing, and Plant are all primitive concepts. Then the normalized form of HealthyVegetarian is

• []

  
  (and Person
  		(all food (and HealthyThing Plant))).
  

The all restrictions on the food role were combined, and the embedded and, which was redundant, was removed.

Now define an OldHealthyVegetarian as

• []

  
  (and HealthyVegetarian (all age Old)).
  

Then the normalized form of OldHealthyVegetarian is

• []

  
  (and Person
  		(all food (and HealthyThing Plant))
  		(all age Old))
  

It inherits the primitive superconcept Person, as well as the all restriction on food.

Suppose concept C is defined as

• []

  
  (all age (and Integer
  		(oneOf 20 25 30)
  		(testH evenp)))
  

where evenp is a HOST test function that recognizes even integers. The normalized form of C is

• []

  
  (all age (and Integer
  		(oneOf 20 30)
  		(testH evenp)))
  

Note 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:

• [](and (atLeast 2 child) (atMost 1 child));

• [](and (all child Male) (all child Female))

where Male and Female are two disjoint primitive concepts of the same disjoint grouping;

• []

  
  (and (fills child Jack)
  		(all child (oneOf Mary  Sue)))
  

since Jack is not a member of the set (oneOf Mary Sue);

• [](and (minimum 3) (maximum 2));

and

• [](and (fills age 17) (all age (minimum 18)))

since 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 Mammal (all food Plant)),
  

and the concept FruitEatingPerson as

• []

  
  (and Person (all food Fruit)).
  

VegetarianMammal subsumes (is more general than) FruitEatingPerson, because:

• Mammal subsumes Person (Person was defined to be more specific than Mammal); and
• the all restriction on food for VegetarianMammal, Plant, subsumes the all restriction on food for FruitEatingPerson, Fruit.

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.

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:

• John contains (all child Male) and (fills child Mary), where Mary is a Female, and Male and Female are two disjoint primitive concepts of the same disjoint grouping;
• Jack contains (atLeast 2 child) and (fills child Jill) (and no other fills statements), and the child role is then closed with cl-ind-close-role ;
• Sally has 2 fillers for the child role, Fred and Sam, and contains the description (atMost 1 child);
• Harry contains (all age Integer) and (fills age 25.5).

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:

• []

  
  (createConcept ProudParent
  		(and Person
  		 		(atLeast 1 child)
  		 		(all child Doctor)))
  (createIndividual Ben) 
  (createIndividual MrsCasey
  		(and ProudParent (fills child Ben)))
  

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:

• [](createConcept Doctor ClassicThing job)
  (createConcept Bum ClassicThing job)

Now define two concepts, ProudParentOfBen and EmbarrassedParentOfBen, that would cause Ben to be a Doctor and a Bum respectively.

• []

  
  (createConcept ProudParentOfBen
  		(and (all child Doctor)
  		 		(fills child Ben))) 
  (createConcept EmbarrassedParentOfBen
  		(and (all child Bum)
  		 		(fills child Ben)))
  

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:

• [](createIndividual MrsCasey ProudParentOfBen)
  (createIndividual MrCasey EmbarrassedParentOfBen)

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:

• []

  
  (and Person
  		(atLeast 1 child)
  		(all child Doctor)
  		(all friend
  		 		(all drink AlcoholicBeverage)))
  

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:

• []

  
  (and Woman
  		(fills child Jack Barbara)
  		(atMost 2 child)
  		(all friend (all drink Wine))
  		(fills friend Susy)).
  

Then C1 subsumes Fran, because each description on C1 is satisfied by Fran:

• Person subsumes Woman;
• Fran has at least 1 child--in fact, she has 2 children (and both are known);
• all her children are Doctors (all of them are known, and they have all been previously asserted to be Doctors);
• all her friends drink only AlcoholicBeverages--in fact, they all drink only Wine, which is subsumed by AlcoholicBeverage.

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.