Expert Systems & the Knowledge Bottleneck
Why hand-written rules scaled so badly.
In 1980 a rule-based program began configuring computer orders at Digital Equipment Corporation, and within a few years the company credited it with savings of tens of millions of dollars a year. A decade later the expert-system industry had collapsed. The reasons were not only commercial; they were logical and probabilistic, and they still shape how AI handles knowledge and uncertainty.
What you’ll learn
- Formalize rule-based inference as forward chaining over Horn clauses, and prove it sound, complete and linear-time.
- Derive MYCIN's certainty-factor combination rule, and prove Heckerman's result that under a likelihood-ratio transformation it is exactly Bayesian updating with conditionally independent evidence.
- Explain the qualification problem, prove that an inconsistent rule base entails every sentence, and describe the nonmonotonic and probabilistic responses.
- Analyze the knowledge acquisition bottleneck, and connect it to knowledge graphs and language models today.
Rules as Horn clauses
An expert system pairs a knowledge base of facts and rules with an inference engine, plus facilities for explanation and knowledge entry. A rule "IF AND … AND THEN " is a definite clause , that is : a Horn clause with exactly one positive literal.
Data-driven systems such as R1/XCON chain forward from the facts; goal-driven systems such as MYCIN chain backward from hypotheses, as Prolog does.
function FC-ENTAILS(KB, q) returns true or false
count[c] ← the number of premises of clause c, for each clause in KB
inferred[s] ← false, for every symbol s
agenda ← the facts (clauses without premises) in KB
while agenda is not empty:
p ← POP(agenda)
if p = q then return true
if not inferred[p]:
inferred[p] ← true
for each clause c in whose premises p appears:
count[c] ← count[c] − 1
if count[c] = 0 then PUSH(conclusion(c), agenda)
return falsePropositional forward chaining with premise counters, after Russell and Norvig. Each symbol is processed once, and each occurrence of a symbol in a premise is decremented once.
Soundness: every inferred symbol follows by modus ponens from facts and from clauses whose premises were all inferred earlier.
Completeness: when the agenda empties, let make exactly the inferred symbols true. Every clause is true in , since a clause whose premises were all true would have reached count 0 and pushed its conclusion. So is a model of KB, any entailed by KB is true in , and hence was inferred. ( is the least model of KB.)
Linear time: each symbol is marked inferred at most once, and each premise occurrence is decremented at most once, so the total work is proportional to the sum of the clause lengths.
Think first Satisfiability is NP-complete. Why is reasoning with definite clauses linear-time?
Definite clauses never force a case split. With exactly one positive literal per clause, there is a unique least model, built greedily by modus ponens. General clauses such as create choices ("which one is true?"), and exploring those choices is where search, and potentially exponential time, comes from.
First-order rules add variables, so each cycle must match rule patterns against working memory by unification. Done naively, a rule with condition elements over facts costs up to match attempts per cycle. Forgy's Rete algorithm (1982) compiles all the rules into one dataflow network that caches partial matches, so each cycle costs time proportional to the change in working memory, trading memory for speed. Rete made systems with thousands of rules, like XCON, practical.
Certainty factors, and when they are probabilities
MYCIN (Shortliffe and Buchanan, 1975) attached a certainty factor to each rule and conclusion: for certainly true, for certainly false, for no evidence. A rule's conclusion receives ; conjoined premises take the minimum of their factors, disjoined premises the maximum. Two rules bearing on the same hypothesis combine in parallel, in the later EMYCIN form:
Two rules support the same diagnosis with certainty factors and . What is the combined certainty factor?
Show the answer
0.8
. Equivalently, the doubts multiply: .
Both positive (): , and the combination multiplies doubts:
Both negative (): , and the second formula multiplies these:
Mixed, say with : then , so the minimum is and the denominator is . (If , the minimum is and the result is , as required.)
The catch. The identity needs evidence that is conditionally independent given and given . MYCIN's factors were elicited from experts, not measured as likelihood ratios, and Heckerman showed that the serial rule for chaining rules does not in general agree with probability theory. Two rules triggered by the same lab result count it twice: .
Exceptions, qualifications and an inconsistent rule base
Classical entailment is monotonic: if then , so learning more never retracts a conclusion. Expert knowledge is full of defaults: birds fly, unless they are penguins, ostriches, injured, caged… McCarthy called the impossibility of listing every precondition of a rule the qualification problem, a sibling of the frame problem (McCarthy and Hayes, 1969).
Leave the exceptions out and the rules are false. Add them as separate rules and the knowledge base can become inconsistent, which is worse than it sounds.
Three responses emerged. Nonmonotonic logics, in a 1980 special issue of Artificial Intelligence: Reiter's default logic ("if Bird, and it is consistent to assume Flies, conclude Flies"), McCarthy's circumscription (minimize abnormality) and McDermott and Doyle's nonmonotonic logic. Specificity in rule engines: prefer the most specific matching rule, an operational version of the same idea. And probability: and coexist without contradiction, one reason Bayesian networks displaced rule bases in diagnosis.
A rule base concludes "Tweety flies" from the fact "Tweety is a bird" and the rule "birds fly". You add the fact "Tweety is a penguin", and nothing else. What does classical entailment now say?
- "Tweety flies" is retracted
- "Tweety flies" still follows: adding premises never removes consequences, because classical entailment is monotonic
- The rule base has become inconsistent
- "Tweety does not fly" now follows
Show the answer
B. "Tweety flies" still follows: adding premises never removes consequences, because classical entailment is monotonic
Adding premises can only add consequences. Retracting "Tweety flies" needs a nonmonotonic logic, or a probabilistic model in which the new evidence lowers the probability. Inconsistency arises only if you also add a rule such as "penguins do not fly", as in the widget.
The bottleneck, then and now
Feigenbaum named the knowledge acquisition bottleneck: knowledge engineers had to elicit rules from experts interview by interview, and much expertise is tacit. Maintenance compounded it. A new rule can conflict with or shadow any of the existing ones, so validating each addition against those already present costs
pairwise checks for rules, before counting longer chains of interaction.
XCON grew to many thousands of rules, and keeping it consistent with a changing product line took a dedicated team. Cyc, begun by Doug Lenat in 1984 to hand-encode common sense, accumulated millions of assertions without becoming the general reasoner it aimed at.
What replaced hand-coding? Learning from data, from the statistical turn of the 1990s to deep learning. Curated and mined knowledge graphs (Wikidata and Google's Knowledge Graph, both 2012), which serve as structured backbones. And language models as knowledge bases: Petroni et al. (2019) showed that pretrained language models answer cloze-style factual queries without any schema.
Language models dissolve the acquisition bottleneck but bring back the problems that rules were meant to solve: no guarantee of consistency, no explicit provenance, and hallucinated facts. Retrieval-augmented generation (RAG) and tool use re-attach explicit sources, and neurosymbolic systems use models to write formal rules or programs that a solver can check.
Key takeaways
- Rules are definite (Horn) clauses. Forward chaining is sound, complete (it computes the least model) and linear-time, and Rete makes first-order matching incremental.
- MYCIN's parallel combination multiplies doubts; under Heckerman's transformation it is exactly Bayesian updating with conditionally independent evidence, but dependent evidence is double-counted and serial chaining is not probabilistically coherent.
- Classical entailment is monotonic, so exceptions create the qualification problem, and an inconsistent knowledge base entails everything. Nonmonotonic logics, specificity and probability are the responses.
- The knowledge acquisition bottleneck (tacit expertise, quadratic maintenance) pushed AI toward learning; language models remove the bottleneck but bring back problems of consistency, provenance and hallucination.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In the completeness proof for forward chaining, what plays the key role?
- The inferred symbols, made true with everything else false, form a model of the knowledge base
- Every clause has at most two literals
- The agenda is processed first-in, first-out
- The query appears in the premises of some rule
Show the answer
A. The inferred symbols, made true with everything else false, form a model of the knowledge base
When the algorithm stops, no clause has all its premises true and its conclusion false, so the assignment "inferred symbols are true" satisfies the KB. Anything the KB entails is true there, and therefore was inferred.
Under Heckerman's transformation (for ), what does MYCIN's parallel combination of two positive certainty factors correspond to?
- Averaging the two likelihood ratios
- Taking the larger likelihood ratio
- Adding the two likelihood ratios
- Multiplying the likelihood ratios, that is, Bayesian updating with conditionally independent evidence
Show the answer
D. Multiplying the likelihood ratios, that is, Bayesian updating with conditionally independent evidence
, and multiplying likelihood ratios is how posterior odds update on conditionally independent evidence.
A rule base contains rules that contradict each other for some case. Under classical entailment, what follows?
- Only the conclusions of the contradictory rules are affected
- The rule base entails every sentence, including absurd ones
- The most recently added rule wins
- Nothing follows from it at all
Show the answer
B. The rule base entails every sentence, including absurd ones
An unsatisfiable KB has no models, so every sentence is true in all of them, vacuously. Conflict-resolution strategies in rule engines are a practical patch for exactly this.
Why does validating a growing rule base get disproportionately expensive?
- Rules take longer to execute as they get older
- Forward chaining takes time exponential in the number of rules
- Each new rule can interact with every existing rule, so pairwise checks grow quadratically with the number of rules
- Each rule must be tested against every possible input
Show the answer
C. Each new rule can interact with every existing rule, so pairwise checks grow quadratically with the number of rules
Adding rule means checking it against others, checks in total, before counting longer chains of interaction. Inference stays fast (Rete, linear-time Horn reasoning); it is knowledge maintenance that scales badly.
Further reading
- B. G. Buchanan & E. H. Shortliffe (eds.), Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project (Addison-Wesley, 1984).
- J. McDermott, "R1: A rule-based configurer of computer systems," Artificial Intelligence 19, 39–88 (1982).
- D. Heckerman, "Probabilistic interpretations for MYCIN's certainty factors," in L. N. Kanal & J. F. Lemmer (eds.), Uncertainty in Artificial Intelligence (North-Holland, 1986).
- R. Reiter, "A logic for default reasoning," Artificial Intelligence 13, 81–132 (1980).
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapters 7 and 10.