LEAP: A Learning Apprentice for VLSI Design

TL;DR

This paper introduces "Learning Apprentice Systems" (LAS), a new class of knowledge-based systems that learn by observing and analyzing user problem-solving steps. The authors present LEAP, a specific LAS for VLSI design, which learns new circuit implementation rules by generalizing from user-provided solutions. This approach aims to overcome the knowledge acquisition bottleneck in building expert systems.

What Problem Does This Paper Address?

Building effective knowledge-based systems (KBS) is often hindered by the "knowledge acquisition bottleneck." This refers to the immense effort required to create a complete and accurate knowledge base that enables high-level performance. Traditional methods involve manual knowledge engineering, which is time-consuming and expensive. While some tools exist to aid this process, machine learning has not yet significantly contributed to practical knowledge acquisition tools. This paper proposes a novel approach: systems that learn interactively from their users' direct problem-solving contributions, thereby automating the acquisition of new knowledge through experience.

Methods

The core of LEAP's approach lies in its ability to learn from user interactions within an existing VLSI design assistant called VEXED. When a user overrides VEXED's suggestions and manually refines a circuit design, LEAP captures this as a "training example." This example consists of:

  1. The function to be implemented: What the circuit module needs to do.
  2. The known characteristics of the input signals: Properties like data type, encoding, start time, and duration.
  3. The circuit entered by the user: The specific implementation provided.

LEAP then employs two key generalization methods:

  • Generalizing the Rule Left-Hand Side (LHS): LEAP uses its domain theory of digital circuits to "explain" why the user's circuit works for the given inputs. It then generalizes the preconditions of the rule by retaining only those signal features essential for this explanation to hold true in general. This identifies the broader class of input signals for which the user's circuit is valid.
  • Generalizing the Rule Right-Hand Side (RHS): This involves generalizing the circuit schematic itself. LEAP verifies that the user's circuit correctly implements the desired function. It then uses this verification process to identify a general class of circuits and functional specifications to which the same verification steps would apply. This is achieved through a "Verification-Based Learning" approach, where a sequence of algebraic transformations is used to show the equivalence between the composed specification of the user's circuit and the original specification.

Datasets

Not discussed in the paper. The paper focuses on the mechanism of learning from user interactions rather than pre-defined datasets. The "dataset" is implicitly generated through user interactions with the VEXED system during VLSI design tasks.

Key Insights and Ideas

  • Learning by Doing (and Observing): The most significant insight is the concept of a "Learning Apprentice System" that learns passively and interactively from users. This shifts the burden of knowledge acquisition from the knowledge engineer to the user, who is already engaged in problem-solving.
  • Overcoming the Knowledge Acquisition Bottleneck: By learning directly from user experience, LEAP offers a promising solution to the long-standing challenge of populating knowledge bases.
  • Analytical Generalization: LEAP's reliance on analytical methods (explaining why something works) for generalization, rather than purely empirical methods, allows it to learn from single examples and be more conservative about incorrect learning.
  • Separation of Concerns: The paper highlights the importance of separating "implementation rules" (what is possible) from "control knowledge" (what is preferred). This modularity simplifies learning and knowledge base maintenance.
  • Interactive Nature is Key: The interactive nature of the consultant is crucial, as it allows the system to collect training examples that are precisely targeted at its current knowledge gaps.

Key Results

The paper describes the design and methods of LEAP and its generalization capabilities. It presents examples of how LEAP infers generalized rules (Figures II-2 and II-3) from specific training examples. However, the paper does not present quantitative results such as performance improvements, accuracy metrics, or comparisons against other systems. The primary "result" is the demonstration of a viable methodology for learning new VLSI design rules through user interaction and analytical generalization.

Limitations and Future Work

  • Grain Size Mismatch: The authors acknowledge that users might think of larger "steps" than LEAP's individual rules. Handling these larger-grained training examples is an area for future research, potentially involving methods to decompose them into finer-grained inferences.
  • Domain Theory Dependency: Analytical generalization requires a domain theory (e.g., a theory for verifying circuit correctness). This limits the applicability of the current approach to domains where such a theory exists and is robust. For domains like medical diagnosis, where theories are less clear, empirical methods might be necessary.
  • Error-Prone Training Data: While LEAP's analytical approach is conservative and less prone to learning from errors, it might be insufficient if users make frequent mistakes. Future work may involve combining analytical and empirical learning methods.
  • Combining Learned Rules: When multiple copies of LEAP learn from different users, merging their rule sets could lead to redundancy. Methods for merging and reorganizing learned rules are needed.
  • Learning Control Knowledge: The current focus is on learning implementation rules. Learning control knowledge (when to use a rule) is identified as a more complex but important future direction.

Summary updated

Abstract

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.
BibTeX
@inproceedings{1985leap,
  title = {{LEAP: A Learning Apprentice for VLSI Design}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure