PSVM：并行SVM
555集成块摘要
霍夫曼比例支持向量机（SVM）有着很强大的功能，在数据挖掘领域得到了很广泛的应用。但SVM同样也存在一些问题，其中很显著的一点就是当训练样本量很大时，SVM的时间复杂度和空间复杂度都会变得很高。所以，近年来在各类研讨会以及出版物中，人们越来越多地将目光集中在SVM的可扩展性上，也提出了很多关于SVM的并行算法，这些方法充分利用现阶段硬件的一些新特性，在不同程度上提高了SVM的性能。 本文主要讨论关于SVM的并行形式（parallel SVM：PVSM），PSVM对于降低SVM的空间复杂度以及时间复杂度有着很好的效果。
关键词：支持向量机 并行算法 ICF IPM
1．引言
SVM算法在占用存储和计算时间方面，都存在着很大的可扩展性问题。为了解决这个问题，
一种并行支持向量机算法（PSVM）出现了。PSVM算法解决了这两方面的问题：1唐山师范学院刘丹）利用一种基于列的矩阵分解方法减少了SVM占用的存储空间；2）利用并行的IPC算法求解最优化问题，提高了SVM的执行速度。
下面本文就详细介绍一下PSVM算法。
SVM算法原本是这种形式：给定一个训练数据集，此处是观测到的向量，是的类标签，n是的元素数，而我们就可以利用这个来训练一个二分类器。SVM的目标就是在再生核希尔伯特空间（RKHS）中到一个超平面，同时最大化中两类数据边缘距离，最小化训练误差。此问题可以归纳为如下最优化问题：
是一个权向量，是一个偏移量，是惩罚因子，而是将映射到RKHS的映射函数。SVM的判别函数是：此处和是由问题（1）求解得到的。
但在实际问题中，问题（1）也许会难以直接求解，因为映射函数往往是未知的。所以我们可以利用拉格朗日乘子法将问题转化为以下形式：
在问题（2）中，，是拉格朗日乘子。同时有：。这个新的对偶问题需要计算和的内积，从而可以把这个内积写成一个核函数的形式，所以可以重新记作。对于问题（2），可以用内点法（IPM）求解。
2．PSVM算法
2.1并行不完全乔列斯基分解（PICF）
并行不完全乔列斯基分解（PICF）是PSVM的第一个重要步骤。
ICF可以将一个大矩阵近似为较小矩阵的乘积形式，例如：。而在PSVM中，还可以将H矩阵分布地存储在多台机器上，供并行IPM使用。
具体的基于列的PICF算法如下：
算法1 基于列的PICF
输入：n个训练样本；ICF矩阵H的秩p；执行并行算法的机器数m
输出：分布在m台机器上的矩阵H
变量：
v：储存在本机的Q矩阵对角线元素
k：循环次数
：第i个训练样本
挑山工教学实录M：机器编号，
机器c手术指征的列编号，
1：
2： 通过round robin算法在某台机器上存储
3：
4：Q的一部分对角线元素，可由存储在本地的得到
5：初始化0号机为主机
6：
记录下枢轴量的下标，也就是的列号：
8： 主机收集所有的和。
9： 主机选出全局最大枢轴量，及其列号：
10： 主机广播和
11： 将主机变更为机器
12： 主机计算
13： 主机广播枢轴样本和枢轴列
14： 每台机器计算
15： 每台机器更新本地的向量v：
16：
17：
当把p设为时，ICF误差几乎可以忽略不计。
完成PICF，我们就将SVM的空间复杂度由降到了，当p远小于n是，性能提升是非常显著的。
2.2并行内点法（PIPM）
并行内点法（PIPM）是PSVM真正的求解方法。其实质是牛顿梯度法，迭代地寻函数极值。其每一步迭代如下：
（笔者注：通过翻阅大量资料，这里的即是。）
由于第一步已经将矩阵H分布在机上，所以PIPM广播和，就可以达到计算任务的并行。
在迭代中，最复杂的一步就是与向量的乘法，对于这个问题可以有以下解决方法：
矩阵D为对角矩阵，做乘法要简单很多。而需要注意的一点是对又做了一次不完全乔列斯基分解，转化为的形式，方便计算。
PIPM使得SVM的时间复杂度由降到了。
完成PIPM迭代之后，就完全已知了。从而可以得到判别函数：
这里的b可以通过已知的训练样本，比较相应的和y，得到不同的b值，最后用所有b值的算术平均作为判别函数中的b吴少芳值。
3．总结
PSVM通过PICF和PIPM两个算法解决了传统SVM空间复杂度和时间复杂度过高的问题，充分利用现阶段设备的优良性能，将SVM问题分解到多机系统上；同时原理简单，容易实现。可以说PSVM让SVM的性能上了一个台阶，使得他能处理的问题更多、需求的空间更少、完成的速度更快。
有研究结果表明，PSVM比公认最好的支持向量机算法LIBSVM性能更好，同时也有着很高的正确率。
可以说，SVM的并行化，是今后数据挖掘领域的必然趋势。甚至不仅仅是SVM，各种算法的可扩展性，也必将成为今后学界关注的热点。所以本文所说的PSVM算法，还是很有理
论和现实意义的。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议