Version Space Approach to Learning Context-Free Grammars.

摘要

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. (rrh)