backward chaining
In plain wordsA way of reasoning that starts from the question ('is this true?') and works backward, looking for rules that would prove it and then checking whether their conditions hold.
An inference strategy that starts from a goal, finds rules whose conclusions match it, and treats each such rule's conditions as subgoals, recursing until every subgoal is a known fact or is proven by further rules; when a subgoal fails, the system backtracks to try another rule. Because it explores only rules relevant to the query, it suits diagnosis and question answering, and it lets an expert systemexpert system, n.: A program that stores a human specialist's know-how as many if–then rules and uses them to give advice or make decisions in a narrow field, such as diagnosing infections or configuring computers. ask the user only for facts it actually needs. MYCINMYCIN, prop. n.: A 1970s Stanford program that advised doctors on blood infections and antibiotics by applying hundreds of if–then rules from specialists. It performed about as well as experts but was never used on patients. reasoned backward from candidate infections; PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs. executes programs by backward chaining with depth-first search, using SLD resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known. and unificationunification, n.: Finding values for the blanks in two logical patterns so that they become identical, for example matching 'parent(X, bob)' with 'parent(alice, Y)' by setting X to alice and Y to bob.. Naive implementations loop forever on some recursive rules, which tabling (memoizing subgoals) prevents.
The diagnostic assistant backward-chains from each candidate fault and asks the technician only for the readings that matter.
Origin
Goal-directed reasoning appears in Allen Newell, Cliff Shaw and Herbert Simon's Logic TheoristLogic Theorist, prop. n.: A 1956 computer program that proved theorems from a classic logic textbook by searching cleverly rather than trying every possibility. Many historians count it as the first AI program. (1956), which worked backward from the theorem to be proved toward axioms. The 'chaining' terminology became standard in 1970s–1980s expert-system work.
Related
- forward chainingforward chaining, n.: A way of reasoning that starts from known facts and keeps applying rules to them, adding each new conclusion, until it reaches an answer or nothing new can be concluded.
- inference engineinference engine, n.: The part of an AI system that does the working-out: in older AI, the program that applies rules to facts; in today's AI, the software that runs a trained model to produce answers.
- PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs.
- resolutionresolution, n.: A mechanical step of logical reasoning: from 'A or B' and 'not A or C', conclude 'B or C'. Repeating it can demonstrate any conclusion that genuinely follows from what is known.
- expert systemexpert system, n.: A program that stores a human specialist's know-how as many if–then rules and uses them to give advice or make decisions in a narrow field, such as diagnosing infections or configuring computers.
- means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken.
- forward chainingforward chaining, n.: A way of reasoning that starts from known facts and keeps applying rules to them, adding each new conclusion, until it reaches an answer or nothing new can be concluded.
Mentioned in
forward chainingforward chaining, n.: A way of reasoning that starts from known facts and keeps applying rules to them, adding each new conclusion, until it reaches an answer or nothing new can be concluded., inferenceinference, n.: Drawing a conclusion from evidence. In today's AI it most often means running an already-trained model to get an answer, as opposed to training it., inference engineinference engine, n.: The part of an AI system that does the working-out: in older AI, the program that applies rules to facts; in today's AI, the software that runs a trained model to produce answers., MYCINMYCIN, prop. n.: A 1970s Stanford program that advised doctors on blood infections and antibiotics by applying hundreds of if–then rules from specialists. It performed about as well as experts but was never used on patients., PrologProlog, prop. n.: A programming language from 1972 in which you state facts and rules in logic and then ask questions; the computer finds answers by searching for proofs., rule-based systemrule-based system, n.: A computer system that makes decisions by following a list of 'if… then…' rules written by people, rather than by learning from examples., Horn clauseHorn clause, n.: A simple, restricted form of logical rule ('if these conditions all hold, then this one conclusion holds') that computers can reason with very efficiently., means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken.