String Extension Learning

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 897–906, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics String Extension Learning Jeffrey Heinz University of Delaware Newark, Delaware, USA heinz@udel.edu Abstract This paper provides a unified, learning- theoretic analysis of several learnable classes of languages discussed previously in the literature. The analysis shows that for these classes an incremental, globally consistent, locally conservative, set-driven learner always exists. Additionally, the analysis provides a recipe for constructing new learnable classes. Potential applica- tions include learnable models for aspects of natural language and cognition. 1 Introduction The problem of generalizing from examples to patterns is an important one in linguistics and computer science. This paper shows that many disparate language classes, many previously dis- cussed in the literature, have a simple, natural and interesting (because non-enumerative) learner which exactly identifies the class in the limit from distribution-free, positive evidence in the sense of Gold (Gold, 1967).1 These learners are called String Extension Learners because each string in the language can be mapped (extended) to an ele- ment of the grammar, which in every case, is con- ceived as a finite set of elements. These learners have desirable properties: they are incremental, globally consistent, and locally conservative. Classes previously discussed in the litera- ture which are string extension learnable in- clude the Locally Testable (LT) languages, the Locally Testable Languages in the Strict Sense 1The allowance of negative evidence (Gold, 1967) or re- stricting the kinds of texts the learner is required to succeed on (i.e. non-distribution-free evidence) (Gold, 1967; Horn- ing, 1969; Angluin, 1988) admits the learnability of the class of recursively enumerable languages. Classes of languages learnable in the harder, distribution-free, positive-evidence- only settings are due to structural properties of the language classes that permit generalization (Angluin, 1980b; Blumer et al., 1989). That is the central interest here. (Strictly Local, SL) (McNaughton and Papert, 1971; Rogers and Pullum, to appear), the Piece- wise Testable (PT) languages (Simon, 1975), the Piecewise Testable languages in the Strict Sense (Strictly Piecewise, SP) (Rogers et al., 2009), the Strongly Testable languages (Beauquier and Pin, 1991), the Definite languages (Brzozowski, 1962), and the Finite languages, among others. To our knowledge, this is the first analysis which identi- fies the common structural elements of these lan- guage classes which allows them to be identifiable in the limit from positive data: each language class induces a natural partition over all logically possi- ble strings and each language in the class is the union of finitely many blocks of this partition. One consequence of this analysis is a recipe for constructing new learnable classes. One no- table case is the Strictly Piecewise (SP) languages, which was originally motivated for two reasons: the learnability properties discussed here and its ability to describe long-distance dependencies in natural language phonology (Heinz, 2007; Heinz, to appear). Later this class was discovered to have several independent characterizations and form the basis of another subregular hierarchy (Rogers et al., 2009). …

Content truncated to 500 words