黄石网站建设推荐,狗和女人做的网站,做校园网站,做安利能开个人网站支持向量机#xff08;support vector machines#xff0c;SVM#xff09;是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器#xff0c;间隔最大使它有别于感知机。
1、线性可分支持向量机与硬间隔最大化
1.1、线性可分支持向量机
考虑一个二分…支持向量机support vector machinesSVM是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器间隔最大使它有别于感知机。
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 xi∈XRn y i ∈ Y { 1 , − 1 } y_i \in{\cal{Y}}\{1,-1\} yi∈Y{1,−1} i 1 , 2 , ⋯ , N i1,2,\cdots,N i1,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 xb0 w⋅xb0它由法向量 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 xb0 w⋅xb0 确定的情况下 ∣ w ⋅ x b ∣ \mid w\cdot xb\mid ∣w⋅xb∣ 能够相对地表示点 x x x 距离超平面的远近而 w ⋅ x b w\cdot xb w⋅xb 的符号与类标记 y y y 的符号是否一致能够表示分类是否正确所以可用量 y ( w ⋅ x b ) y(w\cdot xb) y(w⋅xb) 来表示分类的正确性及确信度这就是函数间隔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\parallel1 ∥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_i1 yi1。点 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∥w∥w⋅xi∥w∥b
其中 ∥ 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−(∥w∥w⋅xi∥w∥b)
一般地当样本点 ( 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_iy_i\Big(\dfrac{w}{\parallel w\parallel}\cdot x_i\dfrac{b}{\parallel w\parallel}\Big) γiyi(∥w∥w⋅xi∥w∥b)
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.}\quady_i\Big(\dfrac{w}{\parallel w\parallel}\cdot x_i\dfrac{b}{\parallel w\parallel}\Big)\geq\gamma,\quad i1,2,\cdots,N \end{aligned} w,bmaxs.t.γyi(∥w∥w⋅xi∥w∥b)≥γ,i1,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.}\quady_i(w\cdot x_ib)\geq\hat{\gamma},\quad i1,2,\cdots,N \end{aligned} w,bmaxs.t.∥w∥γ^yi(w⋅xib)≥γ^,i1,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} ∥w∥1 和最小化 1 2 ∥ w ∥ 2 \dfrac{1}{2}\parallel w\parallel^2 21∥w∥2 是等价的于是 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.}\quady_i(w\cdot x_ib)-1\geq0,\quad i1,2,\cdots,N \end{aligned} w,bmins.t.21∥w∥2yi(w⋅xib)−1≥0,i1,2,⋯,N
如果求出了上述优化问题的解 w ∗ , b ∗ w^\ast,b^\ast w∗,b∗那么就可以得到最大间隔分离超平面 w ∗ ⋅ x b ∗ 0 w^\ast\cdot xb^\ast0 w∗⋅xb∗0 及分类决策函数 f ( x ) s i g n ( w ∗ ⋅ x b ∗ ) f(x) {sign} (w^\ast\cdot xb^\ast) f(x)sign(w∗⋅xb∗)即线性可分支持向量机模型。
综上所述就是线性可分支持向量机的学习算法——最大间隔法maximum margin method。
2支持向量和间隔边界
在线性可分情况下训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量support vector。支持向量是使约束条件 y i ( w ⋅ x i b ) − 1 ≥ 0 y_i(w\cdot x_ib)-1\geq0 yi(w⋅xib)−1≥0 等号成立的点即 y i ( w ⋅ x i b ) − 1 0 y_i(w\cdot x_ib)-10 yi(w⋅xib)−10
对 y i 1 y_i1 yi1 的正例点支持向量在超平面 H 1 : w ⋅ x b 1 H_1:w\cdot xb1 H1:w⋅xb1
上对 y i − 1 y_i-1 yi−1 的负例点支持向量在超平面 H 2 : w ⋅ x b − 1 H_2:w\cdot xb-1 H2:w⋅xb−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} ∥w∥2。 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,\ i1,2,\cdots,N αi≥0, i1,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_{i1}^N\alpha_iy_i(w\cdot x_ib)\sum_{i1}^N\alpha_i L(w,b,α)21∥w∥2−i1∑Nαiyi(w⋅xib)i1∑Nα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_{i1}^N\alpha_iy_ix_i0\\ \nabla_bL(w,b,\alpha)-\sum_{i1}^N\alpha_iy_i0 \end{aligned} ∇wL(w,b,α)w−i1∑Nαiyixi0∇bL(w,b,α)−i1∑Nαiyi0
得 w ∑ i 1 N α i y i x i ∑ i 1 N α i y i 0 \begin{aligned} w\sum_{i1}^N\alpha_iy_ix_i\\ \sum_{i1}^N\alpha_iy_i0 \end{aligned} wi1∑Nαiyixii1∑Nαiyi0
将其代入拉格朗日函数即得 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_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i1}^N\alpha_iy_i\Big(\Big(\sum_{i1}^N\alpha_jy_jx_j\Big)\cdot x_ib\Big)\sum_{i1}^N\alpha_i\\ -\dfrac{1}{2}\sum_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\sum_{i1}^N\alpha_i \end{aligned} L(w,b,α)21i1∑Nj1∑Nαiαjyiyj(xi⋅xj)−i1∑Nαiyi((i1∑Nαjyjxj)⋅xib)i1∑Nαi−21i1∑Nj1∑Nαiαjyiyj(xi⋅xj)i1∑Nα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_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\sum_{i1}^N\alpha_i w,bminL(w,b,α)−21i1∑Nj1∑Nαiαjyiyj(xi⋅xj)i1∑Nα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_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\sum_{i1}^N\alpha_i\\ \rm{s.t.}\quad\sum_{i1}^N\alpha_iy_i0\\ \alpha_i\geq 0,\quad i1,2,\cdots,N \end{aligned} αmaxs.t.−21i1∑Nj1∑Nαiαjyiyj(xi⋅xj)i1∑Nαii1∑Nαiyi0αi≥0,i1,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_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i1}^N\alpha_i\\ \rm{s.t.}\quad\sum_{i1}^N\alpha_iy_i0\\ \alpha_i\geq 0,\quad i1,2,\cdots,N \end{aligned} αmins.t.21i1∑Nj1∑Nαiαjyiyj(xi⋅xj)−i1∑Nαii1∑Nαiyi0αi≥0,i1,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_{i1}^N\alpha_i^\ast y_ix_i\\ b^\asty_j-\sum_{i1}^N\alpha_i^\ast y_i(x_i\cdot x_j) \end{aligned} w∗b∗i1∑Nαi∗yixiyj−i1∑Nαi∗yi(xi⋅xj)
从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法是线性可分支持向量机学习的基本算法。
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 xi∈XRn y i ∈ Y { 1 , − 1 } y_i \in{\cal{Y}}\{1,-1\} yi∈Y{1,−1} i 1 , 2 , ⋯ , N i1,2,\cdots,N i1,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 ξi≥0使函数间隔加上松弛变量大于等于 1。这样约束条件变为 y i ( w ⋅ x i b ) ≥ 1 − ξ i y_i(w\cdot x_ib)\geq 1-\xi_i yi(w⋅xib)≥1−ξi
同时对每个松弛变量 ξ i \xi_i ξi支付一个代价 ξ i \xi_i ξi。目标函数由原来的 1 2 ∥ w ∥ 2 \dfrac{1}{2}\parallel w\parallel^2 21∥w∥2 变成 1 2 ∥ w ∥ 2 C ∑ i 1 N ξ i \dfrac{1}{2}\parallel w\parallel^2C\sum_{i1}^N\xi_i 21∥w∥2Ci1∑Nξi
这里 C 0 C0 C0 称为惩罚参数 C C C 值大时对误分类的惩罚增大 C C C 值小时对误分类的惩罚减小。最小化上式目标函数包含两层含义使 1 2 ∥ w ∥ 2 \dfrac{1}{2}\parallel w\parallel^2 21∥w∥2 尽量小即间隔尽量大同时使误分类点的个数尽量小 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^2C\sum_{i1}^N\xi_i\\ \rm{s.t.}\quady_i(w\cdot x_ib)\geq1-\xi_i,\quad i1,2,\cdots,N\\ \xi_i\geq0,\quad i1,2,\cdots,N \end{aligned} w,b,ξmins.t.21∥w∥2Ci1∑Nξiyi(w⋅xib)≥1−ξi,i1,2,⋯,Nξi≥0,i1,2,⋯,N
设上述问题的解是 w ∗ , b ∗ w^\ast,b^\ast w∗,b∗于是得到分类超平面 w ∗ ⋅ x b ∗ 0 w^\ast\cdot xb^\ast0 w∗⋅xb∗0 及分类决策函数 f ( x ) s i g n ( w ∗ ⋅ x b ∗ ) f(x)sign(w^\ast\cdot xb^\ast) f(x)sign(w∗⋅xb∗)。称这样的模型为训练样本线性不可分时的线性支持向量机简称线性支持向量机。
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_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i1}^N\alpha_i\\ \rm{s.t.}\quad\sum_{i1}^N\alpha_iy_i0\\ 0\leq\alpha_i\leq C,\quad i1,2,\cdots,N \end{aligned} αmins.t.21i1∑Nj1∑Nαiαjyiyj(xi⋅xj)−i1∑Nαii1∑Nαiyi00≤αi≤C,i1,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^\ast0 α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^\astC αi∗C则 ξ i 0 \xi_i0 ξi0支持向量 x i x_i xi 刚好落在间隔边界上若 α i ∗ C , 0 ξ i 1 \alpha_i^\astC,0\xi_i1 αi∗C,0ξi1则分类正确 x i x_i xi 在间隔边界与分离超平面之间若 α i ∗ C , ξ i 1 \alpha_i^\astC,\xi_i1 αi∗C,ξi1则 x i x_i xi 在分离超平面上若 α i ∗ C , ξ i 1 \alpha_i^\astC,\xi_i1 αi∗C,ξi1则 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 xi∈XRn对应的标记有两类 y i ∈ Y { − 1 , 1 } , i 1 , 2 , ⋯ , N y_i\in \cal{Y}\{-1,1\},i1,2,\cdots,\it N yi∈Y{−1,1},i1,2,⋯,N。如果能用 R n R^n Rn 的一个超曲面将正负实例正确分开则称这个问题为非线性可分问题。
分线性问题往往不好求解所以采用的方法是进行一个非线性映射将非线性问题转换为线性问题通过解线性问题的方法求解非线性问题如上图所示将左图中椭圆变换成右图的直线将非线性分类问题变换为线性分类问题。
设原空间为 X ⊂ R 2 \cal{X} \subset \it{R}^2 X⊂R2 x ( x ( 1 ) , x ( 2 ) ) T ∈ X x\big(x^{(1)},x^{(2)}\big)^T\in\cal{X} x(x(1),x(2))T∈X新空间为 Z ⊂ R 2 \cal{Z} \subset \it{R}^2 Z⊂R2 z ( z ( 1 ) , z ( 2 ) ) T ∈ Z z\big(z^{(1)},z^{(2)}\big)^T\in\cal{Z} z(z(1),z(2))T∈Z定义从原空间到新空间的变换映射 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 X⊂R2 变换为新空间 Z ⊂ R 2 \cal{Z} \subset \it{R}^2 Z⊂R2原空间中的点相应地变换为新空间中的点原空间中的椭圆 w 1 ( x ( 1 ) ) 2 w 2 ( x ( 2 ) ) 2 b 0 w_1(x^{(1)})^2w_2(x^{(2)})^2b0 w1(x(1))2w2(x(2))2b0
变换成为新空间中的直线 w 1 z ( 1 ) w 2 z ( 2 ) b 0 w_1z^{(1)}w_2z^{(2)}b0 w1z(1)w2z(2)b0
在变换后的新空间里直线 w 1 z ( 1 ) w 2 z ( 2 ) b 0 w_1z^{(1)}w_2z^{(2)}b0 w1z(1)w2z(2)b0 可以将变换后的正负实例点正确分开。这样原空间的非线性可分问题就变成了新空间的线性可分问题。
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):X→H
使得对所有 x , z ∈ X x,z\in\cal{X} x,z∈X函数 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 xi⋅xj 可以用核函数 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_{i1}^N\sum_{j1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i1}^N\alpha_i W(α)21i1∑Nj1∑NαiαjyiyjK(xi,xj)−i1∑Nα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_{i1}^{N_s}\alpha_i^\ast y_i\phi(x_i)\cdot\phi(x)b^\ast\Big)\\ sign\Big(\sum_{i1}^{N_s}\alpha_i^\ast y_iK(x_i,x)b^\ast\Big) \end{aligned} f(x)sign(i1∑Nsαi∗yiϕ(xi)⋅ϕ(x)b∗)sign(i1∑Nsαi∗yiK(xi,x)b∗)
3.2、常用核函数
多项式核函数polynomial kernel function K ( x , z ) ( x ⋅ z 1 ) p K(x,z)(x\cdot z 1)^p K(x,z)(x⋅z1)p高斯核函数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σ2∥x−z∥)
3.3、非线性支持向量分类机
如上所述利用核技巧可以将线性分类的学习问题应用到非线性分类问题中去。将线性支持向量机扩展到非线性支持向量机只需将线性支持向量机对偶形式中的内积换成核函数。
