【机器学习】05-SVM学习笔记

相关词汇

最大间隔
核函数（高斯核，线性核

写在前面的话

为什么我们要使用SVM，SVM有什么作用？SVM简单来讲，就是降维。如果你说出这句话，别人给你一个白眼，问你什么是降维，降维的本质是什么？这些答案我们需要一个一个去回答

SVM算法原理

SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。如下图所示， $y=wx+b=0$y=wx+b=0即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。

在推导之前，先给出一些定义。假设给定一个特征空间上的训练数据集
$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$T=(x1​,y1​),(x2​,y2​),...,(xN​,yN​)
其中，$x_i \in R^n,y_i\in{+1,-1},i=1,2,...,N,x_i为第i个特征向量，y_i为类标记$xi​∈Rn,yi​∈+1,−1,i=1,2,...,N,xi​为第i个特征向量，yi​为类标记，当它等于+1时为正例；为-1时为负例。再假设训练数据集是线性可分的。
几何间隔：对于给定的数据集 $y=wx+b=0$y=wx+b=0 和超平面(x_i,y_i)，定义超平面关于样本点 [公式] 的几何间隔为
$\gamma_i\ = y_i(\frac{W}{||w||}·x_i+\frac{b}{||w||})$γi​ =yi​(∣∣w∣∣W​⋅xi​+∣∣w∣∣b​)
超平面关于所有样本点的几何间隔的最小值为
$\gamma\ =min_{i=1,2,...,N}\gamma_i$γ =mini=1,2,...,N​γi​
实际上这个距离就是我们所谓的支持向量到超平面的距离。
根据以上定义，SVM模型的求解最大分割超平面问题可以表示为以下约束最优化
$max_{w,b}\gamma$maxw,b​γ
$s.t\ y_i(\frac{W}{||w||}·x_i+\frac{b}{||w||})\ge \gamma,i=1,2,...,N$s.t yi​(∣∣w∣∣W​⋅xi​+∣∣w∣∣b​)≥γ,i=1,2,...,N
将约束条件两边同时除以$\gamma$γ,得到
$y_i(\frac{W}{||w||\gamma}·x_i+\frac{b}{||w||\gamma})\ge 1$yi​(∣∣w∣∣γW​⋅xi​+∣∣w∣∣γb​)≥1
因为$||w||,\gamma$∣∣w∣∣,γ都是标量，所以为了表达式简洁起见，令
$\begin{array}{lcr} w\ = \frac{w}{||w||\gamma}\\ b\ = \frac{b}{||w||\gamma} \end{array}$w =∣∣w∣∣γw​b =∣∣w∣∣γb​​
得到
$y_i(w·x_i+b)\ge 1,i=1,2,...,N$yi​(w⋅xi​+b)≥1,i=1,2,...,N
又因为最大化$\gamma$γ,等价于最大化$\frac{1}{||w||}$∣∣w∣∣1​,也就是等价于最小化$\frac{1}{2}||w||^2$21​∣∣w∣∣2($\frac{1}{2}$21​是为了后面求导以后形式简洁，不影响结果），因此SVM模型的求解最大分割超平面问题又可以表示为以下约束最优化问题)
$\begin{array}{lcr} min_{w,b}\ \frac{1}{2}||w||^2\\ s.t\ y_i(w·x_i+b)\ge 1,i=1,2...,N \end{array}$minw,b​ 21​∣∣w∣∣2s.t yi​(w⋅xi​+b)≥1,i=1,2...,N​
这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。
首先，我们将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数
$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}{\alpha_i(y_i(w·x_i+b)-1)}$L(w,b,α)=21​∣∣w∣∣2−∑i=1​αi​(yi​(w⋅xi​+b)−1)
其中$\alpha_i$αi​为拉格朗日乘子，且$\alpha_i \ge 0$αi​≥0。现在我们令
$\theta(w)=max_{\alpha_i\ge 0}L(w,b,\alpha)$θ(w)=maxαi​≥0​L(w,b,α)
当样本点不满足约束条件时，即可在可行解区域外：
$y_i(w·x_i+b)＜ 1$yi​(w⋅xi​+b)＜1
此时，将$\alpha$α设置为无穷大，则$\theta(w)$θ(w)也无穷大。
当满足约束条件时，即在可行解区域内：
$y_i(w·x_i+b)＞ 1$yi​(w⋅xi​+b)＞1
此时，$\theta(w)$θ(w)为原函数本身。于是，将两种情况合并起来就可以得到我们新的目标函数
$\theta(w)=\left\{ \begin{aligned} \frac{1}{2}||w||^2,x\in可行区域\\ +∞,x\in不可行区域\\ \end{aligned} \right.$θ(w)=⎩⎨⎧​21​∣∣w∣∣2,x∈可行区域+∞,x∈不可行区域​
于是原约束问题就等价于
$min_{w,b}\theta(w)\ =min_{w,b}max_{\alpha_i}L(w,b,\alpha)\ =p^*$minw,b​θ(w) =minw,b​maxαi​​L(w,b,α) =p∗
看一下我们的新目标函数，先求最大值，再求最小值。这样的话，我们首先就要面对带有需要求解的参数 $w$w和 $b$b的方程，而 $\alpha_i$αi​又是不等式约束，这个求解过程不好做。所以，我们需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：
$max_{\alpha_i\ge 0}min_{w,b}L(w,b,\alpha)\ =d^*$maxαi​≥0​minw,b​L(w,b,α) =d∗
要有$p^*=d^*$p∗=d∗，需要满足两个条件：
1.优化问题时凸优化问题
2.满足KKT条件
首先，本优化问题显然是一个凸优化问题，所以条件一满足，而要满足条件二，即要求
$\left\{ \begin{aligned} \alpha\ge 0\\ y_i(w·x_i+b)\ge 0\\ \alpha_i(y_i(w·x_i+b)-1)\ =0 \end{aligned} \right.$⎩⎪⎨⎪⎧​α≥0yi​(w⋅xi​+b)≥0αi​(yi​(w⋅xi​+b)−1) =0​
为了得到求解对偶问题的具体形式，令$L(w,b,\alpha)$L(w,b,α)对$w$w和$b$b的偏导为0，可得
$\begin{array}{lcr} w=\sum_{i=1}^{N}\alpha_iy_ix_i\\\\ \sum_{i=1}^{N}\alpha_iy_i\ =0 \end{array}$w=∑i=1N​αi​yi​xi​∑i=1N​αi​yi​ =0​
将以上两个等式带入拉格朗日目标函数，消去 $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{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)$w,bmin​ L(w,b,α)对$\alpha$α的极大，即是对偶问题
$\begin{array}{lcr}max_{\alpha}-\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\\\\ s.t.\ \sum_{i=1}^{N}\alpha_iy_i\ =0\\\\ \alpha_i\ge 0,i=1,2,...,N \end{array}$maxα​−21​∑i=1N​∑i=1N​αi​αj​yi​yj​(xi​⋅xj​)+∑i=1N​αi​s.t. ∑i=1N​αi​yi​ =0αi​≥0,i=1,2,...,N​
把目标式子加一个符号，将求解极大转换为求解极小
$\begin{array}{lcr}max_{\alpha}-\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\\\ s.t.\ \sum_{i=1}^{N}\alpha_iy_i\ =0\\\\ \alpha_i\ge 0,i=1,2,...,N \end{array}$maxα​−21​∑i=1N​∑i=1N​αi​αj​yi​yj​(xi​⋅xj​)−∑i=1N​αi​s.t. ∑i=1N​αi​yi​ =0αi​≥0,i=1,2,...,N​
现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。这里暂时不展开关于使用SMO算法求解以上优化问题的细节，下一篇文章再加以详细推导。

我们通过这个优化算法能得到 $\alpha^*$α∗，再根据$\alpha^*$α∗，我们就可以求解出$w$w和$b$b，进而求得我们最初的目的：找到超平面，即”决策平面”。
前面的推导都是假设满足KKT条件下成立的，KKT条件如下
$\begin{cases} \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\\ \end{cases}$⎩⎪⎨⎪⎧​αi​≥0yi​(wi​⋅xi​+b)−1≥0αi​(yi​(wi​⋅xi​+b)−1)=0​
另外，根据前面的推导，还有下面两个式子成立
$\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^*$α∗中，至少存在一个$\alpha_j＞0$αj​＞0（反证法可以证明，若全为0，则$w=0$w=0，矛盾），对此$j$j有
$y_j(w^* \cdot x_j+b^*)-1\ =0$yj​(w∗⋅xj​+b∗)−1 =0
因此可以得到
$w^*\ =\sum_{i=1}^{N}{\alpha_i^*y_ix_i}$w∗ =∑i=1N​αi∗​yi​xi​
$b^*\ =y_j-\sum_{i=1}^{N}{\alpha_i^*y_i(x_i \cdot x_j)}$b∗ =yj​−∑i=1N​αi∗​yi​(xi​⋅xj​)
对于任意训练样本$(x_i,y_i)$(xi​,yi​)，总有$\alpha_i=0$αi​=0或者$y_i(w \cdot x_j+b)=1$yi​(w⋅xj​+b)=1。若$\alpha_i=0$αi​=0，则该样本不会在最后求解模型参数的式子中出现。若$\alpha_i＞0$αi​＞0，则必有$y_i(w \cdot x_j+b)=1$yi​(w⋅xj​+b)=1，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

到这里都是基于训练集数据线性可分的假设下进行的，但是实际情况下几乎不存在完全线性可分的数据，为了解决这个问题，引入了“软间隔”的概念，即允许某些点不满足约束
$y_i(w \cdot x_j+b)\ge1$yi​(w⋅xj​+b)≥1

采用hinge损失，将原优化问题改写为
$min_{w,b,\xi_i}{\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i}$minw,b,ξi​​21​∣∣w∣∣2+C∑i=1m​ξi​
$s.t.\ y_i(w \cdot x_i +b)\ge 1-\xi_i$s.t. yi​(w⋅xi​+b)≥1−ξi​
$\xi_i\ge0,i=1,2,...,N$ξi​≥0,i=1,2,...,N
其中$\xi_i$ξi​为"松弛变量"，$\xi_i=max(0,1-y_i(w \cdot x_i +b))$ξi​=max(0,1−yi​(w⋅xi​+b))即一个hinge损失函数。每一个样本都有一个对应的松弛变量，表征该样本不满足约束的程度。如果$C$C值越大，对分类的惩罚越大。跟线性可分求解的思路一致，同样这里先用拉格朗日乘子法得到拉格朗日函数，再求其对偶问题。
综合以上讨论，我们可以得到线性支持向量机学习算法如下：
输入：训练数据集$T=\left\{ \left( \boldsymbol{x}_1,y_1 \right) ,\left( \boldsymbol{x}_1,y_1 \right) ,...,\left( \boldsymbol{x}_N,y_N \right) \right\}$T={(x1​,y1​),(x1​,y1​),...,(xN​,yN​)}
其中，$x_i \in R^n$xi​∈Rn， $y_i\in \left\{ +1,-1 \right\} ,i=1,2,...N$yi​∈{+1,−1},i=1,2,...N；
输出: 分离超平面和分类决策函数
（1）选择惩罚参数$C>0$C>0，构造并求解凸二次规划问题
$\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​
$s.t.\ \ \ \ \sum_{i=1}^N{\alpha _iy_i}=0$s.t.    ∑i=1N​αi​yi​=0
$\ \ \ \ \ \ \ 0\le \alpha _i\le C,\ i=1,2,...,N$       0≤αi​≤C, i=1,2,...,N
得到最优解 $\boldsymbol{\alpha }^*=\left( \alpha _{1}^{*},\alpha _{2}^{*},...,\alpha _{N}^{*} \right) ^T$α∗=(α1∗​,α2∗​,...,αN∗​)T计算
$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​)
（3）求分离超平面
$\boldsymbol{w}^*\cdot \boldsymbol{x}+b^*=0$w∗⋅x+b∗=0
分类决策函数：
$f\left( \boldsymbol{x} \right) =sign\left( \boldsymbol{w}^*\cdot \boldsymbol{x}+b^* \right)$f(x)=sign(w∗⋅x+b∗)