SVM是一个非常经典的监督学习算法。下面给出SVM对于二值分类的原理及推导过程。

1、问题转化

如下图所示：
想要找一条直线$wx+b=0$wx+b=0将图中红蓝两类样本区分开，假设将这条线向左和向右分别平移，接触到样本点停止，得到两条新的直线，设它们分别为$wx+b=c\;$wx+b=c和$wx+b=-c$wx+b=−c。
令$w=\frac{w}{c},b=\frac{b}{c}$w=cw​,b=cb​，则这两条直线转化为$wx+b=1\;$wx+b=1和$wx+b=-1$wx+b=−1。此时，令$wx+b=0$wx+b=0也左右同时除以$c$c，仍得到$wx+b=0$wx+b=0。
SVM的目的即找到直线$wx+b=0$wx+b=0，使得$wx+b=1\;$wx+b=1和$wx+b=-1$wx+b=−1之间的距离$2d=\frac{2}{||w||}$2d=∣∣w∣∣2​最大。
所以，只要保证：
$min\quad \frac{1}{2}||w||^{2}$min21​∣∣w∣∣2
由于在上图中红线的上方$wx+b<0\;$wx+b<0，且标签$y=-1$y=−1；而在红线的下方有$wx+b>0\;$wx+b>0，且标签$y=1$y=1，故有约束条件：
$(wx_{i}+b)y_{i}\geq1$(wxi​+b)yi​≥1
到这里，此问题已被转化为一有约束的优化问题：
$\begin{cases} min\; \frac{1}{2}||w||^{2} \\ (wx_{i}+b)y_{i}\geq1 \end{cases}${min21​∣∣w∣∣2(wxi​+b)yi​≥1​
对于小样本问题，可以用拉格朗日乘子法解决。
详细解法参照 https://blog.****.net/qq_36758914/article/details/103324074

2、拉格朗日对偶

此处引入拉格朗日对偶的概念。

1） 原始问题

假设$f_{(x)}, c_{i(x)}, h_{j(x)}$f(x)​,ci(x)​,hj(x)​是定义在$R^{n}$Rn上的连续可微函数，考虑约束最优化问题：
$\mathop{min}\limits_{x\in R^{n}}f_{(x)}$x∈Rnmin​f(x)​
$s.t.\quad c_{i(x)}\leq0\;,i=1,2,…,k;\quad h_{j(x)}=0\;,i=1,2,…,l$s.t.ci(x)​≤0,i=1,2,…,k;hj(x)​=0,i=1,2,…,l
称此约束最优化问题为原始最优化问题或原始问题。
首先，引进广义拉格朗日函数：
$L_{(x,\alpha,\beta)}=f_{(x)}+\sum_{i=1}^{k}\alpha_{i}c_{i(x)}+\sum_{j=1}^{l}\beta_{j}h_{j(x)}$L(x,α,β)​=f(x)​+i=1∑k​αi​ci(x)​+j=1∑l​βj​hj(x)​
这里，$x=(x^{(1)},x^{(2)},…,x^{(n)})^{T}\in R^{n}$x=(x(1),x(2),…,x(n))T∈Rn，$\alpha_{i},\; \beta_{j}$αi​,βj​是拉格朗日乘子，$\alpha_{i}\geq0$αi​≥0。考虑$x$x的函数：
$\theta_{p(x)}=\mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}L_{(x,\alpha,\beta)}$θp(x)​=α,β,αi​≥0max​L(x,α,β)​
假设给定某个$x$x，如果$x$x违反原始问题的约束条件，即存在某个$i$i使得$c_{i(x)}>0\;$ci(x)​>0或者存在某个$j$j使得$h_{j(x)}\ne0$hj(x)​​=0，那么就有：
$\theta_{p(x)}=\mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}[f_{(x)}+\sum_{i=1}^{k}\alpha_{i}c_{i(x)}+\sum_{j=1}^{l}\beta_{j}h_{j(x)}]=+\infty$θp(x)​=α,β,αi​≥0max​[f(x)​+i=1∑k​αi​ci(x)​+j=1∑l​βj​hj(x)​]=+∞
因为若某个$i$i使得$c_{i(x)}>0$ci(x)​>0，则可以令$\alpha_{i}\rightarrow+\infty$αi​→+∞，若某个$j$j使$h_{j(x)}\ne0$hj(x)​​=0，则可令$\beta_{j}\rightarrow+\infty$βj​→+∞。以上两种情况均可以使$\;\theta_{p(x)}=+\infty$θp(x)​=+∞。
相反地，若$x$x满足约束条件，则：
$\theta_{p(x)}=\mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}[f_{(x)}+\sum_{i=1}^{k}\alpha_{i}c_{i(x)}]$θp(x)​=α,β,αi​≥0max​[f(x)​+i=1∑k​αi​ci(x)​]
由于$\alpha_{i}\geq0$αi​≥0，$c_{i(x)}\leq0$ci(x)​≤0，故$\mathop{\sum}\limits_{i=1}^{k}\alpha_{i}c_{i(x)}\leq0$i=1∑k​αi​ci(x)​≤0。所以：
$\theta_{p(x)}=f_{(x)}$θp(x)​=f(x)​
即：
$\theta_{p(x)}=\begin{cases} f_{(x)}, & \text {x\;满足原问题约束} \\ +\infty, & \text {其他} \end{cases}$θp(x)​={f(x)​,+∞,​x满足原问题约束其他​
如果考虑极小化问题
$\mathop{min}\limits_{x}\theta_{p(x)}=\mathop{min}\limits_{x} \mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}L_{(x,\alpha,\beta)}$xmin​θp(x)​=xmin​α,β,αi​≥0max​L(x,α,β)​
由$\theta_{p(x)}$θp(x)​的表达式可知，$\mathop{min}\limits_{x}\theta_{p(x)}$xmin​θp(x)​是与原始最优化问题等价的，也就是说它们的解相同。问题$\mathop{min}\limits_{x} \mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}L_{(x,\alpha,\beta)}$xmin​α,β,αi​≥0max​L(x,α,β)​被称为广义拉格朗日函数的极小极大问题。

2）对偶问题

定义
$\theta_{D(\alpha,\beta)}=\mathop{min}\limits_{x}L_{(x,\alpha,\beta)}$θD(α,β)​=xmin​L(x,α,β)​
再考虑极大化$\theta_{D(\alpha,\beta)}$θD(α,β)​，即：
$\mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}\theta_{D(\alpha,\beta)}=\mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}\mathop{min}\limits_{x}L_{(x,\alpha,\beta)}$α,β,αi​≥0max​θD(α,β)​=α,β,αi​≥0max​xmin​L(x,α,β)​
问题$\mathop{max}\limits_{\alpha,\; \beta,\; \alpha_{i}\geq0}\mathop{min}\limits_{x}L_{(x,\alpha,\beta)}\;$α,β,αi​≥0max​xmin​L(x,α,β)​称为广义拉格朗日函数的极大极小问题。
若目标函数与所有约束函数皆为凸函数，则原始问题和它的对偶问题是等价的。
而对于$SVM$SVM，其所有函数皆为凸函数。

3、SVM的对偶问题

$\begin{cases} min\; \frac{1}{2}w^{2} \\ (wx_{i}+b)y_{i}\geq1 \end{cases}${min21​w2(wxi​+b)yi​≥1​
其广义拉格朗日函数为：
$L_{(w,b,\alpha)}=\frac{1}{2}w^{2}+\sum_{i=1}^{N}\alpha_{i}[1-(wx_{i}+b)y_{i}]$L(w,b,α)​=21​w2+i=1∑N​αi​[1−(wxi​+b)yi​]
原问题：
$\mathop{min}\limits_{w,\;b} \mathop{max}\limits_{\alpha_{i}\geq0}L_{(w,b,\alpha)}$w,bmin​αi​≥0max​L(w,b,α)​
对偶问题：
$\mathop{max}\limits_{\alpha_{i}\geq0}\mathop{min}\limits_{w,\;b}L_{(w,b,\alpha)}$αi​≥0max​w,bmin​L(w,b,α)​
先对$L_{(x,\alpha,\beta)}$L(x,α,β)​求极小值：
$\frac{\partial L}{\partial w}=0\Rightarrow w=\sum_{i=1}^{N}\alpha_{i}x_{i}y_{i}$∂w∂L​=0⇒w=i=1∑N​αi​xi​yi​
$\frac{\partial L}{\partial b}=0\Rightarrow \sum_{i=1}^{N}\alpha_{i}y_{i}=0$∂b∂L​=0⇒i=1∑N​αi​yi​=0
将结果带入对偶问题，可将其转化为下式：
$\mathop{max}\limits_{\alpha_{i}\geq0}\;\frac{1}{2}(\sum_{i=1}^{N}\alpha_{i}x_{i}y_{i})^{2}+\sum_{i=1}^{N}\alpha_{i}[1-((\sum_{j=1}^{N}\alpha_{j}x_{j}y_{j})x_{i}+b)y_{i}]$αi​≥0max​21​(i=1∑N​αi​xi​yi​)2+i=1∑N​αi​[1−((j=1∑N​αj​xj​yj​)xi​+b)yi​]
$=\mathop{max}\limits_{\alpha_{i}\geq0}\;\frac{1}{2}(\sum_{i=1}^{N}\alpha_{i}x_{i}y_{i})^{2}+\sum_{i=1}^{N}\alpha_{i}[1-(\sum_{j=1}^{N}\alpha_{j}x_{j}y_{j})x_{i}y_{i}]$=αi​≥0max​21​(i=1∑N​αi​xi​yi​)2+i=1∑N​αi​[1−(j=1∑N​αj​xj​yj​)xi​yi​]
$=\mathop{max}\limits_{\alpha_{i}\geq0}\;\frac{1}{2}(\sum_{i=1}^{N}\alpha_{i}x_{i}y_{i})^{2}+\sum_{i=1}^{N}\alpha_{i}-\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}x_{i}y_{i}\alpha_{j}x_{j}y_{j}$=αi​≥0max​21​(i=1∑N​αi​xi​yi​)2+i=1∑N​αi​−i=1∑N​j=1∑N​αi​xi​yi​αj​xj​yj​
$=\mathop{max}\limits_{\alpha_{i}\geq0}\;-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}<x_{i}x_{j}>+\sum_{i=1}^{N}\alpha_{i}$=αi​≥0max​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​<xi​xj​>+i=1∑N​αi​
约束条件为：
$\sum_{i=1}^{N}\alpha_{i}y_{i}=0\quad \alpha_{i}\geq0$i=1∑N​αi​yi​=0αi​≥0
$KKT$KKT条件为：
$\alpha_{i}[1-(wx_{i}+b)y_{i}=0$αi​[1−(wxi​+b)yi​=0
故原始问题被转化为：
$\begin{cases} \mathop{max}\limits_{\alpha_{i}\geq0}\;-\frac{1}{2}\mathop{\sum}\limits_{i=1}^{N}\mathop{\sum}\limits_{j=1}^{N}\alpha_{i}\alpha_{j}y_{i}y_{j}<x_{i}x_{j}>+\mathop{\sum}\limits_{i=1}^{N}\alpha_{i} \\ \mathop{\sum}\limits_{i=1}^{N}\alpha_{i}y_{i}=0\quad \alpha_{i}\geq0 \\ \alpha_{i}[1-(wx_{i}+b)y_{i}=0 \end{cases}$⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​αi​≥0max​−21​i=1∑N​j=1∑N​αi​αj​yi​yj​<xi​xj​>+i=1∑N​αi​i=1∑N​αi​yi​=0αi​≥0αi​[1−(wxi​+b)yi​=0​

4、SMO算法（序列最小优化算法）

优化此问题时采用SMO算法。
假设此问题中只有$\alpha_{1}$α1​到$\alpha_{10}$α10​，则SMO算法的步骤如下。
1）先固定$\alpha_{3}$α3​到$\alpha_{10}$α10​，则最优化函数变为：
$\mathop{max}\limits_{\alpha_{i}\geq0}\;-\frac{1}{2}\mathop{\sum}\limits_{i=1}^{2}\mathop{\sum}\limits_{j=1}^{2}\alpha_{i}\alpha_{j}y_{i}y_{j}<x_{i}x_{j}>+\mathop{\sum}\limits_{i=1}^{2}\alpha_{i}$αi​≥0max​−21​i=1∑2​j=1∑2​αi​αj​yi​yj​<xi​xj​>+i=1∑2​αi​
约束条件变为：
$\alpha_{1}y_{1}+\alpha_{2}y_{2}=-\sum_{i=3}^{10}\alpha_{i}y_{i}\text{\;为一常数}$α1​y1​+α2​y2​=−i=3∑10​αi​yi​为一常数
则此优化问题变成了一个二维变量（$\alpha_{1}，\alpha_{2}$α1​，α2​）的优化问题，使原来的十维优化问题大大简化。
这时，可以先算出最优的$\alpha_{1}$α1​和$\alpha_{2}$α2​。
2）固定$\alpha_{1}$α1​和$\alpha_{4}$α4​到$\alpha_{10}$α10​，重复以上操作并代入最优的$\alpha_{1}$α1​，得到最优的$\alpha_{2}$α2​和$\alpha_{3}$α3​。
3）固定$\alpha_{1}$α1​，$\alpha_{2}$α2​和$\alpha_{5}$α5​到$\alpha_{10}$α10​，重复以上操作并代入最优的$\alpha_{1}$α1​和$\alpha_{2}$α2​，得到最优的$\alpha_{3}$α3​和$\alpha_{4}$α4​。
……
4）得到所有的最优$\alpha$α，将其代入$w=\mathop{\sum}\limits_{i=1}^{10}\alpha_{i}x_{i}y_{i}$w=i=1∑10​αi​xi​yi​，得到最优的$w$w值。
5）若得到的$\alpha_{i}=0$αi​=0，则表示第$i$i个约束条件不起作用；若得到的$\alpha_{i}\ne0$αi​​=0，则它对应的$x_{i}$xi​和$y_{i}$yi​就是支持向量。
6）通过$y=(\mathop{\sum}\limits_{i=1}^{N}\alpha_{i}x_{i}y_{i})^{T}x=\mathop{\sum}\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}^{T}x\;$y=(i=1∑N​αi​xi​yi​)Tx=i=1∑N​αi​yi​xiT​x得到某样本点对应的标签。

5、线性不可分核函数

对于一些线性不可分的样本，如下图（左），不能找出一条直线来分类样本。此时需要做空间的变换。
设原空间为$\chi \subset R^{n},x=(x^{(1)},x^{(2)})^{T} \in \chi$χ⊂Rn,x=(x(1),x(2))T∈χ，新空间为$Z\subset R^{2},z=(z^{(1)},z^{(2)})^{T} \in Z$Z⊂R2,z=(z(1),z(2))T∈Z，定义从原空间到新空间的变换（映射）：
$z=\phi_{(x)}=((x^{(1)})^{2},(x^{(2)})^{2})^{T}$z=ϕ(x)​=((x(1))2,(x(2))2)T
经过变换$z=\phi_{(x)}$z=ϕ(x)​，原空间$\chi \subset R^{n}$χ⊂Rn变换为新空间$Z\subset R^{2}$Z⊂R2，原空间中的点相应地变换为新空间中的点，原空间中的椭圆
$w_{1}(x^{(1)})^{2}+w_{2}(x^{(2)})^{2}+b=0$w1​(x(1))2+w2​(x(2))2+b=0
变换为新空间中的直线
$w_{1}z^{(1)}+w_{2}z^{(2)}+b=0$w1​z(1)+w2​z(2)+b=0
即由下图中的左图变为右图。
实际上我们并不需要知道经过空间变换后的$z_{1}$z1​和$z_{2}$z2​的具体值，因为由$y=(\mathop{\sum}\limits_{i=1}^{N}\alpha_{i}x_{i}y_{i})^{T}x=\mathop{\sum}\limits_{i=1}^{N}\alpha_{i}y_{i}x_{i}^{T}x\;$y=(i=1∑N​αi​xi​yi​)Tx=i=1∑N​αi​yi​xiT​x知，我们只需要知道$x_{i}$xi​和$x$x的点积即可。
常用的空间变换有：
1）多项式核函数：
$K_{(x,z)}=(x\cdot z+1)^{p}$K(x,z)​=(x⋅z+1)p
对应的支持向量机是一个$p$p次多项式的分类器。此时，分类决策函数变成：
$f_{(x)}=sign(\mathop{\sum}\limits_{i=1}^{N}\alpha_{i}y_{i}(x_{i}\cdot x+1)^{p}+b)$f(x)​=sign(i=1∑N​αi​yi​(xi​⋅x+1)p+b)
2）高斯核函数：
$K_{(x,z)}=e^{-\frac{||x-z||^{2}}{2\sigma^{2}}}$K(x,z)​=e−2σ2∣∣x−z∣∣2​
对应的支持向量机是高斯径向基函数分类器。此时，分类决策函数变成：
$f_{(x)}=sign(\mathop{\sum}\limits_{i=1}^{N}\alpha_{i}y_{i}e^{-\frac{||x_{i}-x||^{2}}{2\sigma^{2}}}+b)$f(x)​=sign(i=1∑N​αi​yi​e−2σ2∣∣xi​−x∣∣2​+b)