In solving problems in AI we must represent knowledge and there are two entities
Facts which are truths about the real world and what we represent and
Representation of the facts which we manipulate.
We can structure these entities at two levels
the knowledge level at which facts are described and
the symbol level at which representations of objects are defined in terms of symbols that can be manipulated in programs see figure below
English or natural language is an obvious way of representing and handling facts.
Logic enables us to consider the following fact
Spot is a dog
dog(spot)
[[universal]]x : dog(x) -> hasatail(x)
we can then deduce hasatail(Spot)
Using an appropriate backward mapping function the English sentence
Spot has a tail
can be generated.
The available functions are not always one to one but rather are many to many which is a characteristic of English representations. The sentences
`All dogs have tails' and ` every dog has a tail'
both say that each dog has a tail but the first could say that each dog has more than one tail
try substituting teeth for tails. When an AI program manipulates the internal representation of facts these new representations should also be interpretable as new representations of facts.
Consider the classic problem of the mutilated chess board.
Problem
In a normal chess board the opposite corner squares have been eliminated. The given task is to cover all the squares on the remaining board by dominoes so that each domino covers two squares. No overlapping of dominoes is allowed, can it be done. Consider three data structures
(a) (b)
the first two are illustrated in the diagrams above as (a) and (b) and the third data structure is the number of black squares and the number of white squares. The first diagram loses the colour of the squares and a solution is not east to see; the second preserves the colours but produces no easier path whereas counting the number of squares of each colour giving black as 32 and the number of white as 30 yields an immediate solution of NO as a domino must be on one white square and one black square, thus the number of squares must be equal for a positive solution.
Approaches to Knowledge Reresentation
The following properties should be possessed by a good system.
Representational Adequacy -- the ability to represent the required knowledge;
Inferential Adequacy -- the ability to manipulate the knowledge represented to produce new knowledge corresponding to that inferred from the original;
Inferential Efficiency -- the ability to direct the inferential mechanisms into the most productive directions by storing appropriate guides;
Acquisitional Efficiency -- the ability to acquire new knowledge using automatic methods wherever possible rather than reliance on human intervention.
Simple relational knowledge See fig 4.4
The simplest way of storing facts is to use a relational method where each fact about a person is set out systematically in columns. The representation shown gives little opportunity for inference, but it can be used as the knowledge basis for inference engines. Given a set of rules we can easily select the tallest, those that bat and throw with different arms and those that are over 200 pounds
Inheritable knowledge See fig 4.5
The knowledge base we have just discussed consists of relational knowledge which is made up of objects consisting of attributes with associated values. We can make the base more powerful by allowing inference mechanisms such as property inheritance where elements inherit values from being members of a class. To enable property inheritance to occur the data must be organised into a hierarchy of classes as shown in figure 4.5. This structure is known as a slot and filler structure.
The example chosen is a simple one chosen from baseball and is specific to that game apart from the attributes instance and isa. Three finger Brown is an instance of a pitcher and all pitchers are baseball players who are adult males and are people. Generally adult american males are 70 inches high are right handed whereas baseball players are on average three inches taller. The batting average for fielders is higher at 0.262 than average 0.252 as pitchers have poor averages 0.106.
We can deduce that Pee Wee Reese `s team is Brooklyn Dodgers, it actually is an attribute;
Three finger Brown's batting average is 0.106 because there being no value we follow the instance attribute to pitcher. Here there is an attribute with a value hence the average-- actually the average for Three finger Brown was 0.204 much higher than the default average for all pitchers;
Pee Wee Reese`s height is 6-1 by pursuing the path to that of a baseball player, note it is the first successful result that is given;
Three finger Brown bats right handed because he is a baseball player who bats handed unknown at this stage, batting is equal to handed ; but a player is a male person and hence is likely to be right handed and so Three finger Brown is a right hand batter;
actually Three finger Brown was a switch hitter.
The algorithm to retrieve a value for an attribute of an instance object:
1 find the object in the knowledge base
2 if there is a value for the attribute report it
3 otherwise look for a value of instance if none fail
4 got to that node and find a value for the attribute and then report it
5 otherwise search through using isa unti a value is found for the attribute.
Procedural Knowledge
We can handle questions such as theses by using Lisp programs but the reasoning is not as straightforward as if we were using a frame. For that reason there is a trend to use production rules such as
If it is the ninth and last normal innings and
the score is close and
there are less than 2 out and three out to end the innings
first base is vacant and
this batter is better than the next
Then walk the batter let him go to the first base ie skip him
Issues in Knowledge Representation
1 Are there any attributes that occur in many different types of problem? There are two instance and isa and each is important because each supports property inheritance.
2 What about the relationship between the attributes of an object, such as, inverses, existence, techniques for reasoning about values and single valued attributes.
We can consider an example of an inverse in
team ( Pee Wee Reese, Brooklyn Dodgers)
this can be treated as Pee Wee Reese plays for the team Brooklyn Dodgers or Pee Wee Reese's team is Brooklyn Dodgers.
Another representation is
team = Brooklyn Dodgers
team-members=Pee Wee Reese
3 At what level should the knowledge be represented and what are the primitives.
Choosing the Granularity of Representation
Primitives are fundamental concepts such as holding, seeing, playing and as English is a very rich language with over half a million words it is clear we will find difficulty in deciding upon which words to choose as our primitives in a series of situations.
If Tom feeds a dog then it could become feeds(tom, dog)
If Tom gives the dog a bone gives(tom, dog,bone)
are these the same in any sense does giving an object food constitute feeding.
If give(x, food) -> feed(x) then we are making progress but we need to add certain inferential rules.
In the famous program on relationships
Louise is Bill's cousin how do we represent this
louise = daughter (brother or sister (father or mother( bill)))
suppose it is chris then we do not know if it is chris as a male or female and then son applies as well.
Clearly the separate levels of understanding require different levels of primitives and these need many rules to link together apparently similar primitives. Obviously there is a potential storage problem and the underlying question must be what level of comprehension is needed.
see Rich pp118