Two monolingual parses are better than one (synchronous parse)

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 263–266, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Two monolingual parses are better than one (synchronous parse)∗ Chris Dyer UMIACS Laboratory for Computational Linguistics and Information Processing Department of Linguistics University of Maryland, College Park, MD 20742, USA redpony AT umd.edu Abstract We describe a synchronous parsing algorithm that is based on two successive monolingual parses of an input sentence pair. Although the worst-case complexity of this algorithm is and must be O(n6) for binary SCFGs, its average-case run-time is far better. We demonstrate that for a number of common synchronous parsing problems, the two-parse algorithm substantially outperforms alterna- tive synchronous parsing strategies, making it efficient enough to be utilized without resort- ing to a pruned search. 1 Introduction Synchronous context free grammars (SCFGs) gener- alize monolingual context-free grammars to gener- ate strings concurrently in pairs of languages (Lewis and Stearns, 1968) in much the same way that fi- nite state transducers (FSTs) generalize finite state automata (FSAs).1 Synchronous parsing is the prob- lem of finding the best derivation, or forest of deriva- tions, of a source and target sentence pair ⟨f, e⟩ under an SCFG, G.2 Solving this problem is necessary for several applications, for example, optimizing how well an SCFG translation model fits parallel train- ing data. Wu (1997) describes a bottom-up O(n6) synchronous parsing algorithm for ITGs, a binary SCFG with a restricted form. For general grammars, the situation is even worse: the problem has been shown to be NP-hard (Satta and Peserico, 2005). Even if we restrict ourselves to binary ITGs, the ∗This work was supported in part by the GALE program of DARPA, Contract No. HR0011-06-2-001. The author wishes to thank Philip Rensik, Adam Lopez, Phil Blunsom, and Jason Eisner for helpful discussions. 1SCFGs have enjoyed a resurgence in popularity as the for- mal basis for a number of statistical translation systems, e.g. Chiang (2007). However, translation requires only the manipu- lation of SCFGs using monolingual parsing algorithms. 2It is assumed that n = |f| ≈ |e|. O(n6) run-time makes large-scale learning applica- tions infeasible. The usual solution is to use a heuris- tic search that avoids exploring edges that are likely (but not guaranteed) to be low probability (Zhang et al., 2008; Haghighi et al., 2009). In this paper, we derive an alternative synchronous parsing algorithm starting from a conception of parsing with SCFGs as a composition of binary relations. This enables us to factor the synchronous parsing problem into two successive monolingual parses. Our algorithm runs more efficiently than O(n6) with many grammars (including those that required using heuristic search with other parsers), making it possible to take ad- vantage of synchronous parsing without developing search heuristics; and the SCFGs are not required to be in a normal form, making it possible to easily parse with more complex SCFG types. 2 Synchronous parsing Before presenting our algorithm, we review the O(n6) synchronous parser for …

Content truncated to 500 words