基于活跃集的支持向量机切平面法

Active Set Based Cutting Plane Algorithm for SVM

切平面法作为求解非光滑凸优化问题的典型方法,在支持向量机问题的求解中得到了广泛的应用.但是该算法在求解过程中往往会出现不稳定的情况.针对这一不稳定性,前人提出了优化切平面法,通过在切平面法中加入线搜索环节来确保目标函数单调下降.但是优化切平面法的运算复杂度比较高,不适合训练数据量大、对训练速度要求高的应用.本文提出了一种基于活跃集的优化切平面法,在计算目标函数和进行线搜索时,只单独处理活跃集内的样本,将其它样本当作一个整体来进行处理.相对于传统的优化切平面法,本文方法只需在一部分样本上计算目标函数和进行线搜索,从而可以在不损失求解精度的前提下节省求解时间.

As a typical method for solving non-smooth convex optimization problems,cutting plane method is widely used in solving support vector machine problems. However, this algorithm suffers from the instability problem. To ease this instability,re- searchers proposed an optimized cutting plane algorithm which incorporated a line search stage. However, the computational com- plexity of such algorithm is too high for applications where the number of training samples is large. In this paper we propose an ac- tive set based optimized cutting plane algorithm to reduce the computation complexity of the original algorithm. When computing the objective function and performing line search, only those samples which fall in the active set are considered. Compared to opti- mized cutting plane algorithm, the proposed algorithm needs to calculate the objective function and perform line search only for a small fraction of the samples, leading to a sijznificant drop in comoutational comolexity without losing accuracy.