A Comparison of Pruning Methods for CYK-based Decoding in Machine Translation_CWMT.pdf

A Comparison of Pruning Methods for CYK-based Decoding in Machine Translation YuZe Gao Natural Language Processing Lab Northeastern University yuze.gao@ Tong Xiao Natural Language Processing Lab Northeastern University xiaotong@ Abstract We present some popular pruning meth- ods for CYK-based decoding in machine translation, and describe the implementa- tion of them. Then, we provide the exper- imental results of these methods and the comparison of these results. In addition, we analyze each method in terms of de- coding speed and translation accuracy, based on which some possible optimiza- tions for each method are given. Lastly, we propose some novel pruning methods for CYK-based decoding. 1 Introduction In recent years, statistical machine translation (SMT) has been extensively investigated, show- ing state-of-the-art performance in many transla- tion tasks. In current SMT paradigm, a core step is to search for the best target string for the given source string, namely decoding. Several methods are available to implement SMT decod- ers. For instance, we can incrementally add tar- get words in a left-to-right fashion [Ortiz, 2003; Yang, 2010], or build translation hypotheses in a bottom-up fashion [Young, 1996]. One popular method is CYK-based decoding that originates from monolingual parsing [Cheppalier, 1998]. In CYK decoders, a partial hypothesis can be produced by the use of hypotheses generated on smaller segments/spans (Fig. 1). The algorithm starts with the smallest spans, and proceeds once it generates all possible hypotheses for a span. The final translation can be accessed when we finish the computation on the entire span. The brilliance of CYK-based decoding comes from its simplicity and from the natural manner in which one can build derivations using linguisti- cally-motivated grammars or formally syntactic rules. Therefore, it is widely used in hierarchical machine translation (MT) systems [Vilar,