SVM——《统计学习方法第七章》

这篇具有很好参考价值的文章主要介绍了SVM——《统计学习方法第七章》。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

SVM——《统计学习方法第七章》
SVM——《统计学习方法第七章》

为什么叫支持向量机

在第二章中我们学过感知机,它是最小化所有误分类点到超平面的距离之和, M 为误分类点的集合,得到的分离超平面是不唯一的。
min ⁡ ω , b [ − ∑ x i ∈ M y i ( ω ⋅ x i + b ) ] \min_{\omega,b}[-\sum_{x_i \in M}y_i (\omega\cdot x_i+b)] ω,bmin[xiMyi(ωxi+b)]
在支持向量机中,
{ 分类确信度 ∣ ω ⋅ x i + b ∣ ∣ ∣ ω ∣ ∣ 分类正确性 y i ( ω ⋅ x i + b ) ⇒ 几何间隔 γ i = y i ( ω ⋅ x i + b ) ∣ ∣ ω ∣ ∣ \begin{cases} 分类确信度 \frac{|\omega\cdot x_i+b|}{||\omega||}\\ 分类正确性 y_i(\omega\cdot x_i +b) \end{cases} \Rightarrow几何间隔\gamma_i=\frac{y_i(\omega\cdot x_i +b)}{||\omega||} {分类确信度∣∣ω∣∣ωxi+b分类正确性yi(ωxi+b)几何间隔γi=∣∣ω∣∣yi(ωxi+b)
哪些样本最有用?就是几何间隔最小的点 min ⁡ γ i \min \gamma_i minγi
然后使得几何间隔最小的点最大 max ⁡ ω , b min ⁡ γ i \max_{\omega,b}\min \gamma_i maxω,bminγi,一看这形式就知道要使用到最大熵章节讲到的原始问题和对偶问题。
R n R^n Rn空间中点和向量是等价的,最有用的那些点 min ⁡ γ i \min \gamma_i minγi称为支持向量。

线性可分支持向量机

a122df875738429a7dc0543663a3aa61.png
线性可分支持向量机是可以将样本点完全分类开来,但是这种情况在现实中是很少的,但是它是最简单的支持向量机。我们先理清它的过程,还有一些证明,后面的向量机都是在它的基础上发展的。
假设有 N 个样本,M 个特征 ,Y 只有正类(+1)和负类(-1)

几何间隔和函数间隔

几何间隔的定义(点 ( x i , y i ) (x_i,y_i) (xi,yi)到超平面 ω ⋅ x + b = 0 \omega\cdot x + b=0 ωx+b=0的距离):
γ i = ∣ ω ⋅ x i + b ∣ ∣ ∣ ω ∣ ∣ = y i ( ω ⋅ x i + b ) ∣ ∣ ω ∣ ∣ = y i ( ω ∣ ∣ ω ∣ ∣ ⋅ x i + b ∣ ∣ ω ∣ ∣ ) \begin{aligned} \gamma_i&=\frac{|\omega\cdot x_i +b|}{||\omega||}\\ &=\frac{y_i(\omega\cdot x_i +b)} {||\omega||}\\ &=y_i(\frac{\omega}{||\omega||}\cdot x_i+\frac{b}{||\omega||}) \end{aligned} γi=∣∣ω∣∣ωxi+b=∣∣ω∣∣yi(ωxi+b)=yi(∣∣ω∣∣ωxi+∣∣ω∣∣b)
几何间隔的最小值 γ = min ⁡ i γ i \gamma = \min_i \gamma_i γ=miniγi
优化问题为:
max ⁡ ω , b γ s . t . y i ( ω ∣ ∣ ω ∣ ∣ ⋅ x i + b ∣ ∣ ω ∣ ∣ ) ≥ γ , i = 1 , 2 , . . . , N \begin{aligned} & \max_{\omega,b}\quad \gamma\\ &s.t. \quad y_i(\frac{\omega}{||\omega||}\cdot x_i+\frac{b}{||\omega||})\ge \gamma,i=1,2,...,N \end{aligned} ω,bmaxγs.t.yi(∣∣ω∣∣ωxi+∣∣ω∣∣b)γ,i=1,2,...,N


函数间隔的定义:
γ ^ i = ∣ ω ⋅ x i + b ∣ = y i ( ω ⋅ x i + b ) \begin{aligned} \hat\gamma_i&={|\omega\cdot x_i +b|}\\ &={y_i(\omega\cdot x_i +b)} \\ \end{aligned} γ^i=ωxi+b=yi(ωxi+b)
函数间隔的最小值 γ ^ = min ⁡ i γ ^ i \hat\gamma = \min_i \hat\gamma_i γ^=miniγ^i
优化问题为:
max ⁡ ω , b γ ^ / ∣ ∣ ω ∣ ∣ s . t . y i ( ω ⋅ x i + b ) ≥ γ ^ , i = 1 , 2 , . . . , N \begin{aligned} & \max_{\omega,b}\quad \hat\gamma/||\omega||\\ &s.t. \quad {y_i(\omega\cdot x_i +b)}\ge \hat\gamma,i=1,2,...,N \end{aligned} ω,bmaxγ^/∣∣ω∣∣s.t.yi(ωxi+b)γ^,i=1,2,...,N


怎么将几何间隔和函数间隔联系起来?
第一种:将 ω \omega ω归一化,即 ∣ ∣ ω ∣ ∣ = 1 ||\omega||=1 ∣∣ω∣∣=1
以下这三种超平面的 ω , b \omega,b ω,b不一样,但是表示的是同一个超平面。
3 x ( 1 ) + 4 x ( 2 ) + 1 = 0 6 x ( 1 ) + 8 x ( 2 ) + 2 = 0 3 5 x ( 1 ) + 4 5 x ( 2 ) + 1 5 = 0 3x^{(1)}+4x^{(2)}+1=0\\ 6x^{(1)}+8x^{(2)}+2=0\\ \frac{3}{5}x^{(1)}+\frac{4}{5}x^{(2)}+\frac{1}{5}=0\\ 3x(1)+4x(2)+1=06x(1)+8x(2)+2=053x(1)+54x(2)+51=0
ω \omega ω归一化后,函数间隔和几何间隔就是等价的,此时优化问题为:
max ⁡ ω , b γ ^ / ∣ ∣ ω ∣ ∣ s . t . { y i ( ω ⋅ x i + b ) ≥ γ ^ , i = 1 , 2 , . . . , N ∣ ∣ ω ∣ ∣ = 1 \begin{aligned} & \max_{\omega,b}\quad \hat\gamma/||\omega||\\ &s.t. \begin{cases} {y_i(\omega\cdot x_i +b)}\ge \hat\gamma,i=1,2,...,N\\ ||\omega ||=1 \end{cases} \end{aligned} ω,bmaxγ^/∣∣ω∣∣s.t.{yi(ωxi+b)γ^,i=1,2,...,N∣∣ω∣∣=1

第二种:对 γ ^ \hat\gamma γ^做处理,和刚刚三个超平面处理类似,对 ω , b \omega,b ω,b进行放缩,可以使得 γ ^ = min ⁡ i γ ^ i = 1 \hat\gamma=\min_{i}\hat\gamma_i=1 γ^=miniγ^i=1
此时优化问题为:
min ⁡ ω , b ∣ ∣ ω ∣ ∣ s . t . y i ( ω ⋅ x i + b ) ≥ 1 , i = 1 , 2 , . . . , N \begin{aligned} & \min_{\omega ,b}\quad ||\omega||\\ &s.t. \quad {y_i(\omega\cdot x_i +b)}\ge 1,i=1,2,...,N\\ \end{aligned} ω,bmin∣∣ω∣∣s.t.yi(ωxi+b)1,i=1,2,...,N

显然,第二种处理能使得问题更加简单。

证明分离超平面存在且唯一

目标函数是凸函数,约束条件是放射函数,所以这个凸优化问题存在最优解。
现在证最优解是唯一的(反证法):
d39997678c6e8d23b99a3e322a01587.jpg
57fe7f12ee7d118339b2715275c560a.jpg

原始问题算法流程

输入:数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } , y i ∈ { + 1 , − 1 } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},y_i\in \{+1,-1\} T={(x1,y1),(x2,y2),...,(xN,yN)}yi{+1,1}
输出:最大间隔分离超平面与决策函数

  1. 构造优化问题

min ⁡ ω , b 1 2 ∣ ∣ ω ∣ ∣ 2 s . t . 1 − y i ( ω ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N \begin{aligned} & \min_{\omega ,b}\quad \frac{1}{2}||\omega||^2\\ &s.t. \quad 1-{y_i(\omega\cdot x_i +b)}\le 0,i=1,2,...,N\\ \end{aligned} ω,bmin21∣∣ω2s.t.1yi(ωxi+b)0,i=1,2,...,N
所得解为 ω ∗ , b ∗ \omega^* ,b^* ω,b

  1. 分离超平面

ω ∗ ⋅ x + b ∗ = 0 \omega^*\cdot x + b^*=0 ωx+b=0
决策函数
f ( x ) = s i g n ( ω ∗ ⋅ x + b ∗ ) f(x)=\rm sign(\omega^*\cdot x + b^*) f(x)=sign(ωx+b)

对偶算法

推导对偶优化问题

e8fb9ab4d8d0e08e2647368409c3855.jpg

α \alpha α推导 ω \omega ω和 b

d58575e45bd9fefa6ad583247e30693.jpg

对偶算法流程

输入:数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } , y i ∈ { + 1 , − 1 } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},y_i\in \{+1,-1\} T={(x1,y1),(x2,y2),...,(xN,yN)}yi{+1,1}
输出:最大间隔分离超平面与决策函数

  1. 构造优化问题

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 α i ≥ 0 , i = 1 , 2 , . . . , N \begin{aligned} & \min_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i\cdot x_j)-\sum_{i=1}^N \alpha_i\\ &s.t. \quad \sum_{i=1}^N \alpha_i y_i= 0\\ &\quad \quad \alpha_i\ge 0,i=1,2,...,N\\ \end{aligned} αmin21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαis.t.i=1Nαiyi=0αi0,i=1,2,...,N

  1. 求解优化问题,得到最优解

α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T α=(α1,α2,...,αN)T

  1. 根据 α ∗ \alpha^* α得到

ω ∗ = ∑ i = 1 N α i ∗ y i x i \omega^*=\sum_{i=1}^N \alpha_i^* y_i x_i ω=i=1Nαiyixi
找到符合 α j ∗ > 0 \alpha_j^*>0 αj>0的点 ( x j , y j ) (x_j,y_j) (xj,yj),计算
b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) b^*=y_j-\sum_{i=1}^N \alpha_i^*y_i(x_i\cdot x_j) b=yji=1Nαiyi(xixj)

  1. 分离超平面

ω ∗ ⋅ x + b ∗ = 0 \omega^*\cdot x + b^*=0 ωx+b=0
决策函数
f ( x ) = s i g n ( ω ∗ ⋅ x + b ∗ ) f(x)=\rm sign(\omega^*\cdot x + b^*) f(x)=sign(ωx+b)

线性支持向量机(不完全可分)

6f7ee306c430e430421aee0479429156.png

引入松弛因子

在线性支持向量机中,有四类点
正确分类且在分界线外面的点(白色的点): y i ( ω ⋅ x i + b ) ≥ 1 y_i(\omega\cdot x_i+b)\ge 1 yi(ωxi+b)1
分类正确但在超平面与分界线之间的点(黄色的点): y i ( ω ⋅ x i + b ) + ξ i ≥ 1 , ξ i ∈ ( 0 , 1 ) y_i(\omega\cdot x_i+b) + \xi_i\ge 1 ,\xi_i\in (0,1) yi(ωxi+b)+ξi1,ξi(0,1)
在超平面上的点: y i ( ω ⋅ x i + b ) + ξ i ≥ 1 , ξ i = 1 y_i(\omega\cdot x_i+b) + \xi_i\ge 1 ,\xi_i=1 yi(ωxi+b)+ξi1,ξi=1
分类错误的点: y i ( ω ⋅ x i + b ) + ξ i ≥ 1 , ξ i > 1 y_i(\omega\cdot x_i+b) + \xi_i\ge 1 ,\xi_i>1 yi(ωxi+b)+ξi1,ξi>1

解决重点就都集中到了这个关键的参数 ξ i \xi_i ξi 上,我们给它起名叫做弹性因子松弛变量
现在我们就要把原来线性可分的目标函数改成考虑所有松弛变量的新函数,目标函数是:
min ⁡ 1 2 ∣ ∣ ω 2 ∣ ∣ + C ∑ i = 1 N ξ i \min \frac{1}{2}||\omega^2||+C\sum_{i=1}^N \xi_i min21∣∣ω2∣∣+Ci=1Nξi
这里的 C C C 被称作惩罚系数,它决定了原始参数和松弛变量之间的影响权重。

  • C C C越大代表了误分类起到的作用更大,也可以说对误分类的惩罚力度大
  • C C C越小代表正确分类的参数作用更大,对误分类的惩罚力度小

原始问题算法流程

  1. 构造优化问题

min ⁡ ω , b , ξ i 1 2 ∣ ∣ ω 2 ∣ ∣ + C ∑ i = 1 N ξ i s . t . 1 − ξ i − y i ( ω ⋅ x i + b ) ≤ 0 , i = 1 , 2 , . . . , N − ξ i ≤ 0 , i = 1 , 2 , . . . , N \begin{aligned} & \min_{\omega ,b,\xi_i}\quad \frac{1}{2}||\omega^2||+C\sum_{i=1}^N \xi_i\\ &s.t. \quad 1-\xi_i -{y_i(\omega\cdot x_i +b)}\le 0,i=1,2,...,N\\ &\qquad -\xi_i\le 0 ,i=1,2,...,N \end{aligned} ω,b,ξimin21∣∣ω2∣∣+Ci=1Nξis.t.1ξiyi(ωxi+b)0,i=1,2,...,Nξi0,i=1,2,...,N
所得解为 ω ∗ , b ∗ \omega^* ,b^* ω,b

  1. 分离超平面

ω ∗ ⋅ x + b ∗ = 0 \omega^*\cdot x + b^*=0 ωx+b=0
决策函数
f ( x ) = s i g n ( ω ∗ ⋅ x + b ∗ ) f(x)=\rm sign(\omega^*\cdot x + b^*) f(x)=sign(ωx+b)

对偶算法

推导对偶优化问题

cb7471a5559bf44af2567a8c8830889.jpg

α \alpha α推导 ω \omega ω和 b

a63e68f91e1849b47f618753964f377.jpg

对偶算法流程

输入:数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } , y i ∈ { + 1 , − 1 } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},y_i\in \{+1,-1\} T={(x1,y1),(x2,y2),...,(xN,yN)}yi{+1,1}
输出:最大间隔分离超平面与决策函数

  1. 给定惩罚参数 C C C,构造优化问题

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N \begin{aligned} & \min_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i\cdot x_j)-\sum_{i=1}^N \alpha_i\\ &s.t. \quad \sum_{i=1}^N \alpha_i y_i= 0\\ &\quad \quad 0\le\alpha_i\le C,i=1,2,...,N\\ \end{aligned} αmin21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαis.t.i=1Nαiyi=00αiC,i=1,2,...,N

  1. 求解优化问题,得到最优解

α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T α=(α1,α2,...,αN)T

  1. 根据 α ∗ \alpha^* α得到

ω ∗ = ∑ i = 1 N α i ∗ y i x i \omega^*=\sum_{i=1}^N \alpha_i^* y_i x_i ω=i=1Nαiyixi
找到符合 0 < α j ∗ < C 0<\alpha_j^*<C 0<αj<C的点 ( x j , y j ) (x_j,y_j) (xj,yj),计算
b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) b^*=y_j-\sum_{i=1}^N \alpha_i^*y_i(x_i\cdot x_j) b=yji=1Nαiyi(xixj)

  1. 分离超平面

ω ∗ ⋅ x + b ∗ = 0 \omega^*\cdot x + b^*=0 ωx+b=0
决策函数
f ( x ) = s i g n ( ω ∗ ⋅ x + b ∗ ) f(x)=\rm sign(\omega^*\cdot x + b^*) f(x)=sign(ωx+b)

从合页损失的角度理解线性支持向量机

合页的表达式

image.png
b309defc921bf9989a5703b24c44b8fa.png

软间隔和合页损失

原始优化问题:
min ⁡ ω , b , ξ i 1 2 ∣ ∣ ω 2 ∣ ∣ + C ∑ i = 1 N ξ i \min_{\omega ,b,\xi_i}\quad \frac{1}{2}||\omega^2||+C\sum_{i=1}^N \xi_i ω,b,ξimin21∣∣ω2∣∣+Ci=1Nξi
631c3b00c63ca8e171ca20373325792.jpg
ξ i = [ 1 − y i ( ω ⋅ x i + b ) ] + = { 1 − y i ( ω ⋅ x i + b ) ξ i > 0 0 ξ i ≤ 0 \xi_i = [1-y_i(\omega\cdot x_i + b)]_+=\begin{cases} 1-y_i(\omega\cdot x_i + b) & \xi_i > 0\\ 0& \xi_i\le 0 \end{cases} ξi=[1yi(ωxi+b)]+={1yi(ωxi+b)0ξi>0ξi0
min ⁡ ω , b , ξ i 1 2 ∣ ∣ ω 2 ∣ ∣ + C ∑ i = 1 N ξ i = min ⁡ ω , b 1 2 ∣ ∣ ω 2 ∣ ∣ + C ∑ i = 1 N [ 1 − y i ( ω ⋅ x i + b ) ] + = min ⁡ ω , b ∑ i = 1 N [ 1 − y i ( ω ⋅ x i + b ) ] + + 1 2 C ∣ ∣ ω 2 ∣ ∣ = min ⁡ ω , b ∑ i = 1 N [ 1 − y i ( ω ⋅ x i + b ) ] + + λ ∣ ∣ ω 2 ∣ ∣ \min_{\omega ,b,\xi_i}\quad \frac{1}{2}||\omega^2||+C\sum_{i=1}^N \xi_i\\ =\min_{\omega,b}\quad \frac{1}{2}||\omega^2||+C\sum_{i=1}^N [1-y_i(\omega\cdot x_i + b)]_+\\ =\min_{\omega,b}\quad \sum_{i=1}^N [1-y_i(\omega\cdot x_i + b)]_+ + \frac{1}{2C}||\omega^2||\\ =\min_{\omega,b}\quad \sum_{i=1}^N [1-y_i(\omega\cdot x_i + b)]_+ + \lambda ||\omega^2|| ω,b,ξimin21∣∣ω2∣∣+Ci=1Nξi=ω,bmin21∣∣ω2∣∣+Ci=1N[1yi(ωxi+b)]+=ω,bmini=1N[1yi(ωxi+b)]++2C1∣∣ω2∣∣=ω,bmini=1N[1yi(ωxi+b)]++λ∣∣ω2∣∣
可以理解为最小化合页损失,后面是惩罚项。

三个损失函数的比较

image.png

非线性支持向量机

核函数

非线性的也分为可分和不可分两种情况。我们主要看非线性支持向量机(不可分)的情况。
我们需要将非线性转化为线性:原空间的点映射到新空间,用线性支持向量机取解决。
分析线性支持向量机的优化问题,我们可以发现关键计算 ( x i ⋅ x j ) (x_i\cdot x_j) (xixj)这个内积,其余都是单个数,所以要求新空间是能够计算内积的。
设映射是 Φ \Phi Φ,
z i = Φ ( x i ) , z j = Φ ( x j ) z_i = \Phi(x_i),z_j = \Phi(x_j) zi=Φ(xi),zj=Φ(xj)
z i ⋅ z j = Φ ( x i ) ⋅ Φ ( x j ) = K ( x i , x j ) 核函数 z_i\cdot z_j = \Phi (x_i)\cdot \Phi(x_j)=K(x_i,x_j) 核函数 zizj=Φ(xi)Φ(xj)=K(xi,xj)核函数
有很多映射对应一个核函数,我们不关心具体是什么映射,只关心核函数。
在新空间里 min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i \min_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j)-\sum_{i=1}^N \alpha_i αmin21i=1Nj=1NαiαjyiyjK(xi,xj)i=1Nαi


如何找到正定核?( K ( x i , x i ) ≥ 0 K(x_i,x_i)\ge 0 K(xi,xi)0
满足以下两个条件:
K K K是对称函数
② 新空间上的Gram矩阵半正定
image.png
这部分的具体内容需要泛函的知识,难度较大,感兴趣可以看《统计学习方法 李航》


常用核函数(我们所说的核函数就是正定核):

  1. 线性内核函数 K ( x i , x j ) = x i ⋅ x j K(x_i,x_j)=x_i\cdot x_j K(xi,xj)=xixj
  2. 多项式核函数 K ( x i , x j ) = ( x i ⋅ x j + 1 ) q K(x_i,x_j)=(x_i\cdot x_j+1)^q K(xi,xj)=(xixj+1)q
  3. 径向基核函数(高斯核函数,RBF) K ( x i , x j ) = exp ⁡ { − ∣ ∣ x i − x j ∣ ∣ 2 2 σ 2 } K(x_i,x_j)=\exp \{-\frac{||x_i-x_j||^2}{2\sigma^2}\} K(xi,xj)=exp{2σ2∣∣xixj2}

还有一种字符串核函数:
76376f8715b003234ed71c79eafb42f.jpg

算法流程

和线性支持向量机不同的地方就是将 x i ⋅ x j x_i\cdot x_j xixj改为 K ( x i , x j ) K(x_i,x_j) K(xi,xj)

输入:数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } , y i ∈ { + 1 , − 1 } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\},y_i\in \{+1,-1\} T={(x1,y1),(x2,y2),...,(xN,yN)}yi{+1,1}
输出:最大间隔分离超平面与决策函数

  1. 给定惩罚参数 C C C,构造优化问题

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N \begin{aligned} & \min_{\alpha}\quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j)-\sum_{i=1}^N \alpha_i\\ &s.t. \quad \sum_{i=1}^N \alpha_i y_i= 0\\ &\quad \quad 0\le\alpha_i\le C,i=1,2,...,N\\ \end{aligned} αmin21i=1Nj=1NαiαjyiyjK(xi,xj)i=1Nαis.t.i=1Nαiyi=00αiC,i=1,2,...,N

  1. 求解优化问题,得到最优解

α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T α=(α1,α2,...,αN)T

  1. 根据 α ∗ \alpha^* α得到

ω ∗ = ∑ i = 1 N α i ∗ y i K ( ⋅ , x i ) \omega^*=\sum_{i=1}^N \alpha_i^* y_i K(\cdot,x_i) ω=i=1NαiyiK(,xi)
找到符合 0 < α j ∗ < C 0<\alpha_j^*<C 0<αj<C的点 ( x j , y j ) (x_j,y_j) (xj,yj),计算
b ∗ = y j − ∑ i = 1 N α i ∗ y i K ( x i , x j ) b^*=y_j-\sum_{i=1}^N \alpha_i^*y_iK(x_i,x_j) b=yji=1NαiyiK(xi,xj)

  1. 分离超平面

ω ∗ ⋅ x + b ∗ = 0 \omega^*\cdot x + b^*=0 ωx+b=0
决策函数
f ( x ) = s i g n ( ω ∗ ⋅ x + b ∗ ) f(x)=\rm sign(\omega^*\cdot x + b^*) f(x)=sign(ωx+b)

SMO算法

SMO算法用来求解第二步中的优化问题。

坐标下降法(简化优化问题,每次更新一个参数)

4838627F-E16A-4C17-8793-1A9EB49AA447.jpeg

SMO算法求α(每次更新两个参数)

0c547224557ec8bc3ec0b577bd68b74.jpg
adfb12f4ea24dd585e1993471a1018d.jpg
026f02f8264d6dfba832d44b3457dde.jpg

更新完两个α后,更新b和Ei

9b8228d37c0aef578a7928cc81a985d.jpg

参数的选择

a99d4f3514710fd9720b33e602102cd.jpg

SMO算法流程

image.png文章来源地址https://www.toymoban.com/news/detail-476313.html

到了这里,关于SVM——《统计学习方法第七章》的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • python学习笔记:第七章面向对象

    与java类似,python作为一种面向对象的编程语言,也可以创建自定义的对象和类。 它的特性主要有:继承,封装,多态,方法,属性,超类 两者转换 每个类对应每个对象,下面有类变量 起到封装变量,封装函数,代码的作用 格式 实例化类,给类赋值 在创建对象时,就会被

    2024年02月13日
    浏览(53)
  • 《Flink学习笔记》——第七章 处理函数

    为了让代码有更强大的表现力和易用性,Flink 本身提供了多层 API 在更底层,我们可以不定义任何具体的算子(比如 map,filter,或者 window),而只是提炼出一个统一的“处理”(process)操作——它是所有转换算子的一个概括性的表达,可以自定义处理逻辑,所以这一层接口

    2024年02月10日
    浏览(51)
  • 《操作系统真象还原》学习笔记:第七章 中断

    由于 CPU 获知了计算机中发生的某些事,CPU 暂停正在执行的程序,转而去执行处理该事件的程序,当这段程序执行完毕后,CPU 继续执行刚才的程序。整个过程称为中断处理,也称为中断。 把中断按事件来源分类,来自CPU外部的中断就称为外部中断,来自CPU内部的中断就称为

    2024年02月11日
    浏览(54)
  • go 笔记 第七章 golang 的函数 func 方法

    声明函数 func 函数名(入参1 类型, 入参2 类型,… )(出参1 类型, 出参2 类型…){ 函数体,写逻辑 出参一定要全部 return, return 出参 } 函数内部不可以声明带名字的函数,可以声明匿名函数和自执行函数 函数名大写可以被其他包调用,小写私有,变量名也是一样 return 后面可以不

    2024年02月15日
    浏览(44)
  • 人工智能 :一种现代的方法 第七章 逻辑智能体

    本文旨在讲清楚: KBA(knowledge based agent)与逻辑 模型,有效性,可满足性,蕴含,推理过程 如何证明KB蕴含a(模型检验,逻辑等价,推理规则) 基于命题逻辑的Agent如何工作的 7.1 基于知识的智能体 基于知识的系统 基于知识的Agent的核心部件是其知识库,或称KB。 知识库

    2024年01月22日
    浏览(49)
  • 网络基础学习(第七章):VRRP协议介绍及配置

    1.1 VRRP协议介绍 虚拟路由冗余协议(Virtual Router Redundancy Protocol,简称VRRP)是由IETF提出的解决局域网中配置静态网关出现单点失效现象的路由协议。 利用VRRP,一组路由器(同一个VLAN中的接口)协同工作,但只要一个处于Master状态,处于该状态的路由器接口承担实际数据流量的

    2024年02月03日
    浏览(49)
  • 第七章:敏捷开发工具方法-part1-敏捷开发基础

    敏捷开发背景 速度是企业竞争致胜的关键因素,软件项目的最大挑战在于一方面需要应付变动中的需求,一方面需要在有限的时间完成项目,传统的软件工程难以满足这些要求 所以软件团队除了在技术上必须日益精进,更需要运用有效的开发流程,以确保团队能够发挥综效

    2024年02月09日
    浏览(66)
  • OBCP第七章 OB迁移-备份恢复技术架构及操作方法

    为什么需要备份恢复 为满足监管要求 防止管理员误操作后,错误数据同步到所有副本,导致数据无法恢复 防止数据库因各种故障而造成数据丢失,降低灾难性数据丢失的风险,从而达到灾难恢复的目的 硬盘驱动器损坏 黑客攻击、病毒 自然灾害、电源浪涌、磁干扰 物理备份

    2023年04月08日
    浏览(44)
  • 《Pytorch深度学习和图神经网络(卷 1)》学习笔记——第七章

    这一章内容有点丰富,多用了一些时间,实例就有四五个。 这章内容是真多啊!(学完之后又回到开头感叹) 将图像从基础像素到局部信息再到整体信息 即将图片由低级特征到高级特征进行逐级计算,逐级累计。 计算机中对图片的处理可以理解为离散微积分的过程。 利用

    2024年02月12日
    浏览(48)
  • 【Rust】Rust学习 第七章使用包、Crate和模块管理不断增长的项目

    目前为止,我们编写的程序都在一个文件的一个模块中。伴随着项目的增长,你可以通过将代码分解为多个模块和多个文件来组织代码。一个包可以包含多个二进制 crate 项和一个可选的 crate 库。伴随着包的增长,你可以将包中的部分代码提取出来,做成独立的 crate,这些

    2024年02月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包