SPC 2312
Knowledge-Based
Systems
Chapter 9 Reasoning with
Knowledge: Inference Strategies
Objectives
be familiar with the essential concepts of logic and reasoning
– sentence, operators, syntax, semantics, inference methods
appreciate the importance of reasoning for knowledge-based
systems
– generating new knowledge
– explanations
understand the main methods of reasoning used in KBS
– shallow and deep reasoning
– forward and backward chaining
evaluate reasoning methods for specific tasks and scenarios
apply reasoning methods to simple problems
Motivation
❖ without reasoning, knowledge-based systems
would be practically worthless
❖ derivation of new knowledge
❖ examination of the consistency or validity of existing
knowledge
❖ reasoning in KBS can perform certain tasks
better than humans
❖ reliability, availability, speed
❖ also some limitations
❖ common-sense reasoning
❖ complex inferences
4
Shallow and Deep Reasoning
❖ shallow reasoning
❖ also called experiential reasoning
❖ aims at describing aspects of the world heuristically
❖ short inference chains
❖ possibly complex rules
❖ deep reasoning
❖ also called causal reasoning
❖ aims at building a model of the world that behaves like the
“real thing”
❖ long inference chains
❖ often simple rules that describe cause and effect
relationships
5
Examples Shallow and Deep
Reasoning
❖ shallow reasoning ❖ deep reasoning
IF a car has IF the battery is good
THEN there is electricity
a good battery
IF there is electricity AND good
good spark plugs
spark plugs
gas THEN the spark plugs will fire
good tires IF the spark plugs fire AND
there is gas
THEN the car can move THEN the engine will run
IF the engine runs AND
there are good tires
THEN the car can move
6
ES Structure
Knowledge Base
Knowledge
Acquisition
User Interface
Facility
Inference Engine Agenda
Explanation
Facility
Working Memory
7
Reasoning Programs
❖ Inference Engine
❖ Algorithms
❖ Directs search of knowledge base
❖ Forward chaining
❖ Data driven
❖ Start with information, draw conclusions
❖ Backward chaining
❖ Goal driven
❖ Start with expectations, seek supporting evidence
❖ Inference/goal tree
❖ Schematic view of inference process
❖ AND/OR/NOT nodes
❖ Answers why and how
❖ Rule interpreter
8
Rule-Based Inference Engine
Cycle
❖ describes the execution of rules by the inference
engine
❖ conflict resolution
❖ select the rule with the highest priority from the agenda
❖ execution
❖ perform the actions on the consequent of the selected rule
❖ remove the rule from the agenda
❖ match
❖ update the agenda
❖ add rules whose antecedents are satisfied to the agenda
❖ remove rules with non-satisfied agendas
❖ the cycle ends when no more rules are on the
agenda, or when an explicit stop command is
encountered 9
Basic Procedure
While changes are made to Working Memory do:
❖ Match: Construct the Conflict Set -- the set of
all possible (R, F) pairs such that R is one of
the rules and F is a subset of facts in WM that
unify with the antecedent (left-hand side) of R.
❖ Conflict Resolution: Select one pair from the
Conflict Set for execution.
❖ Act: Execute the actions associated with the
consequent (right-hand side) of R, after making
the substitutions used during unification of the
antecedent part with F.
1
0
Conflict Resolution Strategy
Components
❖ Refraction
❖ A rule can only be used once with the same set of facts in WM.
Whenever WM is modified, all rules can again be used. This
strategy prevents a single rule and list of facts from being used
repeatedly, resulting in an infinite loop of reasoning.
❖ Recency
❖ Use rules that match the facts that were added most recently to
WM, providing a kind of “focus of attention” strategy.
❖ Specificity
❖ Use the most specific rule: if both R1 and R2 match, and R1’s
LHS logically implies R2’s LHS, use R2.
❖ Explicit priorities
❖ E.g., numeric salience attribute for rules
1
1
1. Modus Ponens
❖ eliminates =>
(X => Y), X
______________
Y
❖ If it rains, then the streets will be wet.
❖ It is raining.
❖ Infer the conclusion: The streets will be wet.
❖ (affirms the antecedent)
12
1
2
2. Modus tollens
(X => Y), ~Y
_______________
¬X
❖ If it rains, then the streets will be wet.
❖ The streets are not wet.
❖ Infer the conclusion: It is not raining.
NOTE: Avoid the fallacy of affirming the consequent:
❖
❖ If it rains, then the streets will be wet.
❖ The streets are wet.
❖ cannot conclude that it is raining.
❖ If Bacon wrote Hamlet, then Bacon was a great writer.
❖ Bacon was a great writer.
❖ cannot conclude that Bacon wrote Hamlet.
13
1
3
3. Syllogism
❖ chain implications to deduce a conclusion
(X => Y), (Y => Z)
_____________________
(X => Z)
14
1
4
4. Resolution
(X v Y), (~Y v Z)
_________________
(X v Z)
❖basis for the inference mechanism in the Prolog
language and some theorem provers
15
1
5
Inference in Rule-Based ES
❖ knowledge is encoded as IF … THEN rules
❖ these rules can also be written as production rules
❖ the inference engine determines which rule
antecedents are satisfied
❖ the left-hand side must “match” a fact in the working memory
❖ satisfied rules are placed on the agenda
❖ rules on the agenda can be activated (“fired”)
❖ an activated rule may generate new facts through its right-
hand side
❖ the activation of one rule may subsequently cause the
activation of other rules
1
6
Example Rules
IF … THEN Rules
antecedent
Rule: Red_Light (left-hand-side)
IF the light is red
THEN stop
Rule: Green_Light consequent
IF the light is green (right-hand-side)
THEN go
antecedent (left-hand-side)
Production Rules
the light is red ==> stop
consequent
(right-hand-side)
the light is green ==> go
1
7
Unification
❖ an operation that tries to find consistent variable
bindings (substitutions) for two terms
❖ a substitution is the simultaneous replacement of
variable instances by terms, providing a “binding” for
the variable
❖ without unification, the matching between rules would
be restricted to constants
❖ often used together with the resolution inference rule
❖ unification itself is a very powerful and possibly
complex operation
❖ in many practical implementations, restrictions are imposed
❖ e.g. substitutions may occur only in one direction (“matching”)
1
8
Forward and Backward
Chaining
❖ different methods of rule activation
❖ forward chaining (data-driven)
❖ reasoning from facts to the conclusion
❖ as soon as facts are available, they are used to match antecedents of
rules
❖ a rule can be activated if all parts of the antecedent are satisfied
❖ often used for real-time expert systems in monitoring and control
❖ examples: CLIPS, OPS5
❖ backward chaining (query-driven)
❖ starting from a hypothesis (query), supporting rules and facts are
sought until all parts of the antecedent of the hypothesis are satisfied
❖ often used in diagnostic and consultation systems
❖ examples: EMYCIN
1
9
5. Forward Chaining
❖ given a set of basic facts, we try to derive a
conclusion from these facts
❖ example: What can we conjecture about Clyde?
IF elephant(x) THEN mammal(x)
IF mammal(x) THEN animal(x)
elephant (Clyde)
modus ponens:
unification:
IF p THEN q
p find compatible values for
variables
q
20
2
0
Forward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q
IF elephant( x ) THEN mammal( x )
elephant (Clyde)
21
2
1
Forward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q
IF elephant(Clyde) THEN mammal(Clyde)
elephant (Clyde)
22
2
2
Forward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q
IF mammal( x ) THEN animal( x )
IF elephant(Clyde) THEN mammal(Clyde)
elephant (Clyde)
23
2
3
Forward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q
IF mammal(Clyde) THEN animal(Clyde)
IF elephant(Clyde) THEN mammal(Clyde)
elephant (Clyde)
24
2
4
Forward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal( x )
IF mammal(Clyde) THEN animal(Clyde)
IF elephant(Clyde) THEN mammal(Clyde)
elephant (Clyde)
25
2
5
Forward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde)
IF mammal(Clyde) THEN animal(Clyde)
IF elephant(Clyde) THEN mammal(Clyde)
elephant (Clyde)
26
2
6
6. Backward Chaining
❖ try to find supportive evidence (i.e. facts) for a
hypothesis
❖ example: Is there evidence that Clyde is an
animal? IF elephant(x) THEN mammal(x)
IF mammal(x) THEN animal(x)
elephant (Clyde)
modus ponens:
unification:
IF p THEN q
p find compatible values for
variables
q
27
2
7
Backward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde) ?
IF mammal( x ) THEN animal( x )
28
2
8
Backward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde) ?
IF mammal(Clyde) THEN animal(Clyde)
29
2
9
Backward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde) ?
IF mammal(Clyde) THEN animal(Clyde)
?
IF elephant( x ) THEN mammal( x )
30
Backward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde) ?
IF mammal(Clyde) THEN animal(Clyde)
?
IF elephant(Clyde) THEN mammal(Clyde)
31
3
1
Backward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde) ?
IF mammal(Clyde) THEN animal(Clyde)
?
IF elephant(Clyde) THEN mammal(Clyde)
elephant ( x ) ? 32
3
2
Backward Chaining Example
IF elephant(x) THEN mammal(x) unification:
IF mammal(x) THEN animal(x) find compatible values for
variables
elephant(Clyde)
modus ponens:
IF p THEN q
p
q animal(Clyde)
IF mammal(Clyde) THEN animal(Clyde)
IF elephant(Clyde) THEN mammal(Clyde)
elephant (Clyde)
33
Forward vs. Backward
Chaining
Forward Chaining Backward Chaining
planning, control diagnosis
data-driven goal-driven (hypothesis)
bottom-up reasoning top-down reasoning
find possible conclusions find facts that support a given
supported by given facts hypothesis
similar to breadth-first search similar to depth-first search
antecedents (LHS) control consequents (RHS) control
evaluation evaluation
34
3
4
Summary Reasoning
❖ reasoning relies on the ability to generate new knowledge
from existing knowledge
❖ implemented through inference rules
❖ related terms: inference procedure, inference mechanism, inference engine
❖ computer-based reasoning relies on syntactic symbol
manipulation (derivation)
❖ inference rules prescribe which combination of sentences can
be used to generate new sentences
❖ ideally, the outcome should be consistent with the meaning of
the respective sentences (“sound” inference rules)
❖ logic provides the formal foundations for many knowledge
representation schemes
❖ rules are frequently used in expert systems
35
3
5
Ex: Other Inference Methods
deduction
◆ conclusions must follow from their premises; prototype of logical
reasoning
induction
◆ inference from specific cases (examples) to the general
abduction
◆ reasoning from a true conclusion to premises that may have
caused the conclusion
generate and test
◆ a tentative solution is generated and tested for validity
◆ often used for efficiency (trial and error)
3
6
Inference Methods
default reasoning
general or common knowledge is assumed in the absence of
specific knowledge
analogy
a conclusion is drawn based on similarities to another situation
heuristics
rules of thumb based on experience
intuition
typically human reasoning method
nonmonotonic reasoning
new evidence may invalidate previous knowledge
autoepistemic
reasoning about your own knowledge
3
7
Alternative Inference
Methods
❖ theorem proving
❖ emphasis on mathematical proofs, not so much on
performance and ease of use
❖ probabilistic reasoning
❖ integrates probabilities into the reasoning process
❖ fuzzy reasoning
❖ enables the use of ill-defined predicates
3
8
Exercise
❖ KB:
❖ allergies(X) sneeze(X)
❖ cat(Y) allergicToCats(X) allergies(X)
❖ cat(felix)
❖ allergicToCats(mary)
❖ Goal:
❖ sneeze(mary)
3
9