Minimum Sample Risk Methods for Language Modeling

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 209–216, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Minimum Sample Risk Methods for Language Modeling 1 Jianfeng Gao Microsoft Research Asia jfgao@microsoft.com Hao Yu, Wei Yuan Shanghai Jiaotong Univ., China Peng Xu John Hopkins Univ., U.S.A. xp@clsp.jhu.edu 1 The work was done while the second, third and fourth authors were visiting Microsoft Research Asia. Thanks to Hisami Suzuki for her valuable comments. 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 objec- tive 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 train- ing samples; it significantly outperforms a regular trigram model trained using maxi- mum likelihood estimation, and it also out- performs the two widely applied discrimi- native methods, the boosting and the per- ceptron algorithms, by a small but statisti- cally significant margin. 1 Introduction Language modeling (LM) is fundamental to a wide range of applications, such as speech recognition and Asian language text input (Jelinek 1997; Gao et al. 2002). The traditional approach uses a paramet- ric model with maximum likelihood estimation (MLE), usually with smoothing methods to deal with data sparseness problems. This approach is optimal under the assumption that the true distribution of data on which the parametric model is based is known. Unfortunately, such an assumption rarely holds in realistic applications. An alternative approach to LM is based on the framework of discriminative training, which uses a much weaker assumption that training and test data are generated from the same distribution but the form of the distribution is unknown. Unlike the traditional approach that maximizes the function (i.e. likelihood of training data) that is loosely as- sociated with error rate, discriminative training methods aim to directly minimize the error rate on training data even if they reduce the likelihood. So, they potentially lead to better solutions. However, the error rate of a finite set of training samples is usually a step function of model parameters, and cannot be easily minimized. To address this prob- lem, previous research has concentrated on the development of a loss function that approximates the exact error rate and can be easily optimized. Though these methods (e.g. the boosting method) have theoretically appealing properties, such as convergence and bounded generalization error, we argue that the approximated loss function may prevent them from attaining the original objective of minimizing the error rate. In this paper we present a new estimation pro- cedure for LM, called minimum sample risk (MSR). It differs from most existing discriminative training methods in that instead of searching on an ap- proximated loss function, MSR employs a simple heuristic …

Content truncated to 500 words