This 1986 classic from the AAAI proceedings addresses a fundamental tension in machine learning: the representation that makes a concept easy to learn is rarely the same one that makes it easy to use. The authors introduce a "multiple representation strategy" and a system called Wyl that learns complex game concepts (like "traps" in checkers) by translating them into a functional space before compiling them back into a structural one.
The Representation Mismatch
In the mid-80s, researchers observed that if a system tried to learn a concept using the same language it used to perform a task, the learning process was often inefficient. For example, teaching a computer chess end-games using structural terms (piece positions) required hundreds of examples to learn a single concept.
The authors argue this is due to a "representation mismatch" between performance and learning:
- Performance tasks (e.g., recognizing a board state) require structural representations: where are the pieces, and what are their spatial relationships?
- Learning tasks require functional representations: what does this position do? Does it lead to a specific outcome, like a loss in three moves?
When a system is forced to learn a functional concept (like a "trap") using only structural terms, the resulting definition becomes a massive, disjunctive list of specific configurations. This causes the search space to explode, requiring vast amounts of data to narrow down.
The Wyl System: A Three-Stage Pipeline
To bridge this gap, the authors developed Wyl, a system that utilizes a three-stage pipeline to learn and then optimize concept representations:
- Envisionment (Structural to Functional): The system takes a structural board position (Environment Representation) and uses a minimax search to determine if it leads to known goals like "win" or "loss." It produces a functional "explanation tree" (Learning Representation) that describes why the position is a trap.
- Generalization: Wyl analyzes multiple functional trees to perform inductive inference. It employs a "no-coincidences" bias: if the same square or piece type appears in multiple parts of an explanation, it assumes that equality is a necessary part of the concept. This allows the system to generalize from very few examples.
- Compilation (Functional to Structural): To make the learned concept useful for fast recognition, Wyl translates the functional definition back into a structural one (Performance Representation). It generates possible board states fitting the functional definition and uses clustering algorithms to find simpler, more general structural descriptions (e.g., "a piece is two squares south of another").
Key Insights and Results
The paper evaluates this approach using checkers (learning "traps") and chess (learning "skewers" and "knight-forks"). Key findings include:
- Data Efficiency: Wyl demonstrated that by using the right representation, it could learn concepts from a handful of examples—sometimes as few as two—that previously required hundreds.
- Naturalness and Succinctness: Inductive learning is most effective when the concept description is succinct. By moving to a functional representation, a concept requiring 146 structural rules can be reduced to a single functional rule.
- Vocabulary Discovery: The system was able to "invent" its own descriptive terms, such as "NorthCenterSide" or "South2squares," to facilitate the description of learned concepts.
Limitations and Future Work
While powerful, the approach has notable drawbacks. The compilation process—generating all possible instances and clustering them—is computationally expensive. Learning a simple trap required several hours of CPU time on a VAX 11/750. Additionally, the system relies on a pre-existing hierarchy of goals (win, loss, survival) and cannot learn concepts outside its high-level functional understanding of the domain.
The authors suggest that "goal regression" (back-propagating constraints through game rules) would be a more efficient alternative to the generation-and-clustering approach for the compilation stage.
Summary updated