Boosting-based Parse Reranking with Subtree Features

Proceedings of the 43rd Annual Meeting of the ACL, pages 189–196, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Boosting-based parse reranking with subtree features Taku Kudo ∗ Jun Suzuki Hideki Isozaki NTT Communication Science Laboratories. 2-4 Hikaridai, Seika-cho, Soraku, Kyoto, Japan {taku,jun,isozaki}@cslab.kecl.ntt.co.jp Abstract This paper introduces a new application of boost- ing for parse reranking. Several parsers have been proposed that utilize the all-subtrees representa- tion (e.g., tree kernel and data oriented parsing). This paper argues that such an all-subtrees repre- sentation is extremely redundant and a compara- ble accuracy can be achieved using just a small set of subtrees. We show how the boosting algo- rithm can be applied to the all-subtrees representa- tion and how it selects a small and relevant feature set efficiently. Two experiments on parse rerank- ing show that our method achieves comparable or even better performance than kernel methods and also improves the testing efficiency. 1 Introduction Recent work on statistical natural language pars- ing and tagging has explored discriminative tech- niques. One of the novel discriminative approaches is reranking, where discriminative machine learning algorithms are used to rerank the n-best outputs of generative or conditional parsers. The discrimina- tive reranking methods allow us to incorporate vari- ous kinds of features to distinguish the correct parse tree from all other candidates. With such feature design flexibility, it is non- trivial to employ an appropriate feature set that has a good discriminative ability for parse reranking. In early studies, feature sets were given heuristically by simply preparing task-dependent feature templates (Collins, 2000; Collins, 2002). These ad-hoc solu- tions might provide us with reasonable levels of per- ∗Currently, Google Japan Inc., taku@google.com formance. However, they are highly task dependent and require careful design to create the optimal fea- ture set for each task. Kernel methods offer an ele- gant solution to these problems. They can work on a potentially huge or even infinite number of features without a loss of generalization. The best known kernel for modeling a tree is the tree kernel (Collins and Duffy, 2002), which argues that a feature vec- tor is implicitly composed of the counts of subtrees. Although kernel methods are general and can cover almost all useful features, the set of subtrees that is used is extremely redundant. The main question ad- dressed in this paper concerns whether it is possible to achieve a comparable or even better accuracy us- ing just a small and non-redundant set of subtrees. In this paper, we present a new application of boosting for parse reranking. While tree kernel implicitly uses the all-subtrees representation, our boosting algorithm uses it explicitly. Although this set-up makes the feature space large, the l1-norm regularization achived by boosting automatically se- lects a small and relevant feature set. Such a small feature set is useful in practice, as it is interpretable and makes the parsing (reranking) time faster. We also incorporate a variant of the branch-and-bound technique to achieve efficient feature selection in each boosting iteration. 2 …

Content truncated to 500 words