Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 477–485, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty Yoshimasa Tsuruoka†‡ Jun’ichi Tsujii†‡∗ Sophia Ananiadou†‡ † School of Computer Science, University of Manchester, UK ‡ National Centre for Text Mining (NaCTeM), UK ∗ Department of Computer Science, University of Tokyo, Japan {yoshimasa.tsuruoka,j.tsujii,sophia.ananiadou}@manchester.ac.uk Abstract Stochastic gradient descent (SGD) uses approximate gradients estimated from subsets of the training data and updates the parameters in an online fashion. This learning framework is attractive because it often requires much less training time in practice than batch training algorithms. However, L1-regularization, which is be- coming popular in natural language pro- cessing because of its ability to pro- duce compact models, cannot be effi- ciently applied in SGD training, due to the large dimensions of feature vectors and the fluctuations of approximate gra- dients. We present a simple method to solve these problems by penalizing the weights according to cumulative values for L1 penalty. We evaluate the effectiveness of our method in three applications: text chunking, named entity recognition, and part-of-speech tagging. Experimental re- sults demonstrate that our method can pro- duce compact and accurate models much more quickly than a state-of-the-art quasi- Newton method for L1-regularized log- linear models. 1 Introduction Log-linear models (a.k.a maximum entropy mod- els) are one of the most widely-used probabilistic models in the field of natural language process- ing (NLP). The applications range from simple classification tasks such as text classification and history-based tagging (Ratnaparkhi, 1996) to more complex structured prediction tasks such as part- of-speech (POS) tagging (Lafferty et al., 2001), syntactic parsing (Clark and Curran, 2004) and se- mantic role labeling (Toutanova et al., 2005). Log- linear models have a major advantage over other discriminative machine learning models such as support vector machines—their probabilistic out- put allows the information on the confidence of the decision to be used by other components in the text processing pipeline. The training of log-liner models is typically per- formed based on the maximum likelihood crite- rion, which aims to obtain the weights of the fea- tures that maximize the conditional likelihood of the training data. In maximum likelihood training, regularization is normally needed to prevent the model from overfitting the training data, The two most common regularization methods are called L1 and L2 regularization. L1 regular- ization penalizes the weight vector for its L1-norm (i.e. the sum of the absolute values of the weights), whereas L2 regularization uses its L2-norm. There is usually not a considerable difference between the two methods in terms of the accuracy of the resulting model (Gao et al., 2007), but L1 regu- larization has a significant advantage in practice. Because many of the weights of the features be- come zero as a result of L1-regularized training, the size of the model can be much smaller than that produced by L2-regularization. Compact models require less space on memory and …

Content truncated to 500 words