Approximation Lasso Methods for Language Modeling

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 225–232, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Approximation Lasso Methods for Language Modeling Jianfeng Gao Microsoft Research One Microsoft Way Redmond WA 98052 USA jfgao@microsoft.com Hisami Suzuki Microsoft Research One Microsoft Way Redmond WA 98052 USA hisamis@microsoft.com Bin Yu Department of Statistics University of California Berkeley., CA 94720 U.S.A. binyu@stat.berkeley.edu Abstract Lasso is a regularization method for pa- rameter estimation in linear models. It op- timizes the model parameters with respect to a loss function subject to model com- plexities. This paper explores the use of lasso for statistical language modeling for text input. Owing to the very large number of parameters, directly optimizing the pe- nalized lasso loss function is impossible. Therefore, we investigate two approxima- tion methods, the boosted lasso (BLasso) and the forward stagewise linear regres- sion (FSLR). Both methods, when used with the exponential loss function, bear strong resemblance to the boosting algo- rithm which has been used as a discrimi- native training method for language mod- eling. Evaluations on the task of Japanese text input show that BLasso is able to produce the best approximation to the lasso solution, and leads to a significant improvement, in terms of character error rate, over boosting and the traditional maximum likelihood estimation. 1 Introduction Language modeling (LM) is fundamental to a wide range of applications. Recently, it has been shown that a linear model estimated using dis- criminative training methods, such as the boost- ing and perceptron algorithms, outperforms significantly a traditional word trigram model trained using maximum likelihood estimation (MLE) on several tasks such as speech recogni- tion and Asian language text input (Bacchiani et al. 2004; Roark et al. 2004; Gao et al. 2005; Suzuki and Gao 2005). The success of discriminative training meth- ods is largely due to fact that unlike the tradi- tional approach (e.g., MLE) that maximizes the function (e.g., likelihood of training data) that is loosely associated with error rate, discriminative training methods aim to directly minimize the error rate on training data even if they reduce the likelihood. However, given a finite set of training samples, discriminative training methods could lead to an arbitrary complex model for the pur- pose of achieving zero training error. It is well-known that complex models exhibit high variance and perform poorly on unseen data. Therefore some regularization methods have to be used to control the complexity of the model. Lasso is a regularization method for parame- ter estimation in linear models. It optimizes the model parameters with respect to a loss function subject to model complexities. The basic idea of lasso is originally proposed by Tibshirani (1996). Recently, there have been several implementa- tions and experiments of lasso on multi-class classification tasks where only a small number of features need to be handled and the lasso solu- tion can be directly computed via numerical methods. To our knowledge, this paper presents the first empirical study of …

Content truncated to 500 words