Minimum Sample Risk Methods for Language Modeling

Jianfeng Gao, Hao Yu, Wei Yuan, Peng XuEMNLP 2005 · OpenReview

Abstract

This paper proposes a new discriminative training method, called minimum sample risk (MSR), for estimating parameters of language models in text input tasks. Unlike traditional discriminative methods that rely on differentiable "proxy" loss functions, MSR minimizes the training error directly using a heuristic training procedure. Evaluations on Japanese text input tasks demonstrate that MSR can handle large feature sets and training samples, significantly outperforming regular trigram models trained via maximum likelihood estimation (MLE) and surpassing widely applied discriminative methods like Boosting and Perceptron.

Introduction

Standard Language Modeling (LM) typically relies on Maximum Likelihood Estimation (MLE), which maximizes the probability of training data. However, MLE assumes the model structure perfectly captures the true data distribution—an assumption rarely met in practice. Discriminative training offers a more robust alternative by focusing on error minimization.

The primary challenge in discriminative training is that the actual error rate (e.g., character error rate) is a non-differentiable step function. Most existing methods circumvent this by optimizing smooth "proxy" loss functions. This paper argues that such approximations are sub-optimal and proposes Minimum Sample Risk (MSR) to optimize the true error rate directly.

The Minimum Sample Risk (MSR) Approach

MSR treats the error rate as a multidimensional function to be optimized through a heuristic, iterative process.

Instead of gradient descent, MSR employs a modified grid line search. It iterates through features, adjusting parameters to find local minima in the "staircase" error function. To prevent the search from becoming trapped in unstable, narrow local minima, the authors introduce a "smoothed sample risk" function to guide the optimization.

The step-function nature of sample risk and the application of smoothed sample risk to navigate local minima.

Feature Selection

To manage the computational complexity of millions of potential n-gram features, MSR uses a two-stage selection process. Features are first ranked by their individual error reduction potential. Subsequently, a cross-correlation filter is applied to ensure the selection of a diverse and complementary feature set, enhancing model robustness and generalization.

Experimental Evaluation

The MSR method was evaluated on a Japanese Input Method Editor (IME) task, converting phonetic input into script. The model was trained on an 80,000-sentence subset of the Nikkei Newspaper corpus, with a baseline MLE trigram model trained on a larger 400,000-sentence set. Generalization was tested across four domains: Yomiuri Newspaper, TuneUp, Encarta, and Shincho.

Results and Discussion

MSR demonstrated superior performance compared to both the MLE baseline and other discriminative training algorithms.

Comparison of Character Error Rate (CER) across different models, showing MSR's superior performance.

As shown in the results, MSR achieved a 2.95% Character Error Rate (CER), a 20.9% reduction over the MLE baseline. It also consistently outperformed Boosting and Perceptron. Furthermore, MSR showed strong domain adaptation capabilities, outperforming traditional Maximum A Posteriori (MAP) adaptation in cross-domain tests.

The efficiency of the heuristic search was also notable, with the algorithm converging in under 20 minutes for a model with 20,000 features. This suggests that MSR is not only effective but also computationally practical for large-scale NLP tasks.

Conclusion

Minimum Sample Risk provides a direct and effective path for optimizing language models. By bypassing proxy loss functions and optimizing the true error rate through heuristic search and smart feature selection, MSR achieves state-of-the-art results in Japanese text input. Future work will explore its application to other complex metrics like BLEU for machine translation and its scalability to millions of features.

Summary updated

Abstract

This paper proposes a new discriminative training method, called minimum sample risk (MSR), of estimating parameters of language models for text input. While most existing discriminative training methods use a loss function that can be optimized easily but approaches only approximately to the objective of minimum error rate, MSR minimizes the training error directly using a heuristic training procedure. Evaluations on the task of Japanese text input show that MSR can handle a large number of features and training samples; it significantly outperforms a regular trigram model trained using maximum likelihood estimation, and it also outperforms the two widely applied discriminative methods, the boosting and the perceptron algorithms, by a small but statistically significant margin.
BibTeX
@inproceedings{gao2005minimum,
  author = {Jianfeng Gao and Hao Yu and Wei Yuan and Peng Xu},
  title = {{Minimum Sample Risk Methods for Language Modeling}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  url = {https://openreview.net/forum?id=Bk4KOXW_-H},
}
Figure