A Fast Accurate Two-stage Training Algorithm for L1-regularized CRFs with Heuristic Line Search Strategy

Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 65–74, Chiang Mai, Thailand, November 8 – 13, 2011. c⃝2011 AFNLP A Fast Accurate Two-stage Training Algorithm for L1-regularized CRFs with Heuristic Line Search Strategy Jinlong Zhou Fudan University Shanghai, China abc9703@gmail.com Xipeng Qiu Fudan University Shanghai, China xpqiu@fudan.edu.cn Xuanjing Huang Fudan University Shanghai, China xjhuang@fudan.edu.cn Abstract Sparse learning framework, which is very popular in the field of nature language processing recently due to the advantages of efficiency and generalizability, can be applied to Conditional Random Fields (CRFs) with L1 regularization method. Stochastic gradient descent (SGD) method has been used in training L1-regularized CRFs, because it often requires much less training time than the batch training algo- rithm like quasi-Newton method in prac- tice. Nevertheless, SGD method some- times fails to converge to the optimum, and it can be very sensitive to the learn- ing rate parameter settings. We present a two-stage training algorithm which guar- antees the convergence, and use heuris- tic line search strategy to make the first stage of SGD training process more robust and stable. Experimental evaluations on Chinese word segmentation and name en- tity recognition tasks demonstrate that our method can produce more accurate and compact model with less training time for L1 regularization. 1 Introduction Conditional Random Fields (CRFs) (Lafferty et al., 2001; Sutton and McCallum, 2006) are one of the most widely-used machine learning approach in the field of nature language processing, for their ability to handle large feature sets and structural dependency between output labels. The applica- tions of CRFs cover a wide range of tasks such as part-of-speech (POS) tagging (Lafferty et al., 2001), semantic role labeling (Toutannova et al., 2005) and syntactic parsing (Finkel et al., 2008). CRFs outperform other models like Maximum En- tropy Markov models (McCallum et al., 2000), be- cause they overcome the problem of “label bias”. Moreover, CRFs can output the probabilistic of la- beling result for further use as pipeline or rerank- ing. For all types of CRFs, the maximum-likelihood method can be applied for parameter estimation, which means training the model is done by max- imizing the log-likelihood on the training data. To avoid overfitting the likelihood is often penal- ized with the regularization term. There were two common regularization methods named L1 and L2 regularization. L1 regularization, also called Laplace prior, penalizes the weight vector with its L1-norm. L2 regularization, also called Gaussian prior, uses L2-form. Based on the work of Gao et al. (2007), there is no significant difference be- tween these two regularization methods in terms of accuracy. But L1 regularization has a major ad- vantage that L1-regularized training can produce models, of which the feature weights can be very sparse, then the size of the model will be much smaller than that produced by L2 regularization. Compact models are more interpretable, general- izable and manageable, require less resources like memory and storage. It is very meaningful espe- cially for the rapid development of mobile appli- cation nowadays, which …

Content truncated to 500 words