AI Notes
Learn backward chaining. Goal-driven search. Reasoning 2024.
What is Backward Chaining?
Backward chaining is a goal-driven reasoning strategy that starts with a hypothesis or query and works backward through the knowledge base to find supporting evidence. Instead of deriving all possible conclusions from known facts (forward chaining), backward chaining asks: "What would need to be true for this conclusion to hold?" and recursively tries to prove each prerequisite.
This approach mirrors how humans often reason in diagnostic situations: a doctor suspects pneumonia and checks for supporting symptoms, rather than cataloging every possible diagnosis from all observed symptoms. Backward chaining is the fundamental reasoning mechanism in Prolog programming, MYCIN-style diagnostic systems, and goal-directed planning.
Algorithm
function backward_chain(KB, goal):
if goal is in known facts:
return TRUE
for each rule R in KB where R.conclusion == goal:
all_proved = TRUE
for each condition C in R.conditions:
if not backward_chain(KB, C):
all_proved = FALSE
break
if all_proved:
return TRUE
// If no rule can prove it, ask the user
answer = ask_user(goal)
return answerComplete Worked Example
Knowledge Base: Animal Identification
| R1 | IF has_feathers THEN is_bird |
| R2 | IF is_bird AND can_fly AND is_large THEN is_eagle |
| R3 | IF is_bird AND cannot_fly AND is_black_white THEN is_penguin |
| R4 | IF is_bird AND can_fly AND sings THEN is_canary |
| R5 | IF has_fur AND eats_meat THEN is_carnivore |
| R6 | IF is_carnivore AND has_stripes THEN is_tiger |
| Known facts | {has_feathers, cannot_fly, is_black_white} |
| Goal | Prove "is_penguin" |
Backward Chaining Trace
| GOAL | is_penguin? |
| Find rule with conclusion = is_penguin | R3 |
| R3 requires | is_bird AND cannot_fly AND is_black_white |
| SUB-GOAL 1 | is_bird? |
| Not in facts. Find rule | R1 |
| R1 requires | has_feathers |
| SUB-GOAL 1.1 | has_feathers? |
| R1 fires | is_bird = TRUE ✓ |
| SUB-GOAL 2 | cannot_fly? |
| SUB-GOAL 3 | is_black_white? |
| All conditions of R3 met | is_penguin = TRUE ✓ |
| RESULT | The animal is a penguin. |
| Proof chain: has_feathers | is_bird → (is_bird ∧ cannot_fly ∧ is_black_white) → is_penguin |
Showing the Backward Search Tree
Backward Chaining with User Interaction
When a sub-goal can't be proved from rules or facts, the system asks the user:
| Goal | is_tiger? |
| R6 requires | is_carnivore AND has_stripes |
| Sub-goal | is_carnivore? |
| R5 requires | has_fur AND eats_meat |
| Sub-goal | has_fur? |
| ASK USER: "Does the animal have fur?" | User: "Yes" |
| Add to facts | has_fur = true |
| Sub-goal | eats_meat? |
| ASK USER: "Does it eat meat?" | User: "Yes" |
| R5 fires | is_carnivore ✓ |
| Sub-goal | has_stripes? |
| ASK USER: "Does it have stripes?" | User: "Yes" |
| R6 fires | is_tiger ✓ |
This demonstrates backward chaining's diagnostic character—it asks targeted questions to confirm or deny hypotheses, rather than asking about everything.
Backward Chaining in Prolog
Prolog implements backward chaining natively:
% Knowledge base
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
male(tom).
male(bob).
female(liz).
female(ann).
% Rules
father(X, Y) :- parent(X, Y), male(X).
grandfather(X, Z) :- father(X, Y), parent(Y, Z).
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.
% Query (backward chaining automatically)
?- grandfather(tom, ann).
% Prolog traces:
% grandfather(tom, ann) needs father(tom, Y), parent(Y, ann)
% father(tom, Y) needs parent(tom, Y), male(tom)
% parent(tom, bob) ✓, male(tom) ✓ → father(tom, bob) ✓
% parent(bob, ann) ✓
% → grandfather(tom, ann) = yes!Handling Cycles and Infinite Loops
Backward chaining can loop infinitely with circular rules:
Problem
R1: IF happy THEN successful
R2: IF successful THEN rich
R3: IF rich THEN happy
Goal: happy? → need successful → need rich → need happy → ...
Infinite loop!
Solutions
1. Depth limit: Stop recursion after N levels
2. Loop detection: Track goals being proved (occur check)
3. Tabled resolution: Cache already-attempted goals
Backward vs. Forward Chaining
| Aspect | Backward Chaining | Forward Chaining |
|---|---|---|
| Direction | Goal → Evidence | Facts → Conclusions |
| Strategy | Hypothesis testing | Exhaustive derivation |
| Questions | Targeted (only relevant) | None (all data upfront) |
| Efficiency | Good when few goals | Good when few rules match |
| Best for | Diagnosis, verification | Monitoring, planning |
| Examples | MYCIN, Prolog | CLIPS, OPS5, Drools |
Applications
Medical Diagnosis
"Is this pneumonia?" → check for fever, cough, X-ray findings
Only asks about pneumonia-relevant symptoms
Technical Troubleshooting
"Is the network down?" → check router, cable, DNS
Focused investigation of one hypothesis at a time
Legal Reasoning
"Is this contract valid?" → check signatures, consideration, capacity
Systematically verify each legal requirement
Configuration
"Can we build this system?" → check component compatibility
Verify each requirement is satisfiable
Interview Questions
Q: When is backward chaining more efficient than forward chaining? A: When the goal is specific and the knowledge base is large. Forward chaining would derive all possible conclusions (potentially thousands), most irrelevant. Backward chaining only explores rules related to the query—like searching a small subtree instead of the entire knowledge base.
Q: How does Prolog implement backward chaining? A: Prolog uses SLD-resolution: to prove a goal, it finds rules whose head (conclusion) unifies with the goal, then recursively proves each body (condition) literal. It uses depth-first search with backtracking—if one proof path fails, it tries alternative rules for the same goal.
Q: What is the relationship between backward chaining and depth-first search? A: Backward chaining explores the proof tree depth-first: it pursues one rule's conditions completely before trying alternative rules. This means it finds a proof quickly if one exists along the first path explored, but may loop or take a long path if the first choice is wrong. Prolog's cut (!) operator controls this exploration.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Backward Chaining - Goal-Driven Reasoning.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, reasoning, and, inference, backward
Related Artificial Intelligence Topics