支持向量机

上图中2为划分超平面：

                      W^Tx+b=0

假设超平面能将训练样本真确分类，yi=1时W^Tx+b>0 yi=-1 时W^Tx+b<0,令1和3表达式为 W^Tx1+b=-1 和 W^Tx2+b=1

故两支持向量之间的距离为

                                W^T(x1-x2)=2

两边取范数：

                               ||W||||x1-x2||cosθ=2

而||x1-x2||cosθ就是两支持向量之间的距离d，所以

                               ||W||d=2

                               即d=2/||W||

欲找到最大硬间隔的距离，只需找到满足表达式的W和b，使b最大

                               max_w,b 2/||w||

                               约束为 yi(W^Txi+b)>=1

也等价于：

                               min_W,b 1/2||W||²-----1

                               约束为 yi(W^Txi+b)>=1

对1式使用拉格朗日乘子可得到其对应的对偶问题，其中拉格朗日乘子α_i>=0,所以1式的拉格朗日函数可以写成：

                             L(W,b,α)=1/2||W||²+∑_{m=1 to M}α_i(1-yi(W^Txi+b))

对上式中的W和b求偏导数：

                            ∂L(W,b,α)/ ∂W=0

                             ∂L(W,b,α)/ ∂b=0

得到：

                           W-∑_{m=1 to M}α_iyixi=0

                            ∑_{m=1 to M}α_iyi=0

将其带入拉格朗日函数得到问题的对偶问题：

                          max_α  ∑_{m=1 to M}α_i- ∑_{i=1 to M ∑j=1 to Mαiyi}α_iyiα_jyjxi^Txi

                          约束为 ∑_{m=1 to M}α_iyi=0

                                     α_i>=0

如何求得α_i SMO算法是求此类问题的算法，流程如下：

1 初始化所有α_i

2 选取其中两个α_i和α_j，并固定其他参数

3 重复第一和第二步，根据对偶函数和约束条件迭代得到α_i和α_j更新后的值，直到收敛    

上面所讨论样本在特征空间中是线性可分的，即存在一个超平面将不同类的样本完全分开，但是实际应用中的样本显然不是这样的，故现在引入软间隔的概念，软间隔允许某些样本不满足约束条件：

                      yi(W^Tx+b)>=1

故引入松弛变量ζ_i>=0，每一个样本对应一个松弛变量，反映样本对约束条件的不满足程度，其中C是惩罚项，C越大，表示对样本的重视程度高，是一个很重要的参数

将1式重写：

                         min_W,b 1/2||W||²+C∑_{i=1 to M}ζ_i

                        约束为 yi(W^Txi+b)>=1-ζ_i

                                 ζ_i>=0

使用拉格朗日乘子得到原问题的对偶问题，原问题的拉格朗日函数是：

                    L(W,b,α,ζ,μ)=1/2||W||²+∑_{m=1 to M}α_i(1-ζ_i-yi(W^Txi+b))+C∑_{i=1 to M}ζ_i-∑_{i=1 to M}ζ_iμ_i

 L(W,b,α,ζ,μ)对W,b,ζ求偏导数：

                          W-∑_{m=1 to M}α_iyixi=0

                           ∑_{m=1 to M}α_iyi=0

                           C=α_i+μ_i

将上面三式带入拉格朗日函数得到：

                          max_α  ∑_{m=1 to M}α_i- ∑_{i=1 to M ∑j=1 to Mαiyi}α_iyiα_jyjxi^Txi

                          约束为 ∑_{m=1 to M}α_iyi=0

                                     C>=α_i>=0

同样使用SMO算法可求得α_i

对于线性不可分的问题，引入将样本从低维空间映射到高维空间的映射函数Φ(x),使得映射到高维空间的样本线性可分

类似地，可以写出：

                        min_W,b 1/2||W||²-----1

                       约束为 yi(W^TΦ(xi)+b)>=1

其对偶形式为：

                       max_α  ∑_{m=1 to M}α_i- ∑_{i=1 to M ∑j=1 to Mαiyi}α_iyiα_jyjΦ(xi)^TΦ(xi)

                          约束为 ∑_{m=1 to M}α_iyi=0

                                     α_i>=0

Φ(xi)^TΦ(xi)是高维空间的内积运算，存在维度灾难问题，所以很难计算，现引入核函数K(xi,xj)=Φ(xi)^TΦ(xi)

将上式重写：

            max_α  ∑_{m=1 to M}α_i- ∑_{i=1 to M ∑j=1 to Mαiyi}α_iyiα_jyjK(xi,xj)

                          约束为 ∑_{m=1 to M}α_iyi=0

                                     α_i>=0

同样的有SMO算法求解α_i

下面说说核函数的选取标准：

              核矩阵K=[K(x1,x2),K(x1,x2),..(x1,xm);K(x2,x1),K(x2,x2),...(x2,xm);...;K(xm,x1),K(xm,x2),..,K(xm,xm)]是半正定的，即矩阵K的eig(K)>=0