Optimizing the Computational Lexicalization of Large Grammars

OPTIMIZING THE COMPUTATIONAL LEXICALIZATION OF LARGE GRAMMARS Christian JACQUEMIN Institut de Recherche en Informatique de Nantes (IR/N) IUT de Nantes - 3, rue du MarEchal Joffre F-441M1 NANTES Cedex 01 - FRANCE a--mail : jaequemin@ irin.iut-nantas.univ-nantas.fr Abstract The computational lexicalization of a grammar is the optimization of the links between lexicalized rules and lexical items in order to improve the quality of the bottom-up filtering during parsing. This problem is N P-complete and untractable on large grammars. An approximation algorithm is presented. The quality of the suboptimal solution is evaluated on real-world grammars as well as on randomly generated ones. Introduction Lexicalized grammar formalisms and more specifically Lexicalized Tree Adjoining Grammars (LTAGs) give a lexical account of phenomena which cannot be considered as purely syntactic (Schabes et al, 1990). A formalism is said to be lexicalized if it is composed of structures or rules associated with each lexical item and operations to derive new structures from these elementary ones. The choice of the lexical anchor of a rule is supposed to be determined on purely linguistic grounds. This is the linguistic side of lexicalization which links to each lexical head a set of minimal and complete structures. But lexicalization also has a computational aspect because parsing algorithms for lexicalized grammars can take advantage of lexical links through a two-step strategy (Schabes and Joshi, 1990). The first step is the selection of the set of rules or elementary structures associated with the lexical items in the input sentence ~. In the second step, the parser uses the rules filtered by the first step. The two kinds of anchors corresponding to these two aspects of lexicalization can be • considered separately : The linguistic anchors are used to access the grammar, update the data, gather together items with similar structures, organize the grammar into a hierarchy... • The computational anchors are used to select the relevant rules during the first step of parsing and to improve computational and conceptual tractability of the parsing algorithm. Unlike linguistic lexicalization, computational anchoring concerns any of the lexical items found in a rule and is only motivated by the quality of the induced filtering. For example, the systematic linguistic anchoring of the rules describing "Nmetal alloy" to their head noun "alloy" should be avoided and replaced by a more distributed lexicalization. Then, only a few rules "Nmetal alloy" will be activated when encountering the word "alloy" in the input. In this paper, we investigate the problem of the optimization of computational lexicalization. We study how to choose the computational anchors of a lexicalized grammar so that the distribution of the rules on to the lexical items is the most uniform possible The computational anchor of a rule should not be optional (viz included in a disjunction) to make sure that it will be encountered in any string derived from this rule. 196 with respect to rule weights. Although introduced with reference to LTAGs, this optimization concerns any portion of a grammar where rules include one or …

Content truncated to 500 words