Knowledge Representation
Issues
Introduction
• Discussed: Search-based problem solving
programs
• Power is limited because of their generality
• Knowledge representation models allow for
more specific, more powerful problem-solving
mechanisms
Representations and Mappings
• In order to solve the complex problems
encountered in AI
-needs a large amount of knowledge
-some mechanisms for manipulating that
knowledge to create solutions to new problems
Two entities:
Facts: truths in some relevant world. These are
the things we want to represent
Representations of facts in some chosen
formalism. These are the things we will actually
be able to manipulate.
Representations and Mappings
• Structuring entities:
The knowledge level, at which facts (including
each agent’s behaviors & current goals) are
described
The symbol level, at which representations of
objects at the knowledge level are defined in
terms of symbols that can be manipulated by
programs
Mappings between Facts & Representations
* Internal
Reasoning
Facts Programs
Representations
*
English Understanding English Generation
English
Representations
• Representation mappings:
Forward representation mappings (facts-representation)
Backward representation mappings (representation-facts)
Mappings between Facts & Representations
• Spot is a dog.
• Fact (logic): dog (Spot)
• Logical representation (all dogs have tails):
x: dog (x) hastail (x)
-Using deductive mechanisms of logic, new representation of
object:
hastail (Spot)
-Using an appropriate backward mappings function, generate
English sentence:
Spot has a tail.
Or we could make use of this representation of a new fact
to cause us to take some appropriate action or to derive
representations of additional facts.
Mappings between Facts & Representations
• The available mapping functions are not one-to-one
• They are not even functions but rather many-to-many
relations
-Each object in the domain may map to several elements in
the range
-several elements in the domain may map to the same
element in the range
All dogs have tails Every dog has a tail
Bothe represent the same fact (every dog has at least one
tail)
Mappings between Facts & Representations
• Former: every dog has at least one tail/each dog
has several tails
• Latter: every dog has at least one tail/there is a
tail that every dog has
• When we try to convert English sentences into
some other representation (such as logical
propositions) ,
-we must first decide what facts the sentence
represent & then convert those facts into the
new representation
Mappings between Facts & Representations
• What an AI program does is to manipulate the
internal representation of the facts it is given
• This manipulation should result in new
structures than can also be interpreted as the
internal representations of facts
• More precisely, these structures should be the
internal representations of facts that
correspond to the answer to the problem
described by the starting set of facts
Representation of Facts: Expanded view
Initial Desired real reasoning Final
facts facts
Forward Backward
* representation representation *
mapping mapping
Internal Internal
representation Operation of representation
of initial facts program of final facts
• Dotted line: abstract reasoning process that a program is
intended to model
• Solid line: concrete reasoning process that a particular
program performs
Representation of Facts: Expanded view
• This program successfully models the abstract process
to the extent that, when the backward representation
mapping is applied to the program’s output, the
appropriate final facts are actually generated
• If either the program operation/one of the
representation mappings is not faithful to the problem
that is being modeled, then the final facts will probably
not be the desired ones
• If no good mapping can be defined for a problem, then
no matter how good the program to solve the problem
is, it will not be able to produce answers that
correspond to real answers to the problem
Approaches to Knowledge Representation
• A good system for representation of knowledge should possess 04
properties:
1. Representational Adequacy: ability to represent all of the kinds of
knowledge that are needed in that domain
2. Inferential Adequacy: ability to manipulate the representational
structures in such a way as to derive new structures corresponding to
new knowledge inferred from old
3. Inferential Efficiency: ability to incorporate into the knowledge
structure additional information that can be used to focus the
attention of the inference mechanisms in the most promising
directions
4. Acquisitional Efficiency: ability to acquire new info easily. The
simplest case involves direct insertion, by a person, of new
knowledge into the database. Ideally, the program itself would be
able to control knowledge acquisition
-no single system that optimizes all of the capabilities for all kinds of
knowledge has yet been found.
Simple Relational Knowledge
• Simplest way to represent declarative facts is as a
set of relations of the same sort used in database
systems.
Player Height Weight Bats-Throws
Babul 6-0 180 Right-Right
Alim 5-10 170 Right-Right
Didar 6-2 215 Left-Left
Rubel 6-3 205 Left-Right
player_info(‘babul’, 6-0, 180, right-right)
• Representation is simple, provides very weak
inferential capabilities
Simple Relational Knowledge
• Knowledge represented in this form may serve as the
input to more powerful inference engines
• It is not possible even to answer the simple question,
“Who is the heaviest player?”
• But if a procedure for finding the heaviest player is
provided, then these facts will enable the procedure
to compute an answer.
• We are provided with a set of rules for deciding
which hitter to put up against pitcher (based on
right-& left-handedness), then this same relation can
provide at least some of the info required by those
rules
Inheritable knowledge
• Relational knowledge corresponds to a set of
attributes & associated values that together
describe the objectives of the knowledge base
Player Height Weight Bats-Throws
Babul 6-0 180 Right-Right
Alim 5-10 170 Right-Right
Didar 6-2 215 Left-Left
Rubel 6-3 205 Left-Right
player_info(‘babul’, 6-0, 180, right-right)
• It is possible to augment the basic representation
with inference mechanisms that operate on the
structure of the representation
Inheritable knowledge
• For this to be effective, the structure must be
designed to correspond to the inference
mechanisms that are desired
Inheritable knowledge
• One of the most useful forms of inference is
property inheritance, in which elements of
specific classes inherit attributes & values
from more general classes in which they are
included
• In order to support property inheritance,
objects must be organized into classes &
classes must be arranged in a generalization
hierarchy.
Inheritable knowledge
• Some additional baseball knowledge inserted
into a structure that is so arranged.
• Lines: attributes
• Boxed nodes: objects& values
• Values can also be viewed as objects to its
value along the corresponding attribute line
• Slot-and-filler structure
• Semantic network/a collection of frames
Baseball Player: Semantic Net
handed
Person Right
Lines: attributes
isa Boxed nodes:
Adult- objects& values
5-10
Male height
isa
6-1
bats Baseball
Equal to
-Player Batting -average
handed
isa isa .252
Batting -average
Fielder Batting -average .262
.106 Pitcher
instance instance
team
Chicago- Three-Finger- Pee-Wee- team Brooklyn-
Cubs Brown Reese Dodgers
Baseball Player: Frame
Baseball-player
isa: Adult-Male
Viewing a Node as a Frame
bats: (EQUAL handed)
height: 6-1
batting-average: .252
-All of the objects & most of the attributes to correspond to the
baseball domain.
Two Exceptions:
-attribute isa show class inclusion
-attribute instance show class membership
-these attributes provide the basis for property inheritance as an
inference technique
Algorithm: Property Inheritance
To retrieve a value V for attribute A of an instance object O:
1. Find O in the knowledge base
2. If there is a value there for the attribute A, report that
value
3. Otherwise, see if there is a value for the attribute
instance. If not, then fail
4. Otherwise move to the node corresponding to that
value & look for a value for the attribute A. if one
found, report it
5. Otherwise, do until there is no value for the isa
attribute or until an answer found:
a) Get the value of the isa attribute & move to that node
b) See if there is a value for the attribute A. if there is,
report it
Example
• Team (Pee-Wee-Reese)=Brooklyn-Dodgers. The
attribute had a value stored explicitly in the knowledge
base
• batting-average (Three-Finger-Brown)=.106. Since
there is no value for batting average stored explicitly
for Three-Finger-Brown, we follow the instance
attribute to Pitcher & extract the value stored there.
• height (Pee-Wee-Reese) = 6-1.
This represent another default inference.
Note: we get to it first, the more specific fact about the
height of baseball players overrides a more general fact
about the height of adult males
Example
• bats (Three-Finger-Brown)=Right.
To get a value for the attribute bats required going up the isa
hierarchy to the class Baseball-Player.
But what we found there was not a value but a rule for
computing a value
This rule required another value (that for handed) as input
So the entire process must be begun again recursively to find
a value handed
This time, it is necessary to go all the way up to Person to
discover that the default value for handedness for people is
Right.
Now the rule for bats can be applied, producing the result
Right, that turns out to be wrong, since Brown is a switch
hitter (he can hit both left-and-right-handed )
Inferential Knowledge
• Sometimes all the power of traditional logic
(sometimes even more than that) is necessary
to describe the inferences that are needed
First Order Predicate Logic
x : Ball( x) Fly( x) Fair( x) Infield Catachable( x)
Occupied Base( First) Occupied Base( Second) (Outs 2)
[ Line Drive( x) Attempted B1( x) Infield Fly( x)
x, y : Batter( x) batted( x, y ) Infield Fly( y ) Out ( x)
Inferential Knowledge
• This knowledge is useless unless there is also an
inference procedure that can exploit it
• The required inference procedure now is one that
implements the standard logical rules of inference
• There are many such procedures, some of which
reason forward from given facts to conclusions,
others of which reason backward from desired
conclusions to given facts.
• Resolution most commonly used
The Frame Problem
• How to represent efficiently sequences of problem
states that arise from a search process
• For complex ill-structured problems, this can be a
serious matter
• Consider the world of a household robot.
• There are many objects & relationships in the world, & a
state description must somehow included facts
On(Plant12,Table34), under(Table34,Window13), and
in(Table34,Room15)
-one strategy is to store each state description as a list of
such facts
The Frame Problem
• But what happens during the problem solving process if
each of those descriptions is very long?
• Most of the facts will not change from one state to
another, yet each fact will be represented once at every
node & will quickly run out of memory
• Furthermore, spend the majority of time creating these
nodes & copying these facts-most of which do not change
often-from one node to another.
• Spend a lot of time recording above(Ceiling,Floor)
at every node
-All of these is, of course, in addition to the real problem
figuring out which facts should be different at each node
The Frame Problem
• This whole problem of representing the facts that
change as well as that do not is known as the frame
problem.
• In some domains, the only hard part is representing all
the facts
• In other, though, figuring out which ones change is
nontrivial
Robot World: there might be a table with a plant on it
under the window. Suppose we move the table to the
center of the room. We must also infer that the plant is
now in the center of the room too but the window is
not.
The Frame Problem
• To support this kind of reasoning, some
systems make use of an explicit set of axioms
(Frame Axioms).
-describes all the things that do not change
when a particular operator is applied in state
n to produce state n+1 (the things that do
change must be mentioned as part of the
operator itself)
color(x,y,s1) move(x,s1,s2) color(x,y,s2)