Using Decision Trees to Construct a Practical Parser

Using Decision Trees to Construct a Practical Parser Masahiko Haruno* Satoshi Shirai t Yoshifumi Ooyamai mh aruno({i'ldl).at.r.co.jt) sld rai'(i'cs]al).k(~cl.n|,t.co.jl) ooyal na.(.~}csla I).kccl.nl, t..co.j p * A'I'I{ lhtma.n In retina.lion I'roccssing Research Laboratories 9_9 llikaridai, S '~d~a.-cho, Soraku-gun, Kyol;o 619-02, Japan *NTT Communication Science l,aboratories 2-4 ltika.ridai, S Aka-(ho, Soraku-gun, Kyoto 619-02, 3apan. Abstract This l)al)er describes novel and practical .lal)anesc parsers that uses decision trees, l"irst, we COl> struct a single, decision tree to estimate modifica-- lion probabilities; how one phrase tends t.o modify another. Next, we introduce a boosting algorithm in which several decision t.rees are COllst.ructed and then combined for probalfility estiinat.ion. 'lThe two constructed parsers are evalua.ted I)y using the El)t{ .Japanese annotated corpus. The single-tree method outperforlns the conventional Japanese stochastic reel.hods by 4%. Moreover, the boosting version is shown to h;we significant adwmtages; 1 ) better pars- ing accuracy than ils single-tree counl.erparl for any alnoullt o[" training data and 2) no over-titling 1o data. for va.rious iterations. 1 Introduction Conventional parsers with practical levels of per for mance require a number of sophisticated rules that. haw" to be hand-crafted by human linguists. It is time-consuming and cumbersome to mainl.ahl tltese rules for two reasons. * The rules are specific to the application domain. * Specific rules handling collocat.ional expressions create side effects. Such rules often deteriorate the overall performance of the parser. q'he stochastic approach, on the other hand, has the potential to overcome these difficulties. Because il induces stochastic rules to maximize ow~'ra.ll per- ['onnance against t.raining data, it. llOf Ollly adapts to any application domain but also may avoid ow>r- fitting to the data. In the late 80s and early 90s, lhe induction and parameter estimation of l)robabilis - tie context, free grammars (PCF(',s) from corpora were intensively studied, la;ecause 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 broa.der range of information, in lmrticular lexical in- forinatiolq was tbund to be essential in disambiguat- ing the syntactic structures of real-world sentences. SI'ATTEt{ (Magerman, 1995) augmented the pure I'(:I"G by introducing a. mnnl)er of lexical at.tributes. The parser controlled applications of each rule by us- ing the lexical constraints induced by decision tree algorithnl (Quinlan, 1993). rFhe SI)N]'TEt{ parser attained 87% accuracy and first made stochastic parsers a practical choice. The other type of high- precision parser, which is based on dependency ana[- 5'sis was introduced by Collins (Collins, 1996). l)e- pendency a.mdysis first, segments a sentence into syn- tactically meaningful sequences of words and then considers the modificatioll of each segment. Collins" parser computes the likelihood that each segment modifies the other (2 term relation) by using large corpora. These moditication probabilities are con- ditioned by head words of two S{"glnelltS, distance between the two segments and otlmr syntactic %a- tures. Although these two parsers have showll silni- lar performance, the keys of their success are slight ly diflk~renl.. SPA'[.'TER parser perforlnanee greatly de- pelldS on the …

Content truncated to 500 words