Parsing to Learn Fine Grained Rules

AAAI 1988

TL;DR

This paper tackles the "grain size problem" in explanation-based learning (EBL) for circuit design. They introduce "synthetic parsing" to break down complex manual design steps into smaller, more generalizable rules, leading to improved coverage and reduced redundancy in learned design knowledge.

What Problem Does This Paper Address?

Explanation-based learning (EBL) systems, like LEAP in the VEXED circuit design tool, learn design rules by analyzing user-provided examples. A key challenge is determining the appropriate "grain size" of these learned rules. If rules are too coarse-grained, they may not be applicable in many situations, limiting their usefulness. Conversely, if they are too fine-grained, the system might require too many rules, making the design process inefficient. This paper focuses on the former issue: how to learn rules that are fine-grained enough to be broadly applicable and avoid redundancy, without sacrificing efficiency.

Methods

The core contribution is the introduction of synthetic parsing. This technique aims to decompose a manual design step (provided by a user) into a hierarchy of existing refinement rules and a new, yet-to-be-learned rule.

Here's how it works:

  1. Parsing: The system attempts to "parse" the manual refinement using its existing synthesis knowledge (refinement rules). This means finding a sequence of existing rules that can explain parts of the manual design.
  2. Identifying the Mismatch: Any part of the manual design that cannot be explained by existing rules is identified as the "unparsed portion."
  3. Synthetic Rule Creation: This unparsed portion is then generalized by LEAP (using its EBL capabilities) into a new, finer-grained refinement rule. This new rule essentially bridges the gap left by the existing rules.

This process is described as "synthetic parsing" because it allows the creation of new rules during the parsing process, rather than solely relying on pre-existing rules.

Datasets

Not discussed in the paper. The paper uses a specific circuit design example (a modified 2-to-1 multiplexer) to illustrate the technique, rather than a formal dataset.

Key Insights and Ideas

  • The "Grain Size Problem" is Crucial: The paper highlights that the granularity of learned rules directly impacts their practical utility. Coarse rules lead to limited applicability, while overly fine rules can lead to redundancy and inefficiency.
  • Synthetic Parsing as a Solution: By breaking down complex manual steps, synthetic parsing allows EBL systems to learn more specific, yet still generalizable, rules. This addresses the coverage and redundancy issues.
  • Shifting the Burden: Synthetic parsing effectively shares the burden of explanation between the system's analysis knowledge (EBL) and its synthesis knowledge (refinement rules). This can help overcome limitations in incomplete analysis theories.
  • Trade-off Management: The paper implicitly suggests a two-phase approach: Phase 1 (synthetic parsing) for learning fine-grained rules, and Phase 2 (rule composition) for creating larger-grained rules to improve efficiency.

Key Results

The paper demonstrates that synthetic parsing, when combined with LEAP, yields finer-grained rules compared to learning directly from the entire manual refinement. This leads to:

  • Improved Coverage: Learned rules are applicable in more situations (e.g., Rule 2 is applicable to Spec2 as well as Spec1).
  • Reduced Redundancy: The learned rules capture only the knowledge missing from existing rules, avoiding overlap.
  • Smaller Proof Trees: The verification and generalization steps for the newly learned, finer-grained rules are significantly smaller and less expensive.

Limitations and Future Work

  • Identifying "Good" Parse Trees: The current system generates multiple parse trees, and selecting the "best" one for learning a new rule is done manually. The authors suggest that heuristics for selecting good parse trees would be highly beneficial.
  • Sensitivity to Rule Order: The learning of a new rule can depend on the order in which existing rules are known. The authors suggest that factoring existing rules might help overcome this.
  • Efficiency of Parsing: While the focus is on learning finer-grained rules, the efficiency of the synthetic parsing process itself is not the primary concern in this prototype.
  • Future Work: The authors propose a two-phase approach: Phase 1 (synthetic parsing) for learning fine-grained rules, and Phase 2 for reorganizing these rules into larger macro-steps to improve performance efficiency.

Summary updated

BibTeX
@inproceedings{1988parsing,
  title = {{Parsing to Learn Fine Grained Rules}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure