SVM支持向量机算法原理-蒲公英云

SVM支持向量机算法原理

特点概述

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

口头描述

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值。

核函数

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

不同的核函数有不同的映射效果

名称	表达式
线性核	κ ( x i , x j ) = x i T x j \kappa(x_i,x_j)=x_i ^T x_j κ(xi,xj)=xiTxj
多项式核	κ ( x i , x j ) = ( x i T x j ) d \kappa(x_i,x_j)=(x_i^Tx_j)^d κ(xi,xj)=(xiTxj)d
高斯核	κ ( 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)
拉普拉斯核	κ ( 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∥)
Sigmod核	κ ( 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+θ)

该如何选取？

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

如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM

如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel

如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况