Backward Chaining: Reasoning from Goals to Evidence, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.9 Free with a free account

Backward Chaining: Reasoning from Goals to Evidence

Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.9 · lesson 47 of 6911 min · free with a free account

← Forward Chaining: Deriving Conclusions from RulesNext lesson: Prolog: A Logic-Based Programming Language for AI →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How goal-driven reasoning breaks questions into subgoals and backtracks.

  • Trace backward chaining from a goal through subgoals to known facts
  • Use unification and standardizing apart when rules contain variables
  • Explain why depth-first backward chaining can loop and how rule order prevents it
  • Compare forward and backward chaining and choose the right one for a task

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,630 words). Read along, or search it.

Opening Question

Did the Butler Do It

A detective doesn't read every page of the case file, hoping something turns up. She starts with a question: did the butler do it? Then she asks what would have to be true. The butler would need a motive, the opportunity, and the means. Each of those becomes a new question, checked against the evidence. Questions that can't be answered directly break into smaller ones, until every piece rests on something known. That's backward chaining: start from the goal, and work back toward the evidence. A medical assistant asking, could this be disease X, and which findings would confirm it, reasons the same way.

Method

Four Steps from Goal to Subgoals

Backward chaining uses the same kind of knowledge base as forward chaining: facts and rules. A rule's conclusion is its head, and its list of conditions is its body. The method has four steps. Take the goal. If it's a known fact, it's proven. Otherwise, find a rule whose head matches the goal. Turn each condition of that rule into a new subgoal, and prove them all. If a subgoal can't be proven, try a different rule for the goal. If none is left, the goal fails.

Worked Example

Proving Scholarship Eligibility Backward

Take the scholarship rules from forward chaining. Is this student Eligible? Rule R1 needs GoodGrades AND InNeed. Both are needed, so these subgoals form an AND. GoodGrades can come from R2 or R3, so those alternatives form an OR. R2 is tried first. It needs AwardWinner, which isn't a fact, and no rule concludes it. That fails, so back up. R3 needs HighGPA, a known fact. So GoodGrades is proven. Then InNeed: R4 needs LowIncome, also a known fact. So InNeed is proven, and Eligible is proven too.

Key Features

Relevance and Backtracking

Two features of that search matter. First, it looked only at rules relevant to the goal. A thousand facts about unrelated students would never have been touched. Second, when AwardWinner failed, it didn't give up. It backed up to the last choice it made, and tried the next alternative. That's called backtracking. As a program, the goals are a to-do list. Take the first goal, and for each rule that concludes it, put that rule's conditions at the front of the list, then prove the new list. A fact is just a rule with no conditions. If the list empties, every goal is proven. Putting conditions at the front makes the search go deep, on one line of enquiry, before returning to the rest.

Quick Check

Library Fails First and Forces a Backtrack

Quick check, with new rules. Pass IF Studied AND Slept. Then, Studied IF Library, listed first, and Studied IF Tutor. The facts are Tutor and Slept. Backward chaining asks: Pass? Which goal is the first to fail, and force a backtrack? Library, Tutor, or Slept? Pause, and decide. Library. Pass needs Studied, then Slept. Studied's first rule needs Library, which isn't a fact and has no rule, so it fails. The reasoner backs up, tries Studied IF Tutor, and Tutor is a fact. Then Slept is a fact too, so Pass is proven. Tutor and Slept never fail: both are known.

Unification

Matching Goals with Variable Rule Heads

Real knowledge bases use rules with variables. Grandparent x, z IF Parent x, y AND Parent y, z. Lowercase letters are variables, and capitalized names are constants. To use such a rule, the reasoner must decide whether its head matches the goal, and what the variables stand for. That's unification: finding a substitution, like x slash Ann, that makes two expressions identical. Parent x, Bob, and Parent Alice, y, unify with x as Alice and y as Bob. Knows John x, and Knows y, Mother of y, give y as John, and x as Mother of John. Likes Alice Bob can't match Likes Alice Carol: the constants differ. Parent x x can't match Parent Alice Bob. And P of x can't match P of f of x: that's the occurs check. Knows John x, and Knows x Elizabeth, fail only because they share the name x by accident. So each time a rule is used, its variables get fresh names. That's standardizing apart.

Worked Example

Finding Ann's Grandchildren

Who are Ann's grandchildren? The facts are Parent Ann Bob, Parent Bob Cara, and Parent Bob Dan, with the grandparent rule. The query is Grandparent Ann w. The query unifies with the rule's head, after renaming its variables: x1 is Ann, and z1 is w. That gives two subgoals: Parent Ann y1, and Parent y1 w. Parent Ann y1 matches the first fact, so y1 is Bob, and the goal left is Parent Bob w. That matches Parent Bob Cara: w is Cara, an answer. Then it backtracks, to see whether other facts fit too, and finds w is Dan. Compared with the simple version, only three things are new: rename the rule's variables, unify instead of comparing names, and apply the bindings to the goals still waiting.

Quick Check

Unifying Nested Car Terms

Quick check. Unify, Owns x, Car of x, with, Owns, Car of Bea, y. Is the result x as Car of Bea, and y as Car of Car of Bea? Is it x as Bea, and y as Car of Bea? Or no unifier, because of the occurs check? Pause, and decide. The first. The first arguments bind x to Car of Bea. Apply that, and the second arguments become Car of, Car of Bea, against y. So y is Car of Car of Bea. The second option would need x to be Bea, but x faces Car of Bea, not Bea. And the occurs check doesn't apply: y doesn't occur inside Car of Car of Bea.

Depth-First Problems

Loops, Missed Answers and Repeated Work

This algorithm is depth first. It follows the first matching rule all the way down, and returns to an earlier choice only when a branch fails. That's easy to build, and needs very little memory. But it brings problems. Infinite loops: a rule whose first condition is the same kind of goal as its head, keeps creating the same subgoal, forever. Missed answers: the search gets lost in an endless branch, and never reaches an answer in another one. Repeated work: the same subgoal gets proven again and again. And sensitivity to order: rule order and condition order change the speed, and even the outcome, though the logic is unchanged. The remedies: put base cases first and recursion last, or detect goals already on the path. Limit the depth and deepen it gradually. Remember solved subgoals, called tabling. And put likely failures early.

Rule Order

Safe and Risky Ancestor Rules

The loop problem is clearest with ancestors. x is an ancestor of y if x is a parent of y, or if x is an ancestor of some parent of y. Two versions say exactly that, in different orders. The risky version lists Ancestor x y IF Ancestor x z AND Parent z y, first. Its first condition is another Ancestor goal of the same kind, again and again. It never finishes. The safe version lists Ancestor x y IF Parent x y, first, then Ancestor x y IF Parent x z AND Ancestor z y. With Ann's family, it returns Bob, Cara, and Dan, then stops. So list the simple rules first, and in each rule, put the condition that makes progress, like a fact lookup, before the recursive one. Depth-first backward chaining is sound: every answer really follows. But it isn't complete: it can miss an answer, or never stop. Prolog, in lesson six point ten, is built around exactly this method.

Quick Check

Bob's Descendants Without Looping

Quick check, with the safe ancestor rules and the same three facts. The query is Ancestor of Bob, w. What happens? Cara and Dan, and the search ends? Cara and Dan, then it loops forever? Or Ann, Cara, and Dan? Pause, and decide. Cara and Dan, and it ends. The first rule finds Bob's children, Cara and Dan. Then the second rule asks for an ancestor relation below each child, but Cara and Dan have no children, so those branches fail. Every recursive call moves down the tree to a fact lookup, so it can't loop. And Ann is Bob's parent, not his descendant.

Comparison

Forward Versus Backward Chaining

Forward chaining starts from the known facts, and works toward conclusions. Data drives it: each new fact can trigger rules. Backward chaining starts from the goal, and works back to the facts. Forward chaining may derive many facts nobody asked about. Backward chaining examines only rules relevant to the goal, and returns an answer with values for its variables. Forward chaining stops when no new facts appear. Backward chaining stops when the goal is proven or fails, though depth-first search can loop. So forward asks, what follows from what we know? It suits monitoring, alarms, and configuration. Backward asks, is this true, and why? It suits diagnosis, question answering, and proving a specific claim.

Choosing a Method

When Each Chaining Strategy Fits

Sensor readings stream in, and an alarm must sound the moment a rule becomes true: that's forward chaining, because new data triggers the rules. One question about a knowledge base with millions of facts fits backward chaining, which avoids deriving millions of irrelevant facts. So does a doctor asking which tests would show a disease: the subgoals list the evidence still needed. Many questions answered quickly from the same stable facts fit forward chaining: work the conclusions out once, then look them up. Many practical systems combine the two: forward chaining keeps conclusions current as facts arrive, and backward chaining answers specific questions. For definite rules, both are sound. The choice is about efficiency, not correctness.

Key Takeaways

Goal-Driven Reasoning in Review

To sum up. Backward chaining starts from a goal, matches a rule's head, and turns its conditions into subgoals. It examines only relevant rules, and backtracks when a branch fails. Unification matches goals with rule heads, and rules get fresh variable names each time. Depth-first search is light on memory, but rule order matters, since recursion can loop. And forward chaining is driven by data, backward chaining by goals, with the same conclusions from the same rules.

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Backward Chaining: Reasoning from Goals to Evidence

What is backward chaining in AI?
Backward chaining is a goal-driven inference method that starts from a question and works back toward known facts. If the goal is a fact, it is proven; otherwise the reasoner finds a rule whose head matches the goal and turns that rule's conditions into subgoals. If a subgoal fails, it backtracks and tries another rule, and the goal fails when no rules remain.
What is the difference between forward and backward chaining?
Forward chaining starts from known facts and derives everything that follows, while backward chaining starts from a goal and examines only rules relevant to it. Forward chaining suits monitoring, alarms and configuration, where new data should trigger rules. Backward chaining suits diagnosis, question answering and proving a specific claim. For definite rules both are sound, so the choice is about efficiency, not correctness.
Why can backward chaining get stuck in an infinite loop?
Depth-first backward chaining loops when a rule's first condition is the same kind of goal as its head, so it keeps creating the same subgoal. Ancestor(x, y) IF Ancestor(x, z) AND Parent(z, y), listed first, never finishes. Listing the base rule Ancestor(x, y) IF Parent(x, y) first, and putting a fact lookup before the recursive condition, fixes it. Depth limits and tabling also help.
What is standardizing apart in backward chaining?
Standardizing apart gives a rule's variables fresh names each time the rule is used, so they cannot clash with variables already in the goal. Without it, Knows(John, x) and Knows(x, Elizabeth) fail to unify only because both happen to use the name x. After renaming one x, they unify, with one variable bound to John and the other to Elizabeth.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →