Verification-based Learning: A Generalized Strategy for Inferring Problem-Reduction Methods

Sridhar Mahadevan

Abstract

Verification-Based Learning (VBL) is a novel framework designed to enable AI systems to learn complex problem-solving strategies from a single expert example. By constructing a formal proof (verification) of why a specific solution is correct, the system distinguishes essential structural features from irrelevant noise. This analytical approach allows the system to justify its generalizations based on underlying domain theory rather than statistical correlations, facilitating the automatic acquisition of problem-reduction methods.

Introduction

Historically, building high-performance knowledge-based systems was a manual and laborious process. To create an expert system for tasks like circuit design or symbolic integration, human engineers had to manually encode thousands of specific rules. Early machine learning attempts often focused on state-space models—finding paths between states—but many engineering challenges are better framed as problem reduction: the process of decomposing a large goal into smaller, manageable subproblems.

This paper addresses the challenge of automating this decomposition. The author proposes a "Learning Apprentice" model, where a system learns new problem-reduction methods by observing a human expert solve a single problem instance.

The Verification-Based Learning (VBL) Method

Unlike empirical learning, which requires large datasets to identify patterns, VBL is an analytical technique that can generalize from a single instance. The process is structured into five key phases:

  1. Forming the Composed Specification: The system analyzes the expert's solution to determine what the combined subproblems achieve.
  2. Verification: Using a "domain theory"—a set of known primitive transformations like De-Morgan’s laws or mathematical identities—the system attempts to prove that the expert's solution satisfies the original goal.
  3. Constraint Backpropagation (CBP): Once a proof is established, the system propagates requirements backward through the proof steps to identify the most general conditions under which the proof remains valid.
  4. Generalization: Specific details of the training example (such as variable names or constants) are stripped away, leaving only the structural features necessary for the proof.
  5. Method Creation: This generalized template is saved as a new problem-reduction rule for future use.
Figure 1: A circuit specification illustrating the problem reduction approach where a goal is decomposed into sub-specifications.

Experimental Domains

The VBL strategy was evaluated across two distinct domains to demonstrate its versatility:

  • Digital Circuit Design: The system was tasked with learning how to implement logical expressions using NOR gates. Within the LEAP (Learning Apprentice) system, it observed specific implementations to infer general rules for boolean logic.
  • Symbolic Integration: The system learned the "Integral-of-a-Sum" rule by verifying it against its internal knowledge of differentiation rules, effectively "re-discovering" standard calculus identities.

Key Results and Insights

The paper demonstrates that VBL successfully extracts reusable methods from single examples. In the circuit design domain, the system observed a specific NOR-gate implementation and successfully inferred a general method for implementing any conjunction of two boolean expressions.

Figure 2: A specific NOR-gate implementation of a boolean expression used as a training instance for the VBL system.

Several key insights emerged from this research:

  • Justifiable Generalization: VBL creates rules it can "prove," making the learned knowledge more robust and explainable than empirical methods that might overfit to coincidental data patterns.
  • Leveraging Domain Theory: The system does not learn from scratch; it uses existing low-level knowledge to "explain" high-level expert maneuvers.
  • Search Space Pruning: By using an expert example to guide the proof process, the system avoids the combinatorial explosion inherent in searching for proofs for every possible generalization.

Limitations and Future Work

Despite its success, VBL has notable dependencies. It is only as effective as the system's underlying domain theory; without the basic building blocks to verify a solution, the system cannot learn. This limits its application in "weak" domains like medicine or geology where formal theories are incomplete.

Furthermore, while VBL ensures correctness, it does not inherently guarantee efficiency. Future work is required to help systems distinguish between a correct solution and the optimal solution. Additionally, the current implementation of Constraint Backpropagation struggles with complex disjunctive ("OR") conditions, which can lead to exponential complexity in learned rules. Integrating goal-directed learning may help prune these inefficient paths in the future.

Summary updated

BibTeX
@inproceedings{mahadevan1985verification,
  author = {Sridhar Mahadevan},
  title = {{Verification-based Learning: A Generalized Strategy for Inferring Problem-Reduction Methods}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1985},
}
Figure