Cube Pruning as Heuristic Search

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 62–71, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Cube Pruning as Heuristic Search Mark Hopkins and Greg Langmead Language Weaver, Inc. 4640 Admiralty Way, Suite 1210 Marina del Rey, CA 90292 {mhopkins,glangmead}@languageweaver.com Abstract Cube pruning is a fast inexact method for generating the items of a beam decoder. In this paper, we show that cube pruning is essentially equivalent to A* search on a specific search space with specific heuris- tics. We use this insight to develop faster and exact variants of cube pruning. 1 Introduction In recent years, an intense research focus on ma- chine translation (MT) has raised the quality of MT systems to the degree that they are now viable for a variety of real-world applications. Because of this, the research community has turned its at- tention to a major drawback of such systems: they are still quite slow. Recent years have seen a flurry of innovative techniques designed to tackle this problem. These include cube pruning (Chiang, 2007), cube growing (Huang and Chiang, 2007), early pruning (Moore and Quirk, 2007), clos- ing spans (Roark and Hollingshead, 2008; Roark and Hollingshead, 2009), coarse-to-fine methods (Petrov et al., 2008), pervasive laziness (Pust and Knight, 2009), and many more. This massive interest in speed is bringing rapid progress to the field, but it comes with a certain amount of baggage. Each technique brings its own terminology (from the cubes of (Chiang, 2007) to the lazy lists of (Pust and Knight, 2009)) into the mix. Often, it is not entirely clear why they work. Many apply only to specialized MT situ- ations. Without a deeper understanding of these methods, it is difficult for the practitioner to com- bine them and adapt them to new use cases. In this paper, we attempt to bring some clarity to the situation by taking a closer look at one of these existing methods. Specifically, we cast the popular technique of cube pruning (Chiang, 2007) in the well-understood terms of heuristic search (Pearl, 1984). We show that cube pruning is essen- tially equivalent to A* search on a specific search space with specific heuristics. This simple obser- vation affords a deeper insight into how and why cube pruning works. We show how this insight en- ables us to easily develop faster and exact variants of cube pruning for tree-to-string transducer-based MT (Galley et al., 2004; Galley et al., 2006; DeN- ero et al., 2009). 2 Motivating Example We begin by describing the problem that cube pruning addresses. Consider a synchronous context-free grammar (SCFG) that includes the following rules: A → ⟨A 0 B 1 , A 0 B 1 ⟩ (1) B → ⟨A 0 B 1 , B 1 A 0 ⟩ (2) A → ⟨B 0 A 1 , c B 0 b A 1 ⟩ (3) B → ⟨B 0 A 1 , B 0 A 1 ⟩ (4) Figure 1 shows CKY decoding in progress. CKY is …

Content truncated to 500 words