Backward chaining
Encyclopedia
Backward chaining is an inference
method that can be described (in lay terms) as working backward from the goal(s). It is used in automated theorem provers, proof assistants and other artificial intelligence
applications, but it has also been observed in primates.
In game theory
, its application to (simpler) subgame
s in order to find a solution to the game is called backward induction
. In chess, it is called retrograde analysis
, and it is used to generate tablebases for chess endgames for computer chess
.
Backward chaining is implemented in logic programming
by SLD resolution
. Both rules are based on the modus ponens
inference rule. It is one of the two most commonly used methods of reasoning with inference rules and logical implications – the other is forward chaining
. Backward chaining systems usually employ a depth-first search
strategy, e.g. Prolog
.
) and works backwards from the consequent
to the antecedent
to see if there is data
available that will support any of these consequents. An inference engine
using backward chaining would search the inference
rules until it finds one which has a consequent (Then clause) that matches a desired goal. If the antecedent (If clause) of that rule is not known to be true, then it is added to the list of goals (in order for one's goal to be confirmed one must also provide data that confirms this new rule).
For 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 four rules:
This rule base would be searched and the third and fourth rules would be selected, because their consequents (Then Fritz is green, Then Fritz is yellow) match the goal (to determine Fritz's color). It is not yet known that Fritz is a frog, so both the antecedents (If Fritz is a frog, If Fritz is a canary) are added to the goal list. The rule base is again searched and this time the first two rules are selected, because their consequents (Then X is a frog, Then X is a canary) match the new goals that were just added to the list. The antecedent (If Fritz croaks and eats flies) is known to be true and therefore it can be concluded that Fritz is a frog, and not a canary. The goal of determining Fritz's color is now achieved (Fritz is green if he is a frog, and yellow if he is a canary, but he is a frog since he croaks and eats flies; therefore, Fritz is green).
Note that the goals always match the affirmed versions of the consequents of implications (and not the negated versions as in modus tollens
) and even then, their antecedents are then considered as the new goals (and not the conclusions as in affirming the consequent
) which ultimately must match known facts (usually defined as consequents whose antecedents are always true); thus, the inference rule which is used is modus ponens
.
Because the list of goals determines which rules are selected and used, this method is called goal-driven
, in contrast to data-driven
forward-chaining
inference. The backward chaining approach is often employed by expert systems.
Programming languages such as Prolog
, Knowledge Machine
and ECLiPSe
support backward chaining within their inference engines.
, a bonobo
(pygmy chimpanzee, Pan paniscus) dramatically illustrated his use of this strategy when he was being taught how to create stone tool
s by a human
expert. Unable to replicate the manipulations of the human expert, Kanzi eventually resorted to smashing stones upon others, and simply selected shards with sharp edges, in order to produce his stone tools.
Inference
Inference is the act or process of deriving logical conclusions from premises known or assumed to be true. The conclusion drawn is also called an idiomatic. The laws of valid inference are studied in the field of logic.Human inference Inference is the act or process of deriving logical conclusions...
method that can be described (in lay terms) as working backward from the goal(s). It is used in automated theorem provers, proof assistants and other artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
applications, but it has also been observed in primates.
In game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, its application to (simpler) subgame
Subgame
In game theory, a subgame is any part of a game that meets the following criteria :#It has a single initial node that is the only member of that node's information set In game theory, a subgame is any part (a subset) of a game that meets the following criteria (the following terms allude to a game...
s in order to find a solution to the game is called backward induction
Backward induction
Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this...
. In chess, it is called retrograde analysis
Retrograde analysis
In chess, retrograde analysis is a computational method used to solve game positions for optimal play by working backward from known outcomes , such as the construction of endgame tablebases. In game theory at large, this method is called backward induction...
, and it is used to generate tablebases for chess endgames for computer chess
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
.
Backward chaining is implemented in logic programming
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
by SLD resolution
SLD resolution
SLD resolution is the basic inference rule used in logic programming. It is a refinement of resolution, which is both sound and refutation complete for Horn clauses.-The SLD inference rule:...
. Both rules are based on the modus ponens
Modus ponens
In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...
inference rule. It is one of the two most commonly used methods of reasoning with inference rules and logical implications – the other is forward chaining
Forward chaining
Forward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
. Backward chaining systems usually employ a depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
strategy, e.g. Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
.
How it works
Backward chaining starts with a list of goals (or a hypothesisHypothesis
A hypothesis is a proposed explanation for a phenomenon. The term derives from the Greek, ὑποτιθέναι – hypotithenai meaning "to put under" or "to suppose". For a hypothesis to be put forward as a scientific hypothesis, the scientific method requires that one can test it...
) and works backwards from the consequent
Consequent
A consequent is the second half of a hypothetical proposition. In the standard form of such a proposition, it is the part that follows "then".Examples:* If P, then Q.Q is the consequent of this hypothetical proposition....
to the antecedent
Antecedent (logic)
An antecedent is the first half of a hypothetical proposition.Examples:* If P, then Q.This is a nonlogical formulation of a hypothetical proposition...
to see if there is data
Data
The term data refers to qualitative or quantitative attributes of a variable or set of variables. Data are typically the results of measurements and can be the basis of graphs, images, or observations of a set of variables. Data are often viewed as the lowest level of abstraction from which...
available that will support any of these consequents. An inference engine
Inference engine
In computer science, and specifically the branches of knowledge engineering and artificial intelligence, an inference engine is a computer program that tries to derive answers from a knowledge base. It is the "brain" that expert systems use to reason about the information in the knowledge base for...
using backward chaining would search the inference
Inference
Inference is the act or process of deriving logical conclusions from premises known or assumed to be true. The conclusion drawn is also called an idiomatic. The laws of valid inference are studied in the field of logic.Human inference Inference is the act or process of deriving logical conclusions...
rules until it finds one which has a consequent (Then clause) that matches a desired goal. If the antecedent (If clause) of that rule is not known to be true, then it is added to the list of goals (in order for one's goal to be confirmed one must also provide data that confirms this new rule).
For 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 four rules:
- If X croaks and eats flies – Then X is a frog
- If X chirps and sings – Then X is a canary
- If X is a frog – Then X is green
- If X is a canary – Then X is yellow
This rule base would be searched and the third and fourth rules would be selected, because their consequents (Then Fritz is green, Then Fritz is yellow) match the goal (to determine Fritz's color). It is not yet known that Fritz is a frog, so both the antecedents (If Fritz is a frog, If Fritz is a canary) are added to the goal list. The rule base is again searched and this time the first two rules are selected, because their consequents (Then X is a frog, Then X is a canary) match the new goals that were just added to the list. The antecedent (If Fritz croaks and eats flies) is known to be true and therefore it can be concluded that Fritz is a frog, and not a canary. The goal of determining Fritz's color is now achieved (Fritz is green if he is a frog, and yellow if he is a canary, but he is a frog since he croaks and eats flies; therefore, Fritz is green).
Note that the goals always match the affirmed versions of the consequents of implications (and not the negated versions as in modus tollens
Modus tollens
In classical logic, modus tollens has the following argument form:- Formal notation :...
) and even then, their antecedents are then considered as the new goals (and not the conclusions as in affirming the consequent
Affirming the consequent
Affirming the consequent, sometimes called converse error, is a formal fallacy, committed by reasoning in the form:#If P, then Q.#Q.#Therefore, P....
) which ultimately must match known facts (usually defined as consequents whose antecedents are always true); thus, the inference rule which is used is modus ponens
Modus ponens
In classical logic, modus ponendo ponens or implication elimination is a valid, simple argument form. It is related to another valid form of argument, modus tollens. Both Modus Ponens and Modus Tollens can be mistakenly used when proving arguments...
.
Because the list of goals determines which rules are selected and used, this method is called goal-driven
Goal-oriented
The concept of goal orientation was developed to describe variability in dispositional or situational goal preferences that an individual implicitly sets for him/herself in achievement situations. GOs assist in providing a motivational framework for how individuals perceive, interpret, and judge...
, in contrast to data-driven
Data driven
Data driven means that progress in an activity is compelled by data, rather than by intuition or personal experience. This often refers to:* Data-driven programming* Data driven journalism* Data-driven testing* Data driven learning, or DDL...
forward-chaining
Forward chaining
Forward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
inference. The backward chaining approach is often employed by expert systems.
Programming languages such as Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, Knowledge Machine
Knowledge Machine
The Knowledge Machine is a concept of Seymour Papert, which is intended to enable children to explore any situation and engage them completely. Although Papert never clearly defined the Knowledge Machine, one interpretation is a virtual reality device that allows the user to slip into any situation...
and ECLiPSe
ECLiPSe
ECLiPSe is a software system for the development and deployment of Constraint Programming applications, e.g. in the areas of optimization, planning, scheduling, resource allocation, timetabling, transport etc....
support backward chaining within their inference engines.
Use by primates
KanziKanzi
Kanzi , also known by the lexigram , is a male bonobo who has been featured in several studies on great ape language. According to Sue Savage-Rumbaugh, a primatologist who has studied the bonobo throughout her life, Kanzi has exhibited advanced linguistic aptitude.- Biography :Born to Lorel and...
, a bonobo
Bonobo
The bonobo , Pan paniscus, previously called the pygmy chimpanzee and less often, the dwarf or gracile chimpanzee, is a great ape and one of the two species making up the genus Pan. The other species in genus Pan is Pan troglodytes, or the common chimpanzee...
(pygmy chimpanzee, Pan paniscus) dramatically illustrated his use of this strategy when he was being taught how to create stone tool
Stone tool
A stone tool is, in the most general sense, any tool made either partially or entirely out of stone. Although stone tool-dependent societies and cultures still exist today, most stone tools are associated with prehistoric, particularly Stone Age cultures that have become extinct...
s by a human
Human
Humans are the only living species in the Homo genus...
expert. Unable to replicate the manipulations of the human expert, Kanzi eventually resorted to smashing stones upon others, and simply selected shards with sharp edges, in order to produce his stone tools.
See also
- Backward inductionBackward inductionBackward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this...
- Forward chainingForward chainingForward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
- Opportunistic reasoningOpportunistic reasoningOpportunistic reasoning is a method of selecting a suitable logical inference strategy within artificial intelligence applications.Specific reasoning methods may be used to draw conclusions from a set of given facts in a knowledge base, e.g. forward chaining versus backward chaining...
- Working backward from the goal
General References
- Russell, Stuart J.Stuart J. RussellStuart Russell is a computer scientist known for his contributions to artificial intelligence.Stuart Russell was born in Portsmouth, England. He received his Bachelor of Arts degree with first-class honours in Physics from Wadham College, Oxford in 1982, and his Ph.D. in Computer Science from...
; Norvig, PeterPeter NorvigPeter Norvig is an American computer scientist. He is currently the Director of Research at Google Inc.-Educational Background:...
(2009), Artificial Intelligence: A Modern ApproachArtificial Intelligence: A Modern ApproachArtificial Intelligence: A Modern Approach is a college textbook on Artificial Intelligence, written by Stuart J. Russell and Peter Norvig. The third edition of the book was released 11 December 2009...
(3rd ed.), Upper Saddle River, New Jersey: Prentice Hall, (ISBN 0-13-604259-7), http://aima.cs.berkeley.edu/ .