Lecture9_SVM

1、SVMChapter 14主要内容 SVM最大间隔(margin)分类器对偶表示(Dual Representation)Hinge 损失回归中的SVM稀疏核模型 稀疏：只选择训练样本的子集 (Chapter 13 中 D=N) 通过L1 正则达到稀疏 稀疏向量机(Sparse Vector Machine) 通过自动相关性确定达到稀疏 (Automatic Relevancy Determination, ARD) 相关向量机(Relevance Vector Machine, RVM) 更稀疏 但非凸 通过损失函数 + L2 正则达到稀疏 支持向量机(Support Vector Mach

2、ine, SVM) 分类：Hinge Loss 回归：-insensitive Loss SVM 回顾正则化的经验风险最小： 分类：将负log似然损失用 hinge loss代替 回归：损失函数用 不敏感损失代替 解是稀疏的：用损失函数表达稀疏性而非先验21,NiiiJL y yww支持向量机(Support Vector Machine) 最大间隔准则：最大化两个类最近点之间的距离。这个距离被称为间隔(margin)。 边缘上的点被称为支持向量(support vectors)。我们先假设分类器是线性可分的。最大间隔准则 线性分类面： 则有 其中x到分类面的距离r T0fwxw xprwxx

3、w最大间隔准则 代入得到 当x=0时，原点到分类面的距离 TT0p0TTp0fwxrwxrwfrwxw xwww wwwxwTpp02T0fxwxww ww 00fwr 0ww线性判别函数 线性判别函数利用一个超平面把特征空间分隔成两个区域。 超平面的方向由法向量w确定，它的位置由阈值w0确定。 判别函数f(x)正比于x点到超平面的代数距离（带正负号） 当x点在超平面的正侧时， f(x) 0； 当x点在超平面的负侧时， f(x) 1 1 = 02 wC-SVM 等价于最小化 其中参数C控制间隔和松弛变量惩罚项之间的平衡 被误分的点的 ，因此 为被误分点的数目的上界，可视为训练误差 因此参数C可

4、视为控制最小训练误差和模型复杂度的参数2T01, subject to 1, 2iiiiiCywi ww xii1iC-SVM对偶 对应的Lagrangian为01T0111, ,2 1NTiiNNiiiiiiiiLwCy w ww ww xC-SVM KKT Conditions0001010000iTiiiTiiiiiiiiywyw w xw xC-SVM对偶 对Lagrangian求偏导数，得 上述结果代入Lagrangian，得到其对偶问题 与线性可分情况相同10NiiiiLywxw1000NiiiLyw0iiiLC 1111 ,2NNNiijijijiijQy yx xC-SVM对偶

5、 最大化目标函数 但限制变为 最后的决策函数形式同线性可分情况100NiiiiyC 1111 ,2NNNiijijijiijQy yx x的稀疏性 与线性可分情况类似，一些数据点 被正确分类，在支持超平面之外，对预测没有贡献 对 的点，必须满足 若 ， 则 ，位于支持平面/边界上 若 ，则 （位于支持平面/边界里面，或 （被误分）0i0i01Tiiiyw w xiC0,0iiiC1i1iQP的计算 最流行的SVM训练算法： SMO (sequential minimal optimization ) 坐标下降法 在SVM中，因为 ，所以不能单独改变一个 ，而是每次每次选取一对 做优化,ij 0

6、*00wLy1i损失函数 在C-SVM中， 当 其他点： 因此目标函数 可写成 其中 起到C的作用。该损失函数称为Hinge Loss2211T011NNiiiiiiyyww xwwT01,0iiiyww xT01iiiyw w x212iiCwy与Logstic回归之间的关系 在Logistic回归中，令 对应的标签的概率为 则负log似然函数为损失函数 再加入二次正则项，得到正则化的Logistic回归 与SVM的目标函数相比，只是损失函数不同21,NnlliiiregularizerLyw,log| ,log 1 expnllLyp yy x w1, 1iy |,()iiiip ysig

7、m yx w1 exp1|,1loglog1|,1 expexpTiiiTTiiiTiip yfp y w xx wxx ww xw xw x损失函数 Hingle Loss和logstic误差均可视为是分类误差的近似ySVM for 回归 insensitive loss： 误差较小时不惩罚 目标函数为 亦可写成 为凸函数，但不可微360,if yyLy yyyotherwise21,NiiiJLy yww211,2NiiiJCCLy ywwSVM for 回归(cond.) 实际应用时，再加入松弛变量，用于表示每个点允许在管道外的程度 则目标函数变为 约束为211,2NiiiJCCwwii

8、iiiiyfyfxx0,0iiSVM for 回归(cond.) 目标函数变为 可以证明最优解为： 预测为： 利用kernel trick 核化线性SVM：即用核函数 代替点积 ：211,2NiiiJCCww1Niiiwx 001NTTiiiywwxw xx x 01,iiiNkywxxx,ik x xTix xSome Examples LIBSVM applet: .tw/cjlin/libsvm/ 39RVM vs. SVM 当性能相当时，RVM看起来比SVM的模型更稀疏，并且能给出预测信度的度量 另外，RVM 的机制更通用， 可以用于回归、两类分类和多类分类 可以与任意类型的基函数（不必是以数据为中心的PSD核）一起使用 RVM 能自动估计超参数 SVM 通常采用交叉验证的