SVM支持向量机模型

SVM支持向量机模型

1.支持向量机简介
支持向量机是一种二类分类模型，定义在特征空间上的间隔最大的线性分类器，间隔最大使其有别于感知机。
即求解凸二次规划的最优化算法，包括线性可分支持向量机，线性支持向量机以及非线性支持向量机三种。

2.线性可分支持向量机

训练数据线性可分时调用，通过硬间隔最大化学习

2.1函数间隔
对于给定训练数据集T与超平面(w,b)，定义超平面关于样本点的函数间隔为
γ i ′ = y i ( w x i + b ) gamma_i'=y_i(wx_i+b) γi′​=yi​(wxi​+b)
定义超平面关于训练集的函数间隔为超平面关于T中所有样本点的函数间隔最小值
γ i ′ = m i n γ i gamma_i'=mingamma_i γi′​=minγi​
函数间隔用于表现分类预测的正确性与确信度
若不对w进行约束，一旦w，b成比例增加时，超平面无变化但是函数间隔会倍数增加，规范化 ∣ ∣ w ∣ ∣ = 1 ||w||=1 ∣∣w∣∣=1
γ = y i ( w ∣ ∣ w ∣ ∣ x i + b ∣ ∣ w ∣ ∣ ) gamma=y_i(frac{w}{||w||}x_i+frac{b}{||w||}) γ=yi​(∣∣w∣∣w​xi​+∣∣w∣∣b​)

2.2几何间隔
对于给定训练数据集T与超平面(w,b)，定义超平面关于样本点的几何间隔为
γ i = y i ( w ∣ ∣ w ∣ ∣ x i + b ∣ ∣ w ∣ ∣ ) gamma_i=y_i(frac{w}{||w||}x_i+frac{b}{||w||}) γi​=yi​(∣∣w∣∣w​xi​+∣∣w∣∣b​)
定义超平面关于训练集的几何间隔为超平面关于T中所有样本点的几何间隔最小值
γ = m i n γ i gamma=mingamma_i γ=minγi​

2.3硬间隔最大化
2.3.1最大间隔分离超平面
即求 m a x γ maxgamma maxγ使得
y i ( w ∣ ∣ w ∣ ∣ x i + b ∣ ∣ w ∣ ∣ ) ≥ γ y_i(frac{w}{||w||}x_i+frac{b}{||w||})gegamma yi​(∣∣w∣∣w​xi​+∣∣w∣∣b​)≥γ
或求 m a x ( γ ′ / ∣ ∣ w ∣ ∣ ) max(gamma'/||w||) max(γ′/∣∣w∣∣)
y i ( w x i + b ) ≥ γ ′ y_i(wx_i+b)gegamma' yi​(wxi​+b)≥γ′
尝试转化为凸二次规划问题，求解w，b,因为 γ gamma γ取值并不影响结果，令其为1，将max问题转化为等价二次min问题
m i n 1 2 ∣ ∣ w ∣ ∣ 2 minfrac{1}{2}||w||^2 min21​∣∣w∣∣2
s . t . y i ( w x i + b ) − 1 ≥ y_i(wx_i+b)-1i​(wxi​+b)−1≥0

2.3.2最大间隔法

• 输入：线性可分训练集T={(x1,y1)(x2,y2)…(xn,yn)};Y={-1,1}
• 输出：最大间隔分离超平面和分类决策函数
• 1）构造并求解约束最优化问题
• m i n 1 2 ∣ ∣ w 2 ∣ ∣ minfrac{1}{2}||w^2|| min21​∣∣w2∣∣
  s . t . y i ( w x i + b ) − 1 ≥ y_i(wx_i+b)-1i​(wxi​+b)−1≥0求得 w ∗ , b ∗ w^*,b^* w∗,b∗
• 由此得到分离超平面与分类决策函数
• w ∗ x + b ∗ = 0 w^*x+b^*=0 w∗x+b∗=0
• f ( x ) = s i g n ( w ∗ x + b ∗ ) f(x)=sign(w^*x+b^*) f(x)=sign(w∗x+b∗)

2.3.3拉格朗日求解对偶问题求解
引入拉格朗日乘子a向量
L ( w , b , a ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ a i y i ( w x i + b ) + ∑ a i L(w,b,a)=frac{1}{2}||w||^2-sum{a_iy_i(wx_i+b)}+sum{a_i} L(w,b,a)=21​∣∣w∣∣2−∑ai​yi​(wxi​+b)+∑ai​
由拉格朗日对偶性，转化为求对偶问题
m a x a m i n w , b L ( w , b , a ) max_amin_{w,b}L(w,b,a) maxa​minw,b​L(w,b,a)
分别求偏导数=0，转化为
m i n ( 1 2 ∑ a i a j y i y j x i x j − ∑ a i min(frac{1}{2}sum{a_ia_jy_iy_jx_ix_j}-sum{a_i} min(21​∑ai​aj​yi​yj​xi​xj​−∑ai​
∑ a i y i = 0 ， a i ≥ 0 sum{a_iy_i}=0，a_ige0 ∑ai​yi​=0，ai​≥0
求出a，分离超平面为
∑ a i y i ( x x i ) + b = 0 sum{a_iy_i(xx_i)}+b=0 ∑ai​yi​(xxi​)+b=0

2.3.4线性可支持向量机学习算法

• 输入：线性可分训练集T={(x1,y1)(x2,y2)…(xn,yn)};Y={-1,1}

• 输出：分离超平面及分类决策函数

• 1）构造并求解约束最优化问题

• m i n ( 1 2 ∑ a i a j y i y j x i x j − ∑ a i min(frac{1}{2}sum{a_ia_jy_iy_jx_ix_j}-sum{a_i} min(21​∑ai​aj​yi​yj​xi​xj​−∑ai​
  ∑ a i y i = 0 ， a i ≥ 0 sum{a_iy_i}=0，a_ige0 ∑ai​yi​=0，ai​≥0求得最优解a（偏导）

• 计算 w ∗ = ∑ a i ∗ y i x i w^*=sum{a_i^*y_ix_i} w∗=∑ai∗​yi​xi​

• 选择一个a正分量计算 b ∗ = y j − ∑ a j ∗ y i ( x i x j ) b^*=y_j-sum{a_j^*y_i(x_ix_j)} b∗=yj​−∑aj∗​yi​(xi​xj​)

• 由此得到分离超平面与分类决策函数

• w ∗ x + b ∗ = 0 w^*x+b^*=0 w∗x+b∗=0

• f ( x ) = s i g n ( w ∗ x + b ∗ ) f(x)=sign(w^*x+b^*) f(x)=sign(w∗x+b∗)

3.线性支持向量机

当训练数据线性不可分时，使用软间隔最大化
即存在特异值，使训练集线性不可分（画不出完全正确的分离超平面）

3.1软间隔最大化
因此，对每个样本增加一个大于0矫正量，松弛变量 ϵ epsilon ϵ
约束条件为
y i ( w x i + b ) ≥ 1 − ϵ i y_i(wx_i+b)ge1-epsilon_i yi​(wxi​+b)≥1−ϵi​
ϵ i ≥ 0 epsilon_ige0 ϵi​≥0
同时，对于每个松弛变量支付一个代价，并对总代价增加一个参数C>0，作为惩罚变量，目标函数则变为
m i n ( 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ ( ϵ i ) ) min (frac{1}{2}||w||^2+Csum(epsilon_i)) min(21​∣∣w∣∣2+C∑(ϵi​))
理解：一方面，保持原目标使得几何间隔尽可能大，另一方面，惩罚量越少则误分类点个数尽量小，C用于调和两者权重

3.2线性支持向量机算法

• 输入：线性可分训练集T={(x1,y1)(x2,y2)…(xn,yn)};Y={-1,1}

• 输出：分离超平面及分类决策函数

• 1）选择惩罚参数C>0,构造并求解约束最优化问题

• m i n ( 1 2 ∑ a i a j y i y j x i x j − ∑ a i ) min(frac{1}{2}sum{a_ia_jy_iy_jx_ix_j}-sum{a_i}) min(21​∑ai​aj​yi​yj​xi​xj​−∑ai​)
  ∑ a i y i = 0 ， C ≥ a i ≥ 0 sum{a_iy_i}=0，Cge a_ige0 ∑ai​yi​=0，C≥ai​≥0求得最优解a（偏导）

• 计算 w ∗ = ∑ a i ∗ y i x i w^*=sum{a_i^*y_ix_i} w∗=∑ai∗​yi​xi​

• 选择一个a正分量计算 b ∗ = y j − ∑ a j ∗ y i ( x i x j ) b^*=y_j-sum{a_j^*y_i(x_ix_j)} b∗=yj​−∑aj∗​yi​(xi​xj​)

• 由此得到分离超平面与分类决策函数

• w ∗ x + b ∗ = 0 w^*x+b^*=0 w∗x+b∗=0

• f ( x ) = s i g n ( w ∗ x + b ∗ ) f(x)=sign(w^*x+b^*) f(x)=sign(w∗x+b∗)

3.3合页损失函数
即将最小化目标函数转化为最小化损失函数，取合页损失函数，即 [ z ] + = z [z]_+=z [z]+​=z if z>0 else 0
z即 L ( y ( w x + b ) ) = [ 1 − y i ( w x i + b ) ] + L(y(wx+b))=[1-y_i(wx_i+b)]_+ L(y(wx+b))=[1−yi​(wxi​+b)]+​指样本点正确分类且到分离超平面距离大于1时，损失为0，否则即本身
目标函数为 m i n w , b [ 1 − y ( w x i + b ) ] + + λ ∣ ∣ w ∣ ∣ 2 min_{w,b}[1-y(wx_i+b)]_++lambda||w||^2 minw,b​[1−y(wxi​+b)]+​+λ∣∣w∣∣2

4.非线性支持向量机

4.1核技巧
设 χ chi χ是输入空间（欧式空间 R n R^n Rn的子集或离散集合），又设H为特征空间（希尔伯特空间），如果存在一个从输入空间到输出空间的映射，即对所有 x , z ∈ χ x,zin chi x,z∈χ,函数K(x,z)满足条件：
K ( x , z ) = ϕ ( x ) ϕ ( z ) K(x,z)=phi(x)phi(z) K(x,z)=ϕ(x)ϕ(z)
则称 K ( x , z ) K(x,z) K(x,z)为核函数，为内积
核函数给定时，映射可以有多种
则通过映射后点内积求解线性支持向量机
f ( x ) = s i g n ( ∑ a i y i K ( x , z ) + b ) f(x)=sign(sum{a_iy_iK(x,z)+b}) f(x)=sign(∑ai​yi​K(x,z)+b)

4.2核函数
通常所说的核函数为正定核函数
正定核的充要条件为K(x,z)对应的Gram矩阵为半正定矩阵
可以在实际问题中直接调用已检验为正定核的核函数。

4.3常见核函数
4.3.1 多项式核函数
K ( x , z ) = ( x z + 1 ) p K(x,z)=(xz+1)^p K(x,z)=(xz+1)p
对应的支持向量机是一个p次多项式分类器
则分类决策函数变为
f ( x ) = s i g n ( ∑ a i y i ( x z + 1 ) p + b ) f(x)=sign(sum{a_iy_i(xz+1)^p+b}) f(x)=sign(∑ai​yi​(xz+1)p+b)
2.高斯核函数
K ( x , z ) = e x p ( − ∣ ∣ x − z ∣ ∣ 2 2 σ 2 + b ) K(x,z)=exp(-frac{||x-z||^2}{2sigma^2}+b) K(x,z)=exp(−2σ2∣∣x−z∣∣2​+b)
对应的支持向量机为高斯径向基函数分类器
3.字符串核函数
核函数定义在字符串集合中，用于离散数据集合
用于衡量字符串子串相似度，越相似，则核函数值越大
K ( s , t ) = ∑ [ ϕ ( s ) ] u [ ϕ ( t ) ] u = ∑ λ l ( i ) λ l ( j ) K(s,t)=sum{[phi(s)]_u[phi(t)]_u}=sumlambda^{l(i)}lambda^{l(j)} K(s,t)=∑[ϕ(s)]u​[ϕ(t)]u​=∑λl(i)λl(j)
l(i)为在u维度向量中，与u相似的子串长度大小，如u=‘abc’,s=‘acdasbc’,则l(i)=7-4+1=4,累加为出现次数

4.4非线性支持向量机学习算法
即将原内积换位映射空间内积，以核函数的形式表现

• 输入：线性可分训练集T={(x1,y1)(x2,y2)…(xn,yn)};Y={-1,1}

• 输出：分类决策函数

• 1）选择惩罚参数C>0,构造并求解约束最优化问题

• m i n ( 1 2 ∑ a i a j y i y j K ( x i , x j ) − ∑ a i ) min(frac{1}{2}sum{a_ia_jy_iy_jK(x_i,x_j)}-sum{a_i}) min(21​∑ai​aj​yi​yj​K(xi​,xj​)−∑ai​)
  ∑ a i y i = 0 ， C ≥ a i ≥ 0 sum{a_iy_i}=0，Cge a_ige0 ∑ai​yi​=0，C≥ai​≥0求得最优解a（偏导）

• 选择一个a正分量计算 b ∗ = y j − ∑ a j ∗ y i K ( x i , x j ) b^*=y_j-sum{a_j^*y_iK(x_i,x_j)} b∗=yj​−∑aj∗​yi​K(xi​,xj​)

• 由此得到分类决策函数

• f ( x ) = s i g n ( ∑ a i y i K ( x , z ) + b ) f(x)=sign(sum{a_iy_iK(x,z)+b}) f(x)=sign(∑ai​yi​K(x,z)+b)

5.序列最小最优化算法

为提高算法效率提出的快速实现算法
求解两个变量二次规划的解析方法和选择变量的启发式方法

• 输入：线性可分训练集T={(x1,y1)(x2,y2)…(xn,yn)};Y={-1,1}，精度 ϵ epsilon ϵ
• 输出：近似解a
• 取初值 a 0 = 0 ， k = 0 a^0=0，k=0 a0=0，k=0
• 选取优化变量 a 1 k , a 2 k a_1^k,a_2^k a1k​,a2k​求得最优解，更新a
• m i n a 1 , a 2 W ( a 1 , a 2 ) = 1 2 K 11 a 1 2 + 1 2 K 22 a 2 2 + y 1 y 2 K 12 a 1 a 2 − ( a 1 + a 2 ) + y 1 a 1 ∑ i = 3 N y i a i K i 1 + y 2 a 2 ∑ i = 3 N y i a i K i 2 min_{a_1,a_2}W(a_1,a_2)=frac{1}{2}K_{11}a_1^2+frac{1}{2}K_{22}a_2^2+y_1y_2K_{12}a_1a_2-(a_1+a_2)+y_1a_1sum_{i=3}^{N}y_ia_iK_{i1}+y_2a_2sum_{i=3}^{N}y_ia_iK_{i2} mina1​,a2​​W(a1​,a2​)=21​K11​a12​+21​K22​a22​+y1​y2​K12​a1​a2​−(a1​+a2​)+y1​a1​∑i=3N​yi​ai​Ki1​+y2​a2​∑i=3N​yi​ai​Ki2​
• s.t a 1 y 1 + a 2 y 2 = − ∑ i = 3 N y i a i a_1y_1+a_2y_2=-sum_{i=3}^{N}y_ia_i a1​y1​+a2​y2​=−∑i=3N​yi​ai​
• 0 ≤ a i ≤ C 0le a_ile C 0≤ai​≤C
• 若在精度范围内满足停止条件
• ∑ a i y i = 0 , 0 ≤ a i ≤ C sum{a_iy_i}=0,0le a_ile C ∑ai​yi​=0,0≤ai​≤C
• a i = 0 < = > y i g ( x i ) ≥ 1 a_i=0 <=>y_ig(x_i)ge1 ai​=0<=>yi​g(xi​)≥1
• 0 < a i < C < = > y i g ( x i ) = 1 0<a_i<C <=>y_ig(x_i)=1 0<ai​<C<=>yi​g(xi​)=1
• a i = C < = > y i g ( x i ) ≤ 1 a_i=C <=>y_ig(x_i)le1 ai​=C<=>yi​g(xi​)≤1
• 其中 g ( x i ) = ∑ a j y j K ( x j , x i ) + b g(x_i)=sum{a_jy_jK(x_j,x_i)+b} g(xi​)=∑aj​yj​K(xj​,xi​)+b
• 否则k=k+1，继续