作者：韩信子@ShowMeAI
教程地址：http://www.showmeai.tech/tutorials/34
本文地址：http://www.showmeai.tech/article-detail/196
申明：版权所有，转载请分割平台与作者并注明出处

引言

本篇咱们要解说的模型是赫赫有名的反对向量机SVM，这是已经在机器学习界有着近乎「垄断」位置的模型，影响力继续了好多年。直至今日，即便深度学习神经网络的影响力逐步加强，但SVM在中小型数据集上仍旧有着能够和神经网络抗衡的极好成果和模型鲁棒性。

反对向量机学习办法，针对不同的状况，有由简至繁的不同模型：

• 线性可分反对向量机（linear support vector machine in linearly separable case）：训练数据线性可分的状况下，通过硬距离最大化（hard margin maximization），学习一个线性的分类器，即线性可分反对向量机（亦称作硬距离反对向量机）。
• 线性反对向量机（linear support vector machine）：训练数据近似线性可分的状况下，通过软距离最大化（soft margin maximization），学习一个线性的分类器，称作线性反对向量机（又叫软距离反对向量机）。
• 非线性反对向量机（non-linear support vector machine）：训练数据线性不可分的状况下，通过应用核技巧（kernel trick）及软距离最大化，学习非线性分类器，称作非线性反对向量机。

反对向量机能够借助核技巧实现简单场景下的非线性分类，当输出空间为欧式空间或离散汇合、特色空间为希尔贝特空间时，核函数（kernel function）示意将输出从输出空间映射到特色空间失去的特征向量之间的内积。

通过应用核函数能够学习非线性反对向量机，等价于隐式地在高维的特色空间中学习线性反对向量机。这样的办法称为核技巧。

1.最大距离分类器

1）分类问题与线性模型

分类问题是监督学习的一个外围问题。在监督学习中，当输入变量取无限个离散值时，预测问题便成为分类问题。理论生存中，有很多问题的实质都是分类，如辨认某种模式：文本分类、分词、词性标注、图像内容辨认和指标检测等。

分类问题的数学了解是空间划分（或者寻找不同类别的决策边界），如下图所示是一个简略的线性分类器（这部分更具体的解说参考ShowMeAI文章 图解机器学习 | 机器学习基础知识 和 图解机器学习 | 逻辑回归算法详解）。

2）最大距离分类器

不同的模型在解决分类问题时，会有不同的解决形式，直观上看，咱们会应用不同的决策边界对样本进行划分。

如下图中「冰墩墩」与「雪容融」两类样本点，咱们对其进行分类，能够实现该分类工作的决策边界有无数个。而咱们这里介绍到的SVM模型，要求更高一些，它不仅仅心愿把两类样本点辨别开，还心愿找到鲁棒性最高、稳定性最好的决策边界（对应图中的彩色直线）。

这个决策边界与两侧「最近」的数据点有着「最大」的间隔，这意味着决策边界具备最强的容错性，不容易受到噪声数据的烦扰。直观的了解就是，如果决策边界抖动，最不容易「撞上」样本点或者进而导致误判。

2.反对向量机详解

1）线性可分SVM与硬距离最大化

咱们要找到把下图中红蓝两色的图标点离开的最优分界线。令红色的图标点 \(=+1\) ，蓝色的图标的点 \(=-1\) ，直线 \(f(x) = \boldsymbol{w}\cdot \boldsymbol{x} + b\) ，这里 \(w、x\) 是向量，其实公式等价于 \(f(x) = w_1x_1 + w_2x_2 +…+ w_nx_n + b\) 。

• 当向量 \(x\) 为二维向量时， \(f(x)\) 示意二维空间中的一条直线。
• 当向量 \(x\) 为三维向量时， \(f(x)\) 示意三维空间中的一个立体。
• 当向量 \(x\) 的 \(n\) 维向量（ \(fn>3\) ）时， \(f(x)\) 示意 \(n\) 维空间中的 \(n-1\) 维超平面。

当有一个新的点 \(x\) 须要预测属于哪个分类的时候，咱们用 \(sgn(f(x))\) 就能够预测了。 \(sgn\) 示意符号函数：

• 当 \(f(x)>0\) 的时候， \(sgn(f(x)) = +1\) 。
• 当 \(f(x) < 0\) 的时候 \(sgn(f(x)) = –1\) 。

回到重点，咱们怎样才能获得一个最优的划分直线 \(f(x)\) 呢？下图的直线示意几条可能的 \(f(x)\) ：

咱们心愿这条直线满足「最大距离」准则，也就是如下图的状态。图中位于红色和蓝色线上的图标就是所谓的反对向量（support vector）。

决策边界就是 \(f(x)\) ，红色和蓝色的线是反对向量（support vector）所在的面，红色、蓝色线之间的间隙就是咱们要最大化的分类间的间隙M（Margin Width）。

这里间接给出距离M的计算公式： \(M=\frac{2}{\left | w \right | }\) 。

SVM要求解可能正确划分训练数据集并且「几何距离」最大的拆散超平面。

如下图所示， \(\boldsymbol{w} \cdot \boldsymbol{x}+b=0\) 即为拆散超平面。对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），然而几何距离最大的拆散超平面却是惟一的。

咱们先做一些定义，假如给定一个特色空间上的训练数据集： \(T={(x_1, y_1),(x_2, y_2), \ldots,(x_N, y_N)}\) 。且训练数据集是线性可分的，其中：

• \(x_i \in \mathbb{R}^{n}\) ， \(y_{i} \in \left {+1,-1 \right }\) ， \(i=1,2, \ldots N,x_{i}\) 为第 \(i\) 个特征向量。
• \(y_{i}\) 为类标记，当它等于 \(+1\) 时为正例；为 \(-1\) 时为负例。

（1）几何距离

对于给定的数据集 \(T\) 和超平面 \(wx+b=0\) 。

• 定义超平面对于样本点 \((x_{i}, y_{i})\) 的几何距离为： \(\gamma_{i} = y_i(\frac{w}{\left | w \right | } \cdot x_i + \frac{b}{\left | w \right | })\)
• 超平面对于所有样本点的几何距离的最小值为： \(\gamma = \min _{i=1,2 \ldots, N} \gamma_{i}\) ，实际上这个间隔就是咱们所谓的「反对向量到超平面的间隔」。

① 依据以上定义，SVM模型的「求解最大宰割超平面问题」能够示意为以下束缚最优化问题：

$$\begin{aligned} & \max _{w,b} \gamma \\& s.t. \quad y_{i}(\frac{w}{\left \| w \right \|} \cdot x_i+\frac{b}{\left \| w \right \|}) \geq \gamma, i=1,2, \ldots, N\\\end{aligned}$$

• 下面公式中s.t是subject to的缩写，也就是限度条件的意思。

② 将约束条件两边同时除以 \(\gamma\) 失去：

$$y_{i}(\frac{w}{\left \| w \right \| \gamma} \cdot x_i+\frac{b}{\left \| w \right \|\gamma}) \geq 1$$

③ 因为 \(\left | w \right |\) 、 \(\gamma\) 都是标量，所以为了表达式简洁，令： \(w=\frac{w}{\left | w \right | \gamma}\) 、 \(b=\frac{b}{\left | w \right | \gamma}\) 失去：

$$y_i(w \cdot x_i+b) \geq 1, i=1,2, \ldots, N$$

④ 又因为最大化 \(\gamma\) ，等价于最大化 \(\frac{1}{\left | w \right |}\) ，也就等价于最小化 \(\frac{1}{2}\left | w \right |^{2}\) ，最终SVM模型的求解最大宰割超平面问题又能够示意为以下束缚最优化问题：

$$\begin{aligned} & \min _{w, b} \frac{1}{2}\left \| w \right \|^{2}\\& s.t. \quad y_{i}(w \cdot x_i+b) \geq 1, i=1,2, \ldots, N\end{aligned}$$

（2）对偶算法

求解线性可分反对向量机的最优化问题，咱们很多时候会将它转化为对偶问题（dual problem）来求解，也就是利用「拉格朗日对偶性」，通过求解「对偶问题（dual problem）」失去「原始问题（primal problem）」的最优解，即线性可分反对向量机的对偶算法（dual algorithm）。

这样做有一些长处：

• 对偶问题往往更容易求解。
• 引入天然核函数，进而能够推广到非线性分类问题。

① 咱们首先构建拉格朗日函数（Lagrange function）。为此，对每一个不等式束缚引进拉格朗日乘子（Lagrange multiplier） \(\alpha_i\geq 0,i=1,2,…,N\) ，定义拉格朗日函数：

$$\begin{aligned} L(w, b, \alpha)=&\frac{1}{2}w^Tw+\sum_{i=1}^{N}\alpha_i(1-y_i(w^T x_i + b)) \\ =& \frac{1}{2}w^Tw-\sum_{i=1}^{N}\alpha_i y_i(w^T x_i + b) +\sum_{i=1}^{N}\alpha_i \end{aligned}$$

依据拉格朗日对偶性，原始问题的对偶问题是极大极小问题： \(\max_{\alpha}\min_{w,b}L(w, b, \alpha)\) 。所以，为了失去对偶问题的解，须要先求 \(L(w, b, \alpha)\) 对 \(w、b\) 的极小值，再求对 \(\alpha \) 的极大值。

② 求 \(L(w, b, \alpha)\) 对 \(w、b\) 的极小值

将拉格朗日函数 \(L(w, b, \alpha)\) 别离对 \(w、b\) 求偏导，并令其值为0。

$$\frac{\partial L}{\partial w} = w – \sum_{i=1}^{N}\alpha_i y_i x_i =0 \Rightarrow w = \sum_{i=1}^{N}\alpha_i y_i x_i$$

$$\frac{\partial L}{b}=-\sum_{i=1}^{N}\alpha_iy_i=0 \Rightarrow \sum_{i=1}^{N}\alpha_iy_i=0$$

将上式代入拉格朗日函数，即得：

$$\begin{aligned} \min_{w,b} L(w, b,\alpha)=&\frac{1}{2} (\sum_{i=1}^{N}\alpha_i y_i x_i)^T \sum_{i=1}^{N}\alpha_i y_i x_i-\sum_{i=1}^{N}\alpha_i y_i((\sum_{i=1}^{N}\alpha_i y_i x_i)^T x_i + b) +\sum_{i=1}^{N}\alpha_i \\ =&\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i y_i\alpha_j y_jx_i^Tx_j-\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i y_i\alpha_j y_jx_j^Tx_i+\sum_{i=1}^{N}\alpha_i \\ =& -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i y_i\alpha_j y_jx_i^Tx_j+\sum_{i=1}^{N}\alpha_i \end{aligned}$$

③ 求 \(\min_{w,b}L(w, b,\alpha)\) 对 \(\alpha\) 的极大值，即对偶问题

$$\begin{aligned} & \max_{\alpha} -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i y_i\alpha_j y_jx_i^Tx_j+\sum_{i=1}^{N}\alpha_i \\& s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0 \\& \quad \quad \alpha_i \geq 0,i=1, 2…N \end{aligned}$$

将式中的指标函数由求极大转换成求极小，就失去上面与之等价的对偶最优化问题：

$$\begin{aligned} & \min_{\alpha} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i y_i\alpha_j y_jx_i^Tx_j-\sum_{i=1}^{N}\alpha_i \\ & s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0 \\ & \quad \quad \alpha_i \geq 0,i=1, 2…N \end{aligned}$$

④ 对线性可分训练数据集，假如对偶最优化问题对 \(\alpha\) 的解为 \( \alpha^* = (\alpha_1^*,\alpha_2^*,…,\alpha_N^*)^T\) ，能够由 \( \alpha^* \) 求得原始最优化问题的解 \(w^*、b^* \) 。

有上面的定理：设 \(\alpha^*=(\alpha_1^*,\alpha_2^*,…,\alpha_N^*)^T\) 是对偶最优化问题的解，则存在下标 \(j\) ，使得 \(\alpha_j^*>0\) ，并可按下式求得原始最优化问题的解 \(w^*,b^*\) ：

$$w^*=\sum_{i=1}^*{N} \alpha_i^*y_ix_i$$

$$b^*=y_j-\sum_{i=1}^*{N} \alpha_i^*y_i(x_i^*Tx_j)$$

证实：依据定理，KKT条件成立，即得：

$$\begin{aligned} & \frac{\partial L(w^*,b^*,\alpha ^*)}{\partial w} = w^*-\sum_{i=1}^{N}\alpha_i^* y_i x_i=0 \\ & \frac{\partial L(w^*,b^*,\alpha ^*)}{\partial b} = -\sum_{i=1}^{N}\alpha_i^*y_i=0 \\ & \frac{\partial L(w^*,b^*,\alpha ^*)}{\partial \alpha} = 0 \\ & \alpha_i(1-y_i(w^Tx_i+b)) =0 \\ & \alpha_i \geq 0 , \\ & i=1,2,…,N \\ & 1-y_i(w^Tx_i+b) \leq 0 , i=1,2,…,N \end{aligned}$$

由此得 \(w^*=\sum_{i=1}^{N} \alpha_i^*y_ix_i\)

其中至多有一个 \(\alpha_j^*>0\) （用反正法，假如 \(\alpha_j^*=0\) ，由式可知 \(w^*=0\) ，而 \(w^*=0\) 不是原始最优化问题的解，产生矛盾），由此对 \(j\) 有： \(y_j(w^*\cdot x_j+b^*) – 1 = 0\)

将式代入并留神到 \(y_j^2=1\) ，即得： \(b^* = y_j – w^*{}x_j = y_j – \sum_{i=1}^{N} \alpha_i^*y_i(x_ix_j) \)

⑤ 由此定理可知，拆散超平面能够写成

$$\sum_{i=1}^{N} \alpha_i^*y_i(x\cdot x_i) + b^* = 0$$

⑥ 分类决策函数能够写成

$$f(x) = sign(\sum_{i=1}^{N} \alpha_i^*y_i(x\cdot x_i) + b^*)$$

也就是说，这里的决策函数只依赖于输出 \(x\) 和训练样本输出的内积。上式亦称作线性可分SVM的对偶模式。

综上所述，对于给定得线性可分训练数据集，能够首先求对偶问题的解 \(\alpha^*\) ；再利用公式求得原始问题的解 \(w^*,b^*\) ；从而失去拆散超平面及分类决策函数。这种算法称为线性可分反对向量机的对偶学习算法，是线性可分反对向量机学习的根本算法。

2）线性SVM与软距离最大化

咱们后面提到的是线性可分的状况，但理论利用中齐全线性可分的状况太少见了。如下图就是一个典型的线性不可分的分类图（咱们没有方法找到一条直线，把空间划分为2个区域，一个区域只有黑点，一个区域只有白点）。

要对其进行切分，有2种计划：

计划1：用曲线去将其齐全离开，即非线性的决策边界，这会和之后谈到的核函数关联。

计划2：还是应用直线，不过不谋求齐全可分，会适当容纳一些分错的状况，在这个过程中咱们会在模型中退出惩办函数，尽量让分错的点不要太多太离谱。对分错点的惩办函数就是这个点到其正确地位的间隔，如下图所示：

图上黄色、蓝色的直线别离为反对向量所在的边界，彩色的线为决策函数，那些绿色的线示意分错的点到其相应的决策面的间隔，这样咱们能够在原函数下面加上一个惩办函数，并且带上其限度条件为：

$$\begin{aligned} & \min \frac{1}{2}|w|^{2}+C \sum_{i=1}^{R} \varepsilon_{i}, \\& s.t., y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\varepsilon_{i}, \varepsilon_{i} \geq 0\end{aligned}$$

上述公式为在线性可分问题的根底上加上的惩办函数局部，当 \(x_i\) 在正确一边的时候， \(\varepsilon = 0\) ，R为全副的点的数目，C是一个由用户去指定的系数，示意对分错的点退出多少的惩办：

• 当C很大的时候，分错的点就会更少，然而过拟合的状况可能会比较严重。
• 当C很小的时候，分错的点可能会很多，不过可能由此失去的模型也会不太正确。

理论咱们也会调整和抉择适合的C值。

通过这个变换之后，咱们能够同样求解一个拉格朗日对偶问题，失去原问题的对偶问题的表达式：

$$\begin{aligned} & \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \\ & \text { s.t. }, C \geq \alpha_{i} \geq 0, i=1, \cdots, n , \sum_{i=1}^{n} \alpha_{i} y_{i}=0\end{aligned}$$

在线性不可分状况下失去的对偶问题，不同的中央就是的范畴从[0, +∞)，变为了[0, C]，减少的惩办 \(\varepsilon\) 没有为对偶问题减少太多复杂度。

3）非线性SVM与核函数

如果咱们要解决的分类问题更加简单，甚至不能像下面一样近似线性可分呢，这种状况下找到的超平面分错的水平太高不太可承受。

对于这样的问题，一种解决方案是将样本从原始空间映射到一个更高维的特色空间，使得样本在这个特色空间内线性可分，而后再使用SVM求解，如下图所示：

比方下图中的典型线性不可分的状况：

当咱们应用映射函数 \(z_{1}=x_{1}^{2}, z_{2}=x_{2}^{2}, z_{3}=x_{2}\) 把这两个相似于椭圆形的点映射到三维空间 \((z_1,z_2,z_3)\) 后，对映射后的坐标加以旋转之后就能够失去一个线性可分的点集了。

咱们回顾一下之前失去的对偶问题表达式：

$$\begin{aligned} & \max _{\alpha} \sum_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \\& s.t. , C \geq \alpha_{i} \geq 0, i=1, \cdots, n, \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \\\end{aligned}$$

做一点小小的革新，令： \(x_{i}^{T} x_{j}=\kappa\left(x_{i}, x_{j}\right)\) 。这个式子所做的事件就是将线性的空间映射到高维的空间， \(\kappa\left(x_{i}, x_{j}\right)\) 有很多种，上面是比拟典型的两种：

$$\kappa\left(x_{i}, x_{j}\right)=\left(x_{i} \cdot x_{j}+1\right)^{d}$$

$$\kappa\left(x_{i}, x_{j}\right)= \exp \left(-\frac{\left(x_{i}-x_{j}\right)^{2}}{2\sigma^{2}}\right)$$

上述两个核函数别离为多项式核和高斯核，高斯核甚至是将原始空间映射为无穷维空间，另外核函数有一些比拟好的性质，比如说不会比线性条件下减少多少额定的计算量，等等，此处咱们不深刻。对于一个问题，不同的核函数可能会带来不同的后果，咱们须要做一些尝试来撑持抉择（对于这个局部，大家能够看最下方的python实现局部）。

3.SVM总结

1）模型总结

反对向量机（Support vector machines, SVM）是一种二分类模型，它的根本模型是定义在特色空间上的距离最大的线性分类器，他的学习策略就是距离最大化，同时该办法能够形式化为一个求解图二次布局。

SVM由简至繁可分为三类：线性可分反对向量机、硬距离（hard-margin svm）；线性反对向量机、软距离（soft-margin svm）；非线性反对向量机、Kernel SVM。

SVM中存在三宝：距离、对偶、核技巧。

2）模型优缺点

（1）SVM模型长处

• SVM是一个凸优化问题，求得的解肯定是全局最优而不仅仅是部分最优。
• 不仅实用于线性问题，还实用于非线性问题（借助核技巧）。
• 模型鲁棒性好，决策边界只取决于反对向量而不是全副数据集。
• 中小样本量数据集上成果优异。
• 无需依赖整个数据。
• 泛化能力比拟强。

（2）SVM模型毛病

• 二次布局问题求解将波及n阶矩阵的计算（其中n为样本的个数），计算量随样本量上涨厉害，因而SVM不适用于超大数据集。
• 原始SVM仅实用于二分类问题。（当然，SVM的推广SVR也实用于回归问题；咱们也能够通过one-vs-one，one-vs-rest等思路组合SVM来解决多分类问题）。
• 对非线性问题没有通用解决方案，有时候很难找到一个适合的核函数。
• 对于核函数的高维映射解释力不强，尤其是径向基函数。
• SVM对缺失数据敏感。

更多监督学习的算法模型总结能够查看ShowMeAI的文章AI常识技能速查 | 机器学习-监督学习。

4.基于Python的SVM代码实际

1）算法包阐明

咱们这里间接借助于python机器学习工具包sklearn来演示SVM的利用，sklearn中对SVM的算法实现都包在sklearn.svm上面，具体见sklearn官网文档，其中SVC类是用来进行进行分类的工作，SVR是用来进行数值回归工作的。

不同的核函数须要指定不同的参数。

• 针对线性函数，只须要指定参数C，它示意对不合乎最大间距规定的样本的惩办力度。
• 针对多项式核函数，除了参数C外，还须要指定degree，它示意多项式的阶数。
• 针对高斯核函数，除了参数C外，还须要指定gamma值，这个值对应的是高斯函数公式中 \(\frac{1}{2\sigma ^2}\) 的值。

2）应用线性核函数

import numpy as npimport matplotlib.pyplot as pltfrom sklearn import svm, datasetsiris = datasets.load_iris()X = iris.data[:, :2]  # 只取前两维特色，不便可视化y = iris.targetsvc = svm.SVC(kernel='linear', C=1).fit(X, y)x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1h = (x_max / x_min) / 100xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))plt.subplot(1, 1, 1)Z = svc.predict(np.c_[xx.ravel(), yy.ravel()])Z = Z.reshape(xx.shape)plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)plt.xlabel('Sepal length')plt.ylabel('Sepal width')plt.xlim(xx.min(), xx.max())plt.title('SVC with linear kernel')plt.show()

3）应用多项式核函数

初始化svm对象的代码替换为上面这行

svc = svm.SVC(kernel='poly', degree=3).fit(X, y)

4）应用rbf核函数（高斯核函数）

初始化svm对象的代码替换为上面这行

svc = svm.SVC(kernel='rbf', C=1).fit(X, y)

gamma 值越大，SVM 就会偏向于越精确的划分每一个训练集里的数据，这会导致泛化误差较大和过拟合问题。

C：谬误项的惩办参数C。它还管制平滑决策边界和正确分类训练点之间的衡量。

参考链接

• 反对向量机（SVM）
• 反对向量机(SVM)根底
• 看了这篇文章你还不懂SVM你就来打我

视频教程

能够点击 B站 查看视频的【双语字幕】版本

https://www.bilibili.com/vide...

【双语字幕+材料下载】斯坦福CS229 | 机器学习-吴恩达主讲(2018·完整版)

https://www.bilibili.com/video/BV1TT4y127Nf?p=6

ShowMeAI相干文章举荐

• 1.机器学习基础知识
• 2.模型评估办法与准则
• 3.KNN算法及其利用
• 4.逻辑回归算法详解
• 5.奢侈贝叶斯算法详解
• 6.决策树模型详解
• 7.随机森林分类模型详解
• 8.回归树模型详解
• 9.GBDT模型详解
• 10.XGBoost模型最全解析
• 11.LightGBM模型详解
• 12.反对向量机模型详解
• 13.聚类算法详解
• 14.PCA降维算法详解

ShowMeAI系列教程举荐

• 图解Python编程：从入门到精通系列教程
• 图解数据分析：从入门到精通系列教程
• 图解AI数学根底：从入门到精通系列教程
• 图解大数据技术：从入门到精通系列教程
• 图解机器学习算法：从入门到精通系列教程