A Comparison and Improvement of Online Learning Algorithms for Sequence Labeling

Proceedings of COLING 2012: Technical Papers, pages 1147–1162, COLING 2012, Mumbai, December 2012. A Comparison and Improvement of Online Learning Algorithms for Sequence Labeling Zheng yan He Houf eng Wang ∗ Key Laboratory of Computational Linguistics (Peking University) Ministry of Education,China hezhengyan.hit@gmail.com, wanghf@pku.edu.cn ABSTRACT Sequence labeling models like conditional random fields have been successfully applied in a variety of NLP tasks. However, as the size of label set and dataset grows, the learning speed of batch algorithms like L-BFGS quickly becomes computationally unacceptable. Several online learning methods have been proposed in large scale setting, yet little effort has been made to compare the performance of these algorithms. Comparison is often carried out on a few datasets with fine tuned parameters for specific algorithm. In this paper, we investigate and compare several online learning algorithms for sequence labeling with datasets varying in scale, feature design and label set. We find that Dual Coordinate Ascent (DCA) is robust across datasets even without careful tuning of parameter. Furthermore, a recently proposed variant of Stochastic Gradient Descent (SGD), Adaptive online gradient Descent based on feature Frequency information (ADF), has very fast training speed compared with plain SGD, but fails to converge under certain conditions. Finally, We propose a simple modification of ADF, which bears comparable convergence speed with ADF, and is consistently better than plain SGD. TITLE AND ABSTRACT IN CHINESE 序 序 序列 列 列标 标 标注 注 注在 在 在线 线 线学 学 学习 习 习算 算 算法 法 法的 的 的比 比 比较 较 较和 和 和改 改 改进 进 进 序列标注模型，如条件随机场，已广泛用于自然语言处理的很多任务中。但随着数 据规模和标记集的增大，批量学习算法（如L-BFGS）的训练时间复杂性变得越来越不可接 受；于是，出现了多个大规模环境下的在线学习算法。这些算法有各自的特点，但对这些 算法的比较研究很少有报道。通常情况下都是针对几个数据集，通过对特定算法细致调 整参数来比较最后的测试结果。本文针对几个典型的序列标注在线学习算法，在不同规 模、特征设计和标记集合的数据集上进行了比较研究。结果发现，即使没有特别对参数 调优，对偶坐标上升算法（DCA）在不同数据集上也能有很好的表现；而随机梯度下降 算法（SGD）的一个变种算法——基于特征频度的适应性在线梯度下降法（ADF）与普通 的SGD相比，训练速度更快，但不能保证总收敛。最后，本文还对ADF提出了一种简单的 改进，改进后的算法好于普通的SGD，与ADF 收敛速度接近。 KEYWORDS: Sequence labeling, online learning, stochastic gradient descent, named entity recognition. KEYWORDS IN CHINESE: 序列标注模型，在线学习，随机梯度下降，命名实体识别 ∗Corresponding author 1147 1 Introduction Sequence labeling models have been widely used in a variety of NLP tasks, such as word segmentation, part-of-speech tagging, chunking, and named entity recognition. Various se- quence labeling models have been proposed, like hidden Markov models (HMM) (Rabiner, 1989), structured perceptron (Collins, 2002), conditional random fields (CRFs) (Lafferty et al., 2001) and SVM-HMM (Tsochantaridis et al., 2006). In recent years, discriminative models gain significant popularity over generative models on these tasks, and achieve state-of-the-art performance on most above tasks. Their strength and flexibility come from their ability to incorporate arbitrary declarative features. CRFs is one of such discriminative models for sequence labeling built upon maximum entropy principle. The learning algorithms of CRFs can be divided into batch methods and online methods. Batch methods update parameters by estimating gradient over the entire training data, while online methods estimate noisy gradient with a small portion of the training data, and update parameters frequently. Among all the batch methods, L-BFGS is the most widely used and outperforms others by a substantial margin (Malouf et al., 2002); Conjugate-gradient (CG) method with proper preconditioner can converge as fast as L-BFGS (Sha and Pereira, 2003). However, discriminative models for typical sequence labeling tasks are very large and may involve hundreds of thousands of features, rendering …

Content truncated to 500 words