In Statistical Machine Translation (SMT), the prevailing wisdom has long been that "more data is better." However, as datasets reach billions of words, researchers have observed a "data ceiling" where performance gains level off despite massive increases in training volume. This paper by Kirchhoff and Bilmes (2014) introduces submodularity as a rigorous mathematical framework to address this, demonstrating that a carefully selected 10% of data can actually outperform the full dataset.
The Challenge of Big Data in SMT
Training state-of-the-art SMT systems on massive parallel corpora presents several significant hurdles:
- Resource Constraints: Massive storage and compute requirements for training and tuning.
- Slow Iteration: Long turnaround times for experiments hinder research progress.
- Redundancy and Noise: Adding more data often introduces redundant information or domain-irrelevant noise that can degrade translation quality.
Traditional selection methods, such as cross-entropy (Xent), evaluate sentences in isolation. This often leads to the selection of highly relevant but redundant sentences, wasting the training budget on information already captured. The authors propose a method that considers the interaction between selected sentences to ensure both relevance and diversity.
Submodularity: Modeling Diminishing Returns
The core innovation is framing data selection as a submodular optimization problem. A function is submodular if it satisfies the property of diminishing returns: the incremental gain of adding an element to a set decreases as the set grows larger.
In the context of SMT, this means that once a specific linguistic feature (like an n-gram) is well-represented in the training subset, adding more sentences containing that same feature provides less value. This naturally encourages diversity in the selected data.
Optimization and Function Design
While submodular optimization is generally NP-hard, a simple greedy algorithm—repeatedly selecting the element with the highest incremental gain—is guaranteed to achieve at least 63% of the optimal solution. The authors utilized an accelerated version of this algorithm capable of processing millions of sentences in minutes.
They designed a class of "feature-based" submodular functions defined as: $$f(X) = \sum_{u \in U} w_u \phi(m_u(X))$$ Where $U$ is the set of features (n-grams), $m_u(X)$ is a relevance score, and $\phi$ is a concave function (like square root or log) that acts as the "diminishing returns" engine. The authors explored several variations of these parameters to find the optimal balance for translation tasks.
Experimental Results
The approach was evaluated on two tasks: NIST Arabic-English (189M words) and Europarl German-English (52.8M words). Key findings include:
- Efficiency Gains: On the NIST task, the submodular method SM-6 (defined in the table above) using only 10% of the data achieved a BLEU score of 0.4302, significantly outperforming the system trained on 100% of the data (0.4257).
- Superior Baselines: Submodular selection consistently outperformed the industry-standard cross-entropy method across various subset sizes.
- Concavity Matters: The square root function was found to be more effective than the log function as it decays more gradually, allowing for a better balance between covering new features and reinforcing existing ones.
Conclusion
By formalizing data selection through submodularity, Kirchhoff and Bilmes provide a theoretical foundation for what was previously handled by heuristics. Their work proves that intelligent data selection not only saves computational resources but can actually lead to superior translation performance by focusing on diversity and relevance while actively penalizing redundancy.
Summary updated