Abstract
Explanation-Based Learning (EBL) presents a fundamental paradox: if a system already possesses a complete definition of a concept, what is the purpose of "learning" it from examples? This paper argues that EBL is not about knowledge acquisition, but rather knowledge transformation. We define "operationality" as the bridge between abstract, functional definitions and concrete, usable descriptions. By introducing MetaLEX, we demonstrate a system that dynamically assesses operationality through experimental performance evaluation, moving beyond the brittle, human-defined constraints of traditional EBL.
Introduction: The Explanation-Based Paradox
In the late 1980s, Explanation-Based Learning (EBL) emerged as a powerful paradigm for learning from single instances. Unlike inductive methods that require large datasets, EBL systems use existing domain knowledge to "explain" why a specific instance belongs to a concept. However, this raises a theoretical challenge: if the system already knows the concept definition, it has nothing new to learn in a logical sense.
Richard Keller identifies that the value of EBL lies in operationalization. The goal is to transform a "non-operational" description—one that is correct but difficult for the performance system to evaluate—into an "operational" one that is efficient and usable. For example, a robot might know a cup is "an open, stable, liftable vessel," but it needs a description based on visual primitives like "cylinders" and "flat bottoms" to actually recognize one in the real world.
Defining Operationality
Keller proposes that operationality is not a fixed property of a language but a relationship between a description and a performance system. He breaks this down into two components:
- Usability: The ability of the performance system to evaluate the description using its available primitives and sensors.
- Utility: The degree to which the description improves the system's performance relative to specific goals, such as speed or accuracy.
As shown in Figure 1, the learning process involves searching the Description Space for a version of the concept (C) that maps effectively to the Instance Space while remaining within the "Operational" partition of the Description Space.
MetaLEX: Dynamic and Continuous Operationality
Traditional EBL systems often relied on a "compiled" or "static" definition of operationality, where a programmer pre-defined which features were "easy" to compute. Keller argues this approach is brittle; if the system's environment or hardware changes, the static definitions may no longer be optimal.
To address this, Keller developed MetaLEX, a successor to the LEX2 system. MetaLEX treats operationality as a search problem through a "description space" using a hill-climbing algorithm. Crucially, MetaLEX evaluates descriptions experimentally. It plugs a candidate description into a performance system (such as the SOLVER calculus engine) and measures the actual improvement on benchmark problems. This ensures that the learned knowledge is truly useful for the specific task at hand.
Comparative Analysis of EBL Systems
The paper categorizes several prominent AI systems based on their treatment of operationality along two axes: Granularity (binary vs. continuous) and Variability (static vs. dynamic).
As illustrated in Figure 2, most early systems like Winston's or GENESIS used binary, static definitions. MetaLEX stands out by offering a continuous measure of operationality (e.g., measuring speedup in CPU seconds) and a dynamic assessment that adapts to the current performance environment. This allows MetaLEX to guarantee performance improvements, whereas other systems might "learn" descriptions that actually slow them down.
Conclusion
The shift from knowledge acquisition to knowledge transformation is central to understanding EBL. By defining operationality through usability and utility, Keller provides a framework for building more robust and adaptive AI. While MetaLEX demonstrates the power of experimental evaluation, the high computational cost of running benchmarks remains a challenge. Future research should explore performance estimation techniques to predict the utility of descriptions without exhaustive testing.
Summary updated