支持向量机(SVM)详解

支持向量机(support vector machines,SVM)是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机。

1、线性可分支持向量机与硬间隔最大化

1.1、线性可分支持向量机

考虑一个二分类问题。假设输入空间与特征空间为两个不同的空间,这两个空间的元素一一对应,并将输入空间的输入映射为特征空间中的特征向量,支持向量机的学习是在特征空间进行的。

假设一个特征空间上的训练数据集
T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} T={(x1,y1),(x2,y2),,(xN,yN)}

其中, x i ∈ X = R n x_i\in \cal{X}=\it{R}^n xiX=Rn y i ∈ Y = { + 1 , − 1 } y_i \in{\cal{Y}}=\{+1,-1\} yiY={+1,1} i = 1 , 2 , ⋯ , N i=1,2,\cdots,N i=1,2,,N x i x_i xi 为第 i i i 个特征向量,也称为实例, y i y_i yi x i x_i xi 的类标记。

学习的目标是在特征空间中找到一个分离超平面,能够将实例分到不同的类,分离超平面对应于方程 w ⋅ x + b = 0 w\cdot x+b=0 wx+b=0,它由法向量 w w w 和截距 b b b 决定。一般地,当训练数据集线性可分时,存在无穷个分离超平面可将数据正确分开,例如感知机利用误分类最小的策略,不过其解有无穷多个,而线性可分支持向量机利用间隔最大化求最优分离超平面,因此其解是唯一的。
在这里插入图片描述

1.2、函数间隔和几何间隔

如上图所示, A , B , C A,B,C A,B,C 三个点均在分离超平面的正类一侧,点 A A A 距分离超平面较远,若预测该点为正类,是比较可信的,而预测 C C C 点为正类就不那么可信,点 B B B 介于点 A A A C C C 之间,预测其为正类的可信度也在 A A A C C C 之间。

一般来说,在超平面 w ⋅ x + b = 0 w\cdot x+b=0 wx+b=0 确定的情况下, ∣ w ⋅ x + b ∣ \mid w\cdot x+b\mid wx+b 能够相对地表示点 x x x 距离超平面的远近,而 w ⋅ x + b w\cdot x+b wx+b 的符号与类标记 y y y 的符号是否一致能够表示分类是否正确,所以可用量 y ( w ⋅ x + b ) y(w\cdot x+b) y(wx+b) 来表示分类的正确性及确信度,这就是函数间隔(functional margin)的概念,记作 γ ^ i \hat{\gamma}_i γ^i

但是只要成比例地改变 w w w b b b,例如将它们改为 2 w 2w 2w 2 b 2b 2b,超平面并没有改变,但函数间隔却变为原来的 2 倍,所以需要对 w w w 加某些约束,如 ∥ w ∥ = 1 \parallel w\parallel=1 w∥=1,使得间隔是确定的。这时函数间隔就成为了几何间隔(geometric margin),记作 γ i \gamma_i γi

在这里插入图片描述
上图给出了超平面 ( w , b ) (w,b) (w,b) 及其法向量 w w w。点 A A A 表示某一实例 x i x_i xi,其类标记为 y i = + 1 y_i=+1 yi=+1。点 A A A 与超平面 ( w , b ) (w,b) (w,b) 的距离由线段 A B AB AB 给出,记作 γ i \gamma_i γi
γ i = w ∥ w ∥ ⋅ x i + b ∥ w ∥ \gamma_i=\dfrac{w}{\parallel w\parallel}\cdot x_i+\dfrac{b}{\parallel w\parallel} γi=wwxi+wb

其中, ∥ w ∥ \parallel w\parallel w w w w L 2 L_2 L2 范数。这是点 A A A 在超平面正的一侧的情形。如果点 A A A 在超平面负的一侧,即 y i = − 1 y_i=-1 yi=1,那么点与超平面的距离为
γ i = − ( w ∥ w ∥ ⋅ x i + b ∥ w ∥ ) \gamma_i=-\Big(\dfrac{w}{\parallel w\parallel}\cdot x_i+\dfrac{b}{\parallel w\parallel}\Big) γi=(wwxi+wb)

一般地,当样本点 ( x i , y i ) (x_i,y_i) (xi,yi) 被超平面 ( w , b ) (w,b) (w,b) 正确分类时,点 x i x_i xi 与超平面 ( w , b ) (w,b) (w,b) 的距离是
γ i = y i ( w ∥ w ∥ ⋅ x i + b ∥ w ∥ ) \gamma_i=y_i\Big(\dfrac{w}{\parallel w\parallel}\cdot x_i+\dfrac{b}{\parallel w\parallel}\Big) γi=yi(wwxi+wb)

1.3、间隔最大化

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

(1)最大间隔分离超平面

求最大间隔分离超平面可以表示为下面的约束最优化问题:
max ⁡ w , b γ s . t . y i ( w ∥ w ∥ ⋅ x i + b ∥ w ∥ ) ≥ γ , i = 1 , 2 , ⋯ , N \begin{aligned} \max_{w,b}\quad &\gamma\\ \rm{s.t.}\quad&y_i\Big(\dfrac{w}{\parallel w\parallel}\cdot x_i+\dfrac{b}{\parallel w\parallel}\Big)\geq\gamma,\quad i=1,2,\cdots,N \end{aligned} w,bmaxs.t.γyi(wwxi+wb)γ,i=1,2,,N

即希望最大化超平面 ( w , b ) (w,b) (w,b) 关于训练数据集的几何间隔 γ \gamma γ,约束条件表示的是超平面 ( w , b ) (w,b) (w,b) 关于每个训练样本的几何间隔至少是 γ \gamma γ

考虑几何间隔和函数间隔的关系,可以改写为
max ⁡ w , b γ ^ ∥ w ∥ s . t . y i ( w ⋅ x i + b ) ≥ γ ^ , i = 1 , 2 , ⋯ , N \begin{aligned} \max_{w,b}\quad &\dfrac{\hat{\gamma}}{\parallel w\parallel}\\ \rm{s.t.}\quad&y_i(w\cdot x_i+b)\geq\hat{\gamma},\quad i=1,2,\cdots,N \end{aligned} w,bmaxs.t.wγ^yi(wxi+b)γ^,i=1,2,,N

函数间隔 γ ^ \hat{\gamma} γ^ 的取值并不影响最优化问题的解,事实上,假设将 w w w b b b 按比例改变为 λ w \lambda w λw λ b \lambda b λb,这时函数间隔成为 λ γ ^ \lambda\hat{\gamma} λγ^。函数间隔的这一改变对上面最优化问题的不等式约束没有影响,对目标函数的优化也没有影响,即产生一个等价的最优化问题。这样,就可以取 γ ^ = 1 \hat{\gamma}=1 γ^=1,将其带入上面最优化问题,而最大化 1 ∥ w ∥ \dfrac{1}{\parallel w\parallel} w1 和最小化 1 2 ∥ w ∥ 2 \dfrac{1}{2}\parallel w\parallel^2 21w2 是等价的,于是:
min ⁡ w , b 1 2 ∥ w ∥ 2 s . t . y i ( w ⋅ x i + b ) − 1 ≥ 0 , i = 1 , 2 , ⋯ , N \begin{aligned} \min_{w,b}\quad &\dfrac{1}{2}\parallel w\parallel^2\\ \rm{s.t.}\quad&y_i(w\cdot x_i+b)-1\geq0,\quad i=1,2,\cdots,N \end{aligned} w,bmins.t.21w2yi(wxi+b)10,i=1,2,,N

如果求出了上述优化问题的解 w ∗ , b ∗ w^\ast,b^\ast w,b,那么就可以得到最大间隔分离超平面 w ∗ ⋅ x + b ∗ = 0 w^\ast\cdot x+b^\ast=0 wx+b=0 及分类决策函数 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)= {sign} (w^\ast\cdot x+b^\ast) f(x)=sign(wx+b),即线性可分支持向量机模型

综上所述,就是线性可分支持向量机的学习算法——最大间隔法(maximum margin method)。

(2)支持向量和间隔边界

在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector)。支持向量是使约束条件 y i ( w ⋅ x i + b ) − 1 ≥ 0 y_i(w\cdot x_i+b)-1\geq0 yi(wxi+b)10 等号成立的点,即
y i ( w ⋅ x i + b ) − 1 = 0 y_i(w\cdot x_i+b)-1=0 yi(wxi+b)1=0

y i = + 1 y_i=+1 yi=+1 的正例点,支持向量在超平面
H 1 : w ⋅ x + b = 1 H_1:w\cdot x+b=1 H1:wx+b=1

上,对 y i = − 1 y_i=-1 yi=1 的负例点,支持向量在超平面
H 2 : w ⋅ x + b = − 1 H_2:w\cdot x+b=-1 H2:wx+b=1

上。如下图所示,在 H 1 H_1 H1 H 2 H_2 H2 上的点就是支持向量。注意到 H 1 H_1 H1 H 2 H_2 H2 平行,并且并没有实例点落在它们中间。在 H 1 H_1 H1 H 2 H_2 H2 之间形成一条长带,长带的宽度称为间隔(margin),间隔依赖于分离超平面的法向量 w w w,等于 2 ∥ w ∥ \dfrac{2}{\parallel w\parallel} w2 H 1 H_1 H1 H 2 H_2 H2 称为间隔边界
在这里插入图片描述
在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。如果移动支持向量将改变所求的解;但是如果在间隔边界以外移动其他实例点,甚至去掉这些点,则解是不会改变的。由于支持向量在确定分离超平面中起决定性作用,所以将这种分类模型称为支持向量机。支持向量的个数一般很少,所以支持向量机由很少的 “ 重要的 ” 的训练样本确定。

1.4、学习的对偶算法

为了求解线性可分支持向量机的最优化问题,首先构建拉格朗日函数(Lagrange function),即对每个不等式约束引入拉格朗日乘子(Lagrange multiplier) α i ≥ 0 , i = 1 , 2 , ⋯ , N \alpha_i\geq0,\ i=1,2,\cdots,N αi0, i=1,2,,N,定义拉格朗日函数:
L ( w , b , α ) = 1 2 ∥ w ∥ 2 − ∑ i = 1 N α i y i ( w ⋅ x i + b ) + ∑ i = 1 N α i L(w,b,\alpha)=\dfrac{1}{2}\parallel w\parallel^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i L(w,b,α)=21w2i=1Nαiyi(wxi+b)+i=1Nαi

其中, α = ( α 1 , α 2 , ⋯ , α N ) T \alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T α=(α1,α2,,αN)T 为拉格朗日乘子向量。

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:
max ⁡ α min ⁡ w , b L ( w , b , α ) \max_\alpha\min_{w,b}L(w,b,\alpha) αmaxw,bminL(w,b,α)

所以,为了得到对偶问题的解,需要先求 L ( w , b , α ) L(w,b,\alpha) L(w,b,α) w , b w,b w,b 的极小,再求对 α \alpha α 的极大。

(1)求 min ⁡ w , b L ( w , b , α ) \min_{w,b}L(w,b,\alpha) minw,bL(w,b,α)

L ( w , b , α ) L(w,b,\alpha) L(w,b,α) 分别对 w , b w,b w,b 求偏导并令其等于 0。
∇ w L ( w , b , α ) = w − ∑ i = 1 N α i y i x i = 0 ∇ b L ( w , b , α ) = − ∑ i = 1 N α i y i = 0 \begin{aligned} &\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\ &\nabla_bL(w,b,\alpha)=-\sum_{i=1}^N\alpha_iy_i=0 \end{aligned} wL(w,b,α)=wi=1Nαiyixi=0bL(w,b,α)=i=1Nαiyi=0


w = ∑ i = 1 N α i y i x i ∑ i = 1 N α i y i = 0 \begin{aligned} &w=\sum_{i=1}^N\alpha_iy_ix_i\\ &\sum_{i=1}^N\alpha_iy_i=0 \end{aligned} w=i=1Nαiyixii=1Nαiyi=0

将其代入拉格朗日函数,即得
L ( w , b , α ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i y i ( ( ∑ i = 1 N α j y j x j ) ⋅ x i + b ) + ∑ i = 1 N α i = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i \begin{aligned} L(w,b,\alpha)&=\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_iy_i\Big(\Big(\sum_{i=1}^N\alpha_jy_jx_j\Big)\cdot x_i+b\Big)+\sum_{i=1}^N\alpha_i\\ &=-\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i \end{aligned} L(w,b,α)=21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαiyi((i=1Nαjyjxj)xi+b)+i=1Nαi=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi


min ⁡ w , b L ( w , b , α ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i \min_{w,b}L(w,b,\alpha)=-\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i w,bminL(w,b,α)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi

(2)求 min ⁡ w , b L ( w , b , α ) \min_{w,b}L(w,b,\alpha) minw,bL(w,b,α) α \alpha α 的极大,即是对偶问题

max ⁡ α − 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} \max_\alpha\quad&-\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\\ \rm{s.t.}\quad&\sum_{i=1}^N\alpha_iy_i=0\\ &\alpha_i\geq 0,\quad i=1,2,\cdots,N \end{aligned} αmaxs.t.21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαii=1Nαiyi=0αi0,i=1,2,,N

将上述目标函数由求极大转换为求极小,即
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&\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\ \rm{s.t.}\quad&\sum_{i=1}^N\alpha_iy_i=0\\ &\alpha_i\geq 0,\quad i=1,2,\cdots,N \end{aligned} αmins.t.21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαii=1Nαiyi=0αi0,i=1,2,,N

上述即对偶最优化问题,假设对偶最优化问题对 α \alpha α 的解为 α ∗ = ( α 1 ∗ , α 2 ∗ , ⋯ , α N ∗ ) T \alpha^\ast=(\alpha_1^\ast,\alpha_2^\ast,\cdots,\alpha_N^\ast)^T α=(α1,α2,,αN)T,可以由 α ∗ \alpha^\ast α 求得原始最优化问题对 ( w , b ) (w,b) (w,b) 的解 w ∗ , b ∗ w^\ast,b^\ast w,b
w ∗ = ∑ i = 1 N α i ∗ y i x i b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) \begin{aligned} w^\ast&=\sum_{i=1}^N\alpha_i^\ast y_ix_i\\ b^\ast&=y_j-\sum_{i=1}^N\alpha_i^\ast y_i(x_i\cdot x_j) \end{aligned} wb=i=1Nαiyixi=yji=1Nαiyi(xixj)

从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法,是线性可分支持向量机学习的基本算法。

2、线性支持向量机与软间隔最大化

2.1、线性支持向量机

上一节的方法对线性不可分训练数据是不适用的,因为这时上述方法中的不等式约束并不能都成立。

假设一个特征空间上的训练数据集
T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} T={(x1,y1),(x2,y2),,(xN,yN)}

其中, x i ∈ X = R n x_i\in \cal{X}=\it{R}^n xiX=Rn y i ∈ Y = { + 1 , − 1 } y_i \in{\cal{Y}}=\{+1,-1\} yiY={+1,1} i = 1 , 2 , ⋯ , N i=1,2,\cdots,N i=1,2,,N x i x_i xi 为第 i i i 个特征向量, y i y_i yi x i x_i xi 的类标记。通常情况下,训练数据中有一些特异点(outlier),将这些特异点除去后,剩下大部分的样本点组成的集合是线性可分的。

线性不可分意味着某些样本点 ( x i , y i ) (x_i,y_i) (xi,yi) 不能满足函数间隔大于 1 的约束条件,为了解决这个问题,可以对每个样本点 ( x i , y i ) (x_i,y_i) (xi,yi) 引入一个松弛变量 ξ i ≥ 0 \xi_i\geq0 ξi0,使函数间隔加上松弛变量大于等于 1。这样,约束条件变为
y i ( w ⋅ x i + b ) ≥ 1 − ξ i y_i(w\cdot x_i+b)\geq 1-\xi_i yi(wxi+b)1ξi

同时,对每个松弛变量 ξ i \xi_i ξi,支付一个代价 ξ i \xi_i ξi。目标函数由原来的 1 2 ∥ w ∥ 2 \dfrac{1}{2}\parallel w\parallel^2 21w2 变成
1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i \dfrac{1}{2}\parallel w\parallel^2+C\sum_{i=1}^N\xi_i 21w2+Ci=1Nξi

这里, C > 0 C>0 C>0 称为惩罚参数, C C C 值大时对误分类的惩罚增大, C C C 值小时对误分类的惩罚减小。最小化上式目标函数包含两层含义:使 1 2 ∥ w ∥ 2 \dfrac{1}{2}\parallel w\parallel^2 21w2 尽量小即间隔尽量大,同时使误分类点的个数尽量小, C C C 是调和二者的系数。

上述的思路,我们称为软间隔最大化。线性不可分的线性支持向量机的学习问题变成如下问题(原始问题):
min ⁡ w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 N ξ i s . t . y i ( w ⋅ x i + b ) ≥ 1 − ξ i , i = 1 , 2 , ⋯ , N ξ i ≥ 0 , i = 1 , 2 , ⋯ , N \begin{aligned} \min_{w,b,\xi}\quad &\dfrac{1}{2}\parallel w\parallel^2+C\sum_{i=1}^N\xi_i\\ \rm{s.t.}\quad&y_i(w\cdot x_i+b)\geq1-\xi_i,\quad i=1,2,\cdots,N\\ &\xi_i\geq0,\quad i=1,2,\cdots,N \end{aligned} w,b,ξmins.t.21w2+Ci=1Nξiyi(wxi+b)1ξi,i=1,2,,Nξi0,i=1,2,,N

设上述问题的解是 w ∗ , b ∗ w^\ast,b^\ast w,b,于是得到分类超平面 w ∗ ⋅ x + b ∗ = 0 w^\ast\cdot x+b^\ast=0 wx+b=0 及分类决策函数 f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^\ast\cdot x+b^\ast) f(x)=sign(wx+b)。称这样的模型为训练样本线性不可分时的线性支持向量机,简称线性支持向量机

2.2、学习的对偶算法

原始问题的对偶问题是
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&\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\ \rm{s.t.}\quad&\sum_{i=1}^N\alpha_iy_i=0\\ &0\leq\alpha_i\leq C,\quad i=1,2,\cdots,N \end{aligned} αmins.t.21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαii=1Nαiyi=00αiC,i=1,2,,N

2.3、支持向量

在线性不可分的情况下,对偶问题的解 α ∗ = ( α 1 ∗ , α 2 ∗ , ⋯ , α N ∗ ) T \alpha^\ast=(\alpha_1^\ast,\alpha_2^\ast,\cdots,\alpha_N^\ast)^T α=(α1,α2,,αN)T 中对应于 α i ∗ > 0 \alpha_i^\ast>0 αi>0 的样本点 ( x i , y i ) (x_i,y_i) (xi,yi) 的实例 x i x_i xi 称为支持向量(软间隔的支持向量)。
在这里插入图片描述

如上图所示,这时的支持向量要比线性可分时的情况复杂一些,软间隔的支持向量 x i x_i xi 或者在间隔边界上,或者在间隔边界与分离超平面之间,或者在分离超平面误分一侧。若 α i ∗ < C \alpha_i^\ast<C αi<C,则 ξ i = 0 \xi_i=0 ξi=0,支持向量 x i x_i xi 刚好落在间隔边界上;若 α i ∗ = C , 0 < ξ i < 1 \alpha_i^\ast=C,0<\xi_i<1 αi=C,0<ξi<1,则分类正确, x i x_i xi 在间隔边界与分离超平面之间;若 α i ∗ = C , ξ i = 1 \alpha_i^\ast=C,\xi_i=1 αi=C,ξi=1,则 x i x_i xi 在分离超平面上;若 α i ∗ = C , ξ i > 1 \alpha_i^\ast=C,\xi_i>1 αi=C,ξi>1,则 x i x_i xi 位于分离超平面误分一侧。

3、非线性支持向量机与核函数

对解线性分类问题,线性分类支持向量机是一种有效的方法,但是有时分类问题是非线性的,这时可以使用非线性支持向量机。

3.1、核技巧

(1)非线性分类问题

在这里插入图片描述
如左图所示,无法用直线(线性模型)将正负实例正确分开,但可以用一条椭圆曲线(非线性模型)将它们正确分开。

一般来说,对给定的一个训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} T={(x1,y1),(x2,y2),,(xN,yN)},其中,实例 x i x_i xi 属于输入空间, x i ∈ X = R n x_i\in \cal{X} =R^n xiX=Rn,对应的标记有两类 y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , ⋯ , N y_i\in \cal{Y}=\{-1,+1\},i=1,2,\cdots,\it N yiY={1,+1},i=1,2,,N。如果能用 R n R^n Rn 的一个超曲面将正负实例正确分开,则称这个问题为非线性可分问题

分线性问题往往不好求解,所以采用的方法是进行一个非线性映射,将非线性问题转换为线性问题,通过解线性问题的方法求解非线性问题,如上图所示,将左图中椭圆变换成右图的直线,将非线性分类问题变换为线性分类问题。

设原空间为 X ⊂ R 2 \cal{X} \subset \it{R}^2 XR2 x = ( x ( 1 ) , x ( 2 ) ) T ∈ X x=\big(x^{(1)},x^{(2)}\big)^T\in\cal{X} x=(x(1),x(2))TX,新空间为 Z ⊂ R 2 \cal{Z} \subset \it{R}^2 ZR2 z = ( z ( 1 ) , z ( 2 ) ) T ∈ Z z=\big(z^{(1)},z^{(2)}\big)^T\in\cal{Z} z=(z(1),z(2))TZ,定义从原空间到新空间的变换(映射):
z = ϕ ( x ) = ( ( x ( 1 ) ) 2 , ( x ( 2 ) ) 2 ) T z=\phi(x)=\big((x^{(1)})^2,(x^{(2)})^2\big)^T z=ϕ(x)=((x(1))2,(x(2))2)T

经过变换 z = ϕ ( x ) z=\phi(x) z=ϕ(x),原空间 X ⊂ R 2 \cal{X} \subset \it{R}^2 XR2 变换为新空间 Z ⊂ R 2 \cal{Z} \subset \it{R}^2 ZR2,原空间中的点相应地变换为新空间中的点,原空间中的椭圆
w 1 ( x ( 1 ) ) 2 + w 2 ( x ( 2 ) ) 2 + b = 0 w_1(x^{(1)})^2+w_2(x^{(2)})^2+b=0 w1(x(1))2+w2(x(2))2+b=0

变换成为新空间中的直线
w 1 z ( 1 ) + w 2 z ( 2 ) + b = 0 w_1z^{(1)}+w_2z^{(2)}+b=0 w1z(1)+w2z(2)+b=0

在变换后的新空间里,直线 w 1 z ( 1 ) + w 2 z ( 2 ) + b = 0 w_1z^{(1)}+w_2z^{(2)}+b=0 w1z(1)+w2z(2)+b=0 可以将变换后的正负实例点正确分开。这样原空间的非线性可分问题就变成了新空间的线性可分问题。

(2)核函数的定义

X \cal X X 是输入空间(欧式空间 R n R^n Rn 的子集或离散集合),又设 H \cal H H 为特征空间(希尔伯特空间),如果存在一个从 X \cal X X H \cal H H 的映射
ϕ ( x ) : X → H \phi(x):\cal{X}\rightarrow\cal{H} ϕ(x):XH

使得对所有 x , z ∈ X x,z\in\cal{X} x,zX,函数 K ( x , z ) K(x,z) K(x,z) 满足条件
K ( x , z ) = ϕ ( x ) ⋅ ϕ ( z ) K(x,z)=\phi(x)\cdot\phi(z) K(x,z)=ϕ(x)ϕ(z)

则称 K ( x , z ) K(x,z) K(x,z)核函数 ϕ ( x ) \phi(x) ϕ(x) 为映射函数,式中 ϕ ( x ) ⋅ ϕ ( z ) \phi(x)\cdot\phi(z) ϕ(x)ϕ(z) ϕ ( x ) \phi(x) ϕ(x) ϕ ( z ) \phi(z) ϕ(z) 的内积。

(3)核技巧在支持向量机中的应用

我们注意到在线性支持向量机的对偶问题中,无论是目标函数还是决策函数(分离超平面)都只涉及输入实例域实例之间的内积。在对偶问题的目标函数中的内积 x i ⋅ x j x_i\cdot x_j xixj 可以用核函数 K ( x i , x j ) = ϕ ( x i ) ⋅ ϕ ( x j ) K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j) K(xi,xj)=ϕ(xi)ϕ(xj) 来代替,此时对偶问题的目标函数成为
W ( α ) = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i W(\alpha)=\dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i W(α)=21i=1Nj=1NαiαjyiyjK(xi,xj)i=1Nαi

同样,分类决策函数中的内积也可以用核函数代替,而分类决策函数式成为
f ( x ) = s i g n ( ∑ i = 1 N s α i ∗ y i ϕ ( x i ) ⋅ ϕ ( x ) + b ∗ ) = s i g n ( ∑ i = 1 N s α i ∗ y i K ( x i , x ) + b ∗ ) \begin{aligned} f(x)&=sign\Big(\sum_{i=1}^{N_s}\alpha_i^\ast y_i\phi(x_i)\cdot\phi(x)+b^\ast\Big)\\ &=sign\Big(\sum_{i=1}^{N_s}\alpha_i^\ast y_iK(x_i,x)+b^\ast\Big) \end{aligned} f(x)=sign(i=1Nsαiyiϕ(xi)ϕ(x)+b)=sign(i=1NsαiyiK(xi,x)+b)

3.2、常用核函数

  1. 多项式核函数(polynomial kernel function)
    K ( x , z ) = ( x ⋅ z + 1 ) p K(x,z)=(x\cdot z +1)^p K(x,z)=(xz+1)p
  2. 高斯核函数(Gaussian kernel function)
    K ( x , z ) = exp ⁡ ( − ∥ x − z ∥ 2 σ 2 ) K(x,z)=\exp\Big(-\dfrac{\parallel x-z\parallel}{2\sigma^2}\Big) K(x,z)=exp(2σ2xz)

3.3、非线性支持向量分类机

如上所述,利用核技巧可以将线性分类的学习问题应用到非线性分类问题中去。将线性支持向量机扩展到非线性支持向量机,只需将线性支持向量机对偶形式中的内积换成核函数。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/246924.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vulnhub-dc6

信息收集 # nmap -sn 192.168.1.0/24 -oN live.port Starting Nmap 7.94 ( https://nmap.org ) at 2024-01-25 14:39 CST Nmap scan report for 192.168.1.1 Host is up (0.00075s latency). MAC Address: 00:50:56:C0:00:08 (VMware) Nmap scan report for 192.168.1.2…

Java 字符串 10 字符串相关类的底层原理

底层原理1&#xff0c;底层原理2 底层原理3&#xff1a; 分两种情况&#xff1a; 1、等号右边没有变量&#xff1a; 2、等号右边有变量&#xff1a; 两个对象&#xff0c;一个是StringBuilder&#xff0c;一个是String&#xff0c;浪费空间&#xff0c;性能不高 在jdk8之前&am…

WinRAR压缩包高级技巧:永久设置压缩包单个或批量单独压缩成包并且不内嵌文件夹,解压保留原始时间设置

目录点击跳转&#xff1a;WinRAR压缩包高级技巧&#xff1a;永久设置压缩包单个或批量单独压缩成包并且不内嵌文件夹&#xff0c;解压保留原始时间设置 解压永久设置1 解压保存原始时间 压缩永久设置1 默认压缩成zip手机电脑都通用的格式2 默认压缩文件不多额外嵌套一层文件夹&…

Java复习系列之阶段二:数据库

1. 基础语法 1.1 DQL&#xff08;数据查询语句&#xff09; 执行顺序&#xff1a; from、join 、on、where、group by、having、select、distinct、order by、limit 1.2 DML&#xff08;数据修改语言&#xff09; 对数据表的增删改 insert into update set delete form 1.…

RTP工具改进(五)--使用qt

前篇 第四篇 RTP工具改进(四) - rtmp协议推送 前面使用的工具一直为mfc&#xff0c;今天将使用qt 来做界面&#xff0c;使用qt 来进行程序和协议的编写&#xff0c;qt部分目前还不包括rtp ps流和rtmp&#xff0c;暂时只有rtp 直接传输&#xff0c;关于rtmp协议和ps流协议&…

Qt/QML编程之路:ListView实现横排图片列表的示例(40)

ListView列表,在QML中使用非常多,排列一个行,一个列或者一个表格,都会用到ListView。 ListView显示从内置QML类型(如ListModel和XmlListModel)创建的模型中的数据,或在C++中定义的从QAbstractItemModel或QAbstract ListModel继承的自定义模型类中的数据。 ListView有一…

[GYCTF2020]Ezsqli1

打开环境&#xff0c;下面有个提交表单 提交1&#xff0c;2有正确的查询结果&#xff0c;3以后都显示Error Occured When Fetch Result. 题目是sql&#xff0c;应该考察的是sql注入 简单fuzz一下 发现information_schema被过滤了&#xff0c;猜测是盲注了。 测试发现只要有东…

(七)for循环控制

文章目录 用法while的用法for的用法两者之间的联系可以相互等价用for改写while示例for和while的死循环怎么写for循环见怪不怪表达式1省略第一.三个表达式省略&#xff08;for 改 while&#xff09;全省略即死循环&#xff08;上面已介绍&#xff09; 用法 类比学习while语句 …

mac配置L2TP连接公司内网

1. 打开系统设置 2. 打开网络 3. 点击网络页面其他服务右下角三个点&#xff0c;添加VPN配置中的L2TP 4. 配置VPN&#xff0c;服务器填写公司的服务器ip&#xff0c;共享密钥没有可以随便填写 5. 打开终端编辑文件 sudo vim /etc/ppp/opt…

华为机考入门python3--(4)牛客4-字符串分隔

分类&#xff1a;字符串 知识点&#xff1a; 复制符号* 复制3个0 0*3 000 字符串截取 截取第i位到j-1位 str[i:j] 题目来自【牛客】 input_str input().strip()# 先补齐 if len(input_str) % 8 ! 0: input_str 0 * (8 - len(input_str) % 8) # 每8个分 out…

哪些 3D 建模软件值得推荐?

云端地球是一款免费的在线实景三维建模软件&#xff0c;不需要复杂的技巧&#xff0c;只要需要手机&#xff0c;多拍几张照片&#xff0c;就可以得到完整的三维模型&#xff01; 无论是大场景倾斜摄影测量还是小场景、小物体建模&#xff0c;都可以通过云端地球将二维数据向三…

matplotlib实现动画效果

实现正弦波动画 import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation import numpy as np# 创建图像和轴 fig, ax plt.subplots()# 生成平均分布在0~2*pi之间的100个坐标点 x_data np.linspace(0, 2 * np.pi, 100) # 画出初始图 line, ax.plo…

【鸿蒙】大模型对话应用(一):大模型接口对接与调试

Demo介绍 本demo对接阿里云和百度的大模型API&#xff0c;实现一个简单的对话应用。 DecEco Studio版本&#xff1a;DevEco Studio 3.1.1 Release HarmonyOS API版本&#xff1a;API9 关键点&#xff1a;ArkTS、ArkUI、UIAbility、网络http请求、列表布局 官方接口文档 此…

21.Arrays类

Arrays类 1. 概述2. 常见方法3. sort 方法的自定义排序4. 代码示例5. 输出结果6. 注意事项 具体信息请查看 API 帮助文档 1. 概述 Arrays类是Java中的一个工具类&#xff0c;位于java.util包中。 它提供了一组静态方法&#xff0c;用于操作数组。通过Arrays类&#xff0c;我们…

台式电脑的ip地址在哪里找

在网络连接方面&#xff0c;IP地址是非常重要的信息&#xff0c;它是用于标识网络设备的唯一地址。对于台式电脑用户来说&#xff0c;了解自己设备的IP地址是非常有必要的&#xff0c;因为它可以帮助解决网络连接问题&#xff0c;进行远程访问和共享文件等功能。本文将指导读者…

Redis(秒杀活动、持久化之RDB、AOF)

目录 秒杀活动 一、测压工具jmete的使用 二、java实现秒杀活动 1、myseckillcontroller 2、先启动pos请求添加商品&#xff0c;再启动jmeter进行压测 Redis持久化 一 、Redis持久化之RDB 1.RDB是什么 2. 备份是如何执行的 3.Fork 4. RDB持久化流程 5. dump.rdb文件 6…

想要透明拼接屏展现更加效果,视频源是技术活,尤其作为直播背景

随着科技的飞速发展&#xff0c;视频制作和显示技术也在不断进步。透明拼接屏视频作为一种新型的视频形式&#xff0c;在许多场合都得到了广泛的应用。尼伽小编将深入探讨透明拼接屏视频的制作过程、要求、清晰度&#xff0c;以及目前常作为直播背景的优势。 一、透明拼接屏视频…

【数据结构1-2】二叉树

树形结构不仅能表示数据间的指向关系&#xff0c;还能表示出数据的层次关系&#xff0c;而有很明显的递归性质。因此&#xff0c;我们可以利用树的性质解决更多种类的问题。 但是在平常的使用中&#xff0c;我们并不需要使用这么复杂的结构&#xff0c;只需要建立一个包含int r…

Vue深入学习4—指令和生命周期

1.Vue是怎么识别 v- 指令的&#xff1f; 首先将HTML结构解析成属性列表&#xff0c;存入到数组中&#xff0c;接着遍历数组中的每一个节点&#xff0c;获取到不同指令对应的方法。 // 将HTML看作真正的属性列表 var ndoeAttrs node.attributes; var self this; // 类数组对象…

modbus poll测试工具测试modbus tcp与PLC设备连接使用方法

socket默认端口是502&#xff0c;socket连上之后&#xff0c; 按照modbuspoll工具设置的读写参数 生成的RTU命令格式去组装读PLC的设备数据 modbuspoll工具配置&#xff0c;以v9.9.2中文破解版为例&#xff1a; 首先点连接菜单&#xff08;connection&#xff09;建立连接&…