17. 机器学习——SVM

机器学习面试题汇总与解析——SVM

本章讲解知识点

1. 什么是 SVM
1. SVM 的基本原理
1. 线性不可分 SVM
1. 非线性 SVM
1. SVM 优缺点

本专栏适合于Python已经入门的学生或人士，有一定的编程基础。
本专栏适合于算法工程师、机器学习、图像处理求职的学生或人士。
本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵
如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。
相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。
关于机器学习算法书籍，我强烈推荐一本《百面机器学习算法工程师带你面试》，这个就很类似面经，还有讲解，写得比较好。
关于深度学习算法书籍，我强烈推荐一本《解析神经网络——深度学习实践手册》，简称 CNN book，通俗易懂。
B站机器学习视频：https://space.bilibili.com/10781175/channel/detail?cid=133301

1. 什么是 SVM

在深度神经网络 (Deep Neural Network, DNN) 大热之前, 在机器学习里有个明星算法——支持向量机(Support Vector Machine, SVM)。它是昔日的明星，虽然现在没有DNN风光，但它依然是机器学习领域内耀眼的存在，这当然取决于其强大的学习能力。

SVM是一种常用且强大的机器学习算法，它在解决分类和回归问题中具有广泛的应用。它的优雅和高效使得它成为机器学习领域的重要工具之一。

SVM 的独特之处在于它能够通过在特征空间中寻找最优超平面来进行分类。这意味着 SVM 不仅仅是简单地根据数据的特征进行判断，而是通过将数据映射到高维空间中，并找到最能区分不同类别的超平面来进行分类。这种特性使得 SVM 在处理复杂问题和非线性数据时表现出色。

除了分类问题，SVM 还可以用于回归问题。通过引入核函数，SVM 可以将回归问题转化为寻找最优超平面的问题，从而能够有效地进行回归分析。这使得 SVM 成为一个多功能的算法，适用于各种类型的机器学习任务。

2. SVM 的基本原理

2.1 基本原理和思想

比如有两种类别的数据，class1 与 class2，要把这两类分开，人类一看就知道在这两类别之间画条直线即可，比如图上的绿色虚线和黄色实线，正好都可以把两类数据完美的分开。但计算机可不知道如何，而 SVM 的作用就是告诉计算机，如何找到这样一条线，并且找到“某种意义”上最好的一条线。比如图中，我们人眼凭直觉，黄色实线比绿色虚线更好，但是为什么更好呢？等后面原理一讲就清楚了。

这也就是 SVM 的基本思想：找到这样一条“线”（在二维数据上，恰如图上展示，为一条线；如果是三维的，就成为平面了，如果更高维则称之为“超平面”（hyperplane），使得数据可以区分。

那“支持向量”是如何来的呢? 这就涉及到 SVM 是如何找到这样的“最好的”超平面的。

2.2 如何找到“最好的”超平面

再看第一张图, 很容易就知道，想要区分两类数据，这样的线可有无数条，只要位于两类数据之间即可。

然而，我们的目的（或者说机器学习的目的）不是或者说不只是为了区分现有的两类数据，我们真正想要达到的目的是：当模型在现有数据训练完成后，将其应用到新的（同种）数据时，我们仍然可以很好的区分两类数据,达到预期的分类效果。说得专业一点，即 泛化（generalization）能力。

当有了泛化要求后，自然地考虑到，在这无数条可区他两类数据的线中，并不是都合适的，而且有理由相信，从泛化的角度讲，肯定存在一条线是这无数条线中泛化能力最好。SVM 要找的就是这条线。

那如何来量化泛化能力呢? 再来看下这张图:

绿色虚线和黄色实线都可以区分两类数据，从泛化的角度讲，哪个更好呢? 你会发现绿色虚线距离数据更近些（红圈圈出的数据）。这也意味着，如果新数据（或者称为测试数据）在红圈部位稍微有一点偏差，就会越过虚线，从而导致虚线的分类准确度下降甚至失败。

相较之下，黄色实线距离数据的位置较远，新数据的到来时，实线对数据的波动的容忍度就大些，即实线的泛化能力更强些。

这样我们知道了模型的泛化能力可以用与数据间的距离来量化。距离越远，泛化能力越强，距离最大的，泛化能力也是最强的。因此要找到泛化能力最强的，等价于找到与数据距离最大的超平面。

要衡量一条直线与数据间的距离，我们会下意识地关注离直线最近的数据点与直线的距离，而其他较远的点，没有过多关注，甚至下意识的忽略了，这是完全正确的，也就是说，决定超平面与数据距离的就是与超平面距离最近的数据，换句话说，影响模型泛化能力的，就是这些距离最近的点。

换种角度，找离最近的点距离最大的超平面，可以转化为找到边缘间隔（实线两边虚线间的距离）最大的超平面，如果找到最大间隔，那间隔正中间的位置就是我们梦寐以求的分隔超平面。

我们会发现分隔边缘正好是经过最近数据点的超平面。反过来说（一种比喻），最近数据点就是支撑点一样，支撑（或支持）着分隔边缘。而此类数据点（向量）正是决定模型（或者说分隔超平面）的关键所在。这就是 SVM 为什么用支持向量命名的原因。

因此我们的目标就是最大化两个黄色虚线超平面。

2.3 公式推导

其实有了目标，我们接下来的推导就很容易了。

因此，先描述下超平面，在空间中，超平面可表示如下：

w^Tx+b=0 \\ \tag{1}

其中三个元素均为向量，可将超平面简记为 $(w, b)$ 。那么两条边界线定义为： $w^{T} x + b = y$ 。

则样本空间中的数据点到此超平面的距离就可表示为（点到直线距离公式，高中就学过）：

r=\frac {|w^Tx+b|}{||w||} \\ \tag{2}

由中学知识我们就可知道，在超平面上的点，会满足(1)式，而在超平面之上的点，则会使 $w x + b > 0$ （比如上图中紫色方点在超平面之上）；在超平面之下的点，会使 $w x + b < 0$ （蓝色三角点在超平面之下）。那不妨设：

\begin{cases}y=1,\quad \quad wx+b > 0; \\ y=-1, \quad \quad wx+b< 0 \\ \end{cases} \\ \tag{3}

其中 $y$ 表示类别，则(2)式可改写为（这里解释下为什么要改写，因为分段函数分 $y = 1$ 和 $y = - 1$ 两种情况，要是我们求目标函数还要分段来求，那也太麻烦了，因此我们改写为 $y (w^{T} x + b)$ 就整合为一个表达式了）：

r=\frac {y(w^Tx+b)}{||w||} \\ s.t. \quad y(w^Tx+b) \geq 1 \tag{4}

通过(4)式，我们就可将超平面定位于两类之间。如前所述，衡量其泛化能力，通过其与数据样本空间的距离，而距离的衡量则与支持向量有关了，超平面与支持向量的距离（先找和超平面距离最近的支持向量，即数据点）：

\hat{r}=\min_x r\\ \tag{5}

我们知道满足(4)式的超平面的数量是无数的，哪一个是最优的呢? 当然是泛化能力最强的了，即：

L=\max_{w,b} \hat{r}=\max_{w,b} \min_x \frac {y(w^Tx+b)}{||w||}\\ \\ s.t. \quad y(w^Tx+b) \geq 1 \tag{6}

上面的推导是最直接的形式，然后接下来放缩变量，简化公式，令 $y (w^{T} x + b) = 2$ ， $y (w^{T} x + b)$ 就是函数间隔，可以任意放缩。但是呢不好理解。所以接下来我们转换一下思维，来理解为什么可以令 $y (w^{T} x + b) = 2$ 。

为了简化问题，两个黄色虚线超平面分别定义为： $w^{T} x + b = 1$ 和 $w^{T} x + b = - 1$ （直线可以随意放缩）。

我们转换一下目标，我们最大化两个黄色虚线超平面之间的距离，其实就是我们的目标，则两边界线之间的距离可以表示为（两平面之间的距离，高中知识）： $r=\frac{2}{||w||}$ ，即：

L=\max_{w,b} \frac{2}{||w||}=\min_{w,b} \frac{1}{2}||w||^2\\ \tag{7}

于是我们的目标就是最大化 $r=\frac{2}{||w||}$ ，也等价于最小化 $r=\frac{1}{2}{||w||^2}$ （对偶问题），约束条件为 $y(w^Tx+b) \geq 1$ 。这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。这就是拉格朗日乘子法的作用，将有约束的问题变为无约束的对偶问题，说到底就是为了简化运算。

构造拉格朗日函数：

L(w,b,\alpha)=\frac{1}{2}{||w||^2}+\sum_{i=1}^N \alpha_i(1-y_i(wx_i+b)) \tag{8}

其中 $1\leq i \leq n,\alpha \geq 0$ ，对 $w, b$ 求偏导：

w=\sum_{i=1}^n \alpha_i y_i x_i \\ 0=\sum_{i=1}^n \alpha_i y_i \tag{9}

求得 $b$ ：

b=y_i - \sum_{i=1}^n \alpha_i y_i (x_i x_j) \\ \tag{10}

代入上式，得到对偶问题：

\max_{\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 (x_i^T x_j) \\ s.t. \sum_{i=1}^n \alpha_i y_i =0, \\ \alpha_i \geq 0,i=1,2,...,n. \tag{11}

现在我们的优化问题变成了如上的形式。对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。这里暂时不展开关于使用SMO算法求解以上优化问题的细节。

SMO算法的基本思想是每次选择两个变量，通过优化这两个变量来更新模型的参数。具体步骤如下：

初始化参数：选择初始的模型参数和容忍误差的阈值。
选择两个变量：从训练样本中选择两个变量作为优化目标。选择这两个变量的方式可以采用不同的策略，例如启发式方法或随机选择。
优化目标变量：固定其他变量，通过解析求解或迭代优化的方式来更新这两个变量，以使目标函数达到最优。
更新模型参数：根据更新后的优化目标变量，更新模型的参数。
检查终止条件：检查优化过程是否满足终止条件，例如达到最大迭代次数或误差收敛等。如果不满足条件，返回第2步；否则，结束优化过程。

SMO算法通过不断选择两个变量进行优化，逐步调整模型的参数，直到达到最优解。相比于其他优化算法，SMO算法的特点是每次只更新两个变量，避免了全局优化的复杂性，从而加速了优化过程。

我们通过这个优化算法能得到 $\alpha_i$ ，再根据 $\alpha_i$ 求得 $w$ 和 $b$ ，进而求得我们最初的目的：找到超平面，即”决策平面”。

得到 SVM 基本型：

f(x)=\sum_{i=1}^n \alpha_i y_i x_i^T x +b \tag{12}

对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

2.4 SVM 的损失函数

合页损失函数（Hinge Loss）：常用于支持向量机（SVM）等算法中，用于二分类问题。它基于间隔的概念，鼓励模型将正确类别的预测值与错误类别的预测值之间的间隔最大化。具体公式如下：

L(y,ŷ)=max(0, \quad 1-y \cdot ŷ) \\

SVM 就是使用的合页损失，还加上了正则项。公式意义是，当样本被正确分类且函数间隔大于 1 时，合页损失是 0，否则损失是 $1-y \cdot ŷ$ 。

3. 线性不可分 SVM

上面展示的是最理想的状态，即两类数据泾渭分明，生产实践中可没有那么幸运，数据往不是一条线就能分开的，比如下面的图：

在两边缘之间还有数据点散落，如果我们一定要找一条区分两种类别的线似不可能了，而且也完全没必要。因为就算找到，那这条线也一定会距离数据很近，也就是说泛化能力一定很弱（过拟合 Overfitting）。莫不如在训练时，允许超平面有一定的错误率，即允许少量数据点跑到两边缘间隔之间。这样妥协的好处就是我们还会找到边缘间隔相对较大的超平面，因此在测试数据上会有更好的表现。我们把这样的间隔称为 soft margin。

soft margin 也就意味着：

y_i(w^Tx_i+b) \geq 1-\xi_i, \quad \xi_i \geq 0 \tag{.}

优化函数也相应的变成：

\min_{w,b,\xi_i} \frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i \\ \\ s.t. \quad y_i(w^Tx_i+b) \geq 1-\xi_i \\ \xi_i \geq 0, \quad i=1,2,...N \tag{.}

$\xi_i$ 称之为松弛变量（slack value）， $\xi_i = \max(0,1-y_i(w^Tx_i+b))$ ，即一个hinge损失函数。每一个样本都有一个对应的松弛变量，表征该样本不满足约束的程度。 $C > 0$ 称为惩罚参数， $C$ 越大，对分类的惩罚越大。跟线性可分求解的思路一致，同样这里先用拉格朗日乘子法得到拉格朗日函数，再求其对偶问题。

解法如上：

L(w,b,\alpha,\xi_i,\mu)=\frac{1}{2}{||w||^2}+ C\sum_{ji=1}^m \xi_i+\sum_{i=1}^N \alpha_i(1-\xi_i-y_i(wx_i+b))+\mu_i\xi_i \tag{.}

其中 $1\leq i \leq n,\alpha \geq 0$ ，对 $w,b,\xi_i$ 求偏导：

w=\sum_{i=1}^n \alpha_i y_i x_i \\ 0=\sum_{i=1}^n \alpha_i y_i \\ C=\alpha_i+\mu_i \tag{.}

代入上式，得到对偶问题：

\max_{\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 (x_i^T x_j) \\ s.t. \sum_{i=1}^n \alpha_i y_i =0, \\ C \geq \alpha_i \geq 0,i=1,2,...,n. \tag{.}