Decomposition techniques for training linear programming support vector machines
Decomposition techniques for training linear programming support vector machines
复制标题
DOI：
10.1016/j.neucom.2008.04.008
复制
发表时间：
2009
期刊：
影响因子：
6
通讯作者：
Yusuke Torii;S. Abe
中科院分区：
文献类型：
--
作者：
Yusuke Torii;S. Abe
本文提出了线性规划（LP）问题的三种分解技术：(1)方法1，将变量分解为工作集和固定集，但不分解约束；(2)方法2，只分解约束；(3)方法3，将变量和约束都分解为两个。通过方法1，证明了目标函数的值对于最大化（最小化）问题是非递减（非递增）的，通过方法2，证明了目标函数的值对于最大化（最小化）问题是非递增（非递减）的。因此，方法3是方法1和方法2的结合，目标函数的值不能保证是单调的，存在无限循环的可能性。证明了当无限循环中的变量不从工作集中释放时，无限循环是可解的，方法3收敛于有限步。我们将方法1和3应用于LP支持向量机（svm），并讨论了一种更有效的方法，通过检测违规数量的增加和恢复在前一个迭代步骤中释放的工作集中的变量来加速训练。通过对具有大量输入变量和少量约束的微阵列数据的计算机实验，我们证明了方法1用于训练具有线性核的原始LP支持向量机的有效性。对于非线性LP支持向量机，我们也证明了方法3优于方法1的有效性。
In this paper, we propose three decomposition techniques for linear programming (LP) problems: (1) Method 1, in which we decompose the variables into the working set and the fixed set, but we do not decompose the constraints, (2) Method 2, in which we decompose only the constraints and (3) Method 3, in which we decompose both the variables and the constraints into two. By Method 1, the value of the objective function is proved to be non-decreasing (non-increasing) for the maximization (minimization) problem and by Method 2, the value is non-increasing (non-decreasing) for the maximization (minimization) problem. Thus, by Method 3, which is a combination of Methods 1 and 2, the value of the objective function is not guaranteed to be monotonic and there is a possibility of infinite loops. We prove that infinite loops are resolved if the variables in an infinite loop are not released from the working set and Method 3 converges in finite steps. We apply Methods 1 and 3 to LP support vector machines (SVMs) and discuss a more efficient method of accelerating training by detecting the increase in the number of violations and restoring variables in the working set that are released at the previous iteration step. By computer experiments for microarray data with huge input variables and a small number of constraints, we demonstrate the effectiveness of Method 1 for training the primal LP SVM with linear kernels. We also demonstrate the effectiveness of Method 3 over Method 1 for the nonlinear LP SVMs.