Rule-Based Systems and Expert Systems

It running, with the explanation

# A rule-based expert system with a real inference ENGINE: a match-resolve-act
# cycle, a conflict-resolution strategy, and an explanation trail.
RULES = [
    # (name, priority, premises, conclusion)
    ("R1", 10, ["fever", "cough", "body ache"], "influenza suspected"),
    ("R2", 10, ["fever", "rash"],               "viral exanthem suspected"),
    ("R3", 20, ["influenza suspected", "breathless"], "refer to hospital"),
    ("R4",  5, ["fever"],                       "advise fluids and rest"),
    ("R5", 15, ["fever", "fever above 5 days"], "order a blood test"),
]

def engine(working_memory, trace=True):
    """Match, resolve, act, until no rule fires. Highest priority wins."""
    memory = list(working_memory)
    fired = []
    why = {}
    cycle = 0
    while True:
        cycle += 1
        # MATCH: every rule whose premises are all satisfied and whose
        # conclusion is not yet known
        agenda = [r for r in RULES
                  if r[0] not in fired and all(p in memory for p in r[2])
                  and r[3] not in memory]
        if not agenda:
            break
        # RESOLVE: the conflict-resolution strategy. Highest priority, then
        # most premises, then the order the rules were written.
        agenda.sort(key=lambda r: (-r[1], -len(r[2]), RULES.index(r)))
        if trace:
            print("   cycle %d: %d rule(s) ready: %s"
                  % (cycle, len(agenda), ", ".join(r[0] for r in agenda)))
        name, prio, premises, conclusion = agenda[0]
        # ACT
        memory.append(conclusion)
        fired.append(name)
        why[conclusion] = (name, premises)
        if trace:
            print("        fire %s (priority %d) -> %s" % (name, prio, conclusion))
    return memory, fired, why

def explain(fact, why, facts, depth=0):
    pad = "      " + "   " * depth
    if fact in facts:
        print("%s%s: observed" % (pad, fact))
        return
    name, premises = why[fact]
    print("%s%s: by %s, because" % (pad, fact, name))
    for p in premises:
        explain(p, why, facts, depth + 1)

for case in (["fever", "cough", "body ache", "breathless"],
             ["fever", "rash"],
             ["cough"]):
    print("observed:", ", ".join(case) if case else "nothing")
    memory, fired, why = engine(case)
    print("   concluded:", ", ".join(f for f in memory if f not in case) or "nothing")
    deepest = [f for f in memory if f not in case]
    if deepest:
        print("   WHY %s?" % deepest[-1 if len(deepest) < 3 else 1])
        explain(deepest[-1 if len(deepest) < 3 else 1], why, case)
    print()

observed: fever, cough, body ache, breathless
   cycle 1: 2 rule(s) ready: R1, R4
        fire R1 (priority 10) -> influenza suspected
   cycle 2: 2 rule(s) ready: R3, R4
        fire R3 (priority 20) -> refer to hospital
   cycle 3: 1 rule(s) ready: R4
        fire R4 (priority 5) -> advise fluids and rest
   concluded: influenza suspected, refer to hospital, advise fluids and rest
   WHY refer to hospital?
      refer to hospital: by R3, because
         influenza suspected: by R1, because
            fever: observed
            cough: observed
            body ache: observed
         breathless: observed

observed: fever, rash
   cycle 1: 2 rule(s) ready: R2, R4
        fire R2 (priority 10) -> viral exanthem suspected
   cycle 2: 1 rule(s) ready: R4
        fire R4 (priority 5) -> advise fluids and rest
   concluded: viral exanthem suspected, advise fluids and rest
   WHY advise fluids and rest?
      advise fluids and rest: by R4, because
         fever: observed

observed: cough
   concluded: nothing

Three things in that output are the marks.

The conflict set is printed at every cycle, and it usually has more than one rule in it. At cycle 2, R3 and R4 are both ready. R3 fires because its priority is 20 and R4's is 5, and the order matters: R3's conclusion is the one a doctor needs first.

The cycle is genuinely a cycle, not a single pass. R3's conditions include influenza suspected, which did not exist at cycle 1. It became true because R1 fired. Rules make other rules applicable, which is why the engine loops rather than sweeping once.

The explanation is a tree of rules down to observations. refer to hospital came from R3, which needed influenza suspected, which came from R1, which needed three things the user actually reported. That is the trail a doctor can argue with, and no other technique in this book produces one. A neural network reaching the same conclusion can say nothing at all about why, which is the subject of Transparency and Explainability.

And the third case is the honest one. A cough alone fires nothing, and the system concludes nothing. It does not guess.

What the explanation facility actually provides

Papers ask for these two by name.

WHY, asked while the system is running: why are you asking me this question? The answer is the rule the engine is trying to satisfy, and the goal that rule serves.

HOW, asked of a conclusion: how did you reach that? The answer is the trail printed above, the rules fired and the observations at the leaves.

Both come free from recording the rule that asserted each fact. That is a three-line change to the engine, and it is the whole basis of the claim that an expert system is transparent.

Where expert systems worked

This is not a historical aside. A paper can ask for examples, and the honest ones are specific.

What they have in common is the condition under which the approach works: a narrow domain, a human expert who can state the rules, and a problem where the rules are reliable. Where those three hold, a rule-based system is still the right answer today, and business rule engines are a large industry.

Where they failed, and why

Four failures, and naming them is what turns this topic from a history lesson into an answer.

The knowledge acquisition bottleneck. Getting rules out of an expert is slow, and experts frequently cannot state what they know. A radiologist who reads a film in two seconds cannot list the rules used. This is the single reason machine learning displaced the approach: Module 2's methods learn the rules from examples instead of asking for them.

Brittleness. Outside its narrow domain a rule-based system has no fallback and no common sense. Given a case its rules do not cover it produces nothing, or worse, fires an inappropriate rule confidently. It has no notion of being outside its competence.

Maintenance. With a thousand rules, adding one can silently break another through the conflict set. XCON's rule base became notoriously expensive to maintain, and nobody could say what the whole thing did.

Uncertainty handled by bolt-on. Real expertise is probabilistic, and rules are not. MYCIN's certainty factors were an ad hoc numerical scheme that worked in practice and had no proper semantics. Module 1's fourth row, Bayesian Networks, is the principled replacement, and it arrived after the expert systems era for exactly that reason.

The efficiency problem, and the algorithm that solved it

Worth one paragraph because a paper may name it. Matching a thousand rules against a thousand facts on every cycle is prohibitively slow if done naively, since most rules have not changed status since the last cycle.

The Rete algorithm compiles the rule base into a network in which each condition test is shared between every rule that uses it, and it keeps the partial matches between cycles, updating only what the last fired rule changed. It trades memory for time, and it is what makes a production system with thousands of rules run at all. Every serious rule engine uses it or a descendant.

Distinctions

What it does not mean

A rule-based system is not a program with a lot of if-statements. The rules are data, matched by a separate engine. If they are compiled into the control flow, the architecture's whole benefit is gone.

Conflict resolution is not an implementation detail. Two strategies can produce different conclusions from the same rules and facts, so the strategy is part of the system's meaning.

An expert system does not know it is out of its depth. That is brittleness, and it is why they were dangerous outside their domain.

Certainty factors are not probabilities. MYCIN's scheme was ad hoc and does not obey the probability axioms. Bayesian networks are the principled treatment.

Explanation is not a feature that was added. It falls out of recording which rule asserted each fact, and it is the architecture's main advantage over a learned model.

Rules are not obsolete. They remain right for a narrow domain with stateable, reliable rules, and business rule engines are widely used. What failed was the ambition of encoding general expertise by hand.

Quick revision

• Three parts: rule base (IF-THEN production rules, the knowledge), working memory (the facts of this case), inference engine (domain independent). Plus an explanation facility, knowledge acquisition and a user interface.
• The rule base is separate from the engine. Change the domain by changing the rules.
• The engine runs a match-resolve-act cycle until no rule fires. The matching rules are the conflict set or agenda.
• Conflict-resolution strategies: priority, specificity, recency, refractoriness, order. A system without one is not fully specified, and two strategies can give different answers.
• The cycle loops because a fired rule can make another rule applicable: R3 needed influenza suspected, which R1 produced.
• WHY answers why a question is being asked; HOW answers how a conclusion was reached, as a trail of rules down to observations. Both come from recording which rule asserted each fact.
• Worked: DENDRAL, MYCIN (about 450 rules, certainty factors), XCON, PROSPECTOR. The condition: a narrow domain, a willing expert, reliable rules.
• Failed on: the knowledge acquisition bottleneck, brittleness, maintenance, and uncertainty as a bolt-on. The first is why Module 2 exists; the last is why Bayesian networks do.
• The Rete algorithm shares condition tests between rules and keeps partial matches between cycles, trading memory for time.

Test yourself

1. Name the three main components of a rule-based system and say what each holds. The rule base, holding the domain knowledge as IF-THEN production rules. The working memory, holding the facts of the case currently being reasoned about. And the inference engine, which applies the rules and contains no domain knowledge itself.

2. Describe the match-resolve-act cycle. Match: find every rule whose conditions are satisfied by working memory, forming the conflict set. Resolve: choose one of them by the conflict-resolution strategy. Act: fire it, asserting its conclusion into working memory. Repeat until no rule can fire.

3. Why is a conflict-resolution strategy necessary, and name four. Because more than one rule is usually ready and the order of firing changes the outcome, since a fired rule can make another rule's conditions true or false. Priority or salience, specificity, recency, refractoriness, and file order as a last resort.

4. In this chapter's run, why did rule R3 not fire at cycle 1? Because one of its conditions, influenza suspected, was not yet in working memory. It became true only when R1 fired at cycle 1, which is why the engine loops instead of sweeping the rules once.

5. What does the explanation facility provide, and where does it come from? WHY, explaining why the system is asking a question, in terms of the rule it is trying to satisfy; and HOW, explaining a conclusion as the trail of rules fired down to the user's own observations. Both follow from recording which rule asserted each fact.

6. Name two expert systems and the domain of each, and state the three conditions under which the approach works. MYCIN diagnosed bacterial blood infections with about 450 rules; XCON configured computer orders. The approach works when the domain is narrow, a human expert can state the rules, and the rules are reliable.

7. Give the four reasons expert systems failed, and say which two later parts of this syllabus answer them. The knowledge acquisition bottleneck, since experts often cannot state what they know; brittleness outside the domain, with no common sense and no awareness of incompetence; maintenance, since one new rule can break another through the conflict set; and uncertainty handled by ad hoc devices such as certainty factors. Machine learning in Module 2 answers the first by learning rules from examples, and Bayesian networks answer the last with a principled treatment of uncertainty.