1、SVM 算法与实现2011 11-18报告内容SVM简介求解算法-SMO优化算法多分类问题系统演示wx0w=1x0w=Separating Surface:A+A-SVM算法特点SVM有如下主要几个特点：(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；(3)支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。因此，模型需要存储空间小，算法鲁棒性强；(4)无序任何前提假设，不涉及概率测度；(1)SVM算法对大规模训练样本难以实施由于SVM是借助二次规划
2、来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法(2)用SVM解决多分类问题存在困难经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SV
3、M固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。问题提出线性可分的分类问题：（令黑色的点=-1，白色的点=+1）所以当有一个新的点x需要预测属于哪个分类的时候，我们用sgn(f(x)，就可以预测了，sgn表示符号函数，当f(x)0的时候，sgn(f(x)=+1,当f(x)ijSMO算法SMO算法由Microsoft Research的John C.Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。第一步选取一对参数，选取方法使用启发式方法（Maximal violating p
4、air）。第二步，固定除被选取的参数之外的其他参数，确定W极值。SMO算法设我们选取了初始值满足了问题中的约束条件。接下来，我们固定，这样W就是和的函数。并且和满足条件：由于其余参数都是已知固定，因此为了方便，可将等式右边标记成实数值。SMO算法进而lililjjijijiixxKyyaW111),(21)(lililjjijijilijjijlijjijixxKyyxxKyyxxKyy33112211121),(21),(21),(21liliiiiixxKyyxxKyyxxK33111212121111121),(21),(21),(21liiiixxKyyxxKxxKyy32222222
5、212121),(21),(21),(21liljjijijiliiiiliiiixxKyyxxKyyxxKyy3332223111),(21),(21),(21其中：目标函数：求偏导：带入w,v：求得：参数的求解最终参数的解为：其中：和Cnew10Cnew20？a的取值范围当a1和a2异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1。如下图：横轴是 ，纵轴是 ，和 既要在矩形方框内，也要在直线上，因此 同理，当 和 同号时a2a1CCa1-a2=E(0,-E)(C,C-E)参数求解参数计算：参数b计算：？b的求解设 在界内，则有，带入上式得：两边同乘以 ，得b的求解 在
6、界内，则 在界内，则 、都在界内，则情况1和情况2的B值相等，任取一个；都不在界内，则 取值为情况1和情况2之间的任意值。问题？算法如何终止？对于SMO算法，其中的两个参数如何选择呢？随机？启发式规则一个自然的想法是那些违反KKT最严重的点，他们对间距贡献最大，因此可以通过该启发规则来完成调整参数的选取。（并且此种启发规则计算量小）停止条件1满足KKT条件KKT条件：|,00|,00|,0)(*CajjCajjajjybadjjjjj|,0|,0|,)(-*CajjybCajjybajjybadjjjjjjj1y|,0|,0|,)(y-j*j，当CajjbCajjbajjbadjjjj1y|,
7、0|,0|,)(y-j*j，当CajjbCajjbajjbadjjjj 1,|0|1y,0|,1,|0|1y,0|,)(y-j*j*jjjjjjjjjjyCajCajajjbyCajCajajjbad并设代入得：左移：分别乘以yi：统一：1,|0|1y,0|,1,|0|1y,0|,)(y-j*j*jjjjjjjjjjyCajCajajjbyCajCajajjbad等价于：bbb满足：不满足：0)()(*aMam如果对于：可以判断：停止条件2停止条件3启发式选择算法其他求解方法选块算法分解算法分解算法工作集的选取相关软件问题On the Algorithmic Implementation of
8、Multiclass Kernel-based Vector MachinesGrammer&singer 多分类支持向量机基本思想Grammer-singer多分类支持向量机的出发点是直接用超平面把样本空间划分成M个区域，其中每个区域对应一个类别的输入。如下例，用从原点出发的M条射线把平面分成M个区域，下图画出了M=3的情形：问题描述设训练点集为：则存在着 使得训练点满足下式：lnllyRyxyxT)(),(),.,(11likYyRxini,.,1,.3,2,1,kwwww,.,321,.,3,2,1,1),(),(iiriyykrxwxwi引进记号：kjkjjk,0,1,.,3,2,1,
9、1),(),(krxwxwyririyi1),(iryxwwi1),(iryxwwirywwi2213232221wwwwwwDksrsrww2最优化问题根据最大间隔原则：其中：，进而最优化问题可转化为：,1),(),(.yririyxwxwtsiksrsrww2minlikr,.,3,2,1;,.,3,2,1krrksrsrwkww122,1),(),(.yririyxwxwtsikrrw1221minlikr,.,3,2,1;,.,3,2,1最优化问题添加松弛变量其中：,1),(),(.iyririyxwxwtsiliikrrCw11221minlikr,.,3,2,1;,.,3,2,10
10、1max,iiyryirrixwxwii引入拉格朗日函数likriryiriyriiixwxw11,1),(),(liikrrkCwwwwL1122121),.,(0)(,1,1,1,ilryiirikjjilryiiirirxaaxawLwilryiiriilryiirikrrirxaxaaw,1,1,1,)(01,kjjiaCLCakjji1,iliriryilryiriilryirirxaCxaxaCwiii)()(1,1,1,，设riryriaCi,ilirirxw1,则 likyrrriliijyrlikyrrriliijrylikrriliijrylikrriliijljijrkr
11、irliijrylikrriliijljijrkrriryliijrylikrriijljjrlikrriliijljjyliijilikrrirylikrriirlikrriliiyliiliijlikrrryiriyriliiliijiiiiiiiiiiiiiiiiiiiiiiixxxxxxxxxxxxCxxxxxxCxxxwxwCCxxxwxwCxx1,1,1j1ii1,1,1j1ii,11,1j1ii,11,1,1,1j1ii,11,1,1,1j1ii,11,1,11,11,1j1ii11,11,11,111j1ii11,11j1ii),(21-0),(21-)1(),(21-)1()
12、,(),(21)1(),()(),(21)1(),(),(),(21)1(),(),(),(211),(),(),(21，),.,(21kwwwL对偶函数0.)1(),(21max1,1,1,1,1,krrilirykrirliijljijrkrirtsxxii如何优化求参？样本与样本间的参数无约束lpiiyilpjpiijjiylpiiipippppplpiiyiyplpjpiijjilpiiippipppplirykrirliijljijrkrirppiiiiiiKKKKKKxxQ,1,1,1,1,1,1,1,1,1),()1(),(2111),(),(),(21)1(),(21)(BAQ
13、),(21)(iylpiiipiKB1,1,ppKA 由此，进一步可优化如下目标函数ABBABABABAQ2)()(21),(21)(1-1D1and.21)(min2vDvtsvvQviyABDABv1,带入常数凸二次优化问题)11D1()(21)(L12vDvavvkiiii0Liiavv0)(iiiDva,miniiDv构建拉格朗日函数求偏导：iiaviiDv iiaviiDv?,min但是iiDv 关于的等式可以用fixed-point算法1,min11krrkrrDD1-1D1v111krrkrrDv但有约束但如何构建x=f(x)?rrrDDD,max,min1),max(11krrkrrrDDDkDkkrr1,max11=f()1,min11krrkrrDD代入求解算法总算法伪代码总结4月24日yode补充：这个其实是不实用的,因为将所有的sample放在一个优化函数里面，这样的训练时间非常长，几乎无法忍受的地步，test时间还是可以的。小规模数据集可以考虑，如果数据集规模很大，建议不要使用这个。一些问题谢谢！
