支持向量机教材

支持向量机北京10月机器学习班邹博2014年11月9日2/50谱聚类历史遗留问题最小化f’Lf，为什么等价于最小特征值和特征向量？其不满足f⊥1的条件，为什么？特征向量v里的元素是连续的任意实数，能否具体点？求拉普拉斯矩阵的前K个特征值，再对前K个特征值对应的特征向量进行K-means聚类，对特征向量进行K聚类的目的是什么？最小的系列特征向量对应着图最优的系列划分方法，怎么理解向量划分图？什么是NP问题？3/50解答其不满足f⊥1的条件，为什么？4/50切割代价与f’Lf的关系5/50解答6/50解答特征向量v里的元素是连续的任意实数，能否具体点？求拉普拉斯矩阵的前K个特征值，再对前K个特征值对应的特征向量进行K-means聚类，对特征向量进行K聚类的目的是什么？L是实对称正定阵，那么，L的特征向量u，是实向量。即：u的每个元素都是实数。这其实不是我们想要的。如果计算L的次小特征向量v，得到的v中的元素都只能取-1，+1，那么，直接就可以用-1，+1将原始样本聚类成两簇了。（可惜现实中不是这样子）所以，必须将特征向量v根据是否大于0（或其他定值）分成两部分，进而把原始样本聚类成两簇。实践中，往往不是只选择次小的特征向量，而是选择前K个特征向量进行K均值聚类。7/50解答最小的系列特征向量对应着图最优的系列划分方法，怎么理解向量划分图？一般翻译成“连通分量”。什么是NP问题？有些问题，目前人们从未找到过多项式级的时间复杂度，我们把这种问题，叫做NP问题。8/50复习：对偶问题一般优化问题的Lagrange乘子法Lagrange函数对固定的x，Lagrange函数L(x,λ,v)为关于λ和v的仿射函数9/50复习：Lagrange对偶函数(dualfunction)Lagrange对偶函数若没有下确界，定义：根据定义，显然有：对∀λ0，∀v，若原优化问题有最优值p*，则进一步：Lagrange对偶函数为凹函数。10/50另一种表述原始问题引入拉格朗日乘子：原始问题：有如下结论：,,max0:,xLxipljxhkixctsxfiiRxn,2,1,0,2,1,0..minljjjkiiixhxcxfxL11,,原始问题的可行域原始问题的可行域xxxfxp11/50主要内容和目标理解支持向量机SVM的原理和目标掌握支持向量机的计算过程和算法步骤对线性不可分的数据，理解软间隔最大化的含义了解核函数的思想了解SMO算法的过程12/50线性分类问题13/50输入数据假设给定一个特征空间上的训练数据集T={(x1,y1),(x2,y2)…(xN,yN)}，其中，xi∈Rn，yi∈{+1,-1}，i=1,2,…N。xi为第i个特征向量，也称为实例，yi为xi的类标记；当yi=+1时，称xi为正例；当yi=-1时，称xi为负例。(xi,yi)称为样本点。14/50各种概念线性可分支持向量机硬间隔最大化hardmarginmaximization硬间隔支持向量机线性支持向量机软间隔最大化softmarginmaximization软间隔支持向量机非线性支持向量机核函数kernelfunction15/50线性可分支持向量机给定线性可分训练数据集，通过间隔最大化或等价的求解相应的凸二次规划问题学习得到的分离超平面为wx+b=0，相应的分类决策函数f(x)=sign(wx+b)该决策函数称为线性可分支持向量机。16/50二维平面上线性分类问题17/50线性可分支持向量机18/50函数间隔和几何间隔给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi,yi)的函数间隔为：平面法向单位化的函数间隔，即几何间隔19/50最大间隔分离超平面20/50最大间隔分离超平面Niwbxwwytsiibw,2,1,..max,21/50最大间隔分离超平面Nibxwytswiibw,2,1,ˆ..ˆmax,22/50最大间隔分离超平面Nibxwytswiibw,2,1,1..1max,Nibxwytswiibw,2,1,1..21min2,23/50拉格朗日乘子法原问题是极小极大问题原始问题的对偶问题，是极大极小问题,,minmax,bwLbw,,maxmin,bwLbw24/50拉格朗日乘子法将拉格朗日函数L(w,b,α)分别对w，b求偏导并令其为0：25/50拉格朗日乘子法将上式带入拉格朗日函数L(w,b,α)中，得到：26/50继续求minw,bL(w,b,α)对α的极大27/50整理目标函数：添加负号NiyytsxxyyiNiiiNiiNiNjjijiji,,2,1,0..21min111128/50线性可分支持向量机学习算法构造并求解约束最优化问题求得最优解α*NiytsxxyyiNiiiNiiNiNjjijiji,,2,1,00..21min111129/50线性可分支持向量机学习算法计算求得分离超平面分类决策函数NijiiiiNiiiixxyybxyw1*1***0**bxw**bxwsignxf30/50举例给定3个数据点：正例点x1=(3,3)T，x2==(4,3)T，负例点x3=(1,1)T，求线性可分支持向量机。31/50目标3,2,1,00..141242225182121min321321323121232221111itsxxyyiNiiNiNjjijiji32/50将约束带入目标函数，化简计算将带入目标函数，得到关于α1α2的函数：对α1α2求偏导并令其为0，易知s(α1,α2)在点(1.5,-1)处取极值。而改点不满足条件α2≥0，所以，最小值在边界上达到。当α1=0时，最小值s(0,2/13)=-2/13当α2=0时，最小值s(1/4,0)=-1/4于是，s(α1,α2)在α1=1/4，α2=0时达到最小，此时，α3=α1+α2=1/4321212122212122102134,s33/50分离超平面α1=α3=1/4对应的点x1,x3是支持向量。带入公式：得到w1=w2=0.5，b=-2因此，分离超平面为分离决策函数为NijiiiiNiiiixxyybxyw1*1***02212121xx2212121xxsignxf34/50线性支持向量机若数据线性不可分，则增加松弛因子ξi≥0，使函数间隔加上松弛变量大于等于1。这样，约束条件变成目标函数：iiibxwy1NiibwCw12,21miniiibxwy1NiibwCw12,21min35/50线性SVM的目标函数NiNibxwytsCwiiiiNiibw,2,1,0,2,1,1..21min12,,36/50拉格朗日函数拉格朗日函数对w,b,ξ求偏导NiiiNiiiiiNiibxwyCwbwL1112121,,,,0iiC37/50带入目标函数将三式带入L中，得到对上式求关于α的极大，得到：Ci0NiiNiNjjijijibwxxyybwL111,,21,,,,minNiCytsxxyyiiiiNiiiNiiNiNjjijiji,2,10000..21max1111，38/50最终的目标函数整理，得到对偶问题：NiCytsxxyyiNiiiNiiNiNjjijiji,2,1,00..21min111139/50线性支持向量机学习算法构造并求解约束最优化问题求得最优解α*NiCytsxxyyiNiiiNiiNiNjjijiji,,2,1,00..21min111140/50线性支持向量机学习算法计算注意：计算b*时，需要满足0αjC求得分离超平面分类决策函数NijiiiiNiiiixxyybxyw1*1***0**bxw**bxwsignxf41/50核函数可以使用核函数，将输入空间映射到特征空间，从而，使得原本线性不可分的样本可以在特征空间可分。在实际应用中，往往依赖先验领域知识才能选择有效的核函数多项式核函数高斯核函数字符串核函数如：两个字符串的最长公共子序列LCS(X,Y)42/50核函数影射43/50SMO序列最小最优化SequentialMinimalOptimization有多个拉格朗日乘子每次只选择其中两个乘子做优化，其他因子认为是常数。关于这两个变量的解应该更接近原始二次规划问题的解。44/50SMO考察目标函数，假设α1和α2是变量，其他是定值：CyyytsiNiii0..32211NiiiiNiiiiKyyKyyyyKKW322231112121212222211121,2121,min21NiCytsxxKyyiNiiiNiiNiNjjijiji,2,1,00..21min111145/50二变量优化问题46/50SMO的迭代公式迭代公式：NiiiibxxKyxg1,2,1,,1iybxxKyyxgEiNjijjjiii47/50SMO算法1.取初值α(0)=0，令k=02.选择优化变量α1(k)，α2(k)，解析求解两个变量的优化问题，求得最优解α1(k+1)，α2(k+1)，更新α为α(k+1)3.若在精度ε范围内满足退出条件(下一页)，则转4；否则，k++，转24.取α=α(k+1)48/50退出条件NjijjjiiiiiiiiiiNiiibxxKyxgCxCxxxgyNiCy11,,10,10,1,2,1,0049/50参考文献统计学习方法，李航著，清华大学出版社，2012年(对偶问题)SupportVectorMachines,CharlieFrogner,2011SequentialMinimalOptimization:AFastAlgorithmforTrainingSupportVectorMachines,JohnC.Platt.1998SupportVectorMachines,AndrewW.Moore,200150/50感谢大家！恳请大家批评指正！