SVM 公式推导

1.1. SVM

1.1.1. 支持向量机的基本型

思想:找到一个划分两类训练样本的超平面，并使间隔最大化。

（1）超平面:表达式
$w^{T}x+b=0$wTx+b=0

（2）函数间隔
定义样本点 $(x_i,y_i)$(xi​,yi​)到超平面( $w,b$w,b)函数间隔为：
$\widehat{{\gamma }_i}=y_i(w^T{x}_i+b)$γi​^​=yi​(wTxi​+b)

函数间隔为正表明分类正确，负表明分类错误，因此函数间隔可以表示分类预测的正确性;
在超平面保持不变的情况下，等比例缩放 $w、b$w、b,会导致函数间隔也等比例缩放，因此需要进行约束。

（3）几何间隔
样本点 $(x_i,y_i)$(xi​,yi​)到超平面( $w,b$w,b)几何间隔为：
${\gamma }_i=\frac{\mid w^T{x}_i+b\mid }{\parallel w\parallel }$γi​=∥w∥∣∣​wTxi​+b∣∣​​

几何间隔的物理含义是点到超平面的距离,即使超平面参数等比例发生变化，几何间隔仍保持不变

<stron>
若点坐标为 $(x_0,y_0,z_0)$(x0​,y0​,z0​),平面为 $Ax+By+Cz+D=0$Ax+By+Cz+D=0,则点到平面的距离为
$d=\mid \frac{A{x}_0+B{y}_0+C{z}_0+D}{\sqrt{A^2+B^2+C^2}}\mid$d=∣∣∣∣​A2+B2+C2 ​Ax0​+By0​+Cz0​+D​∣∣∣∣​</stron>

几何间隔与函数间隔关系：
${\gamma }_i=\frac{\widehat{{\gamma }_i}}{\parallel w\parallel }$γi​=∥w∥γi​^​​

(4) 间隔最大化
样本点到超平面的最小距离为
$\gamma =\underset{}{\min }{\gamma }_i$γ=i=1,...Nmin​γi​
要使间隔最大化，即求解下面的约束问题：
$\underset{}{\max }\gamma \text{s.t. }\frac{y_i(w^T{x}_i+b)}{\parallel w\parallel }⩾\gamma ,i=1,...N$w,bmax​γs.t. ∥w∥yi​(wTxi​+b)​⩾γ,i=1,...N

根据函数间隔和几何间隔的关系，得到
$\underset{}{\max }\frac{\widehat{\gamma }}{\parallel w\parallel }\text{s.t. }{y}_i(w^T{x}_i+b)⩾\widehat{\gamma },i=1,...N$w,bmax​∥w∥γ^​​s.t. yi​(wTxi​+b)⩾γ^​,i=1,...N

$\widehat{\gamma }$γ^​的改变不影响最优化问题的求解。为方便将 $\widehat{\gamma }=1$γ^​=1，于是得到优化目标 $\frac{1}{\parallel w\parallel }$∥w∥1​。又因为最大化 $\frac{1}{\parallel w\parallel }$∥w∥1​和最小化 $\frac{1}{2}\parallel w{\parallel }^2$21​∥w∥2等价，所以：
$\underset{}{\min }\frac{1}{2}{\parallel w\parallel }^2\text{s.t. }{y}_i(w^T{x}_i+b)⩾1,i=1,2,\dots ,m$w,bmin​21​∥w∥2s.t. yi​(wTxi​+b)⩾1,i=1,2,…,m

1.1.2. 对偶问题

（1）构建拉格朗日函数
对SVM的基本型使用拉格朗日乘子法可以得到拉格朗日函数。即对每条约束添加拉格朗日乘子 ${\alpha }_i⩾0$αi​⩾0.
$L(w,b,\alpha )=\frac{1}{2}\parallel w{\parallel }^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b))$L(w,b,α)=21​∥w∥2+i=1∑m​αi​(1−yi​(wTxi​+b))
原始目标函数转化成：
$\underset{}{\max }L(w,b,\alpha )$w,bmax​L(w,b,α)

如果约束条件不满足，即出现 $(1-y_i(w^T{x}_i+b\left)\right)\&gt;0$(1−yi​(wTxi​+b))>0,令 ${\alpha }_i$αi​趋近于无穷，目标函数取值也趋近于无穷。

对目标函数取最小值，原问题转化成：
$\underset{}{\min }\underset{}{\max }\left(L\right(w,b,\alpha \left)\right)$αmin​w,bmax​(L(w,b,α))

由于不满足约束条件的函数值为无穷大，因此取得的最小值必然满足约束条件

（2）转化为对偶问题

为什么转化为对偶问题？
1.对偶问题将原始问题中的约束转为了对偶问题中的等式约束
2.方便核函数的引入
3.改变了问题的复杂度。由求特征向量w转化为求比例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。

原始问题是极小极大问题，转化为对偶问题为极大极小问题。
$\underset{}{\max }\underset{}{\min }L(w,b,\alpha )$αmax​w,bmin​L(w,b,α)

（3）计算 ${\min }_{}L(w,b,\alpha )$minw,b​L(w,b,α)

令 $L(w,b,x)$L(w,b,x)对 $w,b$w,b的偏导为0
$\frac{\partial L}{\partial w}=w-\sum _{i=1}^m{\alpha }_i{y}_i{x}_i=0$∂w∂L​=w−i=1∑m​αi​yi​xi​=0
$\frac{\partial L}{\partial b}=-\sum _{i=1}^m{\alpha }_i{y}_i=0$∂b∂L​=−i=1∑m​αi​yi​=0
得
$w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$w=i=1∑m​αi​yi​xi​
$\sum _{i=1}^m{\alpha }_i{y}_i=0$i=1∑m​αi​yi​=0
将 $w={\sum }_{i=1}^m{\alpha }_i{y}_i{x}_i$w=∑i=1m​αi​yi​xi​代入拉格朗日函数：
$\begin{array}{cc}{\displaystyle L(w,b,\alpha )}& {\displaystyle =\frac{1}{2}{w}^{T}w+\sum _{i=1}^m{\alpha }_i(1-y_i(w^T{x}_i+b))}\\ {\displaystyle }& {\displaystyle =\frac{1}{2}\sum _{i=1}^m{\alpha }_i{y}_i{x_i}^T\sum _{j=1}^m{\alpha }_j{y}_j{x}_j+\sum _{i=1}^m{\alpha }_i(1-y_i(\sum _{j=1}^m{\alpha }_j{y}_j{x_j}^T{x}_i+b\left)\right)}\\ {\displaystyle }& {\displaystyle =\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x_i}^T{x}_j+\sum _{i=1}^m{\alpha }_i-\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x_i}^T{x}_j+b\sum _{i=1}^m{\alpha }_i{y}_i}\\ {\displaystyle }& {\displaystyle =\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x_i}^T{x}_j}\end{array}$L(w,b,α)​=21​wTw+i=1∑m​αi​(1−yi​(wTxi​+b))=21​i=1∑m​αi​yi​xi​Tj=1∑m​αj​yj​xj​+i=1∑m​αi​(1−yi​(j=1∑m​αj​yj​xj​Txi​+b))=21​i=1∑m​j=1∑m​αi​αj​yi​yj​xi​Txj​+i=1∑m​αi​−i=1∑m​j=1∑m​αi​αj​yi​yj​xi​Txj​+bi=1∑m​αi​yi​=i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xi​Txj​​
（4）对偶问题
上式计算出来是满足条件的间隔，而我们的目标是间隔最大化，同时考虑到关于 $\alpha$α的约束条件，得到如下问题：
$\underset{}{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​
$\begin{array}{cc}\text{ s.t. }& {\sum }_{i=1}^m{\alpha }_i{y}_i=0\\ & {\alpha }_i⩾0,i=1,2,\dots ,m\end{array}$ s.t. ​∑i=1m​αi​yi​=0αi​⩾0,i=1,2,…,m​

原始问题的最优解( $w^{\ast },b^{\ast }$w∗,b∗)和对偶问题最优解( ${\alpha }^{\ast }$α∗)满足KKT条件时：
$\{\begin{array}{c}{\alpha }_i⩾0\\ y_{i}f\left(x_i\right)-1⩾0\\ {\alpha }_i(y_{i}f\left(x_i\right)-1)=0\end{array}$⎩⎨⎧​αi​⩾0yi​f(xi​)−1⩾0αi​(yi​f(xi​)−1)=0​
二者的解相同。

$L(a,b,x)=f\left(x\right)+a\cdot g\left(x\right)+b\cdot h\left(x\right)$L(a,b,x)=f(x)+a⋅g(x)+b⋅h(x), 原始问题最优解 $x^{\ast }$x∗,对偶问题最优解 $a^{\ast },b^{\ast }$a∗,b∗.
KKT条件:
i. ${\nabla }_{x}L(a^{\ast },b^{\ast },x^{\ast })=0,{\nabla }_{a}L(a^{\ast },b^{\ast },x^{\ast })=0,{\nabla }_{b}L(a^{\ast },b^{\ast },x^{\ast })=0$∇x​L(a∗,b∗,x∗)=0,∇a​L(a∗,b∗,x∗)=0,∇b​L(a∗,b∗,x∗)=0
ii. $a^{\ast }\cdot g_i\left(x^{\ast }\right)=0$a∗⋅gi​(x∗)=0
iii. $g_i\left(x^{\ast }\right)\le 0$gi​(x∗)≤0
vi. $a_i^{\ast }\ge 0,h_j\left(x\right)=0$ai∗​≥0,hj​(x)=0

(5) 求解结果
假设求解得到最优解的为 ${\alpha }^{\ast }$α∗,则
$w^{\ast }=\sum _{i=1}^m{\alpha }_i^{\ast }{y}_i{x}_i$w∗=i=1∑m​αi∗​yi​xi​
$b^{\ast }=\frac{1}{\mid S\mid }\sum _{s\in S}(y_s-\sum _{i=1}^m{\alpha }_i{y}_i{x}_i^T{x}_s)$b∗=∣S∣1​s∈S∑​(ys​−i=1∑m​αi​yi​xiT​xs​)
于是超平面为:
$w^{\ast }x+b^{\ast }=0$w∗x+b∗=0
决策函数为:
$f\left(x\right)=sign(w^{\ast }x+b^{\ast })$f(x)=sign(w∗x+b∗)

1.1.3. 软间隔

以上提出的支持向量机模型是线性的，对于线性不可分的数据不适用。线性不可分意味着部分样本不能满足函数间隔大于等于1的约束条件。为此，为每个样本点引入松弛变量 ${\xi }_i⩾0$ξi​⩾0,使得函数间隔加上松弛变量大于等于1，约束条件变成：
$y_i(w^T{x}_i+b)⩾1-{\xi }_i$yi​(wTxi​+b)⩾1−ξi​
对每个松弛变量 ${\xi }_i$ξi​，支付一个代价 ${\xi }_i$ξi​,则目标函数变成：
$\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^m{\xi }_i$21​∥w∥2+Ci=1∑m​ξi​

C为惩罚系数。

（1）原始问题
引入软间隔之后，原始问题变成：
$\underset{}{\min }\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^m{\xi }_i\text{s.t. }{y}_i(w^{T}x+b)⩾1-{\xi }_i,i=1,...,m{\xi }_i⩾0,i=1,...,m$w,b,ξmin​21​∥w∥2+Ci=1∑m​ξi​s.t. yi​(wTx+b)⩾1−ξi​,i=1,...,mξi​⩾0,i=1,...,m

(2)对偶问题
先求出拉格朗日函数：
$\begin{array}{c}{\displaystyle L(w,b,\alpha ,\xi ,\mu )=\frac{1}{2}\parallel w{\parallel }^2+C\sum _{i=1}^m{\xi }_i+\sum _{i=1}^m{\alpha }_i(1-{\xi }_i-y_i(w^T{x}_i+b))-\sum _{i=1}^m{\mu }_i{\xi }_i}\end{array}$L(w,b,α,ξ,μ)=21​∥w∥2+Ci=1∑m​ξi​+i=1∑m​αi​(1−ξi​−yi​(wTxi​+b))−i=1∑m​μi​ξi​​

再对 $w,b,{\xi }_i$w,b,ξi​求偏导等于0得到：
$\begin{array}{cc}{\displaystyle w}& {\displaystyle =\sum _{i=1}^m{\alpha }_i{y}_i{x}_i}\\ {\displaystyle 0}& {\displaystyle =\sum _{i=1}^m{\alpha }_i{y}_i}\\ {\displaystyle C}& {\displaystyle ={\alpha }_i+{\mu }_i}\end{array}$w0C​=i=1∑m​αi​yi​xi​=i=1∑m​αi​yi​=αi​+μi​​

最后得到对偶问题：
$\underset{}{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j\text{s.t. }\sum _{i=1}^m{\alpha }_i{y}_i=00⩽{\alpha }_i⩽C,i=1,2,\dots ,m$αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​s.t. i=1∑m​αi​yi​=00⩽αi​⩽C,i=1,2,…,m

相较于硬间隔支持向量机， ${\alpha }_i$αi​增加了一个约束C,其余相同.

KKT条件:
$\{\begin{array}{c}{\alpha }_i⩾0,{\mu }_i⩾0\\ y_{i}f\left(x_i\right)-1+{\xi }_i⩾0\\ {\alpha }_i(y_{i}f\left(x_i\right)-1+{\xi }_i)=0\\ {\xi }_i⩾0,{\mu }_i{\xi }_i=0\end{array}$⎩⎪⎪⎨⎪⎪⎧​αi​⩾0,μi​⩾0yi​f(xi​)−1+ξi​⩾0αi​(yi​f(xi​)−1+ξi​)=0ξi​⩾0,μi​ξi​=0​

1.1.4. 核函数

(1)核技巧
对于非线性分类问题,首先使用一个变换将原空间的数据映射到新空间,然后再新空间里用线性分类学习方法从训练数据中学习分类模型.

(2)核函数
核函数与映射函数的关系
设 $X$X是输入空间, $H$H是特征空间(希尔伯特空间),如果存在一个从 $X$X到 $H$H的映射,
$\varphi \left(x\right):X\to H$ϕ(x):X→H
使得对于所有的 $x,z\in X$x,z∈X,函数 $K(x,z)$K(x,z)满足条件
$K(x,z)=\varphi (x{)}^T\cdot \varphi (z)$K(x,z)=ϕ(x)T⋅ϕ(z)
则成 $K(x,z)$K(x,z)为核函数.
在实际使用中,只定义核函数,不显性定义映射.因为映射后的空间维数可能很高,直接计算 $\varphi (x{)}^T\cdot \varphi (z)$ϕ(x)T⋅ϕ(z)通常很困难.由于计算结果是一个数,因此可以使用核函数来替代映射内积的结果

(3)原始问题:
$\underset{}{\min }\frac{1}{2}\parallel w{\parallel }^2\text{ s.t. }{y}_i(w^T\varphi \left(x_i\right)+b)⩾1,i=1,2,\dots ,m$w,bmin​21​∥w∥2 s.t. yi​(wTϕ(xi​)+b)⩾1,i=1,2,…,m

(4)对偶问题
$\begin{array}{cc}{\max }_{}& {\sum }_{i=1}^m{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\kappa (x_i,x_j)\\ \text{ s.t. }& {\sum }_{i=1}^m{\alpha }_i{y}_i=0\\ & {\alpha }_i⩾0,i=1,2,\dots ,m\end{array}$maxα​ s.t. ​∑i=1m​αi​−21​∑i=1m​∑j=1m​αi​αj​yi​yj​κ(xi​,xj​)∑i=1m​αi​yi​=0αi​⩾0,i=1,2,…,m​

(5)决策平面
$\begin{array}{cc}{\displaystyle f\left(x\right)}& {\displaystyle =w^T\varphi \left(x\right)+b}\\ {\displaystyle }& {\displaystyle =\sum _{i=1}^m{\alpha }_i{y}_i\varphi {\left(x_i\right)}^T\varphi \left(x\right)+b}\\ {\displaystyle }& {\displaystyle =\sum _{i=1}^m{\alpha }_i{y}_i\kappa (x,x_i)+b}\end{array}$f(x)​=wTϕ(x)+b=i=1∑m​αi​yi​ϕ(xi​)Tϕ(x)+b=i=1∑m​αi​yi​κ(x,xi​)+b​

(6)常用核函数
[外链图片转存失败(img-5QuHpX0x-1562658199123)(https://raw.githubusercontent.com/EEEGUI/ImageBed/master/img/fig_065.png)]