硬间隔支持向量机推导【纯公式……】

骑猪看日落 2023-02-14 03:20 24阅读 0赞

支持向量机很早很早就被提出来了，而且在最近几年里一直在被更新和改进，但是追本溯源，我们还是得回到那个古老的年代，去看看支持向量机原本的模样。原本是用 cTex 写的啦，后来复制到 GitChat 发现压根莫得办法生成，于是就放弃发布了，某天闲的一批我就切到 Markdown 了，现在发出来哦。

支持向量机很早很早就被提出来了，而且在最近几年里一直在被更新和改进，但是追本溯源，我们还是得回到那个古老的年代，去看看支持向量机原本的模样。

我们总是希望这世界上的事情没有那么多的弯弯绕绕，能一刀切开就好了。SVM 最早干的就是这一刀切的工作。现在有两拨样本，标签分别是 $\\left\\\{-1,+1\\right\\\}$，它们在原空间上的分布如下图所示：![!\[image\_1e5ruc3u7gooqcn1eqmpjdimem.png-48.2kB\]\[1\]][image_1e5ruc3u7gooqcn1eqmpjdimem.png-48.2kB_1]

我们希望能够找到一条分界线，把两拨样本合理地分开，而且尽可能地让最靠近分解的样本点之间的距离最大，也就是图中的 $d\_+$ 与 $d\_-$ 之和要最大。当我们确定分界线之后，无论类别是什么，我们取最靠近分界线的样本点，做穿过该样本点且与分界线平行的直线，称之为边界线，两个类别的边界线距离就是间隔(Margin)。我们给图中的线 $H$ 定义一个方程，即：$$w^Tx+b=0$$ 而 $H\_+$ 和 $H\_-$ 则分别是

$$\\left\{ \\begin\{aligned\} w^Tx+b&=1 \\ w^Tx+b&=-1 \\end\{aligned\}\\right.$$

我们合并这两个边界线的方程，即：

$$y*i(w^Tx*i+b)\\geq1\\quad\\quad\\left\{ \\begin\{aligned\} &\\forall i\\in 1,\\cdots,N \\ &\\forall y\_i\\in\\left\{-1,+1\\right\} \\end\{aligned\}\\right.$$

那我们会开始思考，既然我是想要让间隔最大，那我应该考虑间隔是什么，于是这里就要用到高中学的一个知识点——两直线间的距离公式：$$D=\\frac\{|c\_1-c\_2|\}\{\\sqrt\{A^2+B^2\}\}$$由于 $H\_-$ 到 $H$ 的距离和 $H\_+$ 到 $H$ 的距离势必要相等的，因此间隔就是：

$$\\begin\{aligned\}D&=D(H*-,H)+D(H*\+,H)\\&=\\frac\{|b-(b+1)|\}\{\\sqrt\{(w^T)^2\}\}+\\frac\{|b-(b-1)|\}\{\\sqrt\{(w^T)^2\}\}\\&=\\frac\{1\}\{||w||\}+\\frac\{1\}\{||w||\}\\&=\\frac\{2\}\{||w||\}=\\frac\{2\}\{\\sqrt\{w^Tw\}\}\\tag\{1\}\\end\{aligned\}$$

在式 $(1)$ 中，我们能发现如果希望 $D$ 越大，那必须让 $w^Tw$ 越小，因此这就转换成一个最优化问题，求的是 $w^Tw$ 的最小值，当然还有一个限制条件，就是要限制样本点不能出现在间隔当中，只能是在间隔边上或者间隔外，即：

$$\\begin\{aligned\} &minimize\\quad \\Phi(w)=\\frac\{1\}\{2\}w^Tw \\ &subject.to\\quad y*i(w^Tx*i+b)\\geq1\\quad\\forall i\\in1,\\cdots,N\\end\{aligned\}$$

接着我们得构造 $\\Phi(w)$ 的拉格朗日多项式，要先做个说明的是，为什么是减号，而不是加号：

$$\\begin\{aligned\}y*i(w^Tx*i+b)&\\geq1\\1-y*i(w^Tx*i+b)&\\leq0\\-y*i(w^Tx*i+b)+1&\\leq0\\end\{aligned\}$$

说明结束，转换成拉格朗日多项式就是

$$L(w,b,\\alpha)=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*i\[y*i(w^Tx*i+b)-1\]$$

接着对 $w$ 和 $b$ 做微分：

$$\\begin\{aligned\} & \\frac\{\\partial L\}\{\\partial w\}=0\\Rightarrow w=\\sum*\{i=1\}^N\\alpha*iy*ix*i \\ & \\frac\{\\partial L\}\{\\partial b\}=0\\Rightarrow \\sum*\{i=1\}^N\\alpha*iy\_i=0\\end\{aligned\}$$

那这样子我们就能求出在原空间中的 $L(w,b,\\alpha)$ 是个啥了。将拉格朗日多项式的微分所得带回 $L$ 中，但我们可以先算 $w^Tw$ 和 $w^Tx\_i$ 即：

$$\\begin\{aligned\} w^Tw&=(\\sum*\{i=1\}^N\\alpha*iy*ix*i^T)(\\sum*\{j=1\}^N\\alpha*jy*jx*j) \\ &=\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*jx*i^Tx*j \\ w^Tx*i&=(\\sum*\{j=1\}^N\\alpha*jy*jx*j^T)x*i \\ &=\\sum*\{j=1\}^N\\alpha*jy*jx*j^Tx\_i\\end\{aligned\}$$

接着我们把上面两结果带进 $L(w,b,\\alpha)$ 里，可得：

$$\\begin\{aligned\} W(\\alpha)&=L(w(\\alpha),b(\\alpha),\\alpha) \\ &=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*i\[y*i(w^Tx*i+b)-1\] \\ &=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*iy*iw^Tx*i-b\\sum*\{i=1\}^N\\alpha*iy*i+\\sum*\{i=1\}^N\\alpha*i \\ &=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*iy*iw^Tx*i+\\sum*\{i=1\}^N\\alpha*i \\ &=\\frac\{1\}\{2\}\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*jx*i^Tx*j-\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*jx*i^Tx*j+\\sum*\{i=1\}^N\\alpha*i \\ &=\\sum*\{i=1\}^N\\alpha*i-\\frac\{1\}\{2\}\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*jx*i^Tx\_j\\end\{aligned\}$$

到这里，我们可算是把 $W(\\alpha)$ 给整出来了，于是乎我们就转换成了一个对偶问题，来求 $W(\\alpha)$ 的最大值，但是要记得它有俩限制式：

$$\\begin\{aligned\} &(1)\\quad\\quad\\sum*\{i=1\}^N\\alpha*iy*i=0 \\ &(2)\\quad\\quad\\alpha*i\\geq0\\quad\\forall i=1,\\cdots,N\\end\{aligned\}$$

到这里，我们对于原空间的推导就结束了，因为我们的主要目的是把它映射到高维空间去，也就是把全部的 $x\_i$ 都换成 $\\phi(x\_i)$，推导过程和在原空间时是一致的，只不过是把 $w^Tx\_i$ 换成了 $w^T\\phi(x\_i)$，即：

$$\\begin\{aligned\} W(\\alpha)&=L(w(\\alpha),b(\\alpha),\\alpha) \\ &=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*i\[y*i(w^T\\phi(x*i)+b)-1\] \\ &=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*iy*iw^T\\phi(x*i)-b\\sum*\{i=1\}^N\\alpha*iy*i+\\sum*\{i=1\}^N\\alpha*i \\ &=\\frac\{1\}\{2\}w^Tw-\\sum*\{i=1\}^N\\alpha*iy*iw^T\\phi(x*i)+\\sum*\{i=1\}^N\\alpha*i \\ &=\\frac\{1\}\{2\}\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*j\\phi(x*i)^T\\phi(x*j)-\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*j\\phi(x*i)^T\\phi(x*j)+\\sum*\{i=1\}^N\\alpha*i \\ &=\\sum*\{i=1\}^N\\alpha*i-\\frac\{1\}\{2\}\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*j\\phi(x*i)^T\\phi(x*j) \\ &=\\sum*\{i=1\}^N\\alpha*i-\\frac\{1\}\{2\}\\sum*\{i=1\}^N\\sum*\{j=1\}^N\\alpha*i\\alpha*jy*iy*j\\kappa(x*i,x\_j)\\end\{aligned\}$$

接着通过 KKT 来对 $\\alpha^\*$ 做分析，我们会发现当 $\\alpha\_i^\*>0$ 时，因为 $\\alpha\_i^\*\[y\_i(w^\{\*T\}+\\phi(x\_i)+b^\*)-1\]=0$，所以 $y\_i(w^\{\*T\}+\\phi(x\_i)+b^\*)=1$，那样本点刚好就落在边界线上；如果 $y\_i(w^\{\*T\}+\\phi(x\_i)+b^\*)>1$，则意味着 $\\alpha\_i^\*=0$ ，换句话说，当 $\\alpha\_i^\*=0$ 时，该样本点处于间隔之外。

于是我们就能确定: $$w=\\sum\_\{\\alpha\_i^\*≠0\}\\alpha\_i^\*y\_i\\phi(x\_i)$$

$$b^\*=y\_t-w^\{\*T\}\\phi(x\_i)=y\_t-\\sum\_\{i=1\}^N\\alpha\_i^\*\\kappa(x\_i,x\_j)$$

最终得到最后的分界线方程就是：

$$y*\{new\}=sign(\\sum*\{i=1\}^N\\alpha*iy*i\\kappa(x*i,x*\{new\})+b)$$

阅读全文: [http://gitbook.cn/gitchat/activity/5ed3319ca9b2b5295c0e36a7][http_gitbook.cn_gitchat_activity_5ed3319ca9b2b5295c0e36a7]

您还可以下载 CSDN 旗下精品原创内容社区 GitChat App ，阅读更多 GitChat 专享技术内容哦。

![FtooAtPSkEJwnW-9xkCLqSTRpBKX][]

[image_1e5ruc3u7gooqcn1eqmpjdimem.png-48.2kB_1]: https://images.gitbook.cn/3959d120-a2fb-11ea-9c0f-cd8909d48fa9
[http_gitbook.cn_gitchat_activity_5ed3319ca9b2b5295c0e36a7]: http://gitbook.cn/gitchat/activity/5ed3319ca9b2b5295c0e36a7?utm_source=csdn_blog
[FtooAtPSkEJwnW-9xkCLqSTRpBKX]: https://images.gitbook.cn/FtooAtPSkEJwnW-9xkCLqSTRpBKX