Implementation Issues of Second-Order Cone Programming Approaches for Support Vector Machine Learning Problems
Implementation Issues of Second-Order Cone Programming Approaches for Support Vector Machine Learning Problems
复制标题
DOI：
10.1587/transfun.e92.a.1209
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
R. Debnath;M. Muramatsu;Haruhisa Takahashi
中科院分区：
文献类型：
--
作者：
R. Debnath;M. Muramatsu;Haruhisa Takahashi
支持向量机 (SVM) 问题的核心是具有线性约束和有界变量的二次规划问题。该问题可以转化为二阶锥规划（SOCP）问题。如果核矩阵具有低秩，则可以根据存储要求和计算复杂性为 SOCP 问题设计内点法 (IPM)。如果核矩阵不是低秩矩阵，则可以通过低秩正半定矩阵来近似它，该矩阵又将被输入到优化器中。在本文中，我们针对每个 SVM 分类和回归问题提出了两种 SOCP 公式。有多种用于实现 SOCP 的搜索方向方法。我们的主要目标是找到一个更好的搜索方向来实现 SVM 问题的 SOCP 公式。两种流行的搜索方向方法：HKM 和 AHO 针对 SVM 问题进行了分析测试，并有效地实现了。对于 SVM 问题，HKM 和 AHO 搜索方向方法每次迭代的计算成本是相同的。因此，训练时间取决于 IPM 迭代的次数。我们的实验结果表明 HKM 方法比 AHO 方法收敛得更快。我们还将我们的结果与 Fine 和 Scheinberg (2001) 中提出的方法进行了比较，该方法也利用了核矩阵的低秩、最先进的 SVM 优化软件 SVMTorch 和 SVMlight。所提出的方法还与线性核上的 Joachims“线性 SVM”方法进行了比较。
The core of the support vector machine (SVM) problem is a quadratic programming problem with a linear constraint and bounded variables. This problem can be transformed into the second order cone programming (SOCP) problems. An interior-point-method (IPM) can be designed for the SOCP problems in terms of storage requirements as well as computational complexity if the kernel matrix has low-rank. If the kernel matrix is not a low-rank matrix, it can be approximated by a low-rank positive semi-definite matrix, which in turn will be fed into the optimizer. In this paper we present two SOCP formulations for each SVM classification and regression problem. There are several search direction methods for implementing SOCPs. Our main goal is to find a better search direction for implementing the SOCP formulations of the SVM problems. Two popular search direction methods: HKM and AHO are tested analytically for the SVM problems, and efficiently implemented. The computational costs of each iteration of the HKM and AHO search direction methods are shown to be the same for the SVM problems. Thus, the training time depends on the number of IPM iterations. Our experimental results show that the HKM method converges faster than the AHO method. We also compare our results with the method proposed in Fine and Scheinberg (2001) that also exploits the low-rank of the kernel matrix, the state-of-the-art SVM optimization softwares SVMTorch and SVMlight. The proposed methods are also compared with Joachims ‘Linear SVM’ method on linear kernel.