Polynomial Learnability and Locality of Formal Grammars

Polynomial Learnability and Locality of Formal Grammars Naoki Abe* Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA19104. ABSTRACT We apply a complexity theoretic notion of feasible learnability called "polynomial learnabillty" to the eval- uation of grammatical formalisms for linguistic descrip- tion. We show that a novel, nontriviai constraint on the degree of ~locMity" of grammars allows not only con- text free languages but also a rich d~s of mildy context sensitive languages to be polynomiaily learnable. We discuss possible implications, of this result t O the theory of naturai language acquisition. 1 Introduction Much of the formai modeling of natural language acqui- sition has been within the classic paradigm of ~identi- fication in the limit from positive examples" proposed by Gold [7]. A relatively restricted class of formal lan- guages has been shown to be unleaxnable in this sense, and the problem of learning formal grammars has long been considered intractable. 1 The following two contro- versiai aspects of this paradigm, however, leave the im- plications of these negative results to the computational theory of language acquisition inconclusive. First, it places a very high demand on the accuracy of the learn- ing that takes place - the hypothesized language must be exactly equal to the target language for it to be con- sidered "correct". Second, it places a very permissive demand on the time and amount of data that may be required for the learning - all that is required of the learner is that it converge to the correct language in the limit. 2 Of the many alternative paradigms of learning pro- posed, the notion of "polynomial learnability ~ recently formulated by Blumer et al. [6] is of particular interest because it addresses both of these problems in a unified "Supported by an IBM graduate fellowship. The author gratefully acknowledges his advisor, Scott Weinstein, for his guidance and encouragement throughout this research. 1 Some interesting learnable subclasses of regu languages have been discovered and studied by Angluin [3]. lar 2For a comprehensive survey of various paradigms related to "identification in the limit" that have been proposed to address the first issue, see Osheraon, Stob and Weinstein [12]. As for the latter issue, Angluin ([5], [4]) investigates the feasible learnabil- ity of formal languages with the use of powerful oracles such as "MEMBERSHIP" and "EQUIVALENCE". way. This paradigm relaxes the criterion for learning by ruling a class of languages to be learnable, if each lan- guage in the class can be approximated, given only pos- itive and negative examples, a with a desired degree of accuracy and with a desired degree of robustness (prob- ability), but puts a higher demand on the complexity by requiring that the learner converge in time polyno- mini in these parameters (of accuracy and robustness) as well as the size (complexity) of the language being learned. In this paper, we apply the criterion of polynomial learnability to subclasses of formal grammars that are of considerable linguistic interest. Specifically, we present a novel, …

Content truncated to 500 words