title:
Using Decision Trees to Construct a Practical Parser

authors:
Masahiko Haruno
mharuno@hip.atr.co.jp
Satoshi Shirai
shirai@cslab.kecl.ntt.co.jp
Yoshifumi Ooyama
ooyama@cslab.kecl.ntt.co.jp
Hiroshi Aizawa
aizawa@subaru.co.jp

abstract:
  This paper describes a novel and practical Japanese parser
  that uses decision trees. First, we construct a single decision tree
  to estimate modification 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 constructed parsers are evaluated using
  the EDR Japanese annotated corpus.  The single-tree method
  significantly outperforms the conventional Japanese stochastic
  methods.  Moreover, the boosted version of the parser is shown to
  have great advantages; 1) a better parsing accuracy than its
  single-tree counterpart for any amount of training data and 2) no
  over-fitting to data for various iterations. The presented parser,
  the first non-English stochastic parser with practical performance,
  should tighten the coupling between natural language processing and
  machine learning

keywords:
Stochastic parsing, Decision tree,Boosting, Dependency grammar, Corpus linguistics