Backward Reasoning

**Backward chaining** (or **backward reasoning**) is an inference method that can be described colloquially as working backward from the goal(s). It is used in automated theorem provers, inference engines, proof assistants and other artificial intelligence applications.^{[1]}

In game theory, its application to (simpler) subgames 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.^{[2]}

Backward chaining starts with a list of goals (or a hypothesis) and works backwards from the consequent to the antecedent to see if there is data available that will support any of these consequents.^{[3]} 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 a new pet, Fritz, is delivered in an opaque box along with two facts about Fritz:

- Fritz croaks
- Fritz eats flies

The goal is to decide whether Fritz is green, based on a rule base containing the following four rules:

**If**X croaks and X eats flies -**Then**X is a frog**If**X chirps and X sings -**Then**X is a canary**If**X is a frog -**Then**X is green**If**X is a canary -**Then**X is yellow

With backward reasoning, an inference engine can determine whether Fritz is green in four steps. To start, the query is phrased as a goal assertion that is to be proved: "Fritz is green".

1. Fritz is substituted for X in rule #3 to see if its consequent matches the goal, so rule #3 becomes:

IfFritz is a frog -ThenFritz is green

Since the consequent matches the goal ("Fritz is green"), the rules engine now needs to see if the antecedent ("If Fritz is a frog") can be proved. The antecedent therefore becomes the new goal:

Fritz is a frog

2. Again substituting Fritz for X, rule #1 becomes:

IfFritz croaks and Fritz eats flies -ThenFritz is a frog

Since the consequent matches the current goal ("Fritz is a frog"), the inference engine now needs to see if the antecedent ("If Fritz croaks and eats flies") can be proved. The antecedent therefore becomes the new goal:

Fritz croaks and Fritz eats flies

3. Since this goal is a conjunction of two statements, the inference engine breaks it into two sub-goals, both of which must be proved:

Fritz croaks Fritz eats flies

4. To prove both of these sub-goals, the inference engine sees that both of these sub-goals were given as initial facts. Therefore, the conjunction is true:

Fritz croaks and Fritz eats flies

therefore the antecedent of rule #1 is true and the consequent must be true:

Fritz is a frog

therefore the antecedent of rule #3 is true and the consequent must be true:

Fritz is green

This derivation therefore allows the inference engine to prove that Fritz is green. Rules #2 and #4 were not used.

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.^{[4]}

**^**Feigenbaum, Edward (1988).*The Rise of the Expert Company*. Times Books. p. 317. ISBN 0-8129-1731-6.**^**Michel Chein; Marie-Laure Mugnier (2009).*Graph-based knowledge representation: computational foundations of conceptual graphs*. Springer. p. 297. ISBN 978-1-84800-285-2.**^**Definition of backward chaining as a depth-first search method:- Russell & Norvig 2009, p. 337

**^**Languages that support backward chaining:- Russell & Norvig 2009, p. 339

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

What We've Done

Led Digital Marketing Efforts of Top 500 e-Retailers.

Worked with Top Brands at Leading Agencies.

Successfully Managed Over $50 million in Digital Ad Spend.

Developed Strategies and Processes that Enabled Brands to Grow During an Economic Downturn.

Taught Advanced Internet Marketing Strategies at the graduate level.

Manage research, learning and skills at defaultLogic. Create an account using LinkedIn or facebook to manage and organize your IT knowledge. defaultLogic works like a shopping cart for information -- helping you to save, discuss and share.