Parallel Support Vector Machines: The Cascade SVM
Parallel Support Vector Machines: The Cascade SVM
复制标题
DOI：
--
复制
发表时间：
2004-12
期刊：
影响因子：
--
通讯作者：
H. Graf;E. Cosatto;L. Bottou;Igor Durdanovic;V. Vapnik
中科院分区：
文献类型：
--
作者：
H. Graf;E. Cosatto;L. Bottou;Igor Durdanovic;V. Vapnik
我们描述了一种用于支持向量机的算法，该算法可以高效地并行化，并且可以扩展到具有数十万个训练向量的非常大的问题。该方法不是在一个优化步骤中分析整个训练集，而是将数据分成多个子集，分别用多个支持向量机进行优化。部分结果在支持向量机的“级联”中被组合和过滤，直到达到全局最优。级联支持向量机可以以最小的通信开销分布在多个处理器上，并且需要的内存要少得多，因为核矩阵比常规的支持向量机要小得多。通过级联的多次遍历可以保证收敛到全局最优，但单次遍历已经提供了良好的泛化。当在单个处理器上实现时，对于100,000个向量的问题，单次通过比常规的支持向量机快5倍-10倍。在16个处理器的集群上测试了并行实现，测试了100多万个向量(2类问题)，在一两天内收敛，而常规的支持向量机从未在一周以上收敛。
We describe an algorithm for support vector machines (SVM) that can be parallelized efficiently and scales to very large problems with hundreds of thousands of training vectors. Instead of analyzing the whole training set in one optimization step, the data are split into subsets and optimized separately with multiple SVMs. The partial results are combined and filtered again in a 'Cascade' of SVMs, until the global optimum is reached. The Cascade SVM can be spread over multiple processors with minimal communication overhead and requires far less memory, since the kernel matrices are much smaller than for a regular SVM. Convergence to the global optimum is guaranteed with multiple passes through the Cascade, but already a single pass provides good generalization. A single pass is 5x - 10x faster than a regular SVM for problems of 100,000 vectors when implemented on a single processor. Parallel implementations on a cluster of 16 processors were tested with over 1 million vectors (2-class problems), converging in a day or two, while a regular SVM never converged in over a week.