Knowledge Representation and Reasoning
Several of the lectures in the first section of this course are based on the following book:
! Ronald Brachman & Hector Levesque
! Knowledge Representation and Reasoning
! Morgan Kaufmann, 2004.
! ISBN: ISBN: 978-1-55860-932-7.
These slides will be clearly identified.
Up-to-date slides for this book are available from:
! http://www.cs.toronto.edu/~hector/PublicKRSlides.pdf
KR & R! © Brachman & Levesque 2005 Introduction
What is knowledge?
Easier question: how do we talk about it?
We say “John knows that …” and fill the blank with a proposition
• canbetrue/false,right/wrong
Contrast: “John fears that …” • samecontent,differentattitude
Other forms of knowledge: • knowhow,who,what,when,…
• sensorimotor:typing,ridingabike • affective:deepunderstanding
Belief: similar, but not necessarily true and/or held for appropriate reasons
• and weaker yet: “John suspects that …” Here: no distinction
! The main idea: !!
taking the world to be one way and not another
KR & R! © Brachman & Levesque 2005 Introduction
What is representation?
Symbols standing for things in the world
“John” “John loves Mary”
Knowledge representation:
first aid
women restaurant
John
the proposition that John loves Mary
! symbolic encoding of propositions believed (by some agent)
KR & R! © Brachman & Levesque 2005 Introduction
What is reasoning?
Manipulation of symbols encoding propositions to produce representations of new propositions
Analogy: arithmetic
! “1011” + “10” → “1101” !⇓⇓⇓
# eleven two “John is Mary’s
thirteen
“John is an adult male”
father” ⇓⇓
J
M
J
KR & R! © Brachman & Levesque 2005 Introduction
Why knowledge?
For sufficiently complex systems, it is sometimes useful to describe systems in terms of beliefs, goals, fears, intentions
! e.g. a game-playing program
! “because it believed its queen was in danger, but
wanted to still control the center of the board.”
! more useful than description about actual techniques used
for deciding how to move
! “because evaluation procedure P using minimax
returned a value of +7 for this position”
= taking an intentional stance (Daniel Dennett)
But…
Is KR just a convenient way of describing complex systems?
• sometimesanthropomorphizingisinappropriate ! e.g. thermostats
• canalsobeverymisleading!
! fooling users into thinking a system knows more than it does
KR & R! © Brachman & Levesque 2005 Introduction
Why representation?
Note: intentional stance says nothing about what is / is not represented symbolically
! e.g. in game playing
! perhaps the board position is represented, but the goal of getting a knight out early is not
KR Hypothesis: (Brian Smith)
! “Any mechanically embodied intelligent process will be comprised of structural ingredients that a) we as external observers naturally take to represent a propositional account of the knowledge that the overall process exhibits, and b) independent of such external semantic attribution, play a formal but causal and essential role in engendering the behaviour that manifests that knowledge.”
!
• Two issues: existence of structures that
– we can interpret propositionally
– determine how the system behaves
Knowledge-based system: ! one designed in this way!
KR & R! © Brachman & Levesque 2005 Introduction
Two Examples
Example 1
printColour(snow) :- !, write(“It’s white.”).
printColour(grass) :- !, write(“It’s green.”).
printColour(sky) :- !, write(“It’s yellow.”).
printColour(X) :- write(“Beats me.”).
Example 2
printColour(X) :- colour(X,Y), !,
! write(“It’s “), write(Y), write(“.”). printColour(X) :- write(“Beats me.”).
colour(snow,white).
colour(sky,yellow).
colour(X,Y) :- madeof(X,Z), colour(Z,Y).
madeof(grass,vegetation).
colour(vegetation,green).
! Both systems can be described intentionally
! Only the 2nd has a separate collection of symbolic structures à la KR Hypothesis
! its knowledge base (or KB)
∴ a small knowledge-based system
KR & R! © Brachman & Levesque 2005 Introduction
KR & AI
Much of AI involves building systems that are knowledge-based
! ability derives in part from reasoning over explicitly represented knowledge
– language understanding, – planning,
– diagnosis,
– “expert systems”,
– …
Some, to a certain extent – game-playing,
– vision, – …
Some, to a much lesser extent – speech,
– motor control, – …
Current research question:
! how much of intelligent behaviour is knowledge-based?
! ! Challenges: connectionism, others
KR & R! © Brachman & Levesque 2005 Introduction
Why bother?
Why not “compile out” knowledge into specialized procedures?
• distributeKBtoproceduresthatneedit ! (as in Example 1)
• almostalwaysachievesbetterperformance
No need to think. Just do it! – riding a bike
– driving a car
– playing chess? – doing math?
– staying alive??
Skills (Hubert Dreyfus)
! novices think; experts react
! compare to current “expert systems”:
! knowledge-based !
KR & R! © Brachman & Levesque 2005 Introduction
Advantage
Knowledge-based system most suitable for open-ended tasks
! can structurally isolate reasons for particular behaviour Good for
• explanationandjustification
– “Because grass is a form of vegetation.”
• informability:debuggingtheKB
– “No the sky is not yellow. It’s blue.”
• extensibility:newrelations – “Canaries are yellow.”
• newapplications
– returning a list of all the white things – painting pictures
Hallmark of KB’ed system:
! the ability to be told facts about the world and adjust
behaviour correspondingly
“Cognitive penetrability” (Zenon Pylyshyn)
! actions that are conditioned by what is currently believed
! e.g. do not leave the room on hearing a fire alarm if we believe that the alarm is being tested
! ! so this action is cognitively penetrable
KR & R! © Brachman & Levesque 2005 Introduction
Why reasoning?
Want knowledge to affect action
! not!
! but!
do action A if sentence P is in KB do action A if world believed in
! ! satisfies P
Difference:
! P may not be explicitly represented
! Need to apply what is known to particulars of given situation
Example:
! “Patient x is allergic to medication m.”
! “Anybody allergic to medication m is also allergic to m’.”
! IsitOKtoprescribe m’ forx?
Usually need more than just DB-style retrieval of facts in the KB
KR & R! © Brachman & Levesque 2005 Introduction
Entailment
Sentences P1, P2, …, Pn entail sentence P iff the truth of P is implicit in the truth of P1, P2, …, Pn.
! If the world is such that it satisfies the Pi then it must also satisfy P.
! Applies to a variety of languages – languages with truth theories
Inference: the process of calculating entailments
! sound: get only entailments
! complete: get all entailments
Sometimes want unsound / incomplete reasoning
– to be discussed later
Logic: study of entailment relations
– languages
– truth conditions
– rules of inference
KR & R! © Brachman & Levesque 2005 Introduction
Using logic
No universal language / semantics ! WhynotEnglish?
! Differenttasks/worlds
! Differentwaystocarveuptheworld
No universal reasoning scheme ! Gearedtolanguage
! Sometimeswant“extralogical”reasoning Start with first-order predicate calculus (FOL)
! inventedbyphilosopherFregefortheformalizationof mathematics
! butwillconsidersubsets/supersetsandverydifferentlooking representation languages
Allen Newell’s analysis:
Knowledge level:! (semantic)
! deals with language, entailment
Symbol level:! ! (computational) ! deals with representation, inference
Picking a logic has issues at each level
• !
! !
• !
! !
! !
expressive adequacy, theoretical complexity, …
architectures,
data structures, algorithmic complexity
Next: we begin with FOL at KL
KL: !
SL:!
KR & R! © Brachman & Levesque 2005 Introduction