Translation Rules with Right-Hand Side Lattices

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 577–588, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Translation Rules with Right-Hand Side Lattices Fabien Cromières Japan Science and Technology Agency Kawaguchi-shi Saitama 332-0012 fabien@pa.jst.jp Sadao Kurohashi Graduate School of Informatics Kyoto University Kyoto 606-8501 kuro@i.kyoto-u.ac.jp Abstract In Corpus-Based Machine Translation, the search space of the translation candidates for a given input sentence is often defined by a set of (cycle- free) context-free grammar rules. This happens naturally in Syntax-Based Machine Translation and Hierarchi- cal Phrase-Based Machine Translation (where the representation will be the set of the target-side half of the syn- chronous rules used to parse the input sentence). But it is also possible to describe Phrase-Based Machine Trans- lation in this framework. We propose a natural extension to this representa- tion by using lattice-rules that allow to easily encode an exponential num- ber of variations of each rules. We also demonstrate how the representation of the search space has an impact on de- coding efficiency, and how it is possible to optimize this representation. 1 Introduction A popular approach to modern Machine Translation is to decompose the translation problem into a modeling step and a search step. The modeling step will consist in defin- ing implicitly a set of possible translations T for each input sentence. Each translation in T being associated with a real-valued model score. The search step will then consist in find- ing the translation in T with the highest model score. The search is non-trivial because it is usually impossible to enumerate all members of T (its cardinality being typically exponen- tially dependent on the size of the sentence to be translated). Since at least (Chiang, 2007), a common way of representing T has been through a cycle-free context-free grammar. In such a grammar, T is represented as a set of context-free rules such as can be seen on fig- ure 1. These rules themselves can be gener- ated by the modeling step through the use of phrase tables, synchronous parsing, tree-to- string rules, etc. If the model score of each translation is taken to be the sum of rule scores independently given to each rule, the search for the optimal translation is easy with some classic dynamic programming techniques. However, if the model score is going to take into account informations such as the lan- guage model score of each sentence, it cannot be expressed in such a way. Since the lan- guage model score has proven empirically to be a very good source of information, (Chiang, 2007) proposed an approximate search algo- rithm called cube pruning. We propose here to represent T using context-free lattice-rules such as shown in fig- ure 2. This allows us to compactly encode a large number of rules. One benefit is that it adds flexibility to the modeling step, making it easier: many choices such as whether or not a function word should be included, the rela- tive position of …

Content truncated to 500 words