Best Analysis Selection in Inflectional Languages

Best Analysis Selection in Inflectional Languages Aleˇs Hor´ak and Pavel Smrˇz Faculty of Informatics, Masaryk University Brno Botanick´a 68a, 602 00 Brno, Czech Republic E-mail: {hales,smrz}@fi.muni.cz Abstract Ambiguity is the fundamental property of natural language. Perhaps, the most bur- densome case of ambiguity manifests itself on the syntactic level of analysis. In order to face up to the high number of obtained derivation trees, this paper describes several techniques for evaluation of the figures of merit, which define a sort order on parsing trees. The presented methods are based on language specific features of synthetical lan- guages and they improve the results of sim- ple stochastic approaches. 1 Introduction Ambiguity on all levels of representation is an inherent property of natural languages and it also forms a central problem of natu- ral language parsing. A consequence of the natural language ambiguity is a high num- ber of possible outputs of a parser that are usually represented by labeled trees. The av- erage number of parsing trees per input sen- tence strongly depends on the background grammar and thence on the language. There are natural language grammars producing at most hundreds or thousands of parsing trees but also highly ambiguous grammar systems producing enormous number of re- sults. For example, a grammar extracted from the Penn Treebank and tested on a set of sentences randomly generated from a probabilistic version of the grammar has on average 7.2×1027 parses per sentence accord- ing to Moore’s work (Moore, 2000). Such a mammoth extent of result is also no excep- tion in parsing of Czech (Smrˇz and Hor´ak, 2000) (see Fig. 1) due to free word order and Figure 1: The dependence of number of re- sulting analysis on the number of words in the input sentence rich morphology of word forms whose gram- matical case cannot often be unambiguously determined. A traditional solution for these problems is presented by probabilistic parsing tech- niques (Bunt and Nijholt, 2000) aiming at finding the most probable parse of a given input sentence. This methodology is usually based on the relative frequencies of occur- rences of the possible relations in a repre- sentative corpus. “Best” trees are judged by a probabilistic figure of merit (FOM). The term “figure of merit” is usually used to refer to a function that prunes implausi- ble partial analyses during parsing. In this paper, we rather take figure of merit as a measure bounding the true probabilities of the complete parses. S ��� HH H NP1 �� H H AP ���� HHH H ADJ and ADJ N1 V NP4 �� H H ADJ NP4 �� H H N4 N2 −→ selected trigrams: [ADJ,and,ADJ] [ADJ,N1,V] [N1,V,N4] [V,ADJ,N4] [ADJ,N4,N2] Figure 2: Lexical heads as n-gram’s elements. The standard methods of the best analy- sis selection (Caraballo and Charniak, 1998) usually use simple stochastic functions inde- pendent on the peculiarities of the underly- ing language. This approach seems to work satisfactorily in case of analytical languages. On the other hand, the obstacles brought by the …

Content truncated to 500 words