Submodularity for Data Selection in Machine Translation

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 131–141, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Submodularity for Data Selection in Statistical Machine Translation Katrin Kirchhoff Department of Electrical Engineering University of Washington Seattle, WA, USA kk2@u.washington.edu Jeff Bilmes Department of Electrical Engineering University of Washington Seattle, WA, USA bilmes@u.washington.edu Abstract We introduce submodular optimization to the problem of training data subset selection for statistical machine translation (SMT). By explicitly formulating data selection as a submodular program, we ob- tain fast scalable selection algorithms with mathematical performance guarantees, re- sulting in a unified framework that clarifies existing approaches and also makes both new and many previous approaches easily accessible. We present a new class of submodular functions designed specifically for SMT and evaluate them on two differ- ent translation tasks. Our results show that our best submodular method significantly outperforms several baseline methods, including the widely-used cross-entropy based data selection method. In addition, our approach easily scales to large data sets and is applicable to other data selection problems in natural language processing. 1 Introduction SMT has made significant progress over the last decade, not least due to the availability of increas- ingly larger data sets. Large-scale SMT systems are now routinely trained on millions of sentences of parallel data, and billions of words of mono- lingual data for language modeling. Large data sets are often beneficial, but they do create certain other problems. First, they place higher demands on computational resources (storage and compute). Hence, existing software infrastructure may need to be adapted and optimized to handle such large data sets. Second, experimental turn-around time is increased as well, making it more difficult to quickly train, fine-tune, and evaluate novel model- ing approaches. Most importantly, however, SMT performance does not increase linearly with the training data size but levels off after a certain point. This is because the additional training data may be noisy, irrelevant to the task at hand, or inherently redundant. Thus, a linear increase in the amount of training data typically leads to a sublinear increase in performance, an effect known as diminishing returns. Several recent papers (Bloodgood and Callison-Burch, 2010; Turchi et al., 2012a; Turchi et al., 2012b) have amply demonstrated this effect. A way to counteract this is to perform data sub- set selection, i.e., choose a subset of the available training data to optimize a particular quality cri- terion. One scheme is to select a subset that ex- presses as much of the information in the original data set as possible - i.e., the data set should be “summarized” by excluding redundant information. Another scheme, popular in the context of SMT, is to subselect the original training set to match the properties of a particular test set. In this paper, we introduce submodularity for subselecting SMT training data, a methodology that follows both of the above schemes.1 Sub- modular functions (Fujishige, 2005) are a class of discrete set functions having the property of di- …

Content truncated to 500 words