Accession Number:

ADA218943

Title:

A Version Space Approach to Learning Context-Free Grammars

Descriptive Note:

Technical rept.

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA ARTIFICIAL INTELLIGENCE AND PSYCHOLOGY PROJECT

Personal Author(s):

Report Date:

1987-09-29

Pagination or Media Count:

40.0

Abstract:

In principal, the version space approach can be applied to any induction problem. However, in some cases the representation language for generalizations is so powerful that 1 some of the update functions for the version space are not effectively computable, and 2 the version space contains infinitely many generalizations. The class of context-free grammars is a simple representation that exhibits these problems. This paper presents an algorithm that solves these problems for context-free grammars. Given a sequence of strings, the algorithm incrementally constructs a data structure that has almost all the beneficial properties of a version space. The algorithm is fast enough to solve small induction problems completely, and it serves as a framework for biases that permit solving larger problems heuristically. The techniques used to develop the algorithm may be applied in constructing version spaces for representations e.g., production systems, Horn clauses, And-Or graphs that include context-free grammars as special cases.

Subject Categories:

  • Voice Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE