svm_3d_cropped-750x410.png
清白就是你想的意思，svm就是为的分个清白。譬如男女两个类，一个类用+1表示，一个用-1表示，然后拿个样本来（比如有两个特征，身高和胸的大小），然后分出男女。
svm 属于原理很简单，推导很复杂，核心就是找一个分割超平面，然后把数据分成两个类别。当然我们一般只从二维说起，为了简单。
但是正文开始前，我们要介绍点预备知识，当然这个点也就一个——有约束条件下求函数的极值。解决的办法是拉格朗日乘子法。
1.约束是等式的情况
max f(x,y,z)
s.t. g(x,y)=0
例如有个二元的函数f(x,y)=(x+1)*(y+2),它有一个约束x^2+y^2=1即x^2+y^2-1=0,怎么求在这个约束下f(x,y)的极值？现在拉格朗日乘数法上线，方法很简单：
- （1）构造一个新的函数F(x,y,r)=f(x,y)+r*g(x,y)
此例子是F(x,y,r)=(x+1)*(y+2)+r(x^2+y^2-1)
其中的那个小r就是乘子。
- （2）分别求F(x,y,r)对x,y,r的偏导，然后另其等于零，这样可列出下面几个式子：
F对x的偏导数：2xr+y+2=0
F对y的偏导数：2yr+x+1=0
条件： x^2+y^2=1
三个未知数，三个方程，联立这三个式子就可以解得极值在点（0.817,0.576），其函数值是4.68
2.约束是不等式的情况
如果约束是不等式，比如
max f(x,y,z)
s.t. g(x,y)<=0
这种情况我们可以加个数的平方，将不等式变成等式：
g(x,y)+l^2=0 (本身比零小，我加个正数就可以等于零了），然后处理如上：
-
(1) 构建函数
F(x,y,z,r,l)=f(x,y,z)+r*(g(x,y)+l^2) -
(2) 求个变元的偏导，另其等于零
-
(3) 联立方程组，加条件就可以解出来了（虽然复杂点，其实和上面一样）
好了，正文开始。首先是我们要先表示一条直线
我们用Ax+By+C=0来表示直线，当然我们可以换下名字用w1*x1+w2*x2+b=0来表示，一个意思。
然后令w的转置为[w1,w2](列向量不好打，就用转置的行向量表示），同样x的转置为[x1,x2].
然后上面的直线可以用矩阵表示为：
wT*x+b=0 (二维，三维，四维一样的）。
其次我们来表示一个点到这条直线的距离
回想一下，高中一个点到直线的距离：|Ax0+By0+c|/(A^2+B^2)^1/2，按我们的符号，分子其实就是|w1*x1+w2*x2+b|,分母就是(w1^2+w2^2)开根。写成矩阵形式就是|wT*x+b|/||w||.
当然了分子有个讨厌的绝对值，我们用对应样本分类（+1或者-1) 乘以这个分子，就是yi*(wT*x+b)/||w||,这样就把绝对值去掉了。这个式子叫做一个点到直线的几何间距（其实就是点到直线的距离）
因为我们不知一个能用的数据点，我们有大N个训练的样本数据，每一个点都有一个这样的几何距离，我们定义：
数据集中这些点的几何距离，挑出其中最小的那个，我们把它叫做数据集的几何间距：
min {yi*(wT*x+b)/||w||}
到这里，我们可以定义svm是来干什么的，我们目的要找到一个分割超平面，就是wT*x+b,所以我们要确定w和b,确定的方式就是
求w,和b,使得数据集的几何间距最大：
max(w,b) {数据集的几何间距}
又因为数据集中的每个点应该大于等于数据集的几何间距（因为定义是最小的），所以需要加上约束 yi(wTx+b)/||w||>=数据集的几何间距=min {yi(wTx+b)/||w||}
我们先给数据集的几何间距做个小调整，因为求这个间距时，w是确定的，所以可以从min里提出来，变成1/||w||min {yi(wT*x+b)}
好列一下这两个式子：
max(w,b) {数据集的几何间距}
s.t. yi*(wT*x+b)/||w||>=数据集的几何间距=1/||w||*min {yi*(wT*x+b)}
到这里就要有点技巧了，我么刚刚定义了几何间距，其实就是点到直线的距离，现在，我们定义另一个距离：yi(wTx+b) 为函数间距。
函数距离呢，它也可以相对的表示点距离直线的距离，只不过，如果你缩放下w,b发现，函数距离就变了，可是，缩放w,b,分割的直线却不变。
什么意思呢？我们找个小r,则w'=r*w,b'=r*b,这样你会发现，直线是不变的（直线无限长吗），但是函数间距却变了，换句话说：你可以通过调整小r让函数距离等于任何值，这个时候变换后的w',b'和原来的直线没什么不同，所以我们调整小r,想办法让yi(wTx+b)等于1.
然后对上面的式子，我们用函数间距来表示几个间距（就除以个w的长度），假设数据集的函数间距为小v,上面的式子变成了以下：
max {v/||w||}
s.t. yi*(wT*x+b)/||w||>=v/||w|| 两边乘以个||w||,不等式就变成了yi*(wT*x+b)>=v
注意，我们上面说了，我们可以通过缩放w,b是函数间隔唯一，并且直线不变，好了，我们缩放之，是v等于1,因为缩放后直线不改，我们还用w,b表示，然后式子变成了：
max {1/||w||}
s.t. yi*(wT*x+b)>=1
现在该捡起开篇说的限制条件下求函数的极值了，终于一个问题了……，当然为了好搞，我们再变化下
求max {1/||w||} 等价于求 min { 1/2*||w||^2} ,就是分数倒一下，分母变分子，为什么这样？当然是用拉格朗日乘子法时，好求偏导了：
min { 1/2*||w||^2}
s.t. yi*(wT*x+b)>=1
好，我们下面开始用拉格朗日乘子法
- （1）限制条件把不等式变成等式
这个好办，同时两边乘负一，变成小于等于，然后我们再加上个小l的平方就可以等于0了
s.t. yi*(wT*x+b)>=1 => 1-yi*(wT*x+b)<=0 => 1-yi*(wT*x+b)+l^2=0
好了，再列一遍：
min { 1/2*||w||^2}
s.t. 1-yi*(wT*x+b)+l^2=0 （注意这个条件有大N个,因为我们有大N个点
- （2） 构造
F(w,b,r,l)=1/2*||w||^2+sum{ri*(1-yi*(wT*x+b)+l^2)}
其中，变量是w,b,r,l,然后所有点我们都知道，所以x,y都是知道的是常量。sum{ri*(1-yi*(wT*x+b)+l^2)}就是
r1*(1-y1*(wT*x1+b)+l1^2 + r2*(1-y2*(wT*x2+b)+l2^2 + r3*(1-y3*(wT*x3+b)+l3^2 + ... + rM*(1-yN*(wT*xN+b)+lN^2
当然我看网上的都没有l^2的这个部分，我们也去掉，不影响。即：
F(w,b,r,l)=1/2*||w||^2+sum{ri*(1-yi*(wT*x+b))}
- （3）对F求w,的偏导，对F求b的偏导数。这个……比如你问我有||w||这个偏导数怎么求，因为w是个列向量，你要实在不会，假定是二维及wT=[w1,w2]
然后1/2*||w||^2就变成了1/2*(w1^2+w2^2) 然后这个部分对w1求导就是w1,对w2求导就是w2,然后你就知道了1/2*||w||^2这个部分对w求导的结果就是w……
都是辛苦活，不会了就按二维的试。
结果可以得到
1. F对w求偏导等于0=> w=sum{ri*yi*xi}
2. F对b求偏导等于0=> sum{ri*yi}=0
- (4) 把得到这两个结果代入原方程，可以得
F(w,b,r)=1/2*sum{ri)-1/2*||w||^2=1/2*sum{ri}-1/2*sum{ri*rj*yi*yj*xiT*xj}
即：F(r)=1/2*sum{ri}-1/2*sum{ri*rj*yi*yj*xiT*xj}
这样就消掉了w和b,然后只有r了
- (5) 现在的问题变成了另一个约束条件下求极值的问题
即：求max F(r),然后约束条件是sum{ri*yi}=0和r本身大于等于0，即：
max F(r)=1/2*sum{ri}-1/2*sum{ri*rj*yi*yj*xiT*xj}
s.t. sum{ri*yi}=0 and ri>=0
- (6) 好了，到这里，这个规划问题可以直接从数值方法计算求解了，也是各种svm书上推导的结果了
打完收工
注：因为没法打连加符号，所以用
sum{ }表示。因为没法打出平方或者开根用^2和^1/2表示
用||w||来表示w向量的二次模，即||w||=(w1^2+w2^2+w3^2+...+wn^2)^1/2
用min{ } 和 max{ }表示求其最小最大
网友评论