训练结构化支持向量机的优化切平面法

Optimized cutting plane method for training a structural SVM

结构化支持向量机是机器学习中描述结构化输出问题的一种新模型,对其进行训练是一个典型的非光滑凸优化问题,最常用的训练算法是切平面法。切平面法中原问题的目标函数往往会发生振荡,因此一般需要加入线搜索环节。但是还没有针对结构化支持向量机的高效的线搜索方法。该文提出了一种优化的切平面法,通过二次插值来进行近似线搜索,并将其应用到结构化支持向量机的训练中。在多类分类上的实验表明:该算法的迭代次数接近精确线搜索,而每次迭代的计算量保持不变。在序列分类上的实验表明:该算法在训练其他复杂类型的结构化支持向量机时仍然比当前主流算法效率高很多。

The structural support vector machine （SVM） is a new model for structured output problem in machine learning. Model training is a typical nonsmooth convex optimization problem with the most commonly used training algorithm being the cutting plane algorithm. However, the objective function often oscillates in the cutting plane algorithm, so a line-search procedure is commonly added to the algorithm. There is no efficient line-search method for training structural SVM. This paper presents an optimized cutting plane algorithm which does an approximate line-search using quadratic interpolation to train a structural SVM. Tests on multiclass classification demonstrate that the number of iterations with this algorithm is roughly the same as an accurate line-search, with the number of computations in a single iteration remaining unchanged. Tests of sequence tagging verify that this algorithm is much more efficient than the current mainstream algorithm.