Home

 

Quick Start with Elisa  

Using Development System Demo's

 

Language Description

1. Lexical Elements
2. Basic Data Types and Expressions
3. Definitions
4. Streams
5. Backtracking
6. Statements and Special Expressions
7. Arrays

8. Lists
9. Descriptors
10. Components
11. Collections
12. Generic Components
13. Terms
14. Categories
15. Types 

16. Built-in Definitions
17. Higher-order Definitions

18. External Interfaces

Index

Data Structures

1. Sequences
2. Examples involving Lists
3. Trees
4. Graphs
5. Searching State Spaces
6. Language Processing
7. Knowledge Representations          

 

Tutorials

1. Multi-value Functions

2. Lists and Streams

3. Descriptors

4. Trees

 

Back Home Up Next

7 KNOWLEDGE REPRESENTATIONS

 

How knowledge can be represented in the computer is an important topic for those programs which are reasoning about their data. Drawing conclusions from facts is often needed in situations where the data itself does not provide the required information. It is also one of the main tasks of knowledge based systems. Knowledge based systems with built-in expertise for a specific problem domain are generally known as expert systems. In this chapter we will review basic concepts in representing knowledge and associated reasoning mechanisms.

In many problem-solving programs there is a need for decision making which is not only based on data but also based on reasoning. For example, a legacy support program may reason that if Albert is the brother of John and John is the father of Peter that Albert is the uncle of Peter.

Reasoning is often based on drawing conclusions from facts. In our example, the facts are that Albert is the brother of John, and John is the father of Peter; the conclusion is that Albert is the uncle of Peter.

In a computer we will need ways to represent knowledge about facts, about conclusions, and about rules used to derive conclusions from facts. There are several ways for knowledge representation. We will discuss in this chapter three methods, based on the way the knowledge is represented:

  • If-then Rules
  • Semantic Networks
  • Frames

For all these methods we will make a distinction between the knowledge base, which holds the description of the knowledge, and the inference engine which is interpreting the description in the knowledge base.

 

7.1 If-then Rules

If-then rules are used to define logical relations between concepts of a given problem domain. Some examples of such rules are:

  • If an animal has hair or an animal gives milk, then it is a mammal.
  • If an automobile engine will not start and fuel reaches the cylinders, then the ignition system is not working properly.
  • If a plant is wilting and the leaves have no yellow spots then there is not enough water.
  • If the infection is a primary bacteremia, and the site of the culture is one of the sterilesites, and the suspected portal of entry of the organism is the gastrointestinal tract, then there is evidence that the identity of the infecting organism is bacteroides.

These examples illustrate if-then rules in different problem domains such as animal identification, automobile diagnosis, biological systems, and medical diagnosis. There are many problem-solving systems that are based on matching rules to given problems. These are often called if-then systems, rule-based systems, situation-action systems, or production systems.

In general, an if-then rule consists of the following form:

if Condition then Conclusion

A Condition may consists of multiple conditions connected by and's and or's. In some rule-based systems, conditions and conclusions may also contain variables, representing unknown entities. In this chapter we assume, for simplicity, that conditions and conclusions do not contain variables.

Let us assume that we want to represent the rule:

if an animal gives milk, then it is a mammal

In Elisa we may express this as:

if gives (animal, milk) then isa (animal, mammal)

In this example gives (animal, milk) is a notation for animal gives milk. Also isa (animal, mammal) means animal is a mammal. In general, conditions, conclusions, and facts are all represented in relational notation.

Let us use as an example a rule set for the identification of animals:

Rule1 = if has(Animal, hair) | gives(Animal, milk)     
        then isa(Animal, mammal);
Rule2 = if has(Animal, feathers) | does(Animal, fly) & lays(Animal, eggs)	
        then isa(Animal, bird);
Rule3 = if eats(Animal, meat) | has(Animal,pointed_teeth) & 
           has(Animal, claws) & has(Animal, forward_eyes) 
	then isa(Animal, carnivore);
Rule4 = if isa(Animal, mammal) & (has(Animal, hoofs) | chews(Animal, cud))
	then isa (Animal, ungulate);
Rule5 = if isa(Animal, mammal) & isa(Animal, carnivore) &
           has(Animal, tawny_color) & has(Animal, darks_spots) 
        then isa(Animal, cheetah);
Rule6 = if isa(Animal, mammal) & isa(Animal, carnivore) &
           has(Animal, tawny_color) & has(Animal, black_stripes) 
        then isa(Animal, tiger);
Rule7 = if isa(Animal, ungulate) & has(Animal, long_neck) &
           has(Animal, long_legs) & has(Animal, dark_spots) 
        then isa(Animal, giraffe);
Rule8 = if isa(Animal, ungulate) & has(Animal, black_stripes) 
        then isa(Animal, zebra);
Rule9 = if isa(Animal, bird) & does_not(Animal, fly) &
           has(Animal, long_neck) & has(Animal, long_legs) & 
           is(Animal, black_and_white) 
        then isa(Animal, ostrich);
Rule10 = if isa(Animal, bird) & does_not(Animal, fly) &
            does (Animal, swim) & is(Animal, black_and_white) 
         then isa(Animal, penguin);
Rule11 = if isa(Animal, bird) & does(Animal, fly_well)
         then isa(Animal, albatross);

Let us now see how this rule set may be used. Suppose we want to identify an animal where we know some of its characteristics. Let us assume that we know that the animal eats meat, has hair, and has a tawny color with black stripes. We may express that as a list of (initial) facts:

{ eats(Animal, meat),
  has (Animal, hair),
  has (Animal, tawny_color),
  has (Animal, black_stripes) }

This list of initial facts will be extended with new facts during the processing of the rule set. For example, based on the fact that the animal eats meat, Rule3 concludes that the animal is a carnivore. So, isa(Animal, carnivore) will be added to the list of known facts.

Exercise:

  • 7.1 Before you proceed, try to determine the type of animal based on the initial facts and the rule set.

In a rule-based system the knowledge base consists of two components: a rule set, and a list of facts. In addition to the knowledge base we also need an inference engine. An inference engine is an interpreter which is interpreting the rules in the rule set and which adds new facts to the facts list. The rules in the rule set may be interpreted in two different ways:

  • The conditions of a rule are first evaluated before the conclusion is drawn. This method is called forward chaining.
  • The conclusion of a rule is used as a hypothesis which should be proved by working backwards to the conditions of a rule. This method is called backward chaining.

It depends on the interpreter which method is used. We will discuss both methods.

 

7.1.1 Forward Chaining

An interpreter is doing forward chaining if it starts with a collection of facts and tries all available rules over and over, adding new facts as it goes, until no rule applies anymore.

In our rule set, an if-then rule has the following form:

Rule = if Conditions then Conclusion

We can easily translate that in a definition which tries to apply a rule:

TryRule(term) -> nothing;
TryRule( phrase( Rule = if Conditions then Conclusion )) = 
                       if Test (Conditions) then add(Facts, Conclusion);

This definition uses pattern matching to separate the various elements of a rule. The pattern has the format of an if-then rule. The pattern variables are Rule, Conditions, and Conclusion. The if and then keywords and the = sign are used as separators.

If the input term matches with an if-then rule then the right side of the definition rule will be executed. This is an if statement which starts with the execution of a Test function to determine if the Conditions are true. If that is the case then the Conclusion is added to the list of Facts.

The Test function can be defined as follows:

Test(term) -> boolean;
Test(Condition1 & Condition2) = Test(Condition1) & Test(Condition2);
Test(Condition1 | Condition2) = Test(Condition1) | Test(Condition2);
Test(Condition) = member(Condition, Facts);

The Test function consists of three definition rules. The first two rules are using pattern matching for determining the & and the | operations. In these rules the Test function is called recursively until the last rule is activated, which asks if a Condition is in the Facts list.

However, this Test definition is inefficient in some cases. It is doing too much when Condition1 of an & expression appears to be false; there is no need to test Condition2 in that case. The same applies if the Condition1 of an | expression appears to be true. So, we will rewrite the Test definition:

Test(term) -> boolean;
Test(Condition1 & Condition2) = 
                 if Test(Condition1) then Test(Condition2) else false;
Test(Condition1 | Condition2) = 
                 if Test(Condition1) then true else Test(Condition2);
Test(Condition) = member(Condition, Facts);

The member function determines if a Condition is in the Facts list:

member(term, list (term)) -> boolean;
member(T, L) = [ return(true) when items(L) == T; false];

Now we can use this set of definitions and the rule set to draw some conclusions based on our initial list of facts:

TryRule (items (RuleSet) );
Facts?

The Facts list now contains the following facts:

{ eats(Animal, meat),
  has (Animal, hair),
  has (Animal, tawny_color),
  has (Animal, black_stripes),
  isa (Animal, mammal),
  isa (Animal, carnivore),
  isa (Animal, tiger) }

And this is what we may have expected.

One of the important properties of a rule-based system is that the final result is not dependent on the order of the if-then rules. An easy way to test that is to loop through the rules of the rule set in inverse order with the initial facts:

TryRule (prioritems (RuleSet));
Facts?

The Facts list now contains the following facts:

{ eats(Animal, meat),
  has (Animal, hair),
  has (Animal, tawny_color),
  has (Animal, black_stripes),
  isa (Animal, carnivore),
  isa (Animal, mammal) }

However, the final result that the animal is a tiger has not been concluded by the system. A little investigation of the rule set reveals that this happens because the conditions of Rule6 are tested before the conclusions of Rule3 and Rule1 are known. To remedy these kinds of problems we must change our algorithm in such a way that it continues with trying all rules until no new conclusions are added to the list of facts. Therefore we need a more sophisticated rule interpreter.

There is also another problem we have to tackle. Various rules in a rule set may produce identical results which in our current version are all included in the facts list. To avoid that, we will first test if a conclusion is already in the facts list before entering it. So, we will revise the TryRule definition in the following way:

TryRule (Rule = term, Facts = list (term) ) -> boolean;
TryRule ( phrase(Rule = if Conditions then Conclusion), Facts) = 
        [ Result := false;
          if Test(Conditions) then 
             [ Result:= ~ member (Conclusion, Facts);
               if Result then add (Facts, Conclusion) ];
          Result ];

This can now be used in a forward chaining rule interpreter:

Deduce (RuleSet = list (term), Facts = list (term) ) -> list (term);
Deduce (RuleSet, Facts) = 
        repeat [ NewFacts:= false;
                 NewFacts:= TryRule (items (RuleSet), Facts) | NewFacts;
                 ready when ~ NewFacts ];

Now we are able to define a component for forward chaining which is independent from a knowledge base. This component (see Figure 7-1) can be used for any knowledge base which is built according to the principles outlined above.


component ForwardChaining;
  Deduce (RuleSet = list (term), Facts = list (term) ) -> nothing;
begin
  Facts:= alist (term); << empty Facts list >>
  Deduce (RuleSet = list (term), Facts = list (term) ) -> nothing;
  Deduce (RuleSet, facts) = 
         [ Facts:= facts;
           repeat [ NewFactS:= false;
                    NewFactS:= TryRule (items (RuleSet)) | NewFacts;
                    ready when ~ NewFacts ] ];
  TryRule (Rule = term) -> boolean;
  TryRule (phrase(Rule = if Conditions then Conclusion)) = 
        [ Result := false;
          if Test (Conditions) then 
              [ Result:= ~ member (Conclusion, Facts);
                if Result then add (Facts, Conclusion)];
          Result];
  Test (term) -> boolean;
  Test (Condition1 & Condition2) = 
           if Test (Condition1) then Test (Condition2) else false;
  Test (Condition1 | Condition2) = 
           if Test (Condition1) then true else Test (Condition2);
  Test (Condition) = member (Condition, Facts);
  member (term, list(term)) -> boolean;
  member (T, L) = [ return (true) when items (L) == T; false];
end component ForwardChaining;

Figure 7-1: Example of a forward chaining interpreter

We may now use the component in the following way:

Input = OpenInputTermsFile ("Animals.txt");
Facts = readlist (Input);
RuleSet = readlist (Input);
close (Input);
Deduce (RuleSet, Facts);
Facts?

The textfile "Animals.txt" contains a list of initial facts and the rule set for animal identification as given above. The facts after the interpretation are:

{ eats(Animal, meat),
  has (Animal, hair),
  has (Animal, tawny_color),
  has (Animal, black_stripes),
  isa (Animal, mammal),
  isa (Animal, carnivore),
  isa (Animal, tiger) }

And this concludes our discussion of forward chaining. Let us now see what backward chaining means.

 

7.1.2 Backward Chaining

An interpreter is doing backward chaining if it starts with a hypothesis and tries to prove it. For example, if the hypothesis is that an animal may be a giraffe, the interpreter will search for a rule with a giraffe as its conclusion. In our example this is:

Rule7 = if isa(Animal, ungulate) & has(Animal, long_neck) &
           has(Animal, long_legs) & has(Animal, dark_spots) 
        then isa(Animal, giraffe);

Using this rule, the interpreter observes that there are four conditions to be fulfilled before we may call an animal a giraffe. It starts with the condition that the animal must be an ungulate. Being an ungulate becomes a new hypothesis which must be proved before we can continue with the rest of the conditions. Because we can use the same procedure as used for proving that an animal is a giraffe, the system has to work recursively. If it has been proved that an animal is an ungulate then the next condition, that the animal must have a long neck, will become a new hypothesis, and so on. After all conditions have been satisfied then the hypothesis that the animal is a giraffe has been proved.

In our backward chaining interpreter the TryRule function is even simpler than with forward chaining:

TryRule(Rule = term, Hypothesis = term) -> optional (boolean);
TryRule(phrase(Rule = if Conditions then Conclusion), Conclusion) = Test(Conditions);

This definition compares if the conclusion of a rule is equal to a given hypothesis. If that is the case then the conditions of the rule are tested.

The Test function is comparable to the forward chaining version, except for the last definition rule:

Test (term) -> boolean;
Test (Condition1 & Condition2) = 
      if Test (Condition1) then Test (Condition2) else false;
Test (Condition1 | Condition2) = 
      if Test (Condition1) then true else Test (Condition2);
Test (Condition) = Verify (Condition);

The last definition rule indicates that the condition must be verified. There are several ways to verify if a condition is true. In our example interpreter we will use the following steps:

  • Test if the condition is already known as a fact
  • If that is not the case, use the condition as a new hypothesis which must be proved

Both methods are used in the following definition:

Verify (Condition = term) -> boolean;
Verify (Condition) = [ Found:= member (Condition, Facts);
                       if ~ Found then 
                          [ Found:= ScanRules (Condition);
                            if Found then add (Facts, Condition) ];
                       Found ];

The Verify definition examines first if the condition is already known in the Facts list. If that is not the case then the rules of the rule set are scanned with the condition as a new hypothesis. If the hypothesis is proved from the rule set, the new proved condition is added to the Facts list.

The rules in the rule set are scanned by the definition:

ScanRules (Hypothesis = term) -> optional (boolean);
ScanRules (Hypothesis) = TryRule (items (RuleSet), Hypothesis);

With these definitions we are now able to verify in a dialog session, based on the characteristics in the initial facts list, if the animal we want to identify is a tiger:

Animal, tiger => term;
isa (term, term) => term;
Hypothesis = isa (Animal, tiger);
ScanRules (Hypothesis)?

The answer is true as we may have expected.

Finally, we may incorporate the definitions of a backward chaining interpreter into a component (see Figure 7-2).


component BackwardChaining;
  Deduce(RuleSet = list(term), Facts = list(term), Hypothesis = term) 
                                                          -> optional(boolean);
begin
  Facts:= alist(term);
  RuleSet:= alist(term);
  Deduce (rules, facts, Hypothesis) = 
         [ RuleSet:= rules; Facts:= facts; ScanRules (Hypothesis) ];
  ScanRules (Hypothesis = term) -> optional (boolean);
  ScanRules (Hypothesis) = TryRule (items (RuleSet), Hypothesis);
  TryRule (Rule = term, Hypothesis = term) -> optional(boolean);
  TryRule (phrase(Rule = if Conditions then Conclusion), Conclusion) = Test (Conditions);
  Test (term) -> boolean;
  Test (Condition1 & Condition2) = 
        if Test (Condition1) then Test (Condition2) else false;
  Test (Condition1 | Condition2) = 
        if Test (Condition1) then true else Test (Condition2);
  Test (Condition) = Verify (Condition);
  Verify (Condition = term) -> boolean;
  Verify (Condition) = [ Found:= member (Condition, Facts);
                         if ~ Found then 
                            [ Found:= ScanRules (Condition);
                              if Found then add (Facts, Condition) ];
                         Found ];
  member (term, list (term)) -> boolean;
  member (T, L) = [ return (true) when items (L) == T; false ];
end component BackwardChaining;

Figure 7-2: Example of a backward chaining interpreter

We may now use this component by calling it with the rule set, the facts, and the hypothesis as defined before:

Deduce (RuleSet, Facts, Hypothesis)?

The answer is true, indicating that the hypothesis can be proved based on the facts and the rule set.

One of the drawbacks of our forward and backward chaining components is that a complete set of initial facts has to be entered into the system before it can start to work. In practical situations many of the initial facts may not be needed for the inference process. Thus, the user may do unnecessary work inputting irrelevant information. The user may even forget to provide all the applicable facts, in which case the system may produce wrong answers.

Another problem is that the system produces only a simple answer being true or false without providing an explanation how it arrived at its conclusions.

How to rectify these drawbacks will be the subject of the next section.

Exercises:

  • 7.1 In practice, it is not always easy to determine which external hypotheses should be investigated. Assume that in our animal identification example all animals are included in our hypotheses list, how will the system react?
  • 7.2 The deduction systems described, both forward and backward, say nothing about how certain their conclusions are. Read about certainty factors (see References) and extend the system given here to calculate and report how certain conclusions are.

 

7.2 Semantic Networks

Another class of knowledge representation formalism are semantic networks. They differ from rule-based representations in that they can represent in a structured way, large sets of facts.

A semantic network represents entities and relations between entities. It is customary to represent a semantic network as a graph. There are a wide variety of forms of semantic networks using various conventions, but usually the nodes of the graph correspond to entities, while the arcs represent the relations between them. Nodes may represent objects, events, concepts, or situations in a given domain while arcs are shown as links labeled by the names of the relations.

As an example we will represent the relations between different kinds of birds as shown in Figure 7-5.

                                       animal
                                          |
                                          | isa
                                          |
                           active_at      |      moving_method
           daylight <------------------- bird ---------------------> fly
                                          / \
                                         /   \   
                                    isa /     \ isa
                                       /       \ 
                                      /         \
                       color         /           \       color
   black_and_white <--------- albatross          kiwi -------------> brown
                                / |              / | \
                               /  |   active_at /  |  \
                          isa /   |isa         /   |   \ moving_method
                             /    |           / isa|    \
                            /     |          /     |     \
                        Albert   Ross      night  Kim    walk

Figure 7-5: A semantic network

The relation name isa stands for 'is a' or 'is a kind of '. It sometimes relates an individual or instance of a class with the class itself (Albert is an albatross), and sometimes relates a class with a superclass (animal is a superclass of the class bird).

This network represents relations such as:

  • A bird is an animal, which is active at daylight, and its moving method is flying.
  • An albatross is a bird, which color is black and white.
  • A kiwi is a bird, which color is brown, is active at night, and its moving method is walking.
  • Albert is an albatross, as well as Ross.
  • Kim is a kiwi.

These relations can be easily translated into the following definitions:

bird      = { isa(animal), active_at(daylight), moving_method(fly) };
albatross = { isa(bird), color(black_and_white) };
kiwi      = { isa(bird), color(brown), active_at(night), moving_method(walk) };
Albert    = { isa(albatross)};
Ross      = { isa(albatross)};
Kim       = { isa(kiwi)};

In this form of knowledge representation, each node is represented by a list of relations.

Relations are terms which should be declared for a given problem domain. For our example, the following declarations are required:

animal, daylight, fly, walk, night, black_and_white, brown => term;
isa, active_at, moving_method, color => term;
isa (term)           => term;
isa (list (term))    => term;
active_at (term)     => term;
moving_method (term) => term;
color (term)         => term;

We can now ask for how Albert is represented:

Albert?

The system returns with:

{ isa ({ isa ({ isa (animal), 
                active_at (daylight), 
                moving_method (fly) }), 
         color (black_and_white) } ) }

The same question about Kim:

Kim? 
{ isa ({ isa ({ isa (animal),
                active_at (daylight), 
                moving_method (fly)}), 
         color (brown), 
         active_at (night), 
         moving_method (walk)})}

Both representations show the corresponding tree structures of these individuals.

Based on a semantic network as a knowledge base an inference engine can be defined for drawing conclusions. In semantic network representations, there is no formal semantics, no agreed-upon notion of what a given representational structure means, as there is in rule-based systems, for instance. Meaning is assigned to a network structure only by nature of the procedures that manipulate the network. A wide variety of network-based systems have been designed that use totally different procedures for making inferences.

One of the interesting properties of semantic networks is that inferences can be made based on the concept of inheritance. For example, the fact that an albatross flies is inherited from the fact that birds fly. Similarly, Albert inherits all the properties of an albatross, while Kim inherits all the properties of a kiwi. In general, facts or properties are inherited by means of the isa relation. In Elisa, we can define a general fact finding definition based upon inheritance in the following way:

fact (list (term), property = term ) -> term;
fact (List, Property ) = 
  [ [ Relation = items (List);
      return (Relation) when term: functor (Relation) == Property ];
    fact (list (term): argument (fact (List, isa), 1), Property) ];

This definition tries to find a property in a semantic network. It starts with searching the current list for a relation which has, as a functor, the desired property. If that has been found, the relation is returned. If the list does not contain the desired property, the same list is searched for an isa relation. After this has been found the list referred by the isa relation will be scanned for the desired property, and so on. Note that the order of relations in a list is not relevant.

Our semantic network can now used to ask some questions:

fact (Kim, color)?
color (brown)
fact (Kim, moving_method)?
moving_method (walk)
fact (Kim, active_at)?
active_at (night)
fact (Albert, moving_method)?
moving_method (fly)
fact (Albert, active_at)?
active_at (daylight)

In this examples, the properties of Kim are inherited from the properties of a kiwi, while the properties of Albert are inherited from one level higher in the inheritance hierarchy, the bird level.

Exercise:

  • 7.5 Our fact finding definition does not take care of the situation when a given fact cannot be found. Adapt the fact finding definition to correct that.

 

7.3 Frames

Another form of knowledge representation is provided by frames. In frame representations, knowledge is clustered around so-called frames. A frame may represent objects, events, concepts, or situations.

Frames are compound data structures whose components are called slots. Slots have names and may contain information of various kinds. Slots may contain values, references to other frames or even procedures that can compute a slot value from other information. A slot may also be unfilled. Slots are filled in by the system as information is gathered. Some slots can be filled in with information from the user or from a database. Other slots can be inferred from information that has already been entered into other slots. As with semantic networks, one of the most common principles of inferences is based on inheritance. When a frame represents a class of objects (such as albatross) and another frame represents a superclass of this class (such as bird), then the class frame may inherit slot values from the superclass frame.

For example, knowledge about birds can be put into a frame structure as follows:

bird frame:

isa = animal

active_at = daylight

moving_method = fly

This frame stands for the class of all birds. It has three slots. The first slot says that a bird is an animal; the second slot says that, in general, a bird is active during daylight, and the last slot tells us that a typical bird flies.

Two other frames for albatross and kiwi, both being subclasses of bird, are:

albatross frame:

isa = bird

color = black_and_white

This frame stands for the class of all albatrosses. An albatross is a typical bird which inherits the daylight activity and the flying ability from the frame bird.

kiwi frame:

isa = bird

color = brown

active_at = night

moving_method = walk

The kiwi frame stands for the class of all kiwi's. A kiwi is a rather atypical bird and the active_at and the moving_method values for birds have to be overruled for the kiwi.

Frames can be represented in different ways in Elisa. We will discuss three methods: one based on lists, the other two based on descriptors.

 

Method 1: frames based on lists

One way is to represent frames in the same way as semantic networks: a frame is in that case a list of slots and a slot is represented by a relational term. A general slot finding method can be defined which uses isa slots to search for inherited slots. It means, with this method, that the terminology of semantic networks and frames are different but that the functions are the same.

 

Method 2: frames based on various types of descriptors

Another method is to represent frames by means of descriptors. One way of doing that is by defining for each frame a separate descriptor, as in the following examples:

Bird = bird:[ isa = animal; active_at = daylight; moving_method = fly];
Albatross = albatross:[ isa = Bird; color = black_and_white];
Kiwi = kiwi:[ isa = Bird; color = brown; active_at = night; moving_method = walk];

With this method, each descriptor has a unique type, which should be specified beforehand. Furthermore, also the terms representing symbolic values should be specified:

type bird;
type albatross;
type kiwi;
animal, daylight, fly, walk, night, black_and_white, brown => term;

We may now define specific instances of an albatross or a kiwi and ask for their representation:

Albert = Albatross;
Albert?

The system returns with the answer:

albatross:[ isa = bird:[ isa = animal;
                         active_at = daylight;
                         moving_method = fly];
            color = black_and_white]

The same question for Kim as a kiwi:

Kim = Kiwi;
Kim?

The system returns with:

kiwi:[ isa = bird:[ isa = animal;
                    active_at = daylight;
                    moving_method = fly];
       color = brown;
       active_at = night;
       moving_method = walk]

If we now want to know what the moving method is from a kiwi, we first have to introduce a corresponding definition:

moving_method (kiwi) -> term;
moving_method (kiwi) = kiwi.moving_method;

We may use this definition for asking what the moving method of Kim is:

moving_method (Kim)?

The system returns with:

walk

However, this definition cannot be used to ask for the moving method of an albatross. Because an albatross is inheriting its moving method from the bird frame, we need two definitions:

moving_method (bird) -> term;
moving_method (bird) = bird.moving_method;
moving_method (albatross) -> term;
moving_method (albatross) = moving_method (albatross.isa);

These definitions can now be used for asking what the moving method of Albert is:

moving_method (Albert)?

The system returns with:

fly

These examples learn us that with this approach, for each frame type corresponding inquiry operations should be defined which will directly return the requested slot value, if defined, or will use inheritance if the corresponding slot has not been defined at this level.

 

Method 3: frames based on a single type descriptor

A third approach is to use one frame structure for a number of related frames. For example, to describe birds, albatrosses, and kiwi's we may all use the same frame structure, called animal. To fill such a frame structure we will also introduce a corresponding constructor function:

type animal;
     animal (name = text, class = animal, active_at = term,
                          moving_method = term, color = term ) -> animal;
     animal (name, class, active_at, moving_method, color) =
                          animal:[ name; class; active_at; moving_method; color];

Note that we are now using the word class instead of the word isa to emphasize the class relationship. In addition, a new slot representing the name of the animal has been introduced.

Furthermore we need to specify the symbolic names which may be used as possible values of the different slots:

daylight, fly, walk, night, black_and_white, brown => term;

We can now use the constructor function in the following way:

bird      = animal("bird", null(animal), daylight, fly, null(term));
albatross = animal("albatross", bird, null(term), null(term),black_and_white);
kiwi      = animal("kiwi", bird, night, walk, brown);
Albert    = animal("Albert", albatross, null(term), null(term), null(term));
Kim       = animal("Kim", kiwi, null (term), null(term), null(term));

With this approach, individuals such as Albert and Kim, are also represented by frames.

We can now ask for Albert:

Albert?
animal:[ name = "Albert";
         class = animal:[ name = "albatross";
                          class = animal:[ name = "bird";
                                           class = [ ];
                                           active_at = daylight;
                                           moving_method = fly;
                                           color = [ ] ];
                          active_at = [ ];
                          moving_method = [ ];
                          color = black_and_white];
         active_at = [ ];
         moving_method = [ ];
         color = [ ] ]

and for Kim:

Kim?
animal:[ name = "Kim";
         class = animal:[ name = "kiwi";
                          class = animal:[ name = "bird";
                                           class = [ ];
                                           active_at = daylight;
                                           moving_method = fly;
                                           color = [ ] ];
                          active_at = night;
                          moving_method = walk;
                          color = brown ];
         active_at = [ ];
         moving_method = [ ];
         color = [ ] ]

With this method we only need one definition to determine the moving method of an animal:

moving_method (animal) -> term;
moving_method (animal) = 
   if animal.moving_method <> null (term) then animal.moving_method
                                          else moving_method (animal.class);

We can now ask what the moving methods of Kim and Albert are:

moving_method (Kim)?
walk
moving_method (Albert)?
fly

Comparing the three methods for frame representation, the obvious question is: which method is better. As always with these kinds of questions, the answer is: it depends on the application.

Method 1, based on lists, is very versatile and flexible but requires always searching for slot values.

Method 2, based on various types of descriptors, provides a compact representation for each frame type, but may require many different frame types and many different inquiry operations.

Method 3, based on one type of descriptor, provides a uniform frame representation and a limited number of inquiry operations, but may result in many empty slots.

In practice, the choice will depend on the kinds of problems to be solved. Sometimes it may also be feasible to use a combination of the different methods (see Exercise 7.7 ).

Exercises:

  • 7.6 Our last moving_method definition does not take care of the situation when a slot cannot be found. Correct that.
  • 7.7 Design a frame representation for animals based on a combination of Method 3 and Method 1. Hint: use the name and class slots as fixed descriptor elements and represent the other slots as variable elements of a list.

 

7.4 Summary

  • In many problem-solving programs there is a need for decision making which is not only based on data but also based on reasoning. Reasoning is often based on drawing conclusions from facts.
  • There are several ways for knowledge representation. Knowledge can be represented by: if-then rules, semantic networks, and frames.
  • If-then rules are used to define logical relations between concepts of a given problem domain. In a rule-based system the knowledge base consists of two components: a rule set, and a list of facts. In addition to the knowledge base there is also an inference engine, which is interpreting the rules in the rule set and which adds new facts to the facts list.
  • Two basic ways of reasoning in rule-based systems are: forward and backward chaining. Forward chaining means: the conditions of a rule are first evaluated before the conclusion is drawn. Backward chaining uses the conclusion of a rule as a hypothesis which should be proved by validating the conditions of the rule.
  • Expert systems try to emulate human expertise. An expert system is a program that intends to behave like a human expert for some problem domain. It may ask the user for specific information and may draw conclusions based on reasoning.
  • An expert system consists of three main parts: a knowledge base, an inference engine, a user interface. A user interface component takes care of the communication with the user. It may give explanations of the reasoning process in response to user's questions 'How?' and 'Why?'. The inference engine together with the user interface is called an expert system shell.
  • Semantic networks are graphs which represent entities and relations between entities. Usually the nodes of the graph correspond to entities, while the arcs represent the relations between them. Nodes may represent objects, events, concepts, or situations in a given domain. Semantic networks can be used for making inferences based on the concept of inheritance.
  • In frame representations, knowledge is clustered around frames. Frames are compound data structures whose components are called slots. Slots have names and may contain information of various kinds. Frames can be represented in several ways. Three methods have been discussed: one based on lists, the other two based on descriptors.

 

7.5 References

Principles for knowledge representations and expert systems are described in any general text on artificial intelligence. Examples are Winston(1984), Charniak and McDermott(1985), Marcus(1986), Walker(1987), Bratko (1990). Some of the examples in this chapter are taken from Winston and Horn(1984), and Bratko(1990).

 

Top of Page   Part 2: Data Structures   Chapter 7: Knowledge Representations

 
            

 

 

  <!-- Start of StatCounter Code for Default Guide -->
<script type="text/javascript">
var sc_project=11338540;
var sc_invisible=0;
var sc_security="f2d7a14f";
var sc_https=1;
var scJsHost = (("https:" == document.location.protocol) ?
"https://secure." : "http://www.");
document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+
"statcounter.com/counter/counter.js'></"+"script>");
</script>
<noscript><div class="statcounter"><a title="Web Analytics Made Easy -
StatCounter" href="http://statcounter.com/" target="_blank"><img
class="statcounter" src="//c.statcounter.com/11338540/0/f2d7a14f/0/"
alt="Web Analytics Made Easy - StatCounter"></a></div></noscript>
<!-- End of StatCounter Code for Default Guide -->