支持向量机SVM和核函数详述

我不是女神ヾ 2023-07-18 09:17 15阅读 0赞

## 1、拉格朗日乘子 ##

作为一种优化算法，拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。  
如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题？拉格朗日乘数法从数学意义入手，通过引入拉格朗日乘子建立极值条件，对n个变量分别求偏导对应了n个方程，然后加上k个约束条件（对应k个拉格朗日乘子）一起构成包含了（n+k）变量的（n+k）个方程的方程组问题，这样就能根据求方程组的方法对其进行求解。

###### 无条件约束： ######

min ⁡ f ( x ) \\min f(x) minf(x)

###### 等式条件约束： ######

min ⁡ f ( x ) s . t .       h k ( x ) = 0        k = 1 , 2 , … , l F ( x , λ ) = f ( x ) + ∑ k = 1 l λ k h k ( x ) \\min f(x) \\\\ s.t.\\ \\ \\ \\ \\ h\_k(x)=0 \\ \\ \\ \\ \\ \\ k=1, 2, \\dots, l \\\\ F(x, \\lambda)=f(x)+\\sum\_\{k=1\}^l\\lambda\_kh\_k(x) minf(x)s.t.     hk(x)=0      k=1,2,…,lF(x,λ)=f(x)\+k=1∑lλkhk(x)

###### 不等式条件约束： ######

min ⁡ f ( x ) s . t .       h j ( x ) = 0        j = 1 , 2 , … , p             g k ( x ) ≤ 0        k = 1 , 2 , … , q L ( x , λ , μ ) = f ( x ) + ∑ j = 1 p λ j h j ( x ) + ∑ k = 1 q μ k g k ( x ) \\min f(x) \\\\ s.t.\\ \\ \\ \\ \\ h\_j(x)=0 \\ \\ \\ \\ \\ \\ j=1, 2, \\dots, p \\\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ g\_k(x) \\le 0 \\ \\ \\ \\ \\ \\ k=1, 2, \\dots, q \\\\ L(x, \\lambda, \\mu)=f(x)+\\sum\_\{j=1\}^p\\lambda\_jh\_j(x)+\\sum\_\{k=1\}^q\\mu\_kg\_k(x) minf(x)s.t.     hj(x)=0      j=1,2,…,p           gk(x)≤0      k=1,2,…,qL(x,λ,μ)=f(x)\+j=1∑pλjhj(x)\+k=1∑qμkgk(x)

## 2、线性分类器 ##

首先给出一个非常非常简单的分类问题（线性可分），我们要用一条直线，将下图中黑色的点和白色的点分开，很显然，图上的这条直线就是我们要求的直线之一（可以有无数条这样的直线）。  
![20200325135433539.png][]  
假如说，我们令黑色的点 = -1， 白色的点 = +1，直线 f ( x ) = w x + b f(x) = wx + b f(x)=wx\+b。当向量x的维度=2的时候，f(x) 表示二维空间中的一条直线， 当x的维度=3的时候，f(x) 表示三维空间中的一个平面，当x的维度=n > 3的时候，表示n维空间中的超平面。  
一个很直观的感受是，让这条直线到给定样本中最近的点最远，这句话读起来比较拗口，下面给出几个图，来说明一下：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70][]  
这两种分法哪个更好呢？  
就像我们平时判断一个人是男还是女，就是很难出现分错的情况，这就是男、女两个类别之间的间隙非常的大导致的，让我们可以更准确的进行分类。在SVM中，称为Maximum Marginal，是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是有很多道理的，比如说从概率的角度上来说，就是使得置信度最小的点置信度最大，从实践的角度来说，这样的效果非常好。上图被红色和蓝色的线圈出来的点就是所谓的支持向量（support vector）。

## 3、线性可分支持向量机 ##

在这里假设二维特征向量 X =（x1，x2），做另外一个假设就是把b看作是另外一个weight，那么超平面就可以更新为：  
 b + w 1 ∗ x 1 + w 2 ∗ x 2 = 0 b+ w1 \* x1 +w2 \* x2 = 0 b\+w1∗x1\+w2∗x2=0  
所有超平面右上方的点满足：  
 b + w 1 ∗ x 1 + w 2 ∗ x 2 > 0 b + w1 \* x1 +w2 \* x2 > 0 b\+w1∗x1\+w2∗x2>0  
所有超平面左下方的点满足：  
 b + w 1 ∗ x 1 + w 2 ∗ x 2 < 0 b+ w1 \* x1 +w2 \* x2 < 0 b\+w1∗x1\+w2∗x2<0  
给定一个特征空间上的训练数据集： T = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , ( x 3 , y 3 ) … ( x n , y n ) \} T=\\\{(x\_1,y\_1),(x\_2,y\_2),(x\_3,y\_3)\\dots(x\_n,y\_n)\\\} T=\{ (x1,y1),(x2,y2),(x3,y3)…(xn,yn)\}，其中， x 1 ∈ R n ， y i ∈ \{ + 1 , − 1 \} , i = 1 , 2 , 3 , 4 … N x\_1∈R^n，y\_i\\in\\\{+1,-1\\\},i=1, 2, 3, 4\\dots N x1∈Rn，yi∈\{ \+1,−1\},i=1,2,3,4…N， x i x\_i xi为第i个实例（若 n>1， x i x\_i xi为向量）， y i y\_i yi为 x i x\_i xi的类标记，当 y i = + 1 y\_i=+1 yi=\+1时，称 x i x\_i xi为正例，当 y i = − 1 y\_i=-1 yi=−1时，称 x i x\_i xi为负例， ( x i , y i ) (x\_i,y\_i) (xi,yi)称为样本点。  
对平面中的点进行等比例缩小或者放大，总有一个比例，使得支持向量点到超平面的距离为1。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70 1][]

## 4、SVM的目标函数 ##

把 w 1 w\_1 w1和 w 2 w\_2 w2看成一个向量， x 1 x\_1 x1， x 2 x\_2 x2也是一个向量，则有  
 y ( x ) = w T Φ ( x ) + b \{ y ( x i ) > 0 ⟺ y i = + 1 y ( x i ) < 0 ⟺ y i = − 1 ⟹ y i ⋅ y ( x i ) > 0 y(x)=w^T\\Phi(x)+b \\\\ \\begin\{cases\} y(x\_i)\\gt 0\\Longleftrightarrow y\_i=+1 \\\\ y(x\_i)\\lt 0\\Longleftrightarrow y\_i=-1 \\end\{cases\} \\Longrightarrow y\_i\\cdot y(x\_i)\\gt 0 y(x)=wTΦ(x)\+b\{ y(xi)>0⟺yi=\+1y(xi)<0⟺yi=−1⟹yi⋅y(xi)>0  
w，b等比例缩放，等价于点到超平面的距离缩放，从而  
 y i ⋅ y ( x i ) ∣ ∣ w ∣ ∣ = y i ⋅ ( w T ⋅ Φ ( x i ) + b ) ∣ ∣ w ∣ ∣ \\frac\{y\_i\\cdot y(x\_i)\}\{||w||\}=\\frac\{y\_i\\cdot(w^T\\cdot\\Phi(x\_i)+b)\}\{||w||\} ∣∣w∣∣yi⋅y(xi)=∣∣w∣∣yi⋅(wT⋅Φ(xi)\+b)  
前面已经提到过，让这条直线到给定样本中最近的点最远，即目标函数是  
 arg ⁡ max ⁡ w , b \{ 1 ∣ ∣ w ∣ ∣ min ⁡ \[ y i ⋅ ( w T ⋅ Φ ( x i ) + b ) \] \} \\arg\\max\_\{w,b\}\\\{\\frac\{1\}\{||w||\}\\min\[y\_i\\cdot(w^T\\cdot\\Phi(x\_i)+b)\]\\\} argw,bmax\{ ∣∣w∣∣1min\[yi⋅(wT⋅Φ(xi)\+b)\]\}  
因为这里的约束条件是支持向量点到超平面的距离为1，即  
 y i ⋅ ( w T ⋅ Φ ( x i ) + b ) ≥ 1 y\_i\\cdot(w^T\\cdot\\Phi(x\_i)+b)\\ge 1 yi⋅(wT⋅Φ(xi)\+b)≥1  
到这里，我们前面的问题转化为了求  
 arg ⁡ max ⁡ w , b 1 ∣ ∣ w ∣ ∣ s . t .       y i ⋅ ( w T ⋅ Φ ( x i ) + b ) ≥ 1       i = 1 , 2 , … , n \\arg\\max\_\{w,b\}\\frac\{1\}\{||w||\} \\\\ s.t.\\ \\ \\ \\ \\ y\_i\\cdot(w^T\\cdot\\Phi(x\_i)+b)\\ge 1\\ \\ \\ \\ \\ i=1, 2,\\dots, n argw,bmax∣∣w∣∣1s.t.     yi⋅(wT⋅Φ(xi)\+b)≥1     i=1,2,…,n  
 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣是w的二范数，跟 w ⋅ w \\sqrt\{w\\cdot w\} w⋅w表达式是一个意思，之前得到，求SVM的关键就是，最大化这个式子等价于最小化 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣，另外由于 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣是一个单调函数，我们可以对其加入平方，和前面的系数。  
 max ⁡ 1 ∣ ∣ w ∣ ∣ ⟶ min ⁡ 1 2 ∣ ∣ w ∣ ∣ 2 s . t .        y i ( w T ⋅ Φ ( x i ) + b ) ≥ 1 ,        i = 1 , 2 , … , n \\max\\frac\{1\}\{||w||\}\\longrightarrow\\min\\frac\{1\}\{2\}||w||^2 \\\\ s.t.\\ \\ \\ \\ \\ \\ y\_i(w^T\\cdot\\Phi(x\_i)+b)\\ge 1,\\ \\ \\ \\ \\ \\ i=1, 2,\\dots, n max∣∣w∣∣1⟶min21∣∣w∣∣2s.t.      yi(wT⋅Φ(xi)\+b)≥1,      i=1,2,…,n  
转化为对偶问题，并优化求解。  
这个优化问题可以用拉格朗日乘子法去解，使用了KKT条件的理论，这里直接作出这个式子的拉格朗日目标函数：  
 L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 n α i ( y i ( w T x i + b ) − 1 ) L(w, b, \\alpha)=\\frac\{1\}\{2\}||w||^2-\\sum\_\{i=1\}^n\\alpha\_i(y\_i(w^Tx\_i+b)-1) L(w,b,α)=21∣∣w∣∣2−i=1∑nαi(yi(wTxi\+b)−1)  
求解这个式子的过程需要拉格朗日对偶性的相关知识。  
原问题是极小极大问题：  
 min ⁡ w , b max ⁡ α L ( w , b , α ) \\min\_\{w,b\}\\max\_\{\\alpha\}L(w, b, \\alpha) w,bminαmaxL(w,b,α)  
问题的对偶问题，是极大极小问题：  
 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的偏导数为0，得到关于原问题的一个表达式：  
 ∂ L ∂ w = 0 ⟹ w = ∑ i = 1 n α i y i Φ ( x n ) ∂ L ∂ b = 0 ⟹ 0 = ∑ i = 1 n α i y i \\begin\{aligned\} \\frac\{\\partial L\}\{\\partial w\}=0&\\Longrightarrow w=\\sum\_\{i=1\}^n\\alpha\_iy\_i\\Phi(x\_n) \\\\ \\frac\{\\partial L\}\{\\partial b\}=0&\\Longrightarrow 0=\\sum\_\{i=1\}^n\\alpha\_iy\_i \\end\{aligned\} ∂w∂L=0∂b∂L=0⟹w=i=1∑nαiyiΦ(xn)⟹0=i=1∑nαiyi  
目标函数 L ( w , b , α ) L(w, b, \\alpha) L(w,b,α)的推导过程如下：  
 L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 α i \[ y ( i ) ( w T x ( i ) + b ) − 1 \] = 1 2 w T w − ∑ i = 1 m α i y ( i ) w T x ( i ) − ∑ i = 1 m α i y ( i ) b + ∑ i = 1 m α i = 1 2 w T ∑ i = 1 m α i y ( i ) x ( i ) − ∑ i = 1 m α i y ( i ) w T x ( i ) − ∑ i = 1 m α i y ( i ) b + ∑ i = 1 m α i = 1 2 w T ∑ i = 1 m α i y ( i ) x ( i ) − w T ∑ i = 1 m α i y ( i ) x ( i ) − ∑ i = 1 m α i y ( i ) b + ∑ i = 1 m α i = − 1 2 w T ∑ i = 1 m α i y ( i ) x ( i ) − b ∑ i = 1 m α i y ( i ) + ∑ i = 1 m α i = − 1 2 ( ∑ i = 1 m α i y ( i ) x ( i ) ) T ∑ i = 1 m α i y ( i ) x ( i ) − b ∑ i = 1 m α i y ( i ) + ∑ i = 1 m α i = − 1 2 ( ∑ i = 1 m a i y i x i ) T ( ∑ i = 1 m a i y i x i ) − b ∑ i = 1 m a i y i + ∑ i = 1 m a i = − 1 2 ∑ i = 1 m a i y i x i T ∑ i = 1 m a i y i x i + ∑ i = 1 m a i = − 1 2 ∑ i = 1 , j = 1 m a i y i x i T a j y j x j + ∑ i = 1 m a i = ∑ i = 1 m a i − 1 2 ∑ i = 1 , j = 1 m a i a j y i y j x i T x j max ⁡ α min ⁡ w , b L ( w , b , α ) = 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\} L(w, b, \\alpha)&=\\frac\{1\}\{2\}||w||^2-\\sum\_\{i=1\}\\alpha\_i\[y^\{(i)\}(w^Tx^\{(i)\}+b)-1\] \\\\ &=\\frac\{1\}\{2\}w^Tw-\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}w^Tx^\{(i)\}-\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}b+\\sum\_\{i=1\}^m\\alpha\_i \\\\ &=\\frac\{1\}\{2\}w^T\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}x^\{(i)\}-\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}w^Tx^\{(i)\}-\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}b+\\sum\_\{i=1\}^m\\alpha\_i \\\\ &=\\frac\{1\}\{2\}w^T\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}x^\{(i)\}-w^T\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}x^\{(i)\}-\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}b+\\sum\_\{i=1\}^m\\alpha\_i \\\\ &=-\\frac\{1\}\{2\}w^T\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}x^\{(i)\}-b\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}+\\sum\_\{i=1\}^m\\alpha\_i \\\\ &=-\\frac\{1\}\{2\}(\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}x^\{(i)\})^T\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}x^\{(i)\}-b\\sum\_\{i=1\}^m\\alpha\_iy^\{(i)\}+\\sum\_\{i=1\}^m\\alpha\_i \\\\ &=-\\frac\{1\}\{2\}(\\sum\_\{i=1\}^ma\_iy\_ix\_i)^T(\\sum\_\{i=1\}^ma\_iy\_ix\_i)-b\\sum\_\{i=1\}^ma\_iy\_i+\\sum\_\{i=1\}^ma\_i \\\\ &=-\\frac\{1\}\{2\}\\sum\_\{i=1\}^ma\_iy\_ix\_i^T\\sum\_\{i=1\}^ma\_iy\_ix\_i+\\sum\_\{i=1\}^ma\_i \\\\ &=-\\frac\{1\}\{2\}\\sum\_\{i=1, j=1\}^ma\_iy\_ix\_i^Ta\_jy\_jx\_j+\\sum\_\{i=1\}^ma\_i \\\\ &=\\sum\_\{i=1\}^ma\_i-\\frac\{1\}\{2\}\\sum\_\{i=1, j=1\}^ma\_ia\_jy\_iy\_jx\_i^Tx\_j \\\\ \\max\_\{\\alpha\}\\min\_\{w,b\}L(w, b, \\alpha)&=\\min\_\{\\alpha\}\\frac\{1\}\{2\}\\sum\_\{i=1\}^n\\sum\_\{j=1\}^n\\alpha\_i\\alpha\_jy\_iy\_j(\\Phi(x\_i)\\cdot\\Phi(x\_j))-\\sum\_\{i=1\}^n\\alpha\_i \\\\ s.t.\\ \\ \\ \\ \\ \\ &\\sum\_\{i=1\}^n\\alpha\_iy\_i=0 \\\\ &\\alpha\_i\\ge 0,\\ \\ \\ \\ \\ \\ i=1, 2,\\dots, n \\end\{aligned\} L(w,b,α)αmaxw,bminL(w,b,α)s.t.      =21∣∣w∣∣2−i=1∑αi\[y(i)(wTx(i)\+b)−1\]=21wTw−i=1∑mαiy(i)wTx(i)−i=1∑mαiy(i)b\+i=1∑mαi=21wTi=1∑mαiy(i)x(i)−i=1∑mαiy(i)wTx(i)−i=1∑mαiy(i)b\+i=1∑mαi=21wTi=1∑mαiy(i)x(i)−wTi=1∑mαiy(i)x(i)−i=1∑mαiy(i)b\+i=1∑mαi=−21wTi=1∑mαiy(i)x(i)−bi=1∑mαiy(i)\+i=1∑mαi=−21(i=1∑mαiy(i)x(i))Ti=1∑mαiy(i)x(i)−bi=1∑mαiy(i)\+i=1∑mαi=−21(i=1∑maiyixi)T(i=1∑maiyixi)−bi=1∑maiyi\+i=1∑mai=−21i=1∑maiyixiTi=1∑maiyixi\+i=1∑mai=−21i=1,j=1∑maiyixiTajyjxj\+i=1∑mai=i=1∑mai−21i=1,j=1∑maiajyiyjxiTxj=αmin21i=1∑nj=1∑nαiαjyiyj(Φ(xi)⋅Φ(xj))−i=1∑nαii=1∑nαiyi=0αi≥0,      i=1,2,…,n  
假设有最优解 α ∗ \\alpha^\{\\ast\} α∗，则有：  
 w ∗ = ∑ i = 1 N α i ∗ y i Φ ( x i ) b ∗ = y i − ∑ i = 1 N α i ∗ y i ( Φ ( x i ) ⋅ Φ ( x j ) ) \\begin\{aligned\} w^\{\\ast\}&=\\sum\_\{i=1\}^N\\alpha\_i^\{\\ast\}y\_i\\Phi(x\_i) \\\\ b^\{\\ast\}&=y\_i-\\sum\_\{i=1\}^N\\alpha\_i^\{\\ast\}y\_i(\\Phi(x\_i)\\cdot\\Phi(x\_j)) \\end\{aligned\} w∗b∗=i=1∑Nαi∗yiΦ(xi)=yi−i=1∑Nαi∗yi(Φ(xi)⋅Φ(xj))  
求得分离超平面： w ∗ Φ ( x ) + b ∗ = 0 w^\{\\ast\}\\Phi(x)+b^\{\\ast\}=0 w∗Φ(x)\+b∗=0  
分类决策函数： f ( x ) = s i g n ( w ∗ Φ ( x ) + b ∗ ) f(x)=sign(w^\{\\ast\}\\Phi(x)+b^\{\\ast\}) f(x)=sign(w∗Φ(x)\+b∗)  
示例：给定三个数据点：正例点x1=(3,3)，x2=(4,3)，负例点x3=(1,1)，求线性可分支持向量机。  
![20200325181112327.png][]  
 min ⁡ α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 n α i = 1 2 ( 18 α 1 2 + 25 α 2 2 + 2 α 3 2 + 42 α 1 α 2 − 12 α 1 α 3 − 14 α 2 α 3 ) − α 1 − α 2 − α 3 s . t .        3 α 1 + 3 α 2 − α 3 = 0 α i ≥ 0 ,       i = 1 , 2 , 3 \\begin\{aligned\} &\\min\_\{\\alpha\}\\frac\{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 \\\\ &=\\frac\{1\}\{2\}(18\\alpha\_1^2+25\\alpha\_2^2+2\\alpha\_3^2+42\\alpha\_1\\alpha\_2-12\\alpha\_1\\alpha\_3-14\\alpha\_2\\alpha\_3)-\\alpha\_1-\\alpha\_2-\\alpha\_3 \\\\ s.t.\\ \\ \\ \\ \\ \\ &3\\alpha\_1+3\\alpha\_2-\\alpha\_3=0 \\\\ &\\alpha\_i\\ge0,\\ \\ \\ \\ \\ i=1, 2, 3 \\end\{aligned\} s.t.      αmin21i=1∑nj=1∑nαiαjyiyj(xi⋅xj)−i=1∑nαi=21(18α12\+25α22\+2α32\+42α1α2−12α1α3−14α2α3)−α1−α2−α33α1\+3α2−α3=0αi≥0,     i=1,2,3

## 5、引入松弛变量的线性不可分支持向量机 ##

我们知道所有数都不那么干净，不能100%线性可分。我们可以通过引入松弛变量，来允许有些数据点可以处于分割面的错误的一侧。  
需要加一个松弛因子 ξ i ≥ 0 \\xi\_i\\ge0 ξi≥0：  
 y i ( w ⋅ x i + b ) ≥ 1 − ξ i y\_i(w\\cdot x\_i+b)\\ge1-\\xi\_i yi(w⋅xi\+b)≥1−ξi  
目标函数：  
 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\}\\frac\{1\}\{2\}||w||^2+C\\sum\_\{i=1\}^N\\xi\_i \\\\ s.t.\\ \\ \\ \\ \\ &y\_i(w\\cdot x\_i+b)\\ge1-\\xi\_i,\\ \\ \\ \\ \\ i=1, 2,\\dots, n \\\\ &\\xi\_i\\ge0, \\ \\ \\ \\ \\ i=1, 2, \\dots, n \\end\{aligned\} s.t.     w,bmin21∣∣w∣∣2\+Ci=1∑Nξiyi(w⋅xi\+b)≥1−ξi,     i=1,2,…,nξi≥0,     i=1,2,…,n  
拉格朗日函数：  
 L ( w , b , ξ , α , μ ) = 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ i = 1 n ξ i − ∑ i = 1 n α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − ∑ i = 1 n μ i ξ i L(w, b, \\xi, \\alpha, \\mu)=\\frac\{1\}\{2\}||w||^2+C\\sum\_\{i=1\}^n\\xi\_i-\\sum\_\{i=1\}^n\\alpha\_i(y\_i(w\\cdot x\_i+b)-1+\\xi\_i)-\\sum\_\{i=1\}^n\\mu\_i\\xi\_i L(w,b,ξ,α,μ)=21∣∣w∣∣2\+Ci=1∑nξi−i=1∑nαi(yi(w⋅xi\+b)−1\+ξi)−i=1∑nμiξi  
C代表惩罚系数，即如果某个x是属于某一类，但是它偏离了该类，跑到边界上其他类的地方去了，C越大表明越不想放弃这个点，边界就会缩小（sklearn里面默认是1）。  
接下来就是同样的，求解一个拉格朗日对偶问题，得到一个原问题的对偶问题的表达式：  
 min ⁡ w , b max ⁡ α L ( w , b , ξ , α , μ )      原 问 题 ⟹ max ⁡ α min ⁡ w , b L ( w , b , ξ , α , μ )      对 偶 问 题 \\begin\{aligned\} &\\min\_\{w,b\}\\max\_\{\\alpha\}L(w, b, \\xi, \\alpha, \\mu) \\ \\ \\ \\ 原问题\\\\ \\Longrightarrow &\\max\_\{\\alpha\}\\min\_\{w,b\}L(w, b, \\xi, \\alpha, \\mu) \\ \\ \\ \\ 对偶问题 \\end\{aligned\} ⟹w,bminαmaxL(w,b,ξ,α,μ)    原问题αmaxw,bminL(w,b,ξ,α,μ)    对偶问题  
对 w , b , ξ w, b, \\xi w,b,ξ求偏导：  
 ∂ L ∂ w = 0 ⟹ w = ∑ i = 1 n α i y i Φ ( x n ) ∂ L ∂ b = 0 ⟹ 0 = ∑ i = 1 n α i y i ∂ L ∂ ξ = 0 ⟹ C − α i − μ i = 0 \\begin\{aligned\} \\frac\{\\partial L\}\{\\partial w\}=0&\\Longrightarrow w=\\sum\_\{i=1\}^n\\alpha\_iy\_i\\Phi(x\_n) \\\\ \\frac\{\\partial L\}\{\\partial b\}=0&\\Longrightarrow 0=\\sum\_\{i=1\}^n\\alpha\_iy\_i \\\\ \\frac\{\\partial L\}\{\\partial\\xi\}=0&\\Longrightarrow C-\\alpha\_i-\\mu\_i=0 \\end\{aligned\} ∂w∂L=0∂b∂L=0∂ξ∂L=0⟹w=i=1∑nαiyiΦ(xn)⟹0=i=1∑nαiyi⟹C−αi−μi=0  
带入得：  
 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, \\xi\}L(w, b, \\xi, \\alpha, \\mu)=-\\frac\{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,b,ξminL(w,b,ξ,α,μ)=−21i=1∑nj=1∑nαiαjyiyj(xi⋅xj)\+i=1∑nαi  
对原问题求极大得：  
 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 C − α i − μ i = 0 α i ≥ 0 μ i ≥ 0 ,      i = 1 , 2 , … , n \\begin\{aligned\} &\\max\_\{\\alpha\}-\\frac\{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 \\\\ s.t.\\ \\ \\ \\ &\\sum\_\{i=1\}^n\\alpha\_iy\_i=0 \\\\ &C-\\alpha\_i-\\mu\_i=0 \\\\ &\\alpha\_i\\ge0 \\\\ &\\mu\_i\\ge0, \\ \\ \\ \\ i=1,2,\\dots,n \\end\{aligned\} s.t.    αmax−21i=1∑nj=1∑nαiαjyiyj(xi⋅xj)\+i=1∑nαii=1∑nαiyi=0C−αi−μi=0αi≥0μi≥0,    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 0 ≤ α i ≤ C ,       i = 1 , 2 , … , n \\begin\{aligned\} &\\min\_\{\\alpha\}\\frac\{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 \\\\ s.t.\\ \\ \\ \\ &\\sum\_\{i=1\}^n\\alpha\_iy\_i=0 \\\\ &0\\le\\alpha\_i\\le C, \\ \\ \\ \\ \\ i=1,2,\\dots, n \\end\{aligned\} s.t.    αmin21i=1∑nj=1∑nαiαjyiyj(xi⋅xj)−i=1∑nαii=1∑nαiyi=00≤αi≤C,     i=1,2,…,n  
 α i \\alpha\_i αi的取值范围是与线性可分的对偶问题表达式的不同之处。在线性不可分情况下得到的对偶问题，不同的地方就是α的范围从\[0, +∞)，变为了\[0, C\]，增加的惩罚 ε \\varepsilon ε没有为对偶问题增加什么复杂度。

## 6、SVM 序列最小化方法SMO ##

SMO是求两个拉格朗日乘子优化问题的解，假设 α 1 \\alpha\_1 α1和 α 2 \\alpha\_2 α2是变量，其他是定值：  
 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 min ⁡ α 1 , α 2 W ( α 1 , α 2 ) = 1 2 K 11 α 1 T + 1 2 K 22 α 2 2 + y 1 y 2 α 1 α 2 K 12 − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 N y i α i K i 1 + y 2 α 2 ∑ i = 3 N y i α i K i 2 s . t .      α 1 y 1 + α 2 y 2 = − ∑ i = 3 N y i α i = ζ 0 ≤ α i ≤ C \\begin\{aligned\} &\\min\_\{\\alpha\}\\frac\{1\}\{2\}\\sum\_\{i=1\}^N\\sum\_\{j=1\}^N\\alpha\_i\\alpha\_jy\_iy\_jK(x\_i\\cdot x\_j)-\\sum\_\{i=1\}^N\\alpha\_i \\\\ s.t.\\ \\ \\ \\ &\\sum\_\{i=1\}^N\\alpha\_iy\_i=0 \\\\ &0\\le\\alpha\_i\\le C,\\ \\ \\ \\ \\ i=1,2,\\dots, N \\\\ &\\min\_\{\\alpha\_1, \\alpha\_2\}W(\\alpha\_1, \\alpha\_2) \\\\ &=\\frac\{1\}\{2\}K\_\{11\}\\alpha\_1^T+\\frac\{1\}\{2\}K\_\{22\}\\alpha\_2^2+y\_1y\_2\\alpha\_1\\alpha\_2K\_\{12\}-(\\alpha\_1+\\alpha\_2)+y\_1\\alpha\_1\\sum\_\{i=3\}^Ny\_i\\alpha\_iK\_\{i1\}+y\_2\\alpha\_2\\sum\_\{i=3\}^Ny\_i\\alpha\_iK\_\{i2\} \\\\ s.t.\\ \\ \\ \\ &\\alpha\_1y\_1+\\alpha\_2y\_2=-\\sum\_\{i=3\}^Ny\_i\\alpha\_i=\\zeta \\\\ &0\\le\\alpha\_i\\le C \\end\{aligned\} s.t.    s.t.    αmin21i=1∑Nj=1∑NαiαjyiyjK(xi⋅xj)−i=1∑Nαii=1∑Nαiyi=00≤αi≤C,     i=1,2,…,Nα1,α2minW(α1,α2)=21K11α1T\+21K22α22\+y1y2α1α2K12−(α1\+α2)\+y1α1i=3∑NyiαiKi1\+y2α2i=3∑NyiαiKi2α1y1\+α2y2=−i=3∑Nyiαi=ζ0≤αi≤C  
迭代公式：  
 g ( x ) = ∑ i = 1 N y i α i K ( x i , x ) + b η = K ( x 1 , x 1 ) + K ( x 2 , x 2 ) − 2 K ( x 1 , x 2 ) = ∣ ∣ Φ ( x 1 ) − Φ ( x 2 ) ∣ ∣ 2 E i = g ( x i ) − y i = ( ∑ j = 1 N y j α j K ( x j , x i ) + b ) − y i ,      i = 1 , 2 α j n e w = α j o l d + y j ( E i − E j ) η \\begin\{aligned\} g(x)&=\\sum\_\{i=1\}^Ny\_i\\alpha\_iK(x\_i, x)+b \\\\ \\eta&=K(x\_1, x\_1)+K(x\_2, x\_2)-2K(x\_1, x\_2) \\\\ &=||\\Phi(x\_1)-\\Phi(x\_2)||^2 \\\\ E\_i&=g(x\_i)-y\_i \\\\ &=(\\sum\_\{j=1\}^Ny\_j\\alpha\_jK(x\_j,x\_i)+b)-y\_i,\\ \\ \\ \\ i=1,2 \\\\ \\alpha\_j^\{new\}&=\\alpha\_j^\{old\}+\\frac\{y\_j(E\_i-E\_j)\}\{\\eta\} \\end\{aligned\} g(x)ηEiαjnew=i=1∑NyiαiK(xi,x)\+b=K(x1,x1)\+K(x2,x2)−2K(x1,x2)=∣∣Φ(x1)−Φ(x2)∣∣2=g(xi)−yi=(j=1∑NyjαjK(xj,xi)\+b)−yi,    i=1,2=αjold\+ηyj(Ei−Ej)  
退出条件：  
 ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C ,       i = 1 , 2 , … , n y i ⋅ g ( x i ) = \{ ≥ 1 , \{ x i ∣ α i = 0 \}                 落 在 边 界 外 = 1 , \{ x i ∣ 0 < α i < C \}         落 在 边 界 上 ≤ 1 , \{ x i ∣ α i = C \}                落 在 边 界 内 g ( x i ) = ∑ j = 1 n y j α j K ( x j , x i ) + b \\begin\{aligned\} &\\sum\_\{i=1\}^N\\alpha\_iy\_i=0 \\\\ &0\\le\\alpha\_i\\le C, \\ \\ \\ \\ \\ i=1,2,\\dots,n \\\\ &y\_i\\cdot g(x\_i)=\\begin\{cases\} \\ge1, &\\\{x\_i|\\alpha\_i=0\\\} \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ 落在边界外\\\\ =1, &\\\{x\_i|0\\lt\\alpha\_i\\lt C\\\} \\ \\ \\ \\ \\ \\ \\ 落在边界上\\\\ \\le1, &\\\{x\_i|\\alpha\_i=C\\\} \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ 落在边界内 \\\\ \\end\{cases\} \\\\ &g(x\_i)=\\sum\_\{j=1\}^ny\_j\\alpha\_jK(x\_j, x\_i)+b \\end\{aligned\} i=1∑Nαiyi=00≤αi≤C,     i=1,2,…,nyi⋅g(xi)=⎩⎪⎨⎪⎧≥1,=1,≤1,\{ xi∣αi=0\}               落在边界外\{ xi∣0<αi<C\}       落在边界上\{ xi∣αi=C\}              落在边界内g(xi)=j=1∑nyjαjK(xj,xi)\+b

## 7、核函数 ##

![20200325214718974.png][]  
如图所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时该如何把这两类数据分开呢？由我们的经验可以得到，一个理想的分界应该是一个“圆圈”而不是一条线（超平面） 。如果用 X 1 X\_1 X1和 X 2 X\_2 X2来表示这个二维平面的两个坐标的话， 我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写成这样的形式：  
 a 1 X 1 + a 2 X 1 2 + a 3 X 2 + a 4 X 2 2 + a 5 X 1 X 2 + a 6 = 0 a\_1X\_1+a\_2X\_1^2+a\_3X\_2+a\_4X\_2^2+a\_5X\_1X\_2+a\_6=0 a1X1\+a2X12\+a3X2\+a4X22\+a5X1X2\+a6=0  
注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 Z 1 = X 1 ， Z 2 = X 1 2 ， Z 3 = X 2 ， Z 4 = X 2 2 ， Z 5 = X 1 X 2 Z\_1=X\_1，Z\_2=X\_1^2，Z\_3=X\_2，Z\_4=X\_2^2，Z\_5=X\_1X\_2 Z1=X1，Z2=X12，Z3=X2，Z4=X22，Z5=X1X2，那么显然，上面的方程在新的坐标系下可以写做：  
 ∑ i = 1 5 a i Z i + a 6 = 0 \\sum\_\{i=1\}^5a\_iZ\_i+a\_6=0 i=1∑5aiZi\+a6=0  
关于新的坐标Z，这正是一个超平面（hyper plane）的方程。也就是说，如果我们做一个映射 ϕ ： R 2 → R 5 \\phi：R\_2→R\_5 ϕ：R2→R5，将X按照上面的规则映射为Z，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是 Kernel 方法处理非线性问题的基本思想。  
这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上没有这么简单！其实刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算。  
不妨还是从最开始的简单例子出发，设两个向量 x 1 = ( η 1 , η 2 ) T x\_1=(\\eta\_1, \\eta\_2)^T x1=(η1,η2)T和 x 2 = ( ξ 1 , ξ 2 ) T x\_2=(\\xi\_1, \\xi\_2)^T x2=(ξ1,ξ2)T，前面说的五维空间的映射，映射过后的内积为：  
 < ϕ ( x 1 ) , ϕ ( x 2 ) > = η 1 ξ 1 + η 1 2 ξ 1 2 + η 2 ξ 2 + η 2 2 ξ 2 2 + η 1 η 2 ξ 1 ξ 2 <\\phi(x\_1),\\phi(x\_2)>=\\eta\_1\\xi\_1+\\eta\_1^2\\xi\_1^2+\\eta\_2\\xi\_2+\\eta\_2^2\\xi\_2^2+\\eta\_1\\eta\_2\\xi\_1\\xi\_2 <ϕ(x1),ϕ(x2)>=η1ξ1\+η12ξ12\+η2ξ2\+η22ξ22\+η1η2ξ1ξ2  
另外，我们又注意到：  
 ( < x 1 , x 2 > + 1 ) 2 = 2 η 1 ξ 1 + η 1 2 ξ 1 2 + 2 η 2 ξ 2 + η 2 2 ξ 2 2 + 2 η 1 η 2 ξ 1 ξ 2 + 1 (<x\_1, x\_2>+1)^2=2\\eta\_1\\xi\_1+\\eta\_1^2\\xi\_1^2+2\\eta\_2\\xi\_2+\\eta\_2^2\\xi\_2^2+2\\eta\_1\\eta\_2\\xi\_1\\xi\_2+1 (<x1,x2>\+1)2=2η1ξ1\+η12ξ12\+2η2ξ2\+η22ξ22\+2η1η2ξ1ξ2\+1  
二者有很多相似的地方，实际上，我们只要把某几个维度线性缩放一下，然后再加上一个常数维度就是一样的了。  
事实上，大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在。在上文中，我们已经了解到了SVM处理线性可分的情况，那对于非线性的数据SVM如何处理呢？对于非线性的情况，SVM 的处理方法是选择一个核函数K，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。  
具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。  
核函数与之前计算的区别：

*  核函数是映射到高维空间中，然后再根据内积的公式进行计算
 *  之前的计算方式则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果

我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做**核函数（Kernel Function）**，例如在刚才的例子中，我们的核函数为：  
 K ( x 1 , x 2 ) = ( < x 1 , x 2 > + 1 ) 2 K(x\_1, x\_2)=(<x\_1, x\_2>+1)^2 K(x1,x2)=(<x1,x2>\+1)2

###### 常用的几个核函数： ######

多项式核： K ( x 1 , x 2 ) = ( < x 1 , x 2 > + R ) d K(x\_1, x\_2)=(<x\_1, x\_2>+R)^d K(x1,x2)=(<x1,x2>\+R)d  
高斯核函数RBF： K ( x 1 , x 2 ) = exp ⁡ ( − ∣ ∣ x 1 − x 2 ∣ ∣ 2 2 σ 2 ) K(x\_1, x\_2)=\\exp(-\\frac\{||x\_1-x\_2||^2\}\{2\\sigma^2\}) K(x1,x2)=exp(−2σ2∣∣x1−x2∣∣2)  
线性核： K ( x 1 , x 2 ) = < x 1 , x 2 > K(x\_1,x\_2)=<x\_1, x\_2> K(x1,x2)=<x1,x2>

###### 核函数的本质： ######

实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去（如上文的那幅图所示，映射到高维空间后，相关特征便被分开了，也就达到了分类的目的）。  
但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小会很高。  
此时就需要核函数，核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。  
最后引用这里的一个例子举例说明下核函数解决非线性问题的直观效果。  
假设现在你是一个农场主，圈养了一批牛群，但为预防狼群袭击牛群，你需要搭建一个篱笆来把牛群围起来。但是篱笆应该建在哪里？你很可能需要依据牛群和狼群的位置建立一个“分类器”，比较下图这几种不同的分类器，我们可以看到SVM完成了一个很完美的解决方案。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70 2][]

[20200325135433539.png]: /images/20230528/f6fdc1257fdf4dc8848d13b44617b471.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70]: /images/20230528/13f6dc88b61146418daf5994ee4def48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70 1]: /images/20230528/1927a27598274312ad7f05a9355aa79d.png
[20200325181112327.png]: /images/20230528/d0b67525b9754914937a7575528b852c.png
[20200325214718974.png]: /images/20230528/db0285afb500466cb5bf83d5cc24d634.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmd4aWZhY2FpX2JlbGlldmU_size_16_color_FFFFFF_t_70 2]: /images/20230528/f43868975e204db3b5993e6e01e11a6b.png