tailieunhanh - Báo cáo khoa học: "Polynomial Learnability and Locality of Formal Grammars"

We apply a complexity theoretic notion of feasible learnability called "polynomial learnabillty" to the evaluation of grammatical formalisms for linguistic description. We show that a novel, nontriviai constraint on the degree of ~locMity" of grammars allows not only context 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. | 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 learnability to the evaluation of grammatical formalisms for linguistic description. We show that a novel nontrivial constraint on the degree of locality of grammars allows not only context free languages but also a rich class of mildy context sensitive languages to be polynomially learnable. We discuss possible implications of this result to the theory of natural language acquisition. 1 Introduction Much of the formal modeling of natural language acquisition has been within the classic paradigm of identification in the limit from positive examples proposed by Gold 7 . A relatively restricted class of formal languages has been shown to be unlearnable in this sense and the problem of learning formal grammars has long been considered intractable. 1 The following two controversial aspects of this paradigm however leave the implications of these negative results to the computational theory of language acquisition inconclusive. First it places a very high demand on the accuracy of the learning that takes place - the hypothesized language must be exactly equal to the target language for it to be considered correct . Second it places a very permissive demand on the time and amount of data that may be requừed for the learning - all that is required of the learner is that it converge to the correct language in the Of the many alternative paradigms of learning proposed 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. 1Some interesting learnable .