Left-to-Right Tree-to-String Decoding with Prediction

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1191–1200, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Left-to-Right Tree-to-String Decoding with Prediction Yang Feng† Yang Liu‡ Qun Liu⋆ Trevor Cohn† † Department of Computer Science The University of Sheffield, Sheffield, UK {y.feng, t.cohn}@sheffield.ac.uk ‡ State Key Laboratory on Intelligent Technology and Systems Tsinghua National Laboratory for Information Science and Technology Department of Computer Sci. and Tech., Tsinghua University, Beijing, China liuyang2011@tsinghua.edu.cn ⋆Key Laboratory of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences, Beijing, China liuqun@ict.ac.cn Abstract Decoding algorithms for syntax based ma- chine translation suffer from high compu- tational complexity, a consequence of in- tersecting a language model with a con- text free grammar. Left-to-right decoding, which generates the target string in order, can improve decoding efficiency by simpli- fying the language model evaluation. This paper presents a novel left to right decod- ing algorithm for tree-to-string translation, us- ing a bottom-up parsing strategy and dynamic future cost estimation for each partial trans- lation. Our method outperforms previously published tree-to-string decoders, including a competing left-to-right method. 1 Introduction In recent years there has been rapid progress in the development of tree-to-string models for statistical machine translation. These models use the syntac- tic parse tree of the source language to inform its translation, which allows the models to capture con- sistent syntactic transformations between the source and target languages, e.g., from subject-verb-object to subject-object-verb word orderings. Decoding al- gorithms for grammar-based translation seek to find the best string in the intersection between a weighted context free grammar (the translation mode, given a source string/tree) and a weighted finite state accep- tor (an n-gram language model). This intersection is problematic, as it results in an intractably large grammar, and makes exact search impossible. Most researchers have resorted to approximate search, typically beam search (Chiang, 2007). The decoder parses the source sentence, recording the target translations for each span.1 As the partial translation hypothesis grows, its component ngrams are scored and the hypothesis score is updated. This decoding method though is inefficient as it requires recording the language model context (n − 1 words) on the left and right edges of each chart cell. These contexts allow for boundary ngrams to be evaluated when the cell is used in another grammar produc- tion. In contrast, if the target string is generated in left-to-right order, then only one language model context is required, and the problem of language model evaluation is vastly simplified. In this paper, we develop a novel method of left- to-right decoding for tree-to-string translation using a shift-reduce parsing strategy. A central issue in any decoding algorithm is the technique used for pruning the search space. Our left-to-right decod- ing algorithm groups hypotheses, which cover the same number of source words, into a bin. Pruning requires the evaluation of different hypotheses in the same bin, and elimating the least promising options. As each hypotheses …

Content truncated to 500 words