Transcript Reasoning - LES PUC-Rio

Reasoning
Forward and Backward Chaining
Andrew Diniz da Costa
[email protected]
Roadmap
• Overview about Reasoning
• Forward Chaining
– Presentation
– Examples
• Backward Chaining
– Presentation
– Examples
• JTP API
• Final Considerations
© LES/PUC-Rio
Reasoning
• Reasoning is the mental (cognitive) process of looking for
reasons to support beliefs, conclusions, actions or feelings.
• In philosophy, the study of reasoning typically focuses on
what makes reasoning efficient or inefficient, appropriate or
inappropriate, good or bad.
© LES/PUC-Rio
Reasoning
• The main division between forms of reasoning that is made
in philosophy is between deductive reasoning and
inductive reasoning.
• Formal logic has been described as 'the science of
deduction'.
• The study of inductive reasoning is generally carried out
within the field known as informal logic or critical thinking.
© LES/PUC-Rio
Deductive Reasoning
• Deductive arguments are intended to have reasoning that is
valid.
• Reasoning in an argument is valid if the argument's
conclusion must be true when the premises (the reasons
given to support that conclusion) are true.
• Example
• Premise 1: All humans are mortal.
• Premise 2: Socrates is a human.
• Conclusion: Socrates is mortal.
© LES/PUC-Rio
Deductive Reasoning
• Within the field of formal logic, a variety of different forms
of deductive reasoning have been developed.
• Some logics
– Modal logic
– Propositional logic
– Predicate logic
© LES/PUC-Rio
Inductive Reasoning
• Inductive reasoning contrasts strongly with deductive
reasoning.
• Even in the best, or strongest, cases of inductive reasoning,
the truth of the premises does not guarantee the truth of
the conclusion.
• The conclusion of an inductive argument follows with some
degree of probability.
• Example
– Premise: The sun has risen in the east every morning up until
now.
– Conclusion: The sun will also rise in the east tomorrow.
© LES/PUC-Rio
Reasoning
• If-then rules have become the most popular form of
declarative knowledge representation used in AI
applications.
• Algorithms to process if-the rules
– Forward Chaining
– Backward Chaining
• Forward Chaining can be used to produce new facts
• Backward Chaining can deduce whether conclusions are true
or not.
© LES/PUC-Rio
Forward Chaining
• It is one of the two main methods of reasoning when using
inference rules.
• Forward chaining starts with the available data until a goal
to be reached.
• Use inference rules to extract more data until a goal to be
reached.
© LES/PUC-Rio
Forward Chaining
• An inference engine using forward chaining searches the
inference rules until it finds one where the If clause is
known to be true.
• When found it can conclude, or infer, the Then clause,
resulting in the addition of new information to its dataset.
• Require three basic elements
– A knowledge base of rules and facts;
– A working memory for storing data during inferencing;
– An inference engine.
© LES/PUC-Rio
Forward Chaining – First Example
• The Vehicles Rule Base
Cycle: IF num_wheels < 4
THEN vehicleType=cycle
Automobile: IF num_wheels=4 AND motor=yes
THEN vehicleType=automobile
MiniVan: IF vehicleType=automobile
AND size=medium
AND num_doors=3
THEN vehicle=MiniVan
...
© LES/PUC-Rio
Forward Chaining – First Example
• Initial values in the working memory
– num_wheels=4
– motor=yes
– num_doors=3
– size=medium
• Cycle: IF num_wheels < 4
THEN vehicleType=cycle (Rule is false)
• Automobile: IF num_wheels=4 AND motor=yes
THEN vehicleType=automobile
© LES/PUC-Rio
Forward Chaining – First Example
• Values in the working memory
– num_wheels=4
– motor=yes
– num_doors=3
– size=medium
– vehicleType=automobile
• MiniVan: IF vehicleType=automobile
AND size=medium
AND num_doors=3
THEN vehicle=MiniVan
© LES/PUC-Rio
Forward Chaining – First Example
• Values in the working memory
– num_wheels=4
– motor=yes
– num_doors=3
– size=medium
– vehicleType=automobile
– vehicle=MiniVan
© LES/PUC-Rio
Forward Chaining – Second Example
• Suppose that the goal is to conclude the color of my pet
Fritz, given that he croaks and eats flies, and that the rule
base contains the following two rules:
– If Fritz croaks and eats flies - Then Fritz is a frog
– If Fritz is a frog - Then Fritz is green
croaks=true
croaks=true
croaks=true
eats_flies=true
eats_flies=true
eats_flies=true
Fritz=frog
Fritz=frog
green=true
Working memory
© LES/PUC-Rio
Forward Chaining Cycle
1 - Load the rule base into the inference engine and load any facts
from the knowledge base into the working memory.
2 - Add any additional initial data into the working memory
3 - Match the rules against the data in the working memory which
rules are triggered, meaning that all of their antecedent clauses
are true. This set of triggered rules is called the conflict set.
4 – Use a procedure to select a single rule from the conflict set.
5 – Update the working memory.
6 – Repeat steps 3, 4 and 5 until the conflict set is empty.
© LES/PUC-Rio
Backward Chaining
• A particular consequence or goal clause is evaluated first.
• Unlike forward chaining, which uses rules to produce new
information, backward chaining uses rules to answer
questions about whether a goal clause is true or not.
• It only processes rules that are relevant to the question.
© LES/PUC-Rio
Backward Chaining - Example
• We go to work using a rule from our Vehicles rule base as
an example.
Cycle: IF num_wheels < 4
THEN vehicleType=cycle
Automobile: IF num_wheels=4 AND motor=yes
THEN vehicleType=automobile
MiniVan: IF vehicleType=automobile
AND size=medium
AND num_doors=3
THEN vehicle=MiniVan
...
© LES/PUC-Rio
Backward Chaining - Example
• Suppose we want to find out whether the vehicle we have is
a MiniVan.
• MiniVan: IF vehicleType=automobile
AND size=medium
AND num_doors=3
THEN vehicle=MiniVan
• We start with an empty working memory.
• To verify if vehicle=MiniVan in the work memory.
• If not, then all the antecedent clauses of the MiniVan=true:
rule must be true.
© LES/PUC-Rio
Backward Chaining - Example
• The first thing we do is test if vehicleType=automobile is
true.
• The vehicleType variable has no value, so we look for a rule
that has vehicleType=automobile in its consequence clause
• Automobile: IF num_wheels=4
AND motor=yes
AND vehicleType=automobile
• We look num_wheels=4 in the work memory and if there
is a rule related. There are none, so we ask the user.
© LES/PUC-Rio
Backward Chaining - Example
• Working memory
– num_wheels=4
– motor=yes
– vehicleType=automobile
• Going back to our original rule
• MiniVan: IF vehicleType=automobile
AND size=medium
AND num_doors=3
THEN vehicle=MiniVan
© LES/PUC-Rio
Backward Chaining - Example
• Working memory
– num_wheels=4
– motor=yes
– vehicleType=automobile
– size=medium
– num_doors=3
– vehicle=MiniVan
© LES/PUC-Rio
Backward Chaining - Cycle
1 - Load the rule base into the inference engine and load any facts
from the knowledge base into the working memory
2 - Add any additional initial data into the working memory
3 – Specify a goal variable for the inference engine to find
4 – Find the set rules that refer to the goal variable in a consequence
clause. Put each rule on the goal stack
5 – Take the top rule off the goal stack
6 – Try to prove the rule is true by testing all antecedent clauses to
see if they are true.
© LES/PUC-Rio
JTP:An Object-Oriented Modular Reasoning System
• Knowledge Systems Laboratory of Computer Science
Department in Stanford University
• JTP is based on a very simple and general reasoning
architecture.
• Backward-chaining and forward chaining
• Reasoner is the principal functional component of the
architecture.
– process - This method attempts to find proof for the goal.
© LES/PUC-Rio
Final Considerations
• Forward-chaining uses inference rules to extract more data.
• Backward chaining uses rules to answer questions about
whether a goal clause is true or not.
• Very used in AI applications.
• APIs that use forward- and backward-chaining (ex: JTP).
© LES/PUC-Rio
Bibliography
• Bigus, Joseph P.; Bigus, Jennifer, Constructing Intelligent
Agents Using Java – Second Edition.
• Forward chaining - Wikipedia (2007),
http://en.wikipedia.org/wiki/Forward_chaining, August.
• Forward chaining of Rules (2007),
http://msdn2.microsoft.com/en-us/library/aa349441.aspx,
August.
• Reasoning – Wikipedia (2007),
http://en.wikipedia.org/wiki/Reasoning, August
© LES/PUC-Rio
Bibliography
• Backward chaining – Wikipedia (2007)
http://en.wikipedia.org/wiki/Backward_chaining, August.
• API JTP Web site (2007), http://wwwksl.stanford.edu/software/jtp/, August.
© LES/PUC-Rio
Questions?
The End.