并行分解优化大规模SVM的训练效率.pdf

文档介绍：该【并行分解优化大规模SVM的训练效率 】是由【学习的一点】上传分享，文档一共【3】页，该文档可以免费在线阅读，需要了解更多关于【并行分解优化大规模SVM的训练效率 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2002011,47(12)ComputerEngineeringandApplications计算机工程与应用
用LDLT并行分解优化大规模SVM的训练效率
覃华,徐燕子
QINHua,XUYanzi
广西大学计算机与信息工程学院,南宁530004
CollegeofComputerandInformationEngineering,GuangxiUniversity,Nanning530004,China
QINHua,’-
neeringandApplications,2011,47(12):200-202.
Abstract:Ifthesupportvectormachineistrainedonlarge-scaledatasets,thetrainingtimewillbelongerandgeneralization
’slearningalgorithmon
large-scaledatasets,andthekeypointbeingnegativeimpactonSVM’slearningefficiencyonlarge-scaledatasetsisto
solvethelarge-’slearningefficiency,thedimensionsofdi-
rectionequationsaredegraded,thenLDLTparalleldecompositionmethodisusedtosolvethedirectionsub-equationsefficiently.
TheexperimentalresultsshowthatthenewSVM’strainingalgorithmisefficientforlarge-scaledatasetsandthegeneraliza-
tioncapacityofSVMisnotaffected.
Keywords:large-scalesupportvectormachine;pathfollowingmethod;matrixLDLTparalleldecomposition
摘要:支持向量机在大规模训练集上学****时,存在学****时间长、泛化能力下降的问题。研究使用路径跟踪内点法构建面向大规
模训练集的SVM学****算法,找到影响算法学****效率的关键是求解大型线性修正方程,首先使用降维法降低修正方程的维数,再
使用矩阵LDLT并行分解高效地求解子修正方程,达到优化大规模SVM学****效率的目的,实验结果说明SVM训练效率提升的同
时不影响SVM模型的泛化能力。
关键词:大规模支持向量机;路径跟踪内点法;矩阵LDLT并行分解
DOI:.1002-:1002-8331(2011)12-0200-03文献标识码:A中图分类号:TP311
1引言达到优化SVM训练速度的目的,最后通过实验说明算法的可
支持向量机(SupportVectorMachines,SVM)的训练过程行性。
可归结为求解一个凸二次规划问题,当训练样本较大时,训练
的时间会呈现指数级增长。为了提高SVM的训练速度,一些2求解大规模SVM二次规划的降维方法
研究文献提出了并行学****的思路,比较有代表性的方法有:文支持向量机的训练过程可归结为求解最优分类超平面参
献[1-4]提出一种并行分布式学****方法,其基本思路是把大规数的二次规划问题[9]:
模训练集划分成若干个小的训练集,分别交给各个计算工作n
min1w2+Cåξ
站中的SVM模型并行学****各工作站把学****到的支持向量等22i
i=1
(1)
结果反馈给主工作站收集、合成;(wTϕ(x)+b)³1-ξ
iii
确划分训练数据集,使子数据集要带有分类的支持向量,否则ξ³0i=12n
学****结果会因类别支持向量的缺失而产生较大的判断误差。i
其中,x是一个d维向量(输入样本),y是样本x对应的类别
文献[5-8]运用矩阵分解等方法,把SVM学****过程中重复的矩iii
标记,取值是1或-1,表示正、负两种样本。n是训练数据集
阵运算片段或可并行计算的部分分离出来,用并行分布式方
的总样本数。w是特征空间中分类超平面的系数(d维向量),
法计算,达到提高SVM学****速度的目的。本文研究使用路径
b是分类超平面的阈值(一个实数)。ϕ(x)是样本x在高维特
跟踪内点法(Path-FollowingInteriorPointMethod)构造SVMii
征空间的映射,可以是有限维,也可以是无穷维。ξ是考虑分
训练算法,在此基础上找到影响SVM训练速度的关键是求解i
大规模修正方程,本文首先使用降维方法降低修正方程组的类误差而引入的松驰因子,允许边界失败。C是一个与训练错
维数,考虑到降维后的子修正方程具备LDLT分解的条件,再误有关的惩罚因子。
提出使用并行LDLT分解的方法提高子修正方程的求解效率,SVM原问题(1)的Wolf对偶问题为:
基金项目:广西高校人才小高地建设创新团队计划基金资助项目([2007]71)。
作者简介:覃华(1972—),男,副教授,主要研究领域为最优化理论与数据挖掘;徐燕子(1986—),女。E-mail:******@
收稿日期:2009-08-05;修回日期:2009-09-25
覃华,徐燕子:用LDLT并行分解优化大规模SVM的训练效率2011,47(12)201
min1αTQα-eTα主子式非零,因此可以先对式(8d)的系数矩阵进行LDLT分解,
2
(2)再使用L、D来求解此方程组会获得更好的经济性。
=0
0£α£C
3矩阵的LDLT并行分解
其中,α是Lagrange乘子变量。e是n维单位向量。y是一个n
线性方程组不妨简写为Ax=b的形式,其中A是n阶实
维的类别向量,各分量取值为1或-1。C是惩罚因子。Q是
对称系数矩阵,x是变量向量,b是方程组右端项向量。如果
一个Hessian矩阵,其中的元素为:
系数矩阵A是实对称矩阵,并且A的各阶顺序主子式均非奇
Q=yyϕT(x)ϕ(x)(3)
ijijij异时,A可以进行LDLT形式的Cholesky分解,并且分解唯一,
定义核函数K(xx)与内积ϕT(x)ϕ(x)的关系为:
ijij即:A=LDLT,其中:
T
K(xx)=ϕ(xx)ϕ(xx)(4)1édù
ijijijéOù11O
êL1úêdú
则可把式(3)写成核函数形式Q=yyK(xx)。Q是半正定2122
ijijijL=êú,D=êú
êú
êúêOú
实对称矩阵。满足Mercer条件的核函数都应该是正半定的,例LL1d
ën1n2ûënnû
如核函数、高斯核等,则此时式()是一个凸二次规划问题
RBF2矩阵L中各元素的计算方法为:
(QuadraticProgramming,QP),所以可用路径跟踪算法求解。j-1
a-LLd
为了方便讨论式(2)的求解方法,不妨将其写成以下的数ijåikjkkk
L=k=1(9)
学形式:ijd
jj
min1xTQx-eTx式(9)中a是系数矩阵A中第i行第j列上的元素,j<i;i=2,
2ij
T3,…,n;j=1,2,…,i-1。L=0,j>i。L=1,j=i。矩阵D中
=0(5)ijij
x+v=c各元素的计算方法为:
x³0v³0
d=a
其中,xÎRn是n维变量。eÎRn是n维单位向量。aÎRn是1111
i-1
n维向量,a={1-1}。cÎRn是一个向量形式的惩罚因子。d=a-åL2d,i=23n(10)
iiiiiikkk
k=1
n´nn
QÎR是一个正半定、对称的系数矩阵。松驰因子vÎR。按行方式计算L和D各元素的串行方式如图1所示。从图
式(5)的Wolf对偶问题形式为:1可以看出,按行方式计算L和D中各元素有较强的串行计算顺
max-1xTQx+(e+s)Tx-wTv序,计算过程是从上至下,对于某一行而言又是从左到右计算。
2
-e-za-w-s=0(6)观察图1,结合式(9)和式(10)可以发现:在计算出L(i,j)元素后,L
w³0s³0z³0(i,j+1)和L(i+1,j)两元素虽然处在上下两行上,但是可以并行计
在用路径跟踪内点法求解原-对偶问题(5)和(6)时,每次迭算,因为计算所需要的数据均已经产生,不必一定要等到第i行计
代的修正量是通过求解一阶KKT条件导出的修正方程获得:算完后再跳去计算第i+1行逐个计算其中的元素。
e-Qx+za+w+sd
éQ-a-I-I0ùéùé11ù
éDxùêú
êúêTú
aT0000êDzú-axê¯ú
êúêúL®d
êDwú=c-x-v(7)ê2122ú
êI0000úêúêú
êúêDsúêμe-SXeúêú
êS00X0úêúêúêL®L®dú
ëDvû313233
ë00V0Wûëμe-WVeûêú
êú
式(7)的右端项从上至下不妨分别记为:r、r、r、r、êL®L®®Ldú
xzwsën1n2nn-1nnû
r。对于一个大规模的SVM训练集,方程组(7)系数矩阵的维
v图1用串行方法计算L和D中各元素的示意图
数较高,是一个大规模的线性方程组,直接求解此方程组代价根据式(9)和式(10),还发现:在利用a、a计算出L、d
ijiiijii
较大,成为SVM的学****瓶颈。可通过降维的方法,把方程组
后,由于A的对称性,所以a、a原位置可分别用于存储L、
(7)改写成以下形式:ijiiij
d元素,不必在内存中另外生成大型的L和D矩阵,对于一
Dv=r-Δx(8a)ii
w个大规模问题而言,可大幅节省内存开销,并且不会造成有用
Ds=X-1(r-SΔx)(8b)
s计算数据的丢失。
Dw=V-1(r-Wr+WΔx)(8c)
vw根据上述,可以利用MPI消息广播的思想来设计实对称
-1-1'
éQ-XS-VW-aùéΔxùérù矩阵A的LDLT并行分解子算法。假定A是n阶对称矩阵,并行
êú=êxú(8d)
TëΔzûr
ë-a0ûëzû计算工作站数目为p,一般p<<n。为了平衡负载,采用卷帘式存
其中,r'=r+X-1r-V-1(r-Wr)。
xxsvw储方案,把矩阵A中从第2行开始的行数据发送给工作站计算
首先求解方程组(8d)得到Δx、Δz,再直接代入式(8a)~相应的L和D元素。对于A中的第i行,计算出k=(imodp),
(8c)中求解出Δv、Δs、Δw。此时方程组(8d)的求解是SVM其中“mod”是求余数运算,即:把A的第i行计算任务和数据
学****效率的瓶颈,虽然它的规模相对于方程(7)已经降低,但分配给第k号工作站。完成图1一行中所有L、d元素的计
ijii
在大规模SVM训练集上它仍然是一个大型线性系统,需要进算,称为完成一个计算任务。服务器和计算工作站的并行算
一步寻找方程组(8d)的高效求解方法。观察方程组(8d),发法设计如下。
现方程组系数矩阵是一个实对称方阵,并且矩阵的各阶顺序对于服务器,其基于MPI消息机制的算法为:
2022011,47(12)ComputerEngineeringandApplications计算机工程与应用
步骤1接收调用者传入的A。把A的行列数及对角线元再代入式(8a)~(8c)中可直接求解出Dv、Ds、Dw,得出下一
素广播给所有的工作站。次迭代修正量:(DxkDzkDwkDskDvk)。
步骤2根据工作站的数量划分计算任务,把A中相应的步骤7计算步长stepLength。
行数据传递给工作站,分配完毕启动计算指令。步骤8计算新的迭代点:
步骤3生成一个线程侦听并存储工作站广播的L、dk+1k+1k+1k+1k+1kkkkk
ijii(xzwsv)=(xzwsv)+
元素,并存储在A中,接收完毕后返回L、D矩阵给调用者。stepLength´(DxkDzkDwkDskDvk)
对于一个计算工作站,其基于MPI消息机制的算法为:步骤9k=k+1
步骤1接收服务器广播的A行列数,在本地初始化一个步骤10enddo
零矩阵A。用稀疏矩阵形式存储接收到的A对角线元素。步骤11如果没有找到最优解,则给出学****失败提示并退
步骤2接收本工作站的计算任务,将相应的矩阵A数据出。如果找到最优解,则存储支持向量等信息。
存储在本地。
步骤3启动一个线程侦听其他工作站广播的L、d元
ijii5实验
素,并存储在本地A中。实验硬件环境:三台配置完全相同的PC机,CPUP4-
步骤4接收到计算指令后,启动计算线程,逐个取出任务(双核),1GB内存,其中一台作为服务器,另外两台作为并行
i,开始计算第i行上的L、d元素。计算工作站,以太局域网。并行计算借助
ijii100Mb/sMPImpi-
,计算L,广播L。Java软件包实现。用Java(SunJ2SE6)实现本文算法,并部
i1i1
=2toi-1分使用libSVMforJava的源代码实现SVM模型。算法中的
{sum=0;//累加器矩阵运算,例如矩阵求逆等,直接借助BLASforJava矩阵运
=1toj-1算软件包中的函数实现。SVM核函数采用RBF核函数:
{如果具备条件则计算t=LLd,sum=sum+t;2
kikjkkkkK(xy)=exp(-γx-y)(13)
否则等待条件。}RBF-SVM的主要参数C=1,γ=。
=(a-sum)/d,如果计算条件不满足则等
ijijjj选取4个UCI数据集BreastCancer(BC)、Splice(SP)、Ring-
待。在本地存储并广播L。
ijnorm(RN)、Nurnnery(NN)来测试本文算法的可行性。SVM
:}并行计算实验结果如表1所示。
步骤5计算d元素,如果条件不满足则等待。广播d。
iiii表1UCI数据集训练时间及加速比
步骤6如果还有其他计算任务,返回步骤4,否则结果计
训练时间/ms
数据集训练样本数加速比
算线程。串行并行

4带LDLT并行分解的大规模SVM训练算法SP**********.72
路径跟踪内点法迭代过程中的互补间隙为:

Gap=wTv+sTx(11)
在迭代的过程中,扰动因子μ®0,所以不妨将扰动因子在表1中,“训练样本数”列中的数据是从数据集中选出的
定义为:训练样本数目。“训练时间”列是SVM模型学****训练样本所花
Gap费的时间,单位是毫秒;其中的“串行”列是指在本文SVM训
μ=δk(12)
k+12n练算法步骤5中用逆矩阵直接求解(7),此时算法学****样本所
其中δÎ(01)是中心参数。花费的时间;“并行”列是指本文采用LDLT并行分解时,学****br/>每次迭代时,变量的修正量要乘上一个步长值stepLength,训练样本所花费的时间。“加速比”中的数据是串行训练时间
不妨定义步长为:除以并行训练时间所得结果。从表1的加速比上看,本文采用
xzwsv
stepLength=×max{1,-i,-i-i-i-i|两台计算工作站实现LDLT并行分解,SVM训练时间平均得到
DxDzDwDsDv
,训练样本较大时,问题规模变大,求解式(7)代
Dx<0Dz<0Dw<0Ds<0Dv<0}其中下标i是对应于向
iiiii价变大,此时并行计算的加速效果明显。加速比也同时说明,
量变量中的第i个分量。在使用路径跟踪内点法构造SVM学****算法时,求解修正方程
求解式(5)、(6)形式的路径跟踪算法设计如下:组(7)是一个重要的瓶颈,因此本文采用了LDLT并行分解算
00000
步骤1初始化变量(xzwsv),各向量大于0。中心法求解后,SVM的训练效率得到了改善。
参数:δ=,迭代收敛精度ε=10-4。迭代计数器k=0,最大表2数据是并行和串行SVM模型泛化能力的比较。在表
迭代次数kMAX=50。2中,“测试样本”列是测试样本的数目,测试样本和训练样本
步骤2用训练集和初始参数构造出SVM模型。不重复,用来测试SVM的泛化能力。“识别正确率”是指训练
步骤3dowhilek£kMAX后的SVM对测试样本的正确识别的能力,取值是训练后的
步骤4计算互补间隙Gap,如果Gap<ε,则输出最优解。SVM模型对测试样本正确识别数除以总测试样本数。表2比
步骤5计算扰动因子μ。
k+1较了libSVM、本文串行算法、本文并行算法所得到的SVM模
步骤6计算出式(8d)的系数矩阵A,调用LDLT并行计算型泛化能力。从表2实验结果上看,本文采用路径跟踪内点法
子算法分解A,得到L、D。利用L、D求解式(8d),得到Dx、Dz,(下转212页)