Textbook of AI

DENDRAL, developed at Stanford University from 1965 onwards by Edward Feigenbaum, Bruce Buchanan, Joshua Lederberg and Carl Djerassi, is generally regarded as the first major expert system and the founding artefact of knowledge-based AI. The project ran for nearly two decades and demonstrated, on a real scientific problem, that an AI system could match or exceed the performance of human experts in a narrow domain when armed with enough domain knowledge expressed as rules.

The problem

DENDRAL inferred organic molecular structure from mass-spectrometry data. A mass spectrometer bombards a chemical sample with electrons, fragmenting molecules into ions of various mass-to-charge ratios. The resulting spectrum, a histogram of fragment masses, encodes structural information about the parent molecule, but only obliquely: a chemist must reason backwards from fragmentation patterns to plausible structures. For all but the simplest molecules the search space of candidate structures is astronomical, and human chemists rely on heuristics, if a peak appears at mass $X$ with intensity $Y$, then the molecule likely contains a substructure of type $Z$, accumulated over years of training.

Architecture: plan, generate, test

DENDRAL's pipeline embodied a plan-generate-test strategy:

1. Plan. Heuristic rules examined the spectrum and inferred constraints on the molecular structure: which substructures must be present, which must be absent.
2. Generate. An exhaustive structure generator (CONGEN, based on Lederberg's earlier graph-theoretic work on molecular topology) enumerated all candidate structures consistent with the constraints.
3. Test. Each candidate was scored by predicting its mass spectrum and comparing it to the observed spectrum.

The rule base, elicited from Lederberg, Djerassi and other chemists through structured interviews, was the system's intellectual capital. It embodied Feigenbaum's central methodological claim: that knowledge, not algorithms, is the primary source of an AI system's competence. Where earlier symbolic AI (such as the General Problem Solver) had aimed at general-purpose reasoning, Feigenbaum argued that human-level performance required deep domain knowledge, painstakingly elicited and encoded.

Heuristic and Meta-DENDRAL

Two specialised modules divided the work. Heuristic DENDRAL was the rule-based inference engine described above. Meta-DENDRAL (Buchanan and Mitchell, 1976) was an inductive learning system that discovered new mass-spectrometry rules from spectra-structure pairs, making it one of the first significant machine-learning systems in AI history. Meta-DENDRAL prefigured inductive logic programming and influenced Tom Mitchell's later work on version spaces.

Scientific impact

DENDRAL was used in genuine chemical research and produced novel structural inferences that were published in chemistry journals, a rare example of AI research yielding domain-science publications. Lederberg, who had won the 1958 Nobel Prize in Physiology or Medicine for work on bacterial genetics, brought the system to bear on natural-product chemistry and exobiology (NASA had originally funded the project to help analyse Martian soil).

Legacy

DENDRAL's lessons shaped MYCIN (Stanford's 1972 medical diagnosis system) and the entire 1980s expert-systems industry. The methodology it pioneered, knowledge elicitation from human experts, rule-based inference, separation of inference engine from knowledge base, became the template for hundreds of commercial expert systems in finance, manufacturing, configuration and logistics. The knowledge engineering bottleneck that the project exposed (rules are slow and expensive to elicit, brittle outside their narrow domain, and contradict each other when scaled) eventually contributed to the second AI winter of the late 1980s and motivated the shift to statistical learning that defines modern AI.

Feigenbaum received the 1994 Turing Award in part for the DENDRAL work, jointly with Raj Reddy.