Abstract
It is by now well recognized that a major impediment to developing knowledge-based systems is the knowledge-acquisition bottleneck: The task of building up a complete enough and correct enough knowledge base to provide high-level performance. This chapter proposes a new class of knowledge-based systems designed to address this knowledge-acquisition bottleneck by incorporating a learning component to acquire new knowledge through experience. In particular, we define learning apprentice systems as the class of interactive, knowledge-based consultants that directly assimilate new knowledge by observing and analyzing the problem-solving steps contributed by their users through their normal use of the system. This chapter describes a specific learning apprentice system, called LEAP, which is currently being developed in the domain of VLSI design. We also discuss design issues for learning apprentice systems more generally, as well as restrictions on the generality of our current approach.
Introduction
In the mid-1980s, the development of expert systems was hindered by the "knowledge acquisition bottleneck." Building these systems required knowledge engineers to manually extract and code rules from human experts—a process that was notoriously slow and prone to incompleteness. LEAP (Learning Apprentice), developed at Rutgers University, was designed to overcome this by learning directly from human designers during their routine work.
The LEAP Framework
LEAP functions as an extension of VEXED, an interactive VLSI design consultant. Unlike traditional machine learning systems of the era that required separate training phases and massive datasets, LEAP learns "on the job."
The learning process is triggered when a user overrides a suggestion from VEXED. If the user manually implements a circuit component, LEAP treats this as a training example. This example includes the functional specification, input signal characteristics, and the user's specific circuit topology.
Methodology: Analytic Generalization
The core of LEAP's intelligence lies in its ability to generalize from a single example. It employs a "domain theory" of digital circuits to verify and abstract the user's contribution through two primary mechanisms:
- LHS Generalization: Using the CRITTER tool, LEAP propagates constraints (such as timing and signal encoding) to determine the most general conditions under which the design remains valid.
- RHS Generalization: Through Verification-Based Learning, the system uses algebraic transformations to prove that the circuit matches the specification. It then abstracts specific components into general functional blocks.
Key Insights and Results
- Learning in Context: LEAP eliminates the distinction between "working" and "learning" modes, acquiring knowledge during normal use.
- Single-Example Learning: By leveraging domain theory, LEAP can produce robust, justifiable rules from one instance, contrasting with the statistical requirements of empirical learning.
- Knowledge Partitioning: The system separates implementation knowledge (how to build) from control knowledge (which design is better), simplifying maintenance of the knowledge base.
The paper demonstrates that LEAP can successfully take a specific user implementation—such as a circuit using NOR gates to compute a boolean product of sums—and generalize it into a reusable rule. It successfully generalized specific signal timings into general constraints and allowed the system to "re-discover" design tactics previously uncatalogued in its rule base.
Limitations and Future Work
LEAP’s effectiveness is tied to the completeness of its domain theory. In fields where the underlying logic is less understood, this analytic approach would be limited. Furthermore, while LEAP learns how to implement designs, learning preferences (e.g., optimizing for power vs. area) remains a significant challenge. The authors also noted that as different users contribute rules, the system risks becoming a disorganized collection of redundant logic, requiring future work on rule merging and reorganization.
Summary updated