SVM支持向量机算法原理

落日映苍穹つ 2022-05-09 09:56 253阅读 0赞

### 特点概述 ###

*  优点： 泛化性能好，计算复杂度低，结果容易解释
 *  缺点： 对参数和核函数选择敏感，原始分类器不加修改仅适用于二分类问题
 *  适用数据类型：数值型和标称型数据

### 口头描述 ###

SVM认为可以使用一个超平面将数据集分隔开来，距离超平面最近的点称为支持向量，SVM的目标是确定超平面使得支持向量到它的距离最大化。求解的算法有很多种，一般使用SMO算法， 它将大优化问题转化为小优化问题进行求解。

### SVM推导及SMO算法 ###

假设这个超平面由  ω T x + b = 0 \\omega^Tx+ b =0 ωTx\+b=0确定。其中 ω \\omega ω和 b b b是模型参数，分类label为 y y y因为超平面正的一侧 ω T x + b > 1 \\omega^Tx+b>1 ωTx\+b>1且label为1，而另一侧两者为-1，所以有 y i ( ω T x i + b ) ≥ 1 , i = 1 , 2 , . . . m . \\quad y\_i(\\omega ^Tx\_i +b)\\ge 1, \\quad i=1,2,...m. yi(ωTxi\+b)≥1,i=1,2,...m.。两个异类支持向量到超平面的距离之和为 γ = 2 ∥ ω ∥ \\gamma=\\frac\{2\}\{\\|\\omega\\|\} γ=∥ω∥2。我们要确定的就是这两个参数 ω \\omega ω, b b b，使得支持向量的 γ \\gamma γ最大。  
化简可得：  
  
 m i n 1 2 ∣ ∣ ω ∣ ∣ 2 min \\quad\\frac\{1\}\{2\}\\lvert\\lvert\\omega\\rvert\\rvert^2 min21∣∣ω∣∣2  
 s . t . y i ( ω T x i + b ) ≥ 1 , i = 1 , 2 , . . . m . s.t. \\quad y\_i(\\omega ^Tx\_i +b)\\ge 1, \\quad i=1,2,...m. s.t.yi(ωTxi\+b)≥1,i=1,2,...m.  
使用拉格朗日乘子法将式子化简，最终要求解的式子为：  
 m a x α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j ( 1 ) max\_\\alpha \\sum\_\{i=1\}^\{m\}\\alpha\_i -\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{m\}\\sum\_\{j=1\}^\{m\} \\alpha\_i \\alpha\_jy\_i y\_j x\_i^T x\_j \\quad\\quad\\quad\\quad(1) maxαi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxj(1)  
SMO的基本思路是先固定 α i \\alpha\_i αi之外的所有参数，然后求 α i \\alpha\_i αi上的极值。由于存在约束 ∑ i = 1 m α i y i = 0 \\sum\_\{i=1\}^\{m\}\\alpha\_iy\_i=0 ∑i=1mαiyi=0，若固定 α i \\alpha\_i αi之外的其他变量，则 α i \\alpha\_i αi可以由其他变量导出。于是，SMO每次选择两个变量 α i \\alpha\_i αi和 α j \\alpha\_j αj，并固定其他参数，这样，在参数初始化后，SMO不断执行如下两个步骤直至收敛：

*  选取一对需要更新的变量 α i \\alpha\_i αi和 α j \\alpha\_j αj。
 *  固定 α i \\alpha\_i αi和 α j \\alpha\_j αj以外的参数，求解(1)式获得更新之后的 α i \\alpha\_i αi和 α j \\alpha\_j αj。

从而得到 α \\alpha α值。

由于对任意支持向量 ( x s , y s ) (x\_s,y\_s) (xs,ys)都有 y s f ( x s ) = 1 y\_sf(x\_s)=1 ysf(xs)=1，即：  
 y s ( ∑ i ∈ S α i y i x i T x s + b ) = 1 y\_s(\\sum\_\{i\\in S\}\\alpha\_iy\_ix\_i^Tx\_s +b)=1 ys(i∈S∑αiyixiTxs\+b)=1  
其中 S = \{ i ∣ α i > 0 , i = 1 , 2 , 3 , . . . . m \} S=\\\{i|\\alpha\_i>0,i=1,2,3,....m \\\} S=\{ i∣αi>0,i=1,2,3,....m\}，因此使用所有支持向量求解的平均值  
 b = 1 ∣ S ∣ ∑ s ∈ S ( 1 y s − ∑ i ∈ S α i y i x i T x s ) b=\\frac\{1\}\{|S|\}\\sum\_\{s\\in S\}(\\frac\{1\}\{y\_s\}-\\sum\_\{i\\in S\}\\alpha\_iy\_ix\_i^Tx\_s) b=∣S∣1s∈S∑(ys1−i∈S∑αiyixiTxs)  
式子以得到 b b b值。

### 核函数 ###

核函数的作用是将数据从一个特征空间映射到另一个特征空间，方便分类器理解数据。通常情况下，这种映射会将低维特征空间映射到高维特征空间（比如，在平面上看不出超平面，映射到立体空间上或许就可以了）。  
  
不同的核函数有不同的映射效果

<table> 
 <thead> 
 <tr> 
 <th align="center">名称</th> 
 <th align="left">表达式</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td align="center">线性核</td> 
 <td align="left"> κ ( x i , x j ) = x i T x j \kappa(x_i,x_j)=x_i ^T x_j κ(xi,xj)=xiTxj</td> 
 </tr> 
 <tr> 
 <td align="center">多项式核</td> 
 <td align="left"> κ ( x i , x j ) = ( x i T x j ) d \kappa(x_i,x_j)=(x_i^Tx_j)^d κ(xi,xj)=(xiTxj)d</td> 
 </tr> 
 <tr> 
 <td align="center">高斯核</td> 
 <td align="left"> κ ( x i , x j ) = e x p ( − ∥ x i − x j ∥ 2 2 σ 2 ) \kappa(x_i,x_j)=exp(-\frac{\|x_i-x_j\|^2}{2\sigma^2}) κ(xi,xj)=exp(−2σ2∥xi−xj∥2)</td> 
 </tr> 
 <tr> 
 <td align="center">拉普拉斯核</td> 
 <td align="left"> κ ( x i , x j ) = e x p ( − ∥ x i − x j ∥ σ ) \kappa(x_i,x_j)=exp(- \frac{\|x_i-x_j\|}{\sigma}) κ(xi,xj)=exp(−σ∥xi−xj∥)</td> 
 </tr> 
 <tr> 
 <td align="center">Sigmod核</td> 
 <td align="left"> κ ( x i , x j ) = t a n h ( β x i T x j + θ ) \kappa(x_i,x_j)=tanh(\beta x_i^Tx_j+\theta) κ(xi,xj)=tanh(βxiTxj+θ)</td> 
 </tr> 
 </tbody> 
</table>

#### 该如何选取？ ####

一般都要通过专家先验知识选取，或者使用交叉验证，试用不同核函数看效果。  
下面是吴恩达的见解：

> 1.  如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM  
>     
> 2.  如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel  
>     
> 3.  如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况