tailieunhanh - Báo cáo khoa học: "Inducing Combinatory Categorial Grammars with Genetic Algorithms"

This paper proposes a novel approach to the induction of Combinatory Categorial Grammars (CCGs) by their potential affinity with the Genetic Algorithms (GAs). Specifically, CCGs utilize a rich yet compact notation for lexical categories, which combine with relatively few grammatical rules, presumed universal. Thus, the search for a CCG consists in large part in a search for the appropriate categories for the data-set’s lexical items. We present and evaluates a system utilizing a simple GA to successively search and improve on such assignments. . | Inducing Combinatory Categorial Grammars with Genetic Algorithms Elias Ponvert Department of Linguistics University of Texas at Austin 1 University Station B5100 Austin TX 78712-0198 USA ponvert@ Abstract This paper proposes a novel approach to the induction of Combinatory Categorial Grammars CCGs by their potential affinity with the Genetic Algorithms GAs . Specifically CCGs utilize a rich yet compact notation for lexical categories which combine with relatively few grammatical rules presumed universal. Thus the search for a CCG consists in large part in a search for the appropriate categories for the data-set s lexical items. We present and evaluates a system utilizing a simple GA to successively search and improve on such assignments. The fitness of categorial-assignments is approximated by the coverage of the resulting grammar on the data-set itself and candidate solutions are updated via the standard GA techniques of reproduction crossover and mutation. 1 Introduction The discovery of grammars from unannotated material is an important problem which has received much recent research. We propose a novel approach to this effort by leveraging the theoretical insights of Combinatory Categorial Grammars CCG Steedman 2000 and their potential affinity with Genetic Algorithms GA Goldberg 1989 . Specifically CCGs utilize an extremely small set of grammatical rules presumed near-universal which operate over a rich set of grammatical categories which are themselves simple and straightforward data structures. A search for a CCG grammar for a language can be construed as a search for accurate category assignments to the words of that language albeit over a large landscape of potential solutions. GAs are biologically-inspired general purpose search optimization methods that have succeeded in these kinds of environments wherein solutions are straightforwardly coded yet nevertheless the solution space is complex and difficult. We evaluate a system that uses a GA