机器学习和生物信息学实验室联盟

标题: SVM学习笔记（转载） [打印本页]

作者: zouquan 时间: 2012-3-14 08:42
标题: SVM学习笔记（转载）
首先假设样本线性可分，此时的目标是求解最优分类面。
样本需满足的条件公式为y*(wx+b)>=δ，y取值为{-1,1}，分别表示正负样本。
优化的目标函数为max δ ，也就是使得样本距离最大的分类面。
如果w不做约束，则对于任何x，只要w线性增长，则δ可取更大的值；而w线性变化，不会影响分类面形状。因此约束||w||=1。
也就是要求||w||=1条件下的max δ最优化问题。但此时w的解空间是在一个圆周上的点，函数非凸，无法逼近到最优解上。
因此将最优化问题进行转化，变为max δ/||w||，同时约束条件为所有的样本：y*(wx+b)>=δ。
上面的表述，其实是最优化问题的一般性表述，设置一个优化目标，然后添加各种约束条件。
然后对这个优化目标做了转化，设δ=1，则max δ/||w|| 问题等价于 min ||w||。约束条件为y*(wx+b)>=δ。
此时||w||虽然是个圆形区域，圆形区域是非凸的。但由于有约束条件的存在，每个约束条件都是一个分割面，这些分割面将圆形区域切分为凸型区域。然后就可以在这个凸函数上求解最优化函数了。可以使用梯度下降法，也可以使用一些现成的软件。

拉普拉斯算子：
如果只是等于0的约束，则分别使参数的导数为0，就能求到最优解。
公式表示为：L(w, β)=f(w)+∑β*h(w)。其中f(w)为最优化目标函数，h(w)为约束条件，每个w都使得h(w)=0.
更一般的情况，拉普拉斯算子可表示为：L(w, α, β)=f(w)+∑α*g(w)+∑β*h(w)。其中g(w)<=0。是一种新的不等式约束条件。
令θp(α, β)=max(α>=0, β) L(w, α, β)，其中α,β为变量，并且α>=0,。则当 L(w, α, β) 满足约束条件时，θp(w)=f(w)；不满足约束条件时，θp(w)=∞。
此时：min(w) f(w)=min(w) θp(w)。

此处引入对偶问题（dual problem）
令θd(α, β)=min L(w, α, β)，d*=max(α>=0, β) min(w) L(w, α, β)
则一般情况下，d*<=p*。在大多数的实际应用中，可认为d*=p*。此时原始问题和对偶问题有相同的解。可利用对偶问题来求解原始问题。

KKT互补条件
在求解对偶问题时，会用到KKT互补条件。KKT条件共有5个，分别是：
δ L(w, α, β) / δ w = 0。也就是对w求偏导为0。
δ L(w, α, β) / δ β = 0。也就是对β求偏导为0。
α*g(w)=0。
g(w)<=0。
α>=0。
通常情况下α*g(w)=0，意味着α≠0等价于g(w)=0。

回到原始的目标，min f(w) = min (1/2)*(||w||)^2, s.t. gi(w*xi+b)>=1
转变为 g(w, b) = -gi(w*xi+b)+1<=0，
利用KKT条件中的第3个，α>0 => g(w, b) = 0. 这个式子意味着g(w, b)=0的样本xi距离分类面的距离为1，这些样本为支撑样本(support vector)。

求解原始的最优分类面问题，min L(w, b, α) = (1/2)*(||w||)^2 - ∑α*(gi(w*xi+b)-1)
对偶问题 θd(α) = min(w, b) L(w, b, α)
求解对偶问题，也就是让δ L(w, b, α)/ δ w = 0，δ L(w, b, α)/ δ b = 0
这里的解为 δ L(w, b, α)/ δ w = w - ∑αi*yi*xi = 0.
上式等价于 w = ∑αi*yi*xi ，也就是说w是样本x的线性组合。
δ L(w, b, α)/ δ b = -∑yi*αi = 0
将解出的w带入原始的式子，L=∑αi-(1/2)*∑(i)∑(j)yi*yj*αi*αj*<xi, xj>=W(α)
此时的对偶问题为 max W(α), st. αi>=0, ∑yi*xi=0
求解max W(α), 也可以使用偏导等于0的方法。

当求出α之后，就可以求出w，之后就可以求出b。
b = (max(yi=-1) (w*xi)+min(yi=1) (w*xi))/2

整个求解过程为先根据对偶问题，求出w的α表达式，然后根据对偶问题求出α，进而带入w表达式求出w，最后求出b。

关于最有间隔分类器的另一种表述为：
w = ∑αi*yi*xi
预测函数h(x)=g(w*x+b)
w*x+b=∑αi*yi*<xi,x>+b
也就是说预测函数可以被表示为新输入的样本与训练样本的内积之和。

一些心得：
1、学习笔记很重要，可以把重要的概念知识点串起来
2、算法的整体逻辑要理清，要明白重要的求解步骤
3、有一些概念或者关键步骤，老师可能会跳过，利用笔记可以详细思考下背后的原理
4、一节75分钟的课程，前后陆续看了4、5天，在中文翻译和笔记的帮助下，才算学懂。对于复杂的知识不能求快，笨鸟慢飞

作者: zouquan 时间: 2012-3-14 15:58
http://v.163.com/movie/2008/1/C/6/M6SGF6VB4_M6SGJVMC6.html

视频教程

作者: xmubingo 时间: 2012-3-14 16:12
这第一帖的内容真不是人看的....完全就是数学数学，乐义应该可以承受。

作者: 小疯纸一枚 时间: 2012-7-11 14:18
圆形区域怎么会是非凸的呢

……是凸集吧？？？？

作者: tangzk 时间: 2012-10-5 16:57
本帖最后由 tangzk 于 2012-10-5 17:03 编辑

这两天重新在看SVM，这里推荐一些不错的博文。
[attach]1052[/attach]
这篇文章在基础知识部分都讲得不错，不过少了有求解二次规划以及KKT条件的一些内容，上面邹老师已经补充。上面没有说及的是关于结构风险最小化的原理，在这篇博文中有讲到。
不过关于w = ∑αi*yi*xi怎么出来的没怎么看懂，导致和后面的kernel结合起来的时候没理解，需要再看。其实发现看完KKT条件后，support vector的概念及SVM的优势（只有支持向量的ai为非0）就清楚多了。再过渡到松弛变量，那是为解决线性不可分问题，加入软间隔的自然后果。
另外kernel函数还需要再仔细学习下，虽说是个线性变换，但是网上的几个例子居然都没有看懂，汗。
还有SMO算法我就只能暂时放弃了，……

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)