Fast Statistical Parsing with Parallel Multiple Context-Free Grammars

Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 368–376, Gothenburg, Sweden, April 26-30 2014. c⃝2014 Association for Computational Linguistics Fast Statistical Parsing with Parallel Multiple Context-Free Grammars Krasimir Angelov and Peter Ljungl¨of University of Gothenburg and Chalmers University of Technology G¨oteborg, Sweden krasimir@chalmers.se peter.ljunglof@cse.gu.se Abstract We present an algorithm for incremental statistical parsing with Parallel Multiple Context-Free Grammars (PMCFG). This is an extension of the algorithm by An- gelov (2009) to which we added statisti- cal ranking. We show that the new al- gorithm is several times faster than other statistical PMCFG parsing algorithms on real-sized grammars. At the same time the algorithm is more general since it supports non-binarized and non-linear grammars. We also show that if we make the search heuristics non-admissible, the pars- ing speed improves even further, at the risk of returning sub-optimal solutions. 1 Introduction In this paper we present an algorithm for incre- mental parsing using Parallel Multiple Context- Free Grammars (PMCFG) (Seki et al., 1991). This is a non context-free formalism allowing disconti- nuity and crossing dependencies, while remaining with polynomial parsing complexity. The algorithm is an extension of the algorithm by Angelov (2009; 2011) which adds statistical ranking. This is a top-down algorithm, shown by Ljungl¨of (2012) to be similar to other top-down al- gorithms (Burden and Ljungl¨of, 2005; Kanazawa, 2008; Kallmeyer and Maier, 2009). None of the other top-down algorithms are statistical. The only statistical PMCFG parsing algorithms (Kato et al., 2006; Kallmeyer and Maier, 2013; Maier et al., 2012) all use bottom-up parsing strategies. Furthermore, they require the gram- mar to be binarized and linear, which means that they only support linear context-free rewriting sys- tems (LCFRS). In contrast, our algorithm natu- rally supports the full power of PMCFG. By lift- ing these restrictions, we make it possible to ex- periment with novel grammar induction methods (Maier, 2013) and to use statistical disambiguation for hand-crafted grammars (Angelov, 2011). By extending the algorithm with a statistical model, we allow the parser to explore only parts of the search space, when only the most proba- ble parse tree is needed. Our cost estimation is similar to the estimation for the Viterbi probabil- ity as in Stolcke (1995), except that we have to take into account that our grammar is not context- free. The estimation is both admissible and mono- tonic (Klein and Manning, 2003) which guaran- tees that we always find a tree whose probability is the global maximum. We also describe a variant with a non- admissible estimation, which further improves the efficiency of the parser at the risk of returning a suboptimal parse tree. We start with a formal definition of a weighted PMCFG in Section 2, and we continue with a pre- sentation of our algorithm by means of a weighted deduction system in Section 3. In Section 4, we prove that our estimations are admissible and monotonic. In Section 5 we calculate an esti- mate for the minimal inside probability …

Content truncated to 500 words