SVM Soft/Hard/核 原理整理

SVM简介
SVM是定义在特征空间上的间隔最大的线性分类器（可以使用核函数来实现非线性分类），本质上是求解凸二次规划的最优化算法

SVM的特点
１．训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以 SVM 不太容易产生 overfitting
２．SVM 训练出来的模型完全依赖于支持向量，即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型
３．一个 SVM 如果训练得出的支持向量个数比较少，那么SVM 训练出的模型比较容易被泛化
上面三点引用自这个博客

形象图解

上图引用自这篇博客
１．图中的那条实线就是分类线，在如果数据是高维的，那通过直线来分类是不行的，应该是用一个面（曲面，平面）来分，那这个面被成为是超平面
２．这条线的方程为：$w\cdot x+b=0$w⋅x+b=0，与它平行的两条虚线就是最大间隔分界线
３．定义所有数据为：$D=\left\{ \left( \boldsymbol{x}_1,y_1 \right) ,\left( \boldsymbol{x}_2,y_2 \right) ,...,\left( \boldsymbol{x}_N,y_N \right) \right\}$D={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}（注意一下$\boldsymbol{x}$x是向量哦），一共有$N$N个数据点，其中，$x_i\in \mathbb{R}^n$xi​∈Rn，$y_i\in \left\{ +1,-1 \right\} ,i=1,2,...N$yi​∈{+1,−1},i=1,2,...N，对于二分类问题，SVM所要定义的类别标签是1（正例）和-1（反例）
４．我们假设数据$D$D是线性可分的，然后定义线性分类线为$w\cdot x+b=0$w⋅x+b=0，那么每个样本点$\left( \boldsymbol{x}_i,y_i \right)$(xi​,yi​)到分类线的距离为：
$\gamma _i=y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right)$γi​=yi​(∥w∥w​⋅xi​+∥w∥b​)
为什么是这个公式呢？看看初中知识吧：

那为什么会在前面乘上一个$y_i$yi​呢？看看上面的$d$d是绝对值的，也就是说$\gamma _i$γi​是利用了分类标签为+1和-1，去掉了绝对值号
５．然后，计算一下所有样本点到分类线的距离最小值：
$\gamma =\underset{i=1,2...,N}{\min}\gamma _i$γ=i=1,2...,Nmin​γi​
这个距离$\gamma$γ就是支持向量到分类线的距离
６．到这里，我们可以把SVM看成是求解带有约束项的优化问题：
$\underset{\boldsymbol{w,}b}{\max}\ \gamma$w,bmax​ γ
$s.t.\ \ \ y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right) \ge \gamma \ ,i=1,2,...,N$s.t.   yi​(∥w∥w​⋅xi​+∥w∥b​)≥γ ,i=1,2,...,N
化简一下上面的约束条件为：
$y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert \gamma}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert \gamma} \right) \ge 1$yi​(∥w∥γw​⋅xi​+∥w∥γb​)≥1
其中，$\lVert \boldsymbol{w} \rVert \text{，}\gamma$∥w∥，γ均为标量，所以可以令：
$\boldsymbol{w}=\frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert \gamma}$w=∥w∥γw​
$b=\frac{b}{\lVert \boldsymbol{w} \rVert \gamma}$b=∥w∥γb​
因此上述约束可以化简为：
$y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N$yi​(w⋅xi​+b)≥1, i=1,2,...,N
又因为最优问题为最大化$\gamma$γ，所以等价于最大化$\frac{1}{\lVert \boldsymbol{w} \rVert}$∥w∥1​，也就等价于最小化 $\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2$21​∥w∥2
７．那么优化目标又可以简化为：
$\underset{\boldsymbol{w,}b}{\min}\ \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2$w,bmin​ 21​∥w∥2
$s.t.\ \ y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N$s.t.  yi​(w⋅xi​+b)≥1, i=1,2,...,N
这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题(这个高数学过)，由于约束条件有$N$N个，所以下面要减掉$N$N个不等式条件
$L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2-\sum_{i=1}^N{\alpha _i\left( y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right)}$L(w,b,α)=21​∥w∥2−∑i=1N​αi​(yi​(w⋅xi​+b)−1)
其中， $\alpha _i\ge 0$αi​≥0为拉格朗日乘子，然后令$\theta \left( \boldsymbol{w} \right) =\underset{\alpha _{_i}\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)$θ(w)=αi​​≥0max​ L(w,b,α)
具体可以展开成：
$\theta \left( \boldsymbol{w} \right) =\begin{cases} \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2\ ,\boldsymbol{x}\in \text{可行区域}\\ +\infty \ \ \ \ \ ,\boldsymbol{x}\in \text{不可行区域}\\ \end{cases}$θ(w)={21​∥w∥2 ,x∈可行区域+∞     ,x∈不可行区域​
８．因此优化问题转换为：
$\underset{\boldsymbol{w,}b}{\min}\ \theta \left( \boldsymbol{w} \right) =\underset{\boldsymbol{w,}b}{\min}\underset{\alpha _i\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =p^*$w,bmin​ θ(w)=w,bmin​αi​≥0max​ L(w,b,α)=p∗
利用对偶特性，转换为
$\underset{\alpha _i\ge 0}{\max}\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =d^*$αi​≥0max​w,bmin​ L(w,b,α)=d∗
如果要让$p^*=d^*$p∗=d∗，需要满足一下条件：
①　优化问题是凸优化问题(满足，因为$\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2$21​∥w∥2)
②　满足KKT（Karush-Kuhn-Tucker）条件，需要满足一下三个条件：
$\alpha _i\ge 0\\ y_i\left( \boldsymbol{w}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1\ge 0\\ \alpha _i\left( y_i\left( \boldsymbol{w}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right) =0$αi​≥0yi​(wi​⋅xi​+b)−1≥0αi​(yi​(wi​⋅xi​+b)−1)=0
８．为了得到求解对偶问题的具体形式，令 对和 的偏导为0，这样就可以去求解最优的$w$w了，可得：
$\boldsymbol{w}=\sum_{i=1}^N{\alpha _iy_i\boldsymbol{x}_{\boldsymbol{i}}}$w=∑i=1N​αi​yi​xi​
$\sum_{i=1}^N{\alpha _iy_i}=0$∑i=1N​αi​yi​=0
可以明显看出，只要求出了最优的$\alpha _i$αi​就可以找到最优的$\boldsymbol{w}$w了
代入到拉格朗日等式$L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2-\sum_{i=1}^N{\alpha _i\left( y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right)}$L(w,b,α)=21​∥w∥2−∑i=1N​αi​(yi​(w⋅xi​+b)−1)中，消去$w$w和$b$b，得到：
$L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _iy_i\left( \left( \sum_{j=1}^N{\alpha _jy_j\boldsymbol{x}_{\boldsymbol{j}}} \right) \cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) +}\sum_{i=1}^N{\alpha _i}$L(w,b,α)=21​∑i=1N​∑j=1N​αi​αj​yi​yj​(xi​⋅xj​)−∑i=1N​αi​yi​((∑j=1N​αj​yj​xj​)⋅xi​+b)+∑i=1N​αi​
$\ \ \ \ \ \ \ \ \ \ \ =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i}$           =−21​∑i=1N​∑j=1N​αi​αj​yi​yj​(xi​⋅xj​)+∑i=1N​αi​
也就是：
$\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i}$w,bmin​ L(w,b,α)=−21​∑i=1N​∑j=1N​αi​αj​yi​yj​(xi​⋅xj​)+∑i=1N​αi​
因此，优化问题变为：
$\underset{\boldsymbol{\alpha }}{\max}\ -\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i}$αmax​ −21​∑i=1N​∑j=1N​αi​αj​yi​yj​(xi​⋅xj​)+∑i=1N​αi​
$s.t.\ \ \ \ \sum_{i=1}^N{\alpha _iy_i}=0$s.t.    ∑i=1N​αi​yi​=0
$\ \ \ \ \ \ \ \alpha _i\ge 0,\ i=1,2,...,N$       αi​≥0, i=1,2,...,N
等效为：
$\underset{\boldsymbol{\alpha }}{\min}\ \frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _i}$αmin​ 21​∑i=1N​∑j=1N​αi​αj​yi​yj​(xi​⋅xj​)−∑i=1N​αi​
９．在 $\boldsymbol{\alpha }^*$α∗中，至少存在一个 $\alpha _{j}^{*}>0$αj∗​>0（反证法可以证明，若全为0，则$\boldsymbol{w}=0$w=0，矛盾，因为无法构造出分类线了），对此$j$j有：
$y_j\left( \boldsymbol{w}^*\cdot \boldsymbol{x}_{\boldsymbol{j}}+b^* \right) -1=0$yj​(w∗⋅xj​+b∗)−1=0
于是可以得到：
$\boldsymbol{w}^*=\sum_{i=1}^N{\alpha _{i}^{*}y_i\boldsymbol{x}_i}$w∗=∑i=1N​αi∗​yi​xi​
$b^*=y_j-\sum_{i=1}^N{\alpha _{i}^{*}y_i\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}$b∗=yj​−∑i=1N​αi∗​yi​(xi​⋅xj​)
１０．到此，SVM的数学推导就完成了，总结一下，对于任意$\left( \boldsymbol{x}_{\boldsymbol{i}},y_i \right)$(xi​,yi​) ，总有$\alpha _i=0$αi​=0或者$y_{j}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{j}+b\right)=1$yj​(w⋅xj​+b)=1。若$\alpha _i=0$αi​=0，则该样本不会在最后求解模型参数的式子中出现。若 $\alpha _i>0$αi​>0，则必有$y_j\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{j}}+b \right) =1$yj​(w⋅xj​+b)=1 ，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关

以上是对hard SVM的介绍，下面介绍soft SVM
１．soft就是软间隔的意思，使用的原因是：我们最先假定数据是线性可分的，然而实际上总会有孤立点存在，那么模型如果完全按照上面hard SVM操作，那这些孤立点怎么办呢？这时就需要soft间隔了
２．加入松弛变量后，原来的优化目标变为了：
$\underset{\boldsymbol{w,}b,\xi _i}{\min}\ \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2+C\sum_{i=1}^m{\xi _i}$w,b,ξi​min​ 21​∥w∥2+C∑i=1m​ξi​
$s.t.\ \ y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1-\xi _i$s.t.  yi​(w⋅xi​+b)≥1−ξi​
$\ \ \ \ \ \xi _i\ge 0\ ,\ i=1,2,...,N$     ξi​≥0 , i=1,2,...,N
其中 $\xi _i$ξi​ 为“松弛变量”，$\xi _i=\max \left( 0,1-y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \right)$ξi​=max(0,1−yi​(w⋅xi​+b))，即一个hinge损失函数。每一个样本都有一个对应的松弛变量，表征该样本不满足约束的程度。 $C>0$C>0称为惩罚参数， $C$C值越大，对分类的惩罚越大。

核SVM
１．加核函数思路与KPCA一致，具体可以参考我的另一篇博客
２．这里我只说明一下加核的地方：
$\underset{\boldsymbol{\alpha }}{\min}\ \frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_jK\left( \boldsymbol{x}_{\boldsymbol{i}},\boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _i}$αmin​ 21​∑i=1N​∑j=1N​αi​αj​yi​yj​K(xi​,xj​)−∑i=1N​αi​