机器学习—支持向量机理论详细推导（含例题讲解）（三）

痛定思痛。 2023-10-02 20:22 11阅读 0赞

## 9.对偶算法 ##

:构造优化问题  min ⁡ α    θ D ( α ) = 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\{split\} &\\min\_\{\\alpha\}\\;\\theta\_\{D\}(\\alpha)=\\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\\;,\\;\\alpha\_i\\geq0\\;,\\;i=1,2,\\cdots,N \\end\{split\} αminθD(α)=αmin21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαis.t.i=1∑Nαiyi=0,αi≥0,i=1,2,⋯,N

我们求得的 α ∗ = ( α 1 ∗ , α 2 ∗ , ⋯   , α N ∗ ) T \\alpha^\{\*\}=(\\alpha\_1^\{\*\},\\alpha\_2^\{\*\},\\cdots,\\alpha\_N^\{\*\})^T α∗=(α1∗,α2∗,⋯,αN∗)T，N个元素，存在 α j ∗ > 0 \\alpha\_j^\{\*\}>0 αj∗>0， j j j对应样本点 ( x j , y j ) (x\_j,y\_j) (xj,yj)。

(其实我们用的 ( x j , y j ) (x\_j,y\_j) (xj,yj)就是支持向量)。

:计算参数  ω ∗ = ∑ i = 1 N α i ∗ y i x i \\omega^\{\*\}=\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_ix\_i ω∗=i=1∑Nαi∗yixi

b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) ⇒ y j − ω ∗ ⋅ x j = b ∗ ⇒ ω ∗ ⋅ x j + b ∗ = y j ∈ \{ − 1 , + 1 \} \\begin\{split\} &b^\{\*\}=y\_j-\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_i(x\_i\\cdot x\_j)\\\\ \\Rightarrow &y\_j-\\omega^\{\*\}\\cdot x\_j=b^\{\*\}\\\\ \\Rightarrow &\\omega^\{\*\}\\cdot x\_j+b^\{\*\}=y\_j\\in\\\{-1,+1\\\} \\end\{split\} ⇒⇒b∗=yj−i=1∑Nαi∗yi(xi⋅xj)yj−ω∗⋅xj=b∗ω∗⋅xj\+b∗=yj∈\{ −1,\+1\}

我们上面等式恰好表示间隔边界。

如何找支持向量呢？

我们看一个例题:  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JkJpx5r0-1658189645266)(3.png)\]][img-JkJpx5r0-1658189645266_3.png]

优化问题  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 y i α i = 0    ,    α i    ,    i = 1 , 2 , 3 \\begin\{split\} &\\min\\;\\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\}y\_i\\alpha\_i=0\\;,\\;\\alpha\_i\\;,\\;i=1,2,3 \\end\{split\} min21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Nαis.t.i=1∑Nyiαi=0,αi,i=1,2,3

当 x 1    ,    x 1 x\_1\\;,\\;x\_1 x1,x1时:  α 1 α 1 y 1 y 1 ( x 1 ⋅ x 1 ) = 18 α 1 2 \\alpha\_1\\alpha\_1y\_1y\_1(x\_1\\cdot x\_1)=18\\alpha\_1^2 α1α1y1y1(x1⋅x1)=18α12

当 x 1    ,    x 2 x\_1\\;,\\;x\_2 x1,x2时:  
 2 α 1 α 2 y 1 y 2 ( x 1 ⋅ x 2 ) = 42 α 1 α 2 2\\alpha\_1\\alpha\_2y\_1y\_2(x\_1\\cdot x\_2)=42\\alpha\_1\\alpha\_2 2α1α2y1y2(x1⋅x2)=42α1α2

当 x 1    ,    x 3 x\_1\\;,\\;x\_3 x1,x3时:  
 2 α 1 α 3 y 1 y 3 ( x 1 ⋅ x 3 ) = − 12 α 1 α 3 2\\alpha\_1\\alpha\_3y\_1y\_3(x\_1\\cdot x\_3)=-12\\alpha\_1\\alpha\_3 2α1α3y1y3(x1⋅x3)=−12α1α3

当 x 2    ,    x 2 x\_2\\;,\\;x\_2 x2,x2时:  α 2 α 2 y 2 y 2 ( x 2 ⋅ x 2 ) = 25 α 2 2 \\alpha\_2\\alpha\_2y\_2y\_2(x\_2\\cdot x\_2)=25\\alpha\_2^2 α2α2y2y2(x2⋅x2)=25α22

当 x 2    ,    x 3 x\_2\\;,\\;x\_3 x2,x3时:  
 2 α 2 α 3 y 2 y 3 ( x 2 ⋅ x 3 ) = − 14 α 2 α 3 2\\alpha\_2\\alpha\_3y\_2y\_3(x\_2\\cdot x\_3)=-14\\alpha\_2\\alpha\_3 2α2α3y2y3(x2⋅x3)=−14α2α3

当 x 3    ,    x 3 x\_3\\;,\\;x\_3 x3,x3时:  α 3 α 3 y 3 y 3 ( x 3 ⋅ x 3 ) = 2 α 3 2 \\alpha\_3\\alpha\_3y\_3y\_3(x\_3\\cdot x\_3)=2\\alpha\_3^2 α3α3y3y3(x3⋅x3)=2α32

我们代入:  ⇒ min ⁡    1 2 ( 18 α 1 2 + 25 α 2 2 + 2 α 3 2 + 42 α 1 α 2 − 12 α 1 α 3 − 14 α 2 α 3 ) − ( α 1 + α 2 + α 3 ) ∑ i = 1 N y i α i = 0 ⇒ α 1 + α 2 − α 3 = 0 \\begin\{split\} \\Rightarrow &\\min\\;\\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)\\\\ &\\sum\_\{i=1\}^\{N\}y\_i\\alpha\_i=0\\Rightarrow \\alpha\_1+\\alpha\_2-\\alpha\_3=0 \\end\{split\} ⇒min21(18α12\+25α22\+2α32\+42α1α2−12α1α3−14α2α3)−(α1\+α2\+α3)i=1∑Nyiαi=0⇒α1\+α2−α3=0

我们将 α 1 + α 2 − α 3 = 0 \\alpha\_1+\\alpha\_2-\\alpha\_3=0 α1\+α2−α3=0代入计算:  
 ⇒ min ⁡    4 α 1 2 + 13 2 α 2 2 + 10 α 1 α 2 − 2 α 1 − 2 α 2 = s ( α 1 , α 2 ) \\Rightarrow \\min\\;4\\alpha\_1^2+\\frac\{13\}\{2\}\\alpha\_2^2+10\\alpha\_1\\alpha\_2-2\\alpha\_1-2\\alpha\_2\\\\=s(\\alpha\_1,\\alpha\_2) ⇒min4α12\+213α22\+10α1α2−2α1−2α2=s(α1,α2)

我们需要找 s ( α 1 , α 2 ) s(\\alpha\_1,\\alpha\_2) s(α1,α2)的最小值。

如果求偏导数:  \{ ∂ s ∂ α 1 = 8 α 1 + 10 α 2 − 2 = 0 ∂ s ∂ α 2 = 13 α 2 + 10 α 1 − 2 = 0 \\left\\\{ \\begin\{split\} &\\frac\{\\partial s\}\{\\partial \\alpha\_1\}=8\\alpha\_1+10\\alpha\_2-2=0\\\\ &\\frac\{\\partial s\}\{\\partial \\alpha\_2\}=13\\alpha\_2+10\\alpha\_1-2=0 \\end\{split\} \\right. ⎩⎨⎧∂α1∂s=8α1\+10α2−2=0∂α2∂s=13α2\+10α1−2=0

我们解出:  \{ α 1 = 3 2 α 2 = − 1 \\left\\\{ \\begin\{split\} &\\alpha\_1=\\frac\{3\}\{2\}\\\\ &\\alpha\_2=-1 \\end\{split\} \\right. ⎩⎨⎧α1=23α2=−1

因为 α 1    ,    α 2    ,    α 3 ≥ 0 \\alpha\_1\\;,\\;\\alpha\_2\\;,\\;\\alpha\_3\\geq0 α1,α2,α3≥0，所以不满足条件。

如果不能使用费马原理，我们猜测是否在边界上。

（1）如果 α 1 = 0 \\alpha\_1=0 α1=0  
 s ( 0 , α 2 ) = 13 2 α 2 2 − 2 α 2 ⇒ α 2 = 2 13    ,    s = − 2 13 s(0,\\alpha\_2)=\\frac\{13\}\{2\}\\alpha\_2^2-2\\alpha\_2\\Rightarrow \\alpha\_2=\\frac\{2\}\{13\}\\;,\\;s=-\\frac\{2\}\{13\} s(0,α2)=213α22−2α2⇒α2=132,s=−132

（2）如果 α 2 = 0 \\alpha\_2=0 α2=0  
 s ( α 1 , 0 ) = 4 α 1 2 − 2 α 1 ⇒ α 1 = 1 4    ,    s = − 1 4 s(\\alpha\_1,0)=4\\alpha\_1^2-2\\alpha\_1\\Rightarrow \\alpha\_1=\\frac\{1\}\{4\}\\;,\\;s=-\\frac\{1\}\{4\} s(α1,0)=4α12−2α1⇒α1=41,s=−41

我们解出 α 1 = 1 4    ,    α 2 = 0    ,    α 3 = 1 4 \\alpha\_1=\\frac\{1\}\{4\}\\;,\\;\\alpha\_2=0\\;,\\;\\alpha\_3=\\frac\{1\}\{4\} α1=41,α2=0,α3=41，说明 x 1 x\_1 x1和 x 3 x\_3 x3是支持向量。

求解参数  ω ∗ = ∑ i = 1 N α i ∗ y i x i = 1 4 ( 3 , 3 ) T − 1 4 ( 1 , 1 ) T = ( 1 2 , 1 2 ) T b ∗ = y j − ω ∗ ⋅ x j ⇒ b ∗ = 1 − ( 1 2 , 1 2 ) T ⋅ ( 3 , 3 ) T = 1 − 3 = − 2    ,    j = 1 b ∗ = − 1 − ( 1 2 , 1 2 ) T ⋅ ( 1 , 1 ) T = − 1 − 1 = − 2    ,    j = 3 \\begin\{split\} &\\omega^\{\*\}=\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_ix\_i=\\frac\{1\}\{4\}(3,3)^T-\\frac\{1\}\{4\}(1,1)^T=(\\frac\{1\}\{2\},\\frac\{1\}\{2\})^T\\\\ &b^\{\*\}=y\_j-\\omega^\{\*\}\\cdot x\_j\\\\ \\Rightarrow &b^\{\*\}=1-(\\frac\{1\}\{2\},\\frac\{1\}\{2\})^T\\cdot (3,3)^T=1-3=-2\\;,\\;j=1\\\\ &b^\{\*\}=-1-(\\frac\{1\}\{2\},\\frac\{1\}\{2\})^T\\cdot (1,1)^T=-1-1=-2\\;,\\;j=3 \\end\{split\} ⇒ω∗=i=1∑Nαi∗yixi=41(3,3)T−41(1,1)T=(21,21)Tb∗=yj−ω∗⋅xjb∗=1−(21,21)T⋅(3,3)T=1−3=−2,j=1b∗=−1−(21,21)T⋅(1,1)T=−1−1=−2,j=3

分离超平面:  1 2 x ( 1 ) + 1 2 x ( 2 ) − 2 = 0 \\frac\{1\}\{2\}x^\{(1)\}+\\frac\{1\}\{2\}x^\{(2)\}-2=0 21x(1)\+21x(2)−2=0

决策函数为:  f ( x ) = s i g n ( 1 2 x ( 1 ) + 1 2 x ( 2 ) − 2 ) f(x)=sign(\\frac\{1\}\{2\}x^\{(1)\}+\\frac\{1\}\{2\}x^\{(2)\}-2) f(x)=sign(21x(1)\+21x(2)−2)

## 10.线性支持向量机的原始问题 ##

训练集:  
 T = \{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) \}    ,    x i ∈ χ ∈ R n    ,    y i ∈ \{ + 1 , − 1 \} T=\\\{(x\_1,y\_1),(x\_2,y\_2),\\cdots,(x\_N,y\_N)\\\}\\;,\\;x\_i\\in\\chi\\in R^n\\;,\\;y\_i\\in\\\{+1,-1\\\} T=\{(x1,y1),(x2,y2),⋯,(xN,yN)\},xi∈χ∈Rn,yi∈\{ \+1,−1\}

线性可分:  y i ( ω ⋅ x i + b ) ≥ 1 ( 1 ) y i ( ω ⋅ x i + b ) + ξ i ≥ 1    ,    ξ i = ( 0 , 1 ) ( 2 ) y i ( ω ⋅ x i + b ) + ξ i ≥ 1    ,    ξ i > 1 ( 3 ) \\begin\{split\} &y\_i(\\omega\\cdot x\_i+b)\\geq1\\quad(1)\\\\ &y\_i(\\omega\\cdot x\_i+b)+\\xi\_i\\geq1\\;,\\;\\xi\_\{i\}=(0,1)\\quad(2)\\\\ &y\_i(\\omega\\cdot x\_i+b)+\\xi\_i\\geq1\\;,\\;\\xi\_\{i\}>1\\quad(3) \\end\{split\} yi(ω⋅xi\+b)≥1(1)yi(ω⋅xi\+b)\+ξi≥1,ξi=(0,1)(2)yi(ω⋅xi\+b)\+ξi≥1,ξi>1(3)

对于 ( 1 ) (1) (1)表示函数间隔 ≥ 1 \\geq1 ≥1；对于 ( 2 ) (2) (2)表示位于间隔内；对于 ( 3 ) (3) (3)表示位于间隔外（异）。

上述的分类比较有弹性，所以称为软间隔:  
 y i ( ω ⋅ x i + b ) + ξ i ≥ 1 y\_i(\\omega\\cdot x\_i+b)+\\xi\_i\\geq1 yi(ω⋅xi\+b)\+ξi≥1

ξ i \\xi\_i ξi叫做弹性因子，也叫松弛变量。

目标函数:  1 2 ∣ ∣ ω ∣ ∣ 2 + c ∑ i = 1 N ξ i \\frac\{1\}\{2\}||\\omega||^2+c\\sum\_\{i=1\}^\{N\}\\xi\_i 21∣∣ω∣∣2\+ci=1∑Nξi

上式中， c c c表示松弛变量起作用的大小，又叫做惩罚系数。

当 c c c较大时，对误分类惩罚大；当 c c c较小时，取决于第一部分 1 2 ∣ ∣ ω ∣ ∣ 2 \\frac\{1\}\{2\}||\\omega||^2 21∣∣ω∣∣2，对误分类惩罚小。

此时我们的优化问题为:  min ⁡ ω , b , ξ i    1 2 ∣ ∣ ω ∣ ∣ 2 + c ∑ i = 1 N ξ i s . t .    y i ( ω ⋅ x i + b ) + ξ i ≥ 1    ,    ξ i ≥ 0    ,    , i = 1 , 2 , ⋯   , N \\begin\{split\} &\\min\_\{\\omega,b,\\xi\_i\}\\;\\frac\{1\}\{2\}||\\omega||^2+c\\sum\_\{i=1\}^\{N\}\\xi\_i\\\\ &s.t.\\;y\_i(\\omega\\cdot x\_i+b)+\\xi\_i\\geq1\\;,\\;\\xi\_i\\geq0\\;,\\;,i=1,2,\\cdots,N \\end\{split\} ω,b,ξimin21∣∣ω∣∣2\+ci=1∑Nξis.t.yi(ω⋅xi\+b)\+ξi≥1,ξi≥0,,i=1,2,⋯,N

我们接下来的目的是解 ω ∗    ,    b ∗ \\omega^\{\*\}\\;,\\;b^\{\*\} ω∗,b∗。

线性支持向量机的对偶问题:

我们的原始问题如下所示:  1 2 ∣ ∣ ω ∣ ∣ 2 + c ∑ i = 1 N ξ i s . t .    1 − ξ i − y i ( ω ⋅ x i + b ) ≤ 0    ,    − ξ i ≤ 0    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\frac\{1\}\{2\}||\\omega||^2+c\\sum\_\{i=1\}^\{N\}\\xi\_i\\\\ &s.t.\\;1-\\xi\_i-y\_i(\\omega\\cdot x\_i+b)\\leq0\\;,\\;-\\xi\_i\\leq0\\;,\\;i=1,2,\\cdots,N \\end\{split\} 21∣∣ω∣∣2\+ci=1∑Nξis.t.1−ξi−yi(ω⋅xi\+b)≤0,−ξi≤0,i=1,2,⋯,N

得到广义拉格朗日函数为:  L ( ω , b , ξ i , α , μ ) = 1 2 ∣ ∣ ω ∣ ∣ 2 + c ∑ i = 1 N ξ i + ∑ i = 1 N α i \[ ( 1 − ξ i − y i ( ω ⋅ x i + b ) ) \] − ∑ i = 1 N μ i ξ i \\begin\{split\} L(\\omega,b,\\xi\_i,\\alpha,\\mu)=\\frac\{1\}\{2\}||\\omega||^2+c\\sum\_\{i=1\}^\{N\}\\xi\_i+\\sum\_\{i=1\}^\{N\}\\alpha\_i\[(1-\\xi\_i-y\_i(\\omega\\cdot x\_i+b))\]-\\sum\_\{i=1\}^\{N\}\\mu\_i\\xi\_i \\end\{split\} L(ω,b,ξi,α,μ)=21∣∣ω∣∣2\+ci=1∑Nξi\+i=1∑Nαi\[(1−ξi−yi(ω⋅xi\+b))\]−i=1∑Nμiξi

原始问题:  min ⁡ ω , b , ξ i    max ⁡ α , μ    L \\min\_\{\\omega,b,\\xi\_i\}\\;\\max\_\{\\alpha,\\mu\}\\;L ω,b,ξiminα,μmaxL

对偶问题:  max ⁡ α , μ    min ⁡ ω , b , ξ i    L \\max\_\{\\alpha,\\mu\}\\;\\min\_\{\\omega,b,\\xi\_i\}\\;L α,μmaxω,b,ξiminL

（1）内部极小化 θ D ( α , μ ) \\theta\_\{D\}(\\alpha,\\mu) θD(α,μ)  ∂ L ∂ ω = ω − ∑ i = 1 N α i y i x i = 0 ∂ L ∂ b = − ∑ i = 1 N α i y i = 0 ∂ L ∂ ξ i = c − α i − μ i = 0    ,    , i = 1 , 2 , ⋯   , N ⇒ \{ ω = ∑ i = 1 N α i y i x i ∑ i = 1 N α i y i = 0 c − α i − μ i = 0    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\frac\{\\partial L\}\{\\partial \\omega\}=\\omega-\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_ix\_i=0\\\\ &\\frac\{\\partial L\}\{\\partial b\}=-\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\\\ &\\frac\{\\partial L\}\{\\partial \\xi\_i\}=c-\\alpha\_i-\\mu\_i=0\\;,\\;,i=1,2,\\cdots,N\\\\ \\Rightarrow &\\left\\\{ \\begin\{split\} &\\omega=\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_ix\_i\\\\ &\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\\\ &c-\\alpha\_i-\\mu\_i=0\\;,\\;i=1,2,\\cdots,N \\end\{split\} \\right. \\end\{split\} ⇒∂ω∂L=ω−i=1∑Nαiyixi=0∂b∂L=−i=1∑Nαiyi=0∂ξi∂L=c−αi−μi=0,,i=1,2,⋯,N⎩⎨⎧ω=i=1∑Nαiyixii=1∑Nαiyi=0c−αi−μi=0,i=1,2,⋯,N

代入计算:  L = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N ( c − α i − μ i ) ξ i + ∑ i = 1 N α i − ∑ i = 1 N α i y i ∑ j = 1 N α j y j ( x j ⋅ x i ) − ∑ i = 1 N α i y i b = 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N − ∑ i = 1 N α i y i ∑ j = 1 N α j y j ( x j ⋅ x i ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i = θ D ( α , μ ) \\begin\{split\} L&=\\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\}(c-\\alpha\_i-\\mu\_i)\\xi\_i+\\sum\_\{i=1\}^\{N\}\\alpha\_i\\\\ &-\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i\\sum\_\{j=1\}^\{N\}\\alpha\_jy\_j(x\_j\\cdot x\_i)-\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_ib\\\\ &=\\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\}-\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i\\sum\_\{j=1\}^\{N\}\\alpha\_jy\_j(x\_j\\cdot x\_i)\\\\ &=-\\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\\\\ &=\\theta\_\{D\}(\\alpha,\\mu) \\end\{split\} L=21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)\+i=1∑N(c−αi−μi)ξi\+i=1∑Nαi−i=1∑Nαiyij=1∑Nαjyj(xj⋅xi)−i=1∑Nαiyib=21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)\+i=1∑N−i=1∑Nαiyij=1∑Nαjyj(xj⋅xi)=−21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)\+i=1∑Nαi=θD(α,μ)

（2）外部极大化: max ⁡    θ D ( α , μ ) \\max\\;\\theta\_\{D\}(\\alpha,\\mu) maxθD(α,μ)

对偶算法:  min ⁡    1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N s . t .    ∑ i = 1 N α i y i = 0    ,    0 ≤ α i ≤ c    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\min\\;\\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\}\\\\ &s.t.\\;\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\;,\\;0\\leq\\alpha\_i\\leq c\\;,\\;i=1,2,\\cdots,N \\end\{split\} min21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−i=1∑Ns.t.i=1∑Nαiyi=0,0≤αi≤c,i=1,2,⋯,N

其中， μ i = c − α i ≥ 0 ⇒ α i ≤ c \\mu\_i=c-\\alpha\_i\\geq0\\Rightarrow \\alpha\_i\\leq c μi=c−αi≥0⇒αi≤c

我们继续:  ω ∗ − ∑ i = 1 N α i ∗ y i x i = 0 ⇒ ω ∗ = ∑ i = 1 N α i ∗ y i x i \\begin\{split\} &\\omega^\{\*\}-\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_ix\_i=0\\\\ \\Rightarrow &\\omega^\{\*\}=\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_ix\_i \\end\{split\} ⇒ω∗−i=1∑Nαi∗yixi=0ω∗=i=1∑Nαi∗yixi

对KKT条件再次使用:  \{ α i ∗ ( 1 − ξ i − y i ( ω ∗ ⋅ x i + b ∗ ) ) = 0 − μ i ∗ ξ i ∗ = 0 1 − ξ i ∗ − y i ( ω ∗ ⋅ x i + b ∗ ) ≤ 0 α i ∗ ≥ 0 − ξ i ∗ ≤ 0 μ i ∗ ≥ 0 \\left\\\{ \\begin\{split\} &\\alpha\_i^\{\*\}(1-\\xi\_i-y\_i(\\omega^\{\*\}\\cdot x\_i+b^\{\*\}))=0\\\\ &-\\mu\_i^\{\*\}\\xi\_i^\{\*\}=0\\\\ &1-\\xi\_i^\{\*\}-y\_i(\\omega^\{\*\}\\cdot x\_i+b^\{\*\})\\leq0\\\\ &\\alpha\_i^\{\*\}\\geq0\\\\ &-\\xi\_i^\{\*\}\\leq0\\\\ &\\mu\_i^\{\*\}\\geq0 \\end\{split\} \\right. ⎩⎨⎧αi∗(1−ξi−yi(ω∗⋅xi\+b∗))=0−μi∗ξi∗=01−ξi∗−yi(ω∗⋅xi\+b∗)≤0αi∗≥0−ξi∗≤0μi∗≥0

我们知道，存在 α i > 0 \\alpha\_i>0 αi>0，满足软间隔的条件。发生作用的是间隔边界上的。有 ξ i ∗ = 0 \\xi\_i^\{\*\}=0 ξi∗=0， μ i ∗ > 0 \\mu\_i^\{\*\}>0 μi∗>0， c − μ i ∗ − α i ∗ = 0 ⇒ α i ∗ < c c-\\mu\_i^\{\*\}-\\alpha\_i^\{\*\}=0\\Rightarrow \\alpha\_i^\{\*\}<c c−μi∗−αi∗=0⇒αi∗<c。

我们得到新的约束条件为:  s . t . \{ ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ c i = 1 , 2 , ⋯   , N s.t.\\left\\\{ \\begin\{split\} &\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\\\ &0\\leq\\alpha\_i\\leq c\\\\ &i=1,2,\\cdots,N \\end\{split\} \\right. s.t.⎩⎨⎧i=1∑Nαiyi=00≤αi≤ci=1,2,⋯,N

我们计算 b ∗ b^\{\*\} b∗时曾用到 y j y\_j yj，实际上是间隔边界上的点，满足 ω ⋅ x + b = 1 \\omega\\cdot x+b=1 ω⋅x\+b=1.

我们有:  y j ( ω ∗ ⋅ x j + b ∗ = 1 ⇒ ω ∗ ⋅ x j + b ∗ = 1 y j = y j ⇒ b ∗ = y j − ω ∗ ⋅ x j = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) \\begin\{split\} &y\_j(\\omega^\{\*\}\\cdot x\_j+b^\{\*\}=1\\\\ \\Rightarrow &\\omega^\{\*\}\\cdot x\_j+b^\{\*\}=\\frac\{1\}\{y\_j\}=y\_j\\\\ \\Rightarrow &b^\{\*\}=y\_j-\\omega^\{\*\}\\cdot x\_j=y\_j-\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_i(x\_i\\cdot x\_j) \\end\{split\} ⇒⇒yj(ω∗⋅xj\+b∗=1ω∗⋅xj\+b∗=yj1=yjb∗=yj−ω∗⋅xj=yj−i=1∑Nαi∗yi(xi⋅xj)

**\[线性支持向量机总结\]**

输入:训练集 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 ∈ R n    ,    y i ∈ \{ + 1 , − 1 \} x\_i\\in R^n\\;,\\;y\_i\\in\\\{+1,-1\\\} xi∈Rn,yi∈\{ \+1,−1\}。

输出:分离超平面与分类决策函数

算法:

:给定惩罚参数 c > 0 c>0 c>0，构造优化问题  min ⁡ α    1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − 1 2 ∑ i = 1 N α i s . t .    ∑ i = 1 N α i y i = 0    ,    0 ≤ α i ≤ c    ,    i = 1 , 2 , ⋯   , N \\begin\{split\} &\\min\_\{\\alpha\}\\;\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\alpha\_i\\alpha\_jy\_iy\_j(x\_i\\cdot x\_j)-\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{N\}\\alpha\_i\\\\ &s.t.\\;\\sum\_\{i=1\}^\{N\}\\alpha\_iy\_i=0\\;,\\;0\\leq\\alpha\_i\\leq c\\;,\\;i=1,2,\\cdots,N \\end\{split\} αmin21i=1∑Nj=1∑Nαiαjyiyj(xi⋅xj)−21i=1∑Nαis.t.i=1∑Nαiyi=0,0≤αi≤c,i=1,2,⋯,N

:求解最优化问题，得到最优解  
 α ∗ = ( α 1 ∗ , α 2 ∗ , ⋯   , α N ∗ ) T \\alpha^\{\*\}=(\\alpha\_1^\{\*\},\\alpha\_2^\{\*\},\\cdots,\\alpha\_N^\{\*\})^T α∗=(α1∗,α2∗,⋯,αN∗)T

:根据 α ∗ \\alpha^\{\*\} α∗进行计算  
 ω ∗ = ∑ i = 1 N α i ∗ y i x i \\omega^\{\*\}=\\sum\_\{i=1\}^\{N\}\\alpha\_i^\{\*\}y\_ix\_i ω∗=i=1∑Nαi∗yixi

挑出符合 0 < α i ∗ < c 0<\\alpha\_i^\{\*\}<c 0<αi∗<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∗=yj−i=1∑Nαi∗yi(xi⋅xj)

:得到最终结果

分离超平面:  ω ∗ ⋅ x + b ∗ = 0 \\omega^\{\*\}\\cdot x+b^\{\*\}=0 ω∗⋅x\+b∗=0

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

我们最后提一下支持向量的定义:

![cd1b512830604adb91f121007a5caedb.png][]

## 11.合页损失函数 ##

线性支持向量机学习还有另外一种解释，就是最小化以下目标函数：  
 ∑ i = 1 N \[ 1 − y i ( ω ⋅ x i + b ) \] + + λ ∣ ∣ ω ∣ ∣ 2 \\sum\_\{i=1\}^\{N\}\[1-y\_i(\\omega\\cdot x\_i+b)\]\_\{+\}+\\lambda||\\omega||^2 i=1∑N\[1−yi(ω⋅xi\+b)\]\+\+λ∣∣ω∣∣2

第一项:  L ( y ( ω ⋅ x + b ) ) = \[ 1 − y ( ω ⋅ x + b ) \] + L(y(\\omega\\cdot x+b))=\[1-y(\\omega\\cdot x+b)\]\_\{+\} L(y(ω⋅x\+b))=\[1−y(ω⋅x\+b)\]\+  
称为合页损失函数。  \[ z \] + = \{ z    ,    z > 0 0    ,    z ≤ 0 \[z\]\_\{+\}=\\left\\\{ \\begin\{split\} &z\\;,\\;z>0\\\\ &0\\;,\\;z\\leq0 \\end\{split\} \\right. \[z\]\+=\{ z,z>00,z≤0

线性支持向量机原始最优化问题:  
 min ⁡ ω , b , ξ    1 2 ∣ ∣ ω ∣ ∣ 2 + c ∑ i = 1 N ξ i \\min\_\{\\omega,b,\\xi\}\\;\\frac\{1\}\{2\}||\\omega||^2+c\\sum\_\{i=1\}^\{N\}\\xi\_i ω,b,ξmin21∣∣ω∣∣2\+ci=1∑Nξi

s . t . \{ y i ( ω ⋅ x i + b ) ≥ 1 − ξ i    ,    i = 1 , 2 , ⋯   , N ξ i ≥ 0    ,    i = 1 , 2 , ⋯   , N s.t.\\left\\\{ \\begin\{split\} &y\_i(\\omega \\cdot x\_i+b)\\geq1-\\xi\_i\\;,\\;i=1,2,\\cdots,N\\\\ &\\xi\_i\\geq0\\;,\\;i=1,2,\\cdots,N \\end\{split\} \\right. s.t.\{ yi(ω⋅xi\+b)≥1−ξi,i=1,2,⋯,Nξi≥0,i=1,2,⋯,N

等价于:  
 min ⁡ ω , b    ∑ i = 1 N \[ 1 − y i ( ω ⋅ x i + b ) \] + + λ ∣ ∣ ω ∣ ∣ 2 \\min\_\{\\omega,b\}\\;\\sum\_\{i=1\}^\{N\}\[1-y\_i(\\omega\\cdot x\_i+b)\]\_\{+\}+\\lambda||\\omega||^2 ω,bmini=1∑N\[1−yi(ω⋅xi\+b)\]\+\+λ∣∣ω∣∣2

我们的推导过程如下:

我们 ξ i = \[ 1 − y i ( ω ⋅ x i + b ) \] + \\xi\_i=\[1-y\_i(\\omega\\cdot x\_i+b)\]\_\{+\} ξi=\[1−yi(ω⋅xi\+b)\]\+，取合页，考虑距离大于0的情况。  
 min ⁡ ω , b    1 2 ∣ ∣ ω ∣ ∣ 2 + c ∑ i = 1 N \[ 1 − y i ( ω ⋅ x i + b ) \] + ⇒ c > 0 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 \\begin\{split\} &\\min\_\{\\omega,b\}\\;\\frac\{1\}\{2\}||\\omega||^2+c\\sum\_\{i=1\}^\{N\}\[1-y\_i(\\omega\\cdot x\_i+b)\]\_\{+\}\\\\ \\Rightarrow^\{c>0\} &\\min\_\{\\omega,b\}\\;\\sum\_\{i=1\}^\{N\}\[1-y\_i(\\omega\\cdot x\_i+b)\]\_\{+\}+\\frac\{1\}\{2c\}||\\omega||^2\\\\ \\Rightarrow &\\min\_\{\\omega,b\}\\;\\sum\_\{i=1\}^\{N\}\[1-y\_i(\\omega\\cdot x\_i+b)\]\_\{+\}+\\lambda||\\omega||^2 \\end\{split\} ⇒c>0⇒ω,bmin21∣∣ω∣∣2\+ci=1∑N\[1−yi(ω⋅xi\+b)\]\+ω,bmini=1∑N\[1−yi(ω⋅xi\+b)\]\+\+2c1∣∣ω∣∣2ω,bmini=1∑N\[1−yi(ω⋅xi\+b)\]\+\+λ∣∣ω∣∣2

![78ac6669067b4a50ad86fe142045de1c.png][]

可以看到线性支持向量机损失函数作为感知机损失函数的一个上界，所以线性支持向量机可以找到那个唯一的超平面了。

[img-JkJpx5r0-1658189645266_3.png]: https://img-blog.csdnimg.cn/792208352df2430f918fb0b8158ee0e8.png
[cd1b512830604adb91f121007a5caedb.png]: https://img-blog.csdnimg.cn/cd1b512830604adb91f121007a5caedb.png
[78ac6669067b4a50ad86fe142045de1c.png]: https://img-blog.csdnimg.cn/78ac6669067b4a50ad86fe142045de1c.png