# 支持向量机(Support Vector Machine, SVM)
## 0. 写在前面
现在有很多介绍SVM的书籍、博客，但我个人感觉大部分文章的推导部分不够细致，而且少有作者自己的思考分享，对初学者的学习存在一定障碍。~~**当然这篇博客也不敢说能够写的初学者容易理解，笔者尽可能地希望达到这个目的，权当抛砖引玉之作**~~
**（以下内容是废话 您可以跳过）**
事实上我第一次接触SVM大概是19年3月为完成毕设时候的事了，当时的感觉就整的稀里糊涂的。~~（也不知道我毕设是怎么“编”完的）~~然后本文最初的动机也并不是介绍SVM，11月01号时这篇文章的标题是“占个坑，今年完成一篇对KKT条件和对偶性的理解”，初因是那会有个经济学专业的好朋友问我KKT条件是怎么一回事，当时我为了“面子”恶补KKT条件相关的知识，学到了会用的水平就教她怎么用了哈哈哈哈（相当浅尝辄止），于是说立了个flag，今年有空要更一篇优化问题中的KKT条件以及对偶性的理解。但开始写这篇文章时呢，学着学着复习到SVM去了，参考了诸多资料，又深感自己似乎是有点入门的感觉了。故因在这里分享一些我对SVM的理解，在总结中继续学习等等（最重要的是立了flag的嘛...要做的），写本篇博客做个总结。
## 1. 概述
### 1.1 简介
**支持向量机（support vector machines, SVM）**是一种二分类模型，它的基本模型是定义在特征空间上的**间隔**最大的线性分类器(间隔最大使它有别于感知机)；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的学习策略是间隔最大化，可形式化为一个求解**凸二次规划**的问题，也等价于正则化的**合页损失函数(hinge loss)**的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。
**人话版**：
**SVM是一种定义在特征空间上间隔最大的线性二分类器**
SVM有三宝，间隔对偶核技巧
- hard-margin SVM
- soft-margin SVM
- kernel SVM
### 1.2 直观理解
我们从最简单的情况直观感受下SVM的优势。
图中分别有黑点、白点2个类别的二维数据点，H1、H2、H3分别代表3个分类器，试问哪一个分类器性能比较好呢？
直觉上的想法很容易得出H3在该数据分布下是最优的，首先H1并不能将数据正确分类；H2虽然可以将数据正确分类，但分类器和最近的数据点间隔过小，当输入数据存在噪声的时候H2很容易分类出错，即对噪声敏感、泛化能力弱；相反H3以较大的间隔将两类数据点分开，这样对噪声的容忍程度更大，分类器具有更好的泛化能力。
对于支持向量机来说，数据点若是p维向量，我们用p−1维的超平面来分开这些点。但是可能有许多超平面可以把数据分类。最佳超平面的一个合理选择就是以最大间隔把两个类分开的超平面。因此，SVM选择能够使离超平面最近的数据点的到超平面距离最大的超平面。
以上介绍的SVM只能解决线性可分的问题，为了解决更加复杂的问题，支持向量机学习方法有一些由简至繁的模型:
> - 线性可分SVM
当训练数据线性可分时，通过硬间隔(hard margin，什么是硬、软间隔下面会讲)最大化可以学习得到一个线性分类器，即硬间隔SVM，如上图的的H3。
**人话版**：线性可分的简单情况下直接上hard-margin SVM
</br>
> - 线性SVM
当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM。
**人话版**：近似线性可分指允许少部分数据出错的情况下的线性可分，此时用soft-margin SVM
</br>
> - 非线性SVM
当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM。
**人话版**：通过kernel method将数据点从线性不可分的特征空间映射到近似线性可分的空间，然后用soft-margin SVM完成分类任务
## 2. hard-margin SVM
### 2.1 模型定义
在开始推导之前 我们首先需要给出一些定义。
假设给定一个特征空间上的训练数据集T
其中
xi为第i个特征向量，yi为类标记，yi为+1时为正例；yi为-1时为负例且**训练数据集线性可分**。
以二维平面为例，我们首先对一个点到超平面计算几何距离，**记为distance**（图是我自己画的 有点丑见谅55555 >>>如果你有什么画图方便的工具也欢迎告诉我呀)
根据高中学的代数几何知识不难知道
于是所谓的margin就定义为，也就是说**间隔由所有训练数据点到超平面的几何距离的最小值决定**，实际上这个最小值所对应的样本点就是我们说的**支持向量**。
我们前面已经提到，SVM的学习策略总体上是使间隔最大化，于是我们的hard-margin SVM模型就可以定义为：
将margin代入上式即有约束优化问题：
### 2.2 推导过程
由2.1中模型定义，我们首先考虑约束条件
再有：
**Attention**：这步其实很多资料都是直接省略的，事实上我们知道r的值是可以人为赋予的（相应计算出的w、b会有所变化），我们在这里**赋值r=1**，于是模型定义就简化为了：
(**上述等价转换过程为了后面求梯度方便**)
至此，我们已经讲hard-margin模型转换为了一个**凸优化问题**，引入拉格朗日函数有：
通过引入拉格朗日函数，我们可以将**受w、b约束的Primal Problem(原问题)**转换成**无w、b约束的Primal Problem**，即：
其**Dual Problem(对偶问题)**是[在这里有关对偶关系成立的直观解释在评论区略有提及，其证明暂时不予讨论，在后文中给出]:
为求解上述对偶问题，首先只考虑求解
首先计算L对b的偏导并赋值为0，代回拉格朗日函数L有：
然后计算L对w的偏导并赋值为0（注意我们前面将模型定义转化为1/2\**w*Tw的优势发挥出来了)：
再次代回拉格朗日函数L有:
即**Dual Problem**进一步化为：
将目标式子取负号，把求解极大转换为求解极小：
> **若原问题和对偶问题存在强对偶关系，KKT条件成立；反之亦然成立。**
> **同时SVM天然满足强对偶成立的条件** //后续也许会提到
该对偶问题下的KKT条件式子如下:
事实上我们前面已经求出了最优的w\*如下：
我们假设所有的乘子λi均为0，则有w\*=0，则margin = 2/||w|| =∞显然不符实际，于是我们知道至少**有一个乘子λi>0**，从而由**互补松弛条件**我们可以知道至少有一个j（与λi>0对应）使得下式成立：
从而我们可以求解得到最优的b\*：
至此，我们已经求解到了线性可分的hard-margin SVM决策函数为：
### 2.3 再来看看KKT条件?
我们再来考虑KKT中的互补松弛条件，其含义实际上可以分解为：
于是有：
- 若λi=0，此样本点不是支持向量，对模型无贡献
- 若λi>0，此样本点位于最大间隔边界上，为支持向量，参与w\*、b\*的计算
所以，整个SVM的解只与支持向量有关，与非支持向量无关。即在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用。
## 3. soft-margin SVM
在前面的讨论中，我们假定训练数据是严格线性可分的，即一定存在超平面可以完全将两类数据正确分类。但现实中的数据往往是复杂的，这个假设过于苛刻。例如下面的数据:
### 3.1 soft-margin最大化
**所谓的“soft”指的是，我们放宽一点限制，允许SVM分类器在少量样本上出错**，即最小化项从hard-margin变为了：
这里的loss我们常用hinge loss合叶损失函数，其内涵为数据点到超平面的距离定义，即：
记`$$ z = y_i(w^Tx_i+b) $$`，有`$$ {loss}_{hinge}(z) = max(0,1-z) $$`
不妨看一下hinge loss的图像，形如合叶，也就是其名字由来。
当样本点被正确分类时，其hinge loss为0，对计算过程无实质影响
为了简化起见，我们引入松弛变量`$$\xi_i=1-y_i(w^Tx_i+b)\geq0 $$`，于是整个模型定义如下：
```katex
\left\{\begin{aligned}
\min _{w, b, \xi} \frac{1}{2} w^{T} w+C \sum_{i=1}^{N} \xi_{i} \\
\text {s.t } y_{i}\left(w^{T} x_{i}+b\right) \geq 1-\xi_{i} \\
\text {s.t } \xi_{i} \geq 0, i=1,2, \cdots, N
\end{aligned}\right.
```
其中`$$C>0$$`称为惩罚参数，`$$C$$`越小时对误分类惩罚越小，越大时惩罚越大，当C取正无穷时退化为hard-margin SVM。关于`$$\xi_i$$`几何意义的解释如下图所示。
### 3.2 soft-margin SVM推导过程
soft-margin SVM依然是一个凸二次规划问题，和hard-margin SVM推导过程几乎完全一样。
首先引入拉格朗日函数：
类似hard-margin SVM的推导过程，我们首先求
对拉格朗日函数L分别对`$$W、b、\xi$$`求偏导有下列式子成立:
```katex
\begin{aligned}
W=\sum_{i=1}^{n} \alpha_{i} y_{i} X_{i}\\
\sum_{i=1}^{n} \alpha_{i} y_{i}=0\\
C=\alpha_{i}+\beta_{i}
\end{aligned}
```
将上述三式代回拉格朗日函数后有：
`$$\min _{W, b, \xi} L(W, b, \xi, \alpha, \beta)=-\frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} X_{i}^{T} X_{j}+\sum_{i=1}^{n} \alpha_{i}$$`
类似hard-margin SVM，对上式取负号则模型求解问题转化为
```katex
\left\{\begin{array}{c}
{\min_{\alpha} \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} X_{i}^{T} X_{j}-\sum_{i=1}^{n} \alpha_{i}} \\
{\text { s.t } \sum_{i=1}^{n} \alpha_{i} y_{i}=0} \\
{\text { s.t } \quad 0 \leq \alpha_{i} \leq C, i=1,2, \cdots, N}
\end{array}\right.
```
从而根据KKT条件可以求到
```katex
w^{*}=\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} X_{i}
\\b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left({X}_{i}^T \cdot{X}_{j}\right)
```
计算`$$b^*$$`时的样本点满足`$$0 < \alpha_{j}^{*} < C$$`
至此，我们已经求解到了近似线性可分的soft-margin SVM决策函数为：
### 3.3 惩罚参数C？
从上图可以直观的看到，C越小对误分类惩罚也就越小，直观上理解SVM的间隔也就越宽，对错误分类的容忍度越高。
考虑我们的原始目标函数：`$$\min _{W, b, \xi} \frac{1}{2}\|W\|^{2}+C \sum_{i=1}^{n} \xi_{i}$$`
将其一般化，可以推广到：
`$$\min _{f} \quad \Omega(f)+C \sum_{i=1}^{n} l\left(f\left(x_{i}\right), y_{i}\right)$$`
式中的第一项为“**结构风险(structural risk)**”，用来描述所求模型本身的性质(例如SVM的间隔最大性)；第二项称为“**经验风险(empirical risk)**”，用来描述模型与训练数据的契合程度(**即误差**)。而参数C是用来对二者进行权衡的一个参数。
**从正则化角度看，Ω(f)是正则化项，C为惩罚参数，C越大对误分类的惩罚越大，可能导致过拟合；C越小越看重正则化项，可能导致欠拟合**
## 4. kernel SVM
前面介绍的都是线性问题，但是我们经常会遇到非线性的问题(例如异或问题)，训练数据是非线性可分的，此时就需要用到核技巧(kernel trick)将线性支持向量机推广到非线性支持向量机。需要注意的是，不仅仅是SVM，很多线性模型都可以用核技巧推广到非线性模型，例如核线性判别分析(KLDA)。
### 4.1 kernel function
kernel SVM通常分为两步
1. 使用一个映射将原空间的数据映射到新空间(例如更高维甚至无穷维的空间)；
2. 在新空间里用线性方法(soft-margin SVM)从训练数据中学习得到模型。
现在的问题是，如何找到这样一个映射？先来看看kernel function的定义。
> 设`$$\mathcal{X}$$`是输入空间(欧式空间`$$R^{n}$$`的子集或离散集合)，又设`$$\mathcal{H}$$`是特征空间(希尔伯特空间)，如果存在一个`$$\mathcal{X}$$`到`$$\mathcal{H}$$`的映射
`$$ϕ(x)$$`:`$$\mathcal{X}$$`→`$$\mathcal{H}$$`
使得对所有 `$$x,z∈\mathcal{X}$$`，函数`$$K(x,z)$$`满足条件
`$$K(x,z)=ϕ(x)⋅ϕ(z)$$`
则称`$$K(x,z)$$`为核函数，`$$ϕ(x)$$`为映射函数，式中`$$ϕ(x)⋅ϕ(z)$$`为 `$$ϕ(x)$$`和`$$ϕ(z)$$`的內积。
通常，直接计算`$$K(x,z)$$`比较容易而通过`$$ϕ(x)$$`和`$$ϕ(z)$$`计算`$$K(x,z)$$`并不容易。而幸运的是，在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都只涉及到输入样本与样本之间的內积，因此我们不需要显式地定义映射`$$ϕ(x)$$`是什么而只需事先定义核函数`$$K(x,z)$$`即可。也就是说，在核函数 `$$K(x,z)$$`给定的情况下，可以利用解线性问题的方法求解非线性问题的支持向量机，此过程是隐式地在特征空间中进行的。
**人话版**：即通过核技巧我们不必真的找到这个映射使得数据空间发生变化，只需事先定义使用什么核函数即可。(注：我们通常说的核函数是正定核函数)
### 4.2 正定核
由上面的介绍可知，我们只需要定义核函数就可以了。但是如何不通过映射`$$ϕ(x)$$`判断给定的一个函数`$$K(x,z)$$`是不是核函数呢？或者说，`$$K(x,z)$$`需要满足什么条件才是一个核函数。
在下面不加证明的给出正定核的充要条件，具体证明略显复杂，有兴趣的可以参考《统计学习方法》。
> 设`$$\mathcal{X}⊂R^{n}$$` ,`$$K(x,z)$$`是定义在`$$\mathcal{X}×\mathcal{X}$$`上的对称函数(即`$$K(x,z)=k(z,x)$$`)，若对任意的 `$$x_i∈\mathcal{X},i=1,2,···,m$$`，`$$K(x,z)$$`对应的Gram Matrix
`$$K=\left[K\left(x_{i}, x_{j}\right)\right]_{m \times m}$$`是半正定矩阵，则`$$K(x,z)$$`是正定核函数。
虽然有了上述定义，但是实际应用时验证`$$K(x,z)$$`是否是正定核函数依然不容易，因此在实际问题中一般使用已有的核函数，可以按需使用，下面举两个常用的核函数为例。
- 多项式核函数(polynomial kernel function)
`$$K(x, z)=(x \cdot z+1)^{p}$$`
- 高斯核函数(Guassian kernel function)
`$$K(x, z)=\exp \left(-\frac{\|x-z\|^{2}}{2 \sigma^{2}}\right)$$`
### 4.2 kernel SVM推导过程
kernel SVM在计算时只需将线性SVM中的内积替换为核函数即可，其他过程基本上一致。下面简单列举过程。
给定适当核函数`$$K(x,z)$$`和惩罚参数C>0
```katex
\begin{array}{ll}
{\min _{\boldsymbol{\alpha}}}{\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} K\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)-\sum_{i=1}^{N} \alpha_{i}}
\\
{\text{ s.t. }}{\sum_{i=1}^{N} \alpha_{i} y_{i}=0}
\\
{} {0 \leq \alpha_{i} \leq C, i=1,2, \ldots, N}
\end{array}
```
计算得到最优解`$$\boldsymbol{\alpha}^{*}=\left(\alpha_{1}^{*}, \alpha_{2}^{*}, \ldots, \alpha_{N}^{*}\right)^{T}$$`
选择`$$\boldsymbol{\alpha}^{*}$$`的一个分量`$$\alpha_j^*$$`满足0<`$$\alpha_j^* < C $$`，计算得到：
`$$b^{*}=y_{j}-\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} K\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)$$`
于是有分类决策函数如下：
`$$f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i} K\left(x, x_{i}\right)+b^{*}\right)$$`
## 5. 约束优化问题 & 对偶性几何解释
## 6. 总结
### 6.1 SVM优缺点
任何算法都有其优缺点，支持向量机也不例外。
支持向量机的优点是:
> 1. 由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
2. 不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
3. 拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维数灾难”。
4. 理论基础比较完善(例如神经网络就更像一个黑盒子)。
支持向量机的缺点是:
> 1. 二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
2. 只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)
### 6.2 SVM调参经验
SVM很适合做分类任务，但是如果刚开始接触SVM而不知道如何进行合理的参数选择的话可能得不到满意的结果。下面简介运用SVM的基本步骤，或者说调参经验。
>主要参考:
Hsu C W, Chang C C, Lin C J. A practical guide to support vector classification[J]. 2003.
1. 将原始数据转换为SVM算法期待的格式；
2. 将数据进行scaling(很重要)；
3. 一般考虑用高斯核RBF(如果特征维度太高，建议直接用线性SVM)；
4. 交叉验证寻找最优的RBF的参数以及参数 C ;
5. 用上面找到的最优参数在整个训练集上训练；
## 7. 写在最后面
1. 感觉自己的前面写的**尽可能让初学者也能容易看得懂**的目的完全失败了...
2. 关于对偶性的理解也实在懒得码字了直接传手写笔记了55555有人在看这篇文章且有需要的话我再改成电子版吧-。-
3. 排版真是个技术活，还要细致。我好懒哦。
4. 但总结的过程中自己还是学到了很多的。
5. 希望我所写的东西真的对在看的你有一点点帮助。
## 8. References
[1. 看了这篇文章你还不懂SVM你就来打我](https://tangshusen.me/2018/10/27/SVM/ "看了这篇文章你还不懂SVM你就来打我")
[2. 支持向量机（SVM）——原理篇](https://zhuanlan.zhihu.com/p/31886934 "2. 支持向量机（SVM）——原理篇")
[3. 支持向量机通俗导论（理解SVM的三层境界）](https://blog.csdn.net/v_july_v/article/details/7624837 "支持向量机通俗导论（理解SVM的三层境界）")
浅入深出谈SVM
