Interior-Point Methods for Massive Support Vector Machines
Interior-Point Methods for Massive Support Vector Machines
复制标题
DOI：
10.1137/s1052623400374379
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
M. Ferris;T. Munson
中科院分区：
文献类型：
--
作者：
M. Ferris;T. Munson
我们研究了用内点方法来求解带有少量线性约束的二次规划问题，其中二次项包括对半正定矩阵的低阶更新。支持向量机的几个公式就属于这一类。这些特殊问题的一个有趣特征是数据量，这可能导致具有1000到1亿个变量的二次规划，如果显式编写，还会产生稠密的Q矩阵。我们的代码是基于OOQP的，这是一种面向对象的内点代码，线性代数专门用于支持向量机应用。对于目标海量问题，所有数据都存储在核外，我们重叠计算和输入/输出以减少开销。对几个线性支持向量机公式的结果表明，该方法是可靠的和可扩展的。
We investigate the use of interior-point methods for solving quadratic programming problems with a small number of linear constraints, where the quadratic term consists of a low-rank update to a positive semidefinite matrix. Several formulations of the support vector machine fit into this category. An interesting feature of these particular problems is the volume of data, which can lead to quadratic programs with between 10 and 100 million variables and, if written explicitly, a dense Q matrix. Our code is based on OOQP, an object-oriented interior-point code, with the linear algebra specialized for the support vector machine application. For the targeted massive problems, all of the data is stored out of core and we overlap computation and input/output to reduce overhead. Results are reported for several linear support vector machine formulations demonstrating that the method is reliable and scalable.