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.
Direct Optimization and Grid Search
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.
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.
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