SVM的并行化

目前我在SVM的并行化方面已经有解法. SVM在数学上的本质是凸优化理论, 可以有很多种解法。 它的问题具有对偶性, 从原问题出发和从对偶问题出发。传统SVM在大数据集下，它的核矩阵要占用的内存非常大，呈平方地递增。 也就是说1000个数据占用的内存会是100个数据占用的内存的100 倍。为了解决此问题，涉及到SVM的分解，极端的情况下是使用SMO算法，这也是目前SVM最流行的解法。 SMO算法每次只求目标函数的两个alpha值,具有占用内存较小,收敛得比较快的优势。 但在并行上,不是很好做，因为后一步的alpha值依赖前一步的alpha值，前后数据依赖性比较强, 我一直到今年2月中旬左右才从理论上解决此问题。但是，我觉得SMO算法迭代次数太多, 现在我的做法不够完善。

我有几条思路可以完善目前的理论
1. cutting-plane能减少迭代的次数，但cutting-plane一样具有数据依赖性较强的问题，所以我还没有解决。
2. 对比较稀疏的,但维数非常大的数据，例如文本数据，可以用线性SVM代替二次SVM, 因为理论已经证明两者的精度相差不大。但速度上线性SVM要快几个数量级。
3. 从原问题出发，使用内点法。通过矩阵的分解, 使用Incomplete Cholesky Factorization将矩阵分解为两个较小矩阵的乘积, 分布这两个矩阵。

以上提出的思路涉及很多数学原理，我正在看convex optimization这本书，希望能有点收获。SVM根据loss函数，可以分为L1-SVM和L2-SVM。 2007年, Bottou提出了一种梯度下降的方法解决L1-SVM, 2008年Collins 提出了另一种exponentiated梯度下降方法.2008年台湾大学的林智仁教授提出了trust region Netton method(TRON)解决L2-SVM。 目前的SVM算法空前繁盛，我使用了08年末林智仁教授的学生提出另一种串行的梯度下降算法(A Dual Coordinate Desent Method for Large-scale Linear SVM),可以在几十秒之内，对19000个英文新闻进行分类训练, 精度达到96.7%，而 使用SMO算法，我的机器不够内存(2.5GB RAM)，理论上最少也要跑几个小时。它的算法前后数据依赖性非常强,目前我没法把它并行。

以上提出的三条思路，我觉得第1,2条更能达到我的目的，而且效果更好，我正在补数学上的不足，大概有700页左右的数学理论要看。目前我收集的理论资料有229m，我看过其中的一半左右，因为文章过多，所以没有在这里列出来。

有哪位xdjm对这方面比较感兴趣,有自己的见解,请与我联系: [e-mail]

评论

1 楼 conservatism 2009-03-15