[数据结构与算法]机器学习：支持向量机（supported vector machine）基本介绍及公式推导

1.SVM基本介绍

1.1 SVM算法定义

??SVM全称是supported vector machine（支持向量机），即寻找到一个超平面使样本分成两类，并且间隔最大。

??SVM能够执行线性和非线性分类，回归，甚至是异常值监测任务。特别适用于中小型复杂数据集的分类。

1.2 SVM和逻辑回归的区别

1. 逻辑回归和SVM都是寻找一条分类直线，目标是把这两个类别分开
2. 逻辑回归的最终判断标准是：准确率，而SVM最终的判断结果是：准确率+最大间隔
3. 逻辑回归的分类直线可能有多条，而SVM的分类直线只有一条。

单纯考虑准确率和考虑最大间隔哪个泛化性能更好一点：

1. 准确率只考虑了在训练集上的预测能力
2. 准确率+最大间隔即考虑了预测能力，又考虑了模型对未知样本的泛化能力。

1.3 软间隔和硬间隔

硬间隔：指让所有样本都不在最大间隔之间，并且位于分类正确的一边。如果出现异常值或者样本不能线性分割，此时硬间隔无法实现。

软间隔：指容忍一部分样本在最大间隔之内，甚至在错误的一边。相对来说，软间隔可以应用在一些线性不可分的场景中。因此，软间隔可能在训练集表现不是很好，但是在测试集上的泛化性能可能要比硬间隔好。

1.4 惩罚参数C

??在硬间隔的情况下，我们只考虑如何使间隔最大。在软间隔的情况下，我们既要考虑间隔最大化，又要考虑间隔违例样本带来的损失。

??一般间隔违例样本带来的损失为：该点到分类直线之间的距离，C值用于惩罚间隔违例样本带来的损失。

??C值越大，说明间隔违例样本带来的损失越大，就要减少这些样本带来的损失，所以间隔就要越小。

??C值越小，间隔违例样本带来的损失就越小，可以适当增大间隔，以提高模型的泛化性能。

??C值可以用来平衡间隔违例样本损失、最大间隔。当对违反限制间隔的样本点的容忍度很低时，可增大C值，反之就减小C值。

2.SVM算法推导的目标函数

SVM求解目标：将所有样本分类正确的基础上，找出最大间隔。
1.最大间隔距离表示公式：
$$\frac{2}{\Vert \mathbf{w}\Vert }$$

直线方程为：y = w₁x₁ + w₂x₂ + b = 0，平面上任意一点（x_i，x_j）到该直线的距离计算公式为：

$$d=\frac{\left|w_1{x}_i+w_2{x}_j+b\right|}{\sqrt{w_1^2+w_2^2}}$$
分母可以用范数的形式表示：||w||

2.训练样本能够正确分类：
$$\{\begin{array}{ll}{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b?+1,& y_i=+1\\ {\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b??1,& y_i=?1\end{array}$$

我们希望所有样本分类正确的情况下，实现最大间隔。因此，目标函数可以转换为：
$$\begin{array}{l}{\max }_{w,b}=\frac{2}{\Vert w\Vert }\\ \\ \text{?s.t.?}{y}_i\left(w^T{x}_i+b\right)\ge 1,i=1,2,?,m\end{array}$$
将最大化问题转化为最小化问题：
$$\begin{array}{l}{\min }_{w,b}=\frac{1}{2}\Vert w{\Vert }^2\\ \\ \text{?s.t.?}{y}_i\left(w^T{x}_i+b\right)\ge 1,i=1,2,?,m\end{array}$$

• 最大化转换为最小化，加上平方是为了去除二范数的根号，不影响目标优化。1/2是为了求导时候，去掉系数。通过问题转换，让问题向最简单的方向发展。

3.目标函数推导过程

3.1 约束条件优化问题转换

目标函数是一个带有约束条件的优化问题，不容易求解，所以使用拉格朗日乘子法将其转换为多元极值问题，转换构成如下：
$$h(x)=f(x)+\alpha g(x)$$
f(x)是原问题，g(x)是原问题的约束条件。因此，约束条件函数可以转换为：

$$\begin{gathered} y_i(w^T{x}_i+b)\ge 1,i=1,2,?,m \\ \sum _{i=1}^n(1?y_i(w^T??(x_i)+b))\le 0 \end{gathered}$$
目标函数可以转换为：
$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2?\sum _{i=1}^n{\alpha }_i(y_i(w^T??(x_i)+b)?1)$$
此时问题转化为满足所有样本都能正确分类的情况下，求解极小极大值问题：
$$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )$$

• 整个式子求极小值，后边式子求极大值

3.2 对偶问题转换

1.对偶问题转换

对w求偏导，并令其等于0:

$$\begin{gathered} L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2?\sum _{i=1}^n{\alpha }_i(y_i(w^T??(x_i)+b)?1) \\ L(w,b,\alpha )=\frac{1}{2}||w|{|}^2?\sum _{i=1}^n({\alpha }_i{y}_i{w}^T\phi \left(x_i\right)+{\alpha }_i{y}_{i}b?{\alpha }_i)=0 \\ \frac{?L}{?w}=w?\sum _{i=1}^n{\alpha }_i{y}_i\phi (x_i)=0 \end{gathered}$$
得到：
$$w=\sum _{i=1}^n{\alpha }_i{y}_i\phi (x_i)$$
对b求偏导，并令其等于0：
$$\begin{gathered} L(w,b,\alpha )=\frac{1}{2}||w|{|}^2?\sum _{i=1}^n({\alpha }_i{y}_i{w}^T\phi \left(x_i\right)+{\alpha }_i{y}_{i}b?{\alpha }_i)=0 \\ \frac{?L}{?b}=\sum _{i=1}^n{\alpha }_i{y}_i=0 \end{gathered}$$
将对w、b求偏导的结果代入原拉格朗日公式中：
$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2?\sum _{i=1}^n{\alpha }_i(y_i(w^T??(x_i)+b)?1)$$
去括号得：
$$L(w,b,\alpha )=\frac{1}{2}{w}^{T}w?\sum _{i=1}^n{\alpha }_i{y}_i{w}^T?(x_i)?b?\sum _{i=1}^n{\alpha }_i{y}_i+\sum _{i=1}^n{\alpha }_i$$
代入w、b得：
$$L(w,b,\alpha )=\frac{1}{2}{w}^T\sum _{i=1}^n{\alpha }_i{y}_i\phi (x_i)?w^T\sum _{i=1}^n{\alpha }_i{y}_i\phi (x_i)+\sum _{i=1}^n{\alpha }_i$$
化简得：
$$L(w,b,\alpha )=\sum _{i=1}^n{\alpha }_i?\frac{1}{2}(\sum _{i=1}^n{\alpha }_i{y}_i\phi (x_i){)}^T?\sum _{i=1}^n{\alpha }_i{y}_i\phi (x_i)$$
最终得：
$$L(w,b,\alpha )=\sum _{i=1}^n{\alpha }_i?\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{?}^T(x_i)?(x_j)$$
此时，求解当 α 是什么值时，L会变得很大，当求出 α 值，再求解 w, b 值。此时，就变成了极大极小值问题。

3.3 确定超平面

1、求解当α为什么值时，公式的值最大：
$$\begin{gathered} {\alpha }^{?}=\underset{\alpha }{\mathrm{argmax}}(\sum _{i=1}^n{\alpha }_i?\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{?}^T(x_i)?(x_j)) \\ s.t.\sum _{i=1}^n{\alpha }_i{y}_i=0 \\ {\alpha }_i\ge 0,i=1,2,3?,n \end{gathered}$$

2、将上面的问题转换为极小值问题：
$$\underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{?}^T(x_i)?(x_j)?\sum _{i=1}^n{\alpha }_i$$
且满足以下条件：
$$\begin{gathered} \sum _{i=1}^n{\alpha }_i{y}_i=0 \\ {\alpha }_i\ge 0,i=1,2,3?,n \end{gathered}$$
将训练样本代入上面公式，求解出α值。然后，将α值代入公式计算w、b的值
$$\begin{gathered} w^{?}=\sum _{i=1}^n{\alpha }_i^{?}{y}_i\phi (x_i) \\ {b}^{?}=y_i?\sum _{i=1}^n{\alpha }^{?}{y}_i(?(x_i)??(x_j)) \end{gathered}$$
最后求的分离超平面为：
$$w^{?}?(x)+b^{?}=0$$
求的分类决策函数：
$$f(x)=\mathrm{sign}(w^{?}?(x)+b^{?})$$

4.案例代入

正例点x1=(3,3),x2=(4,3)，负例点x3=(1,1)，求线性可分支持向量机。
$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{?}^T(x_i)?(x_j)?\sum _{i=1}^n{\alpha }_i \\ s.t.\sum _{i=1}^n{\alpha }_i{y}_i=0 \\ {\alpha }_i\ge 0,i=1,2,3?,n \end{gathered}$$
将3个样本代入上述公式，得到一个关于α的函数：
$$\frac{1}{2}(18{\alpha }_1^2+25{\alpha }_2^2+2{\alpha }_3^2+42{\alpha }_1{\alpha }_2?12{\alpha }_1{\alpha }_3?14{\alpha }_2{\alpha }_3)?{\alpha }_1?{\alpha }_2?{\alpha }_3??(4.1)$$
由于：
$$\sum _{i=1}^n{\alpha }_i{y}_i=0=>{\alpha }_1{y}_1+{\alpha }_2{y}_2+{\alpha }_3{y}_3=0?????(4.2)$$
可得：
$$\begin{gathered} {\alpha }_1+{\alpha }_2?{\alpha }_3=0??????(4.3) \\ {\alpha }_1+{\alpha }_2={\alpha }_3????????(4.4) \end{gathered}$$
将（4.4）式子代入（4.1）式子中可得：
$$4{\alpha }_1^2+\frac{13}{2}{\alpha }_2^2+10{\alpha }_1{\alpha }_2?2{\alpha }_1?2{\alpha }_2??????(4.5)$$
对 α₁、α₂ 求偏导，并令其等于 0，可得：
$$\{\begin{array}{l}\frac{?s(\alpha 1,\alpha 2)}{?\alpha 1}=8\alpha 1+10{\alpha }_2?2=0\\ \frac{?s(\alpha 1,\alpha 2)}{?\alpha 2}=13\alpha 2+10\alpha 1?2=0\end{array}?\{\begin{array}{l}\alpha 1=1.5\\ \alpha 2=?1\end{array}$$
由于限制条件中 α 值必须大于 0，故而上面求出的结果不是最终结果。

1. 当α₁=0时，对α₂求偏导得 2/13，α₃=2/13
2. 当α₂=0时，对α₁求偏导得 1/4，α₃=1/4

现有两组结果，我们需要找出哪组结果使得结果最小，将每组结果代入（4.5）式子中，得：

1. 第一组结果是：-0.1538
2. 第二组结果是：-0.25

因此，第二组结果最小，所以α₁=1/4，α₂=0，α₃=1/4

接下来，根据 α 和样本计算 w 的值：

1. 正例 1： x1=(3,3)，α₁ = 1/4

2. 正例 1：x2=(4,3)，α₂ = 0

3. 负例 -1： x3=(1,1)，α₃ = 1/4

$$w=\sum _{i=1}^n{\alpha }_i{y}_i\Phi \left(x_n\right)$$
代入得：
$$w=\frac{1}{4}?1?(3,3)+\frac{1}{4}?(?1)?(1,1)=\left(\frac{1}{2},\frac{1}{2}\right)$$
由 f(x) = 0.5x₁ + 0.5x₂ + b，并将任意样本代入，可得 b 为：

1. 0.5*3 + 0.5*3 + b =1，得：b = -2
2. 0.5*1 + 0.5*1 + b =-1，得：b = -2

最终确定分类超平面为：
$$f(x)=\mathrm{sign}\left(0.5x_1+0.5x_2?2\right)$$