Grouping Language Model Boundary Words to Speed K–Best Extraction from Hypergraphs

Proceedings of NAACL-HLT 2013, pages 958–968, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Grouping Language Model Boundary Words to Speed K–Best Extraction from Hypergraphs Kenneth Heafield∗,† Philipp Koehn∗ Alon Lavie† ∗ School of Informatics University of Edinburgh 10 Crichton Street Edinburgh EH8 9AB, UK pkoehn@inf.ed.ac.uk † Language Technologies Institute Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213, USA {heafield,alavie}@cs.cmu.edu Abstract We propose a new algorithm to approximately extract top-scoring hypotheses from a hyper- graph when the score includes an N–gram language model. In the popular cube prun- ing algorithm, every hypothesis is annotated with boundary words and permitted to recom- bine only if all boundary words are equal. However, many hypotheses share some, but not all, boundary words. We use these com- mon boundary words to group hypotheses and do so recursively, resulting in a tree of hy- potheses. This tree forms the basis for our new search algorithm that iteratively refines groups of boundary words on demand. Ma- chine translation experiments show our algo- rithm makes translation 1.50 to 3.51 times as fast as with cube pruning in common cases. 1 Introduction This work presents a new algorithm to search a packed data structure for high-scoring hypothe- ses when the score includes an N–gram language model. Many natural language processing systems have this sort of problem e.g. hypergraph search in hierarchical and syntactic machine translation (Mi et al., 2008; Klein and Manning, 2001), lat- tice rescoring in speech recognition, and confusion network decoding in optical character recognition (Tong and Evans, 1996). Large language models have been shown to improve quality, especially in machine translation (Brants et al., 2007; Koehn and Haddow, 2012). However, language models make search computationally expensive because they ex- amine surface words without regard to the structure at North Korea in North Korea with North Korea with the DPRK at   North Korea in with � the DPRK Figure 1: Hypotheses are grouped by common prefixes and suffixes. of the packed search space. Prior work, including cube pruning (Chiang, 2007), has largely treated the language model as a black box. Our new search algorithm groups hypotheses by common prefixes and suffixes, exploiting the tendency of the language model to score these hypotheses similarly. An exam- ple is shown in Figure 1. The result is a substantial improvement over the time-accuracy trade-off pre- sented by cube pruning. The search spaces mentioned in the previous para- graph are special cases of a directed acyclic hyper- graph. As used here, the difference from a nor- mal graph is that an edge can go from one vertex to any number of vertices; this number is the arity of the edge. Lattices and confusion networks are hypergraphs in which every edge happens to have arity one. We experiment with parsing-based ma- chine translation, where edges represent grammar rules that may have any number of non-terminals, including zero. Hypotheses are paths in the hypergraph scored by a linear combination of features. Many features are additive: they can …

Content truncated to 500 words