# 支持向量机(SVM)原理分析

2019年12月08日 阅读数：100

web

${\stackrel{^}{\gamma }}^{\left(i\right)}={y}^{\left(i\right)}\left({w}^{T}{x}^{\left(i\right)}+b\right)$

${y}^{\left(i\right)}=1$ $y^{(i)}=1$时，为了使间隔最大， ${w}^{T}x+b$ $w^Tx+b$必须是一个尽量大的正数，这样才能确保分类正确的确信度最高。一样地，当 ${y}^{\left(i\right)}=-1$ $y^{(i)}=-1$时，为了使间隔最大， ${w}^{T}x+b$ $w^Tx+b$必须是一个尽量大的负数。

$\stackrel{^}{\gamma }=\underset{i=1,...,m}{min}{\stackrel{^}{\gamma }}^{\left(i\right)}$

${w}^{T}\left({x}^{\left(i\right)}-{\gamma }^{\left(i\right)}\ast \frac{w}{||w||}\right)+b=0.$

${\gamma }^{\left(i\right)}=\frac{{w}^{T}{x}^{\left(i\right)}+b}{||w||}=\left(\frac{w}{||w||}{\right)}^{T}{x}^{\left(i\right)}+\frac{b}{||w||}$

${\gamma }^{\left(i\right)}={y}^{\left(i\right)}\left(\left(\frac{w}{||w||}{\right)}^{T}{x}^{\left(i\right)}+\frac{b}{||w||}\right)$

${\gamma }^{\left(i\right)}=\frac{{\stackrel{^}{\gamma }}^{\left(i\right)}}{||w||}$

$||w||=1$ $||w||=1$ 时，几何间隔就等于函数间隔。

$\gamma =\underset{i=1,...,m}{min}{\gamma }^{\left(i\right)}$

$L\left(w,\beta \right)=f\left(w\right)+\underset{i=1}{\overset{l}{\sum }}{\beta }_{i}{h}_{i}\left(w\right)$

$L\left(w,\alpha ,\beta \right)=f\left(w\right)+\underset{i=1}{\overset{k}{\sum }}{\alpha }_{i}{g}_{i}\left(w\right)+\underset{i=1}{\overset{k}{\sum }}{\beta }_{i}{h}_{i}\left(w\right).$

$\begin{array}{ll}{\theta }_{p}\left(w\right)=\underset{\alpha ,\beta :{\alpha }_{i}\ge 0}{max}& L\left(w,\alpha ,\beta \right)\end{array}$

$\begin{array}{lll}{\theta }_{p}\left(w\right)& =\underset{\alpha ,\beta :{\alpha }_{i}\ge 0}{max}& f\left(w\right)+\underset{i=1}{\overset{k}{\sum }}{\alpha }_{i}{g}_{i}\left(w\right)+\underset{i=1}{\overset{k}{\sum }}{\beta }_{i}{h}_{i}\left(w\right)\\ & =\mathrm{\infty }\end{array}$

${\theta }_{p}\left(w\right)=\left\{\begin{array}{ll}f\left(w\right),& \text{若是w知足全部约束}\\ \mathrm{\infty },& \text{不然}\end{array}$

${p}^{\ast }$ $p^*$即为原问题的解。

${\theta }_{d}\left(\alpha ,\beta \right)=\underset{w}{min}L\left(w,\alpha ,\beta \right)$

${d}^{\ast }$ $d^*$即为对偶问题的解。

$L\left(w,\alpha ,\beta \right)=f\left(w\right)+\underset{i=1}{\overset{k}{\sum }}{\alpha }_{i}{g}_{i}\left(w\right)+\underset{i=1}{\overset{k}{\sum }}{\beta }_{i}{h}_{i}\left(w\right).$

$\begin{array}{}\text{(34)}& q\left(\alpha ,\beta \right)& =\underset{w\in W}{inf}L\left(w,\alpha ,\beta \right)\text{(35)}& f\left(w\right)& =\underset{\alpha ,\beta :{\alpha }_{i}\ge 0}{sup}L\left(w,\alpha ,\beta \right)\end{array}$

$q\left(\alpha ,\beta \right)\le f\left(w\right)$

$\underset{\alpha ,\beta :{\alpha }_{i}\ge 0}{sup}q\left(\alpha ,\beta \right)\le \underset{w\in W}{inf}f\left(w\right)$

$\underset{\alpha ,\beta :{\alpha }_{i}\ge 0}{sup}\underset{w\in W}{inf}L\left(w,\alpha ,\beta \right)\le \underset{w\in W}{inf}\underset{\alpha ,\beta :{\alpha }_{i}\ge 0}{sup}L\left(w,\alpha ,\beta \right)$

$L\left(w,\alpha ,\beta \right)=\frac{1}{2}||w|{|}^{2}+\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}\left[1-{y}^{\left(i\right)}\left({w}^{T}{x}^{\left(i\right)}+b\right)\right].$

$\underset{{\alpha }_{i}\ge 0}{max}\underset{w,b}{min}\frac{1}{2}||w|{|}^{2}+\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}\left[1-{y}^{\left(i\right)}\left({w}^{T}{x}^{\left(i\right)}+b\right)\right].$

${\mathrm{\nabla }}_{w}L\left(w,b,\alpha \right)=w-\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}{x}^{\left(i\right)}=0$

$w=\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}{x}^{\left(i\right)}$

$\frac{\mathrm{\partial }}{\mathrm{\partial }b}L\left(w,b,\alpha \right)=\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}=0$

$L\left(w,b,\alpha \right)=\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}-\frac{1}{2}\underset{i=1}{\overset{m}{\sum }}\underset{j=1}{\overset{m}{\sum }}{y}^{\left(i\right)}{y}^{\left(j\right)}{\alpha }_{i}{\alpha }_{j}\left({x}^{\left(i\right)}{\right)}^{T}{x}^{\left(j\right)}$

$\begin{array}{l}\underset{i:{y}^{\left(i\right)}=-1}{max}{{w}^{\ast }}^{T}{x}^{\left(i\right)}+b=-\stackrel{^}{\gamma }\\ \underset{i:{y}^{\left(i\right)}=1}{min}{{w}^{\ast }}^{T}{x}^{\left(i\right)}+b=\stackrel{^}{\gamma }\end{array}$

$b=-\frac{\underset{i:{y}^{\left(i\right)}=-1}{max}{{w}^{\ast }}^{T}{x}^{\left(i\right)}+\underset{i:{y}^{\left(i\right)}=1}{min}{{w}^{\ast }}^{T}{x}^{\left(i\right)}}{2}.$

$\begin{array}{ll}{w}^{T}x+b& =\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}\left({x}^{\left(i\right)}{\right)}^{T}x+b\\ & =\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}⟨{x}^{\left(i\right)},x⟩+b.\end{array}$

${w}^{T}x+b>0$ $w^Tx+b\gt 0$ 时咱们把该样本预测为正样本， ${w}^{T}x+b\le 0$ $w^Tx+b\le0$ 时预测为负样本。

$\varphi \left(x\right):X\to H$

$K\left(x,z\right)=⟨\varphi \left(x\right),\varphi \left(z\right)⟩$

$\begin{array}{ll}f\left(x\right)& ={w}^{T}\varphi \left(x\right)+b\\ & =\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}\varphi \left({x}^{\left(i\right)}{\right)}^{T}\varphi \left(x\right)+b\\ & =\underset{i=1}{\overset{m}{\sum }}{\alpha }_{i}{y}^{\left(i\right)}k\left({x}^{\left(i\right)},x\right)+b\end{array}$

$K=\left[\begin{array}{ccccc}k\left({x}^{\left(1\right)},{x}^{\left(1\right)}\right)& \cdots & k\left({x}^{\left(1\right)},{x}^{\left(j\right)}\right)& \cdots & k\left({x}^{\left(1\right)},{x}^{\left(m\right)}\right)\\ \cdots & \ddots & ⋮& \ddots & ⋮\\ k\left({x}^{\left(i\right)},{x}^{\left(1\right)}\right)& \cdots & k\left({x}^{\left(i\right)},{x}^{\left(j\right)}\right)& \cdots & k\left({x}^{\left(i\right)},{x}^{\left(m\right)}\right)\\ \cdots & \ddots & ⋮& \ddots & ⋮\\ k\left({x}^{\left(m\right)},{x}^{\left(1\right)}\right)& \cdots & k\left({x}^{\left(m\right)},{x}^{\left(j\right)}\right)& \cdots & k\left({x}^{\left(m\right)},{x}^{\left(m\right)}\right)\end{array}\right]$

$\begin{array}{ll}{z}^{T}Kz& =\underset{i}{\sum }\underset{j}{\sum }{z}_{i}k\left({x}^{\left(i\right)},{x}^{\left(j\right)}\right){z}_{j}\\ & =\underset{i}{\sum }\underset{j}{\sum }{z}_{i}\varphi \left({x}^{\left(i\right)}{\right)}^{T}\varphi \left({x}^{\left(j\right)}\right){z}_{j}\\ & =\underset{i}{\sum }\underset{j}{\sum }{z}_{i}\underset{k}{\sum }{\varphi }_{k}\left({x}^{\left(i\right)}\right){\varphi }_{k}\left({x}^{\left(j\right)}\right){z}_{j}\\ & =\underset{k}{\sum }\underset{i}{\sum }\underset{j}{\sum }{z}_{i}{\varphi }_{k}\left({x}^{\left(i\right)}\right){\varphi }_{k}\left({x}^{\left(j\right)}\right){z}_{j}\\ & =\underset{k}{\sum }\left(\underset{i}{\sum }{z}_{i}{\varphi }_{k}\left({x}^{\left(i\right)}\right){\right)}^{2}\\ & \ge 0.\end{array}$