Cutting-plane training of structural SVMs

作     者：Joachims, Thorsten Finley, Thomas Yu, Chun-Nam John 

作者机构：Cornell Univ Dept Comp Sci Ithaca NY 14853 USA 

出 版 物：《MACHINE LEARNING》 (机器学习)

年 卷 期：2009年第77卷第1期

页      面：27-59页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [IIS-0713483] 

主　　题：Structural SVMs Support vector machines Structured output prediction Training algorithms 

摘      要：Discriminative training approaches like structural SVMs have shown much promise for building highly complex and accurate models in areas like natural language processing, protein structure prediction, and information retrieval. However, current training algorithms are computationally expensive or intractable on large datasets. To overcome this bottleneck, this paper explores how cutting-plane methods can provide fast training not only for classification SVMs, but also for structural SVMs. We show that for an equivalent 1-slack reformulation of the linear SVM training problem, our cutting-plane method has time complexity linear in the number of training examples. In particular, the number of iterations does not depend on the number of training examples, and it is linear in the desired precision and the regularization parameter. Furthermore, we present an extensive empirical evaluation of the method applied to binary classification, multi-class classification, HMM sequence tagging, and CFG parsing. The experiments show that the cutting-plane algorithm is broadly applicable and fast in practice. On large datasets, it is typically several orders of magnitude faster than conventional training methods derived from decomposition methods like SVM-light, or conventional cutting-plane methods. Implementations of our methods are available at http://***.