Explanation-based learning (EBL) is a form of machine learning that exploits a very strong, or even perfect, domain theory - a formal theory of an application domain, akin to a domain model in ontology engineering - in order to make generalizations or form concepts from training examples. Unlike empirical methods that require many examples, EBL can generalize from a single example by using the domain theory to explain why the example is a member of a concept. This explanation is then compiled into a reusable rule, or macro, that speeds up future reasoning. EBL is also linked with encoding in memory to help with learning, as the derived generalizations are stored for efficient retrieval.
The approach is grounded in the idea that a complete domain theory contains, in principle, all information needed to decide any question about the domain. For instance, the rules of chess form a perfect domain theory for chess, allowing deduction of the best move in any position, though in practice this is intractable due to combinatorial explosion. EBL uses training examples to guide the search for deductive consequences, making the process efficient in practice.
Basic Formulation
An EBL system takes four inputs: a hypothesis space (the set of all possible conclusions), a domain theory (axioms about the domain of interest), training examples (specific facts that rule out some hypotheses), and operationality criteria (criteria for determining which features are efficiently recognizable, such as those directly detectable by sensors). The system works by finding a short proof of each training example from the domain theory, then generalizing that proof into a rule that can be applied to classify similar future examples quickly. This process extends the domain-theory database, enabling faster classification of related instances.
The main drawback of EBL is the utility problem, first analyzed by Minton: as the number of learned proof macros grows, the cost of applying them can outweigh their benefits. This issue has driven refinements in how learned rules are selected and used.
Application in Natural Language Processing
An especially good application domain for EBL is natural language processing (NLP). Here, a rich domain theory - such as a natural language grammar - is neither perfect nor complete but can be tuned to a particular application or language usage using a treebank as training examples. Rayner pioneered this work, and the first successful industrial application was to a commercial natural language interface to relational databases. The method has been successfully applied to several large-scale natural language parsing systems, where the utility problem was solved by omitting the original grammar (domain theory) and using specialized LR-parsing techniques, resulting in huge speed-ups at a cost in coverage but with a gain in disambiguation.
When applying EBL to NLP, operationality criteria can be hand-crafted or inferred from the treebank using either the entropy of its or-nodes or a target coverage/disambiguation trade-off (equivalent to recall/precision trade-off or f-score). EBL can also be used to compile grammar-based language models for speech recognition from general unification grammars. The utility problem was solved by discarding the original grammar, and the quoted articles tend to contain the phrase "grammar specialization" - quite the opposite of the original term "explanation-based generalization." Perhaps the best name for this technique would be data-driven search space reduction.
Other researchers who worked on EBL for NLP include Guenther Neumann, Aravind Joshi, Srinivas Bangalore, and Khalil Sima'an. EBL-like techniques have also been applied to surface generation, the converse of parsing.
Relationship to Other Learning Paradigms
EBL contrasts with empirical or inductive learning methods, such as those used in Machine learning and Deep learning, which require large datasets to generalize. While Neural network approaches like Transformer (architecture) models in Large language model systems learn statistical patterns from massive corpora, EBL leverages explicit symbolic knowledge. This makes EBL particularly suited for domains where a strong theory exists but data is scarce. However, EBL's reliance on a perfect or near-perfect domain theory limits its applicability to well-understood domains, whereas statistical methods can handle noisy or poorly understood problems.
In computer vision, EBL is related to one-shot learning, where a model learns from a single example, but EBL requires a domain theory to explain the example, whereas one-shot learning often uses prior knowledge from related tasks. Zero-shot learning, which classifies unseen categories without examples, also shares conceptual similarities but typically uses semantic embeddings rather than deductive proofs.
Limitations and Extensions
The primary limitation of EBL is the utility problem, where the overhead of storing and matching learned rules can degrade performance. Minton's analysis showed that the cost of applying learned proof macros can become prohibitive as they accumulate. Solutions include selective retention of useful rules, as seen in NLP applications that discard the original grammar. Extensions of EBL have explored combining it with inductive methods, such as using EBL to guide search in Curriculum Learning or to refine Data Augmentation strategies. In Artificial intelligence research, EBL has influenced work on explanation-based generalization in planning and diagnosis, though modern Generative AI systems rely primarily on statistical learning.
See Also
- One-shot learning in computer vision
- Zero-shot learning
- Machine learning
- Artificial intelligence