Using Decision Trees to Construct a Practical Parser

Using Decision Trees to Construct a Practical Parser Masahiko Haruno* Satoshi Shirai t Yoshifumi Ooyama t mharuno ~hlp.atr.co.jp shirai,~cslab.kecl.ntt.co.jp oovama~cslal).kecl.nt t.co.j p *ATR Human Information Processing Research Laboratories 2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02, Japan. tNTT Communication Science Laboratories 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02, Japan. Abstract This paper describes novel and practical Japanese parsers that uses decision trees. First, we con- struct a single decision tree to estimate modifica- tion probabilities; how one phrase tends to modify another. Next, we introduce a boosting algorithm in which several decision trees are constructed and then combined for probability estimation. The two constructed parsers are evaluated by using the EDR Japanese annotated corpus. The single-tree method outperforms the conventional .Japanese stochastic methods by 4%. Moreover, the boosting version is shown to have significant advantages; 1) better pars- ing accuracy than its single-tree counterpart for any amount of training data and 2) no over-fitting to data for various iterations. 1 Introduction Conventional parsers with practical levels of perfor- mance require a number of sophisticated rules that have to be hand-crafted by human linguists. It is time-consunaing and cumbersome to naaintain these rules for two reasons. • The rules are specific to the application domain. • Specific rules handling collocational expressions create side effects. Such rules often deteriorate t, he overall performance of the parser. The stochastic approach, on the other hand, has the potential to overcome these difficulties. Because it. induces stochastic rules to maximize overall per- formance against training data, it not only adapts to any application domain but. also may avoid over- fitting to the data. In the late 80s and early 90s, the induction and parameter estimation of probabilis- tic context free grammars (PCFGs) from corpora were intensively studied. Because these grammars comprise only nonterminal and part-of-speech tag symbols, their performances were not enough to be used in practical applications (Charniak, 1993). A broader range of information, in particular lexical in- formation, was found to be essential in disambiguat- ing the syntactic structures of real-world sentences. SPATTER (Magerman, 1995) augmented the pure PCFG by introducing a number of lexical attributes. The parser controlled applications of each rule by us- ing the lexical constraints induced by decision tree algorithm (Quinlan, 1993). The SPATTER parser attained 87% accuracy and first made stochastic parsers a practical choice. The other type of high- precision parser, which is based on dependency anal- ysis was introduced by Collins (Collins, 1996). De- pendency analysis first segments a sentence into syn- tactically meaningful sequences of words and then considers the modification of each segment. Collins' parser computes the likelihood that each segment modifies the other (2 term relation) by using large corpora. These modification probabilities are con- ditioned by head words of two segments, distance between the two segments and other syntactic fea- tures. Although these two parsers have shown simi- lar performance, the keys of their success are slightly different. SPATTER parser performance greatly de- pends on the feature selection ability of the decision tree algorithm rather …

Content truncated to 500 words