机器学习基础 - 分类模型之SVM

SVM：支持向量机

---

简介

https://zhuanlan.zhihu.com/p/77750026

SVM 三宝： 间隔，对偶，核技巧。它属于判别模型。Support Vector Machine

• **支持向量：**在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。
• 支持向量机（SVM）：其含义是通过支持向量运算的分类器。

SVM 是一种二分类模型， 它的目的是寻找一个超平面来对样本进行分割，分割的依据是间隔最大化，最终转化为一个凸二次规划问题来求解。

基础准备

1. 线性可分

$D_0$ 和 $D_1$ 是 n 维空间中的两个点集， 如果存在 n 维向量 $w$ 和实数 $b$ ， 使得：
$$\begin{gathered} w{x}_i+b>0;x_i\in D_0 \\ w{x}_j+b<0;x_j\in D_1 \end{gathered}$$
则称 $D_0$ 与 $D_1$ 线性可分。

2. 最大间隔超平面

能够将 $D_0$ 与 $D_1$ 完全正确分开的 $wx+b=0$ 就成了一个超平面。

为了使得这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。

• 两类样本分别分割在该超平面的两侧
• 两侧距离超平面最近的样本点到超平面的距离被最大化了

3. 什么是支持向量？

训练数据集中与分离超平面距离最近的样本点成为支持向量

4. SVM 能解决哪些问题？

• **线性分类：**对于n维数据，SVM 的目标是找到一个 n-1 维的最佳超平面来将数据分成两部分。

  通过增加一个约束条件： 要求这个超平面到每边最近数据点的距离是最大的。

• 非线性分类： SVM通过结合使用拉格朗日乘子法和KTT条件，以及核函数可以生产线性分类器

5. 支持向量机的分类

• 硬间隔SVM（线性可分SVM)： 当训练数据可分时，通过间隔最大化，学习一个线性表分类器。
• 软间隔SVM(线性SVM)：当训练数据接近线性可分时，通过软间隔最大化，学习一个线性分类器。
• Kernel SVM： 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性SVM。

必会：硬间隔最大化 --> 学习的对偶问题 --> 软间隔最大化 --> 非线性支持向量机（核技巧）

硬间隔 SVM

0. 几何间隔与函数间隔

1. SVM 最优化问题

任意分离超平面可定义为：
$$w^{T}x+b=0$$
二维空间中点 $(x,y)$ 到直线 $Ax+By+C=0$ 的距离公式为：
$$\frac{|Ax+By+C}{\sqrt{A^2+B^2}}$$

扩展到n维空间中，任意点 $x$ 到超平面$w^{T}x+b=0$ 的距离为：
$$\begin{gathered} \frac{|w^{T}x+b|}{||w||} \\ ||w||=\sqrt{w_1^2+...+w_n^2} \end{gathered}$$
假设，支持向量到超平面的距离为 $d$ ，那么就有：
$$\{\begin{array}{ll}\frac{w^T{x}_i+b}{||w||}\ge d,& y_i=+1\\ \frac{w^T{x}_i+b}{||w||}\le -d,& y_i=-1\end{array}$$
稍作转化可得到：
$$\{\begin{array}{ll}\frac{w^T{x}_i+b}{||w||d}\ge 1,& y_i=+1\\ \frac{w^T{x}_i+b}{||w||d}\le -1,& y_i=-1\end{array}$$
考虑到 $||w||d$ 为正数，我们暂且令它为 1（之所以令它等于 1，是为了方便推导和优化，且这样做对目标函数的优化没有影响）：
$$\{\begin{array}{ll}{w}^T{x}_i+b>=+1,& y_i=+1\\ w^T{x}_i+b<=-1,& y_i=-1\end{array}$$

两个方程合并，则有：
$$y_i(w^T{x}_i+b)\ge 1$$
那么我们就得到了最大间隔超平面的上下两个超平面

两个异类超平面的公式分别为：
$$\{\begin{array}{ll}{w}^T{x}_i+b=+1,& y_i\\ w^T{x}_i+b=-1,& \end{array}$$