Better Binarization for the CKY Parsing

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 167–176, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Better Binarization for the CKY Parsing Xinying Song† ∗ Shilin Ding§ ∗ Chin-Yew Lin‡ †MOE-MS Key Laboratory of NLP and Speech, Harbin Institute of Technology, Harbin, China §Department of Statistics, University of Wisconsin-Madison, Madison, USA ‡Microsoft Research Asia, Beijing, China xysong@mtlab.hit.edu.cn dingsl@gmail.com cyl@microsoft.com Abstract We present a study on how grammar binariza- tion empirically affects the efficiency of the CKY parsing. We argue that binarizations af- fect parsing efficiency primarily by affecting the number of incomplete constituents gener- ated, and the effectiveness of binarization also depends on the nature of the input. We pro- pose a novel binarization method utilizing rich information learnt from training corpus. Ex- perimental results not only show that differ- ent binarizations have great impacts on pars- ing efficiency, but also confirm that our learnt binarization outperforms other existing meth- ods. Furthermore we show that it is feasible to combine existing parsing speed-up techniques with our binarization to achieve even better performance. 1 Introduction Binarization, which transforms an n-ary grammar into an equivalent binary grammar, is essential for achieving an O(n3) time complexity in the context- free grammar parsing. O(n3) tabular parsing al- gorithms, such as the CKY algorithm (Kasami, 1965; Younger, 1967), the GHR parser (Graham et al., 1980), the Earley algorithm (Earley, 1970) and the chart parsing algorithm (Kay, 1980; Klein and Manning, 2001) all convert their grammars into bi- nary branching forms, either explicitly or implicitly (Charniak et al., 1998). In fact, the number of all possible binarizations of a production with n + 1 symbols on its right ∗This work was done when Xinying Song and Shilin Ding were visiting students at Microsoft Research Asia. hand side is known to be the nth Catalan Number Cn = 1 n+1 �2n n � . All binarizations lead to the same parsing accuracy, but maybe different parsing effi- ciency, i.e. parsing speed. We are interested in in- vestigating whether and how binarizations will af- fect the efficiency of the CKY parsing. Do different binarizations lead to different pars- ing efficiency? Figure 1 gives an example to help answer this question. Figure 1(a) illustrates the cor- rect parse of the phrase “get the bag and go”. We assume that NP → NP CC NP is in the original grammar. The symbols enclosed in square brackets in the figure are intermediate symbols. VP VP VP VB NP CC VB VB NP CC VB get DT NN and go the bag (a) final parse VP VP[NP CC] VP VB NP CC VB get DT NN and go bag [VP CC] NP? NP? the (b) with left VP VP VP VB NP CC VB get DT NN and go bag [CC VP] the (c) with right Figure 1: Parsing with left and right binarization. If a left binarized grammar is used, see Fig- ure 1(b), an extra constituent [NP CC] spanning “the bag and” will be …

Content truncated to 500 words