Inference: chaining, resolution and unification

Advanced

Introduction

Truth tables double in size with every symbol, so they are useless for large knowledge bases. Inference rules derive new sentences directly from old ones, doing work only where it matters. Rule-based expert systems, Prolog, database query engines and the type checkers of some programming languages all work this way.

How it works

Modus ponens is the basic rule: from A and A → B, infer B. Knowledge bases of Horn clauses, rules such as fever ∧ cough → flu_suspected plus plain facts, can be handled entirely with it.

Forward chaining starts from the facts. It repeatedly scans the rules and fires any rule whose premises are all known, adding its conclusion, until nothing new can be added. It is data-driven: it finds every consequence, including ones nobody asked about.

Backward chaining starts from a goal. To prove a goal, it checks whether the goal is a fact; otherwise it looks for a rule that concludes the goal and tries to prove each premise in turn, recursively. It is goal-driven and does only the work the question needs. It must avoid loops, such as P → Q and Q → P, by refusing to prove a goal that is already on the current path.

Resolution handles any sentence in conjunctive normal form (an "and" of clauses, each an "or" of literals). From clauses (A ∨ B) and (¬A ∨ C), it infers (B ∨ C). To prove KB ⊨ α, add ¬α to the KB and resolve until the empty clause appears, which is a contradiction. This refutation method is complete for propositional logic.

First-order logic adds objects, predicates and variables: Knows(john, X) means "John knows X" for some X. To use a rule such as Knows(Y, Mother(Y)), the reasoner must find values for the variables that make two expressions identical: unification. Unifying Knows(john, X) with Knows(Y, Mother(Y)) gives Y = john and X = Mother(john). The occurs check refuses X = f(X), which would need an infinite term.

Syntax

def unify(a, b, s):
    a, b = walk(a, s), walk(b, s)            # follow existing bindings
    if a == b: return s
    if is_variable(a): return bind(a, b, s)  # unless a occurs in b
    if is_variable(b): return bind(b, a, s)
    if same_functor_and_arity(a, b):
        for x, y in zip(args(a), args(b)):
            s = unify(x, y, s)
            if s is None: return None
        return s
    return None

Example

rules = [
    (["fever", "cough"], "flu_suspected"),
    (["flu_suspected", "positive_test"], "flu"),
    (["flu"], "rest"),
    (["rash"], "allergy_check"),
]
facts = {"fever", "cough", "positive_test"}

print("forward chaining:")
known = set(facts)
changed = True
while changed:
    changed = False
    for premises, conclusion in rules:
        if conclusion not in known and all(p in known for p in premises):
            known.add(conclusion)
            changed = True
            print(f"    {' and '.join(premises)} => {conclusion}")


def prove(goal, depth=0, path=()):
    pad = "    " * (depth + 1)
    if goal in facts:
        print(f"{pad}{goal}: a known fact")
        return True
    for premises, conclusion in rules:
        if conclusion == goal and goal not in path:
            print(f"{pad}{goal}: try the rule {' and '.join(premises)} => {goal}")
            if all(prove(p, depth + 1, path + (goal,)) for p in premises):
                return True
    print(f"{pad}{goal}: cannot be proved")
    return False


for goal in ["rest", "allergy_check"]:
    print(f"backward chaining, goal {goal}:")
    print("    proved" if prove(goal) else "    not proved")
Open in compiler

Line by line

  1. The rules are Horn clauses: a list of premises and one conclusion. Three facts are known.
  2. Forward chaining fires every rule whose premises are known, in passes, and finds flu_suspected, then flu, then rest.
  3. Backward chaining for rest works from the goal: rest needs flu, flu needs flu_suspected and a positive test, and so on down to facts.
  4. Each step is indented by how deep it is in the proof.
  5. For allergy_check, the only rule needs a rash, which is not a fact and has no rule, so the goal cannot be proved.

Expected result

forward chaining:
    fever and cough => flu_suspected
    flu_suspected and positive_test => flu
    flu => rest
backward chaining, goal rest:
    rest: try the rule flu => rest
        flu: try the rule flu_suspected and positive_test => flu
            flu_suspected: try the rule fever and cough => flu_suspected
                fever: a known fact
                cough: a known fact
            positive_test: a known fact
    proved
backward chaining, goal allergy_check:
    allergy_check: try the rule rash => allergy_check
        rash: cannot be proved
    allergy_check: cannot be proved
    not proved

In the real world

Prolog runs programs by backward chaining with unification. Business rule engines, such as those that check insurance claims, use forward chaining over thousands of rules. Datalog, a forward-chaining logic language, is used for program analysis and in some databases. Unification is also how compilers infer types in languages such as Haskell, OCaml and Rust.

Common mistakes

  • Firing a rule again for a conclusion already known, which never ends in a loop of rules.
  • Backward chaining without a loop check, which recurses forever on P → Q, Q → P.
  • Resolving on two literals at once, which is not a valid step.
  • Skipping the occurs check, so X unifies with f(X) and later code loops forever.

Best practices

  • Use forward chaining when new facts arrive and all their consequences are needed; backward chaining for specific questions.
  • Record which rule produced each fact, so conclusions can be explained.
  • Apply a substitution fully before printing it, so every variable shows its final value.

Summary

Forward chaining applies modus ponens from facts until nothing changes; backward chaining proves a goal by proving the premises of a rule that concludes it. Resolution with refutation is complete for propositional logic. Unification finds variable bindings that make two terms equal, which lets rules with variables apply to many objects.

Quick check

1. Which method starts from the facts and derives everything that follows?
2. What does resolution infer from (A ∨ B) and (¬A ∨ C)?
3. Why does backward chaining need a loop check?
4. What do Knows(john, X) and Knows(Y, Mother(Y)) unify to?

Key takeaways

  • Forward chaining derives everything that follows; backward chaining only what a goal needs.
  • Resolution with proof by contradiction is complete for propositional logic.
  • Unification lets one rule apply to many objects, which is the heart of first-order logic and Prolog.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.