支持向量机

总结来说，SVM是一个二分类算法，它是定义在特征空间上的间隔最大分类模型，采用不同的技巧可以处理线性可分数据、部分线性可分数据和线性不可分数据。

主要研究内容

根据处理数据对象的情况可以分为如下三类，由简至繁

线性可分支持向量机
对于线性可分数据集，通过硬间隔最大化，学习出一个分类器，也称作硬间隔支持向量机
线性支持向量机
对于近似线性可分数据集，通过软间隔最大话，学习出一个线性分类器，也称作软间隔支持向量机
非线性支持向量机
对于线性不可分数据，通过核技巧和软间隔最大化，学习出非线性支持向量机。

模型从简单到复杂，简单线性模型是复杂模型的特例，下文会集中算法的具体原理进行介绍。

基本概念

线性可分，是指对于一个数据集，如果能够找到一个超平面能将该数据严格分开，即一部分数据在超平面一侧，另一部分在超平面另外一侧，则称该数据线性可分。

线性可分支持向量机

基本情况介绍。
给定一个特征空间上的数据集 $T=\{(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)\}$, 其中$x_i \in R^{n}, y_i \in y=\{-1, +1\}, i=1,2,\cdots, N$.$x_i$和$y_i$分别为第$i$个样本的特征向量和类别标记，当$y_i=-1$，表示为负例，当$y_i=+1$，表示正例。存在超平面$\boldsymbol{wx}+b=0$ 能将数据集分开，$(\boldsymbol{w}, b)$为超平面的法向量和截距，相应的决策函数为$f(x)=sign(\boldsymbol{wx}+b)$，符号大于0为正例，小于0为负例。

函数间隔

如何评价一个分隔超平面的分类确信度？通过点到超平面的距离可以体现

如果一个点到超平面的距离越大，说明点离超平面的距离越远，也就说明超平面的分类确信度越高，反之，如果点到直线的距离越小，超平面越容易将该点分错，分类确信度越低。

了解这个基本思想之后，点到超平面的距离可以表示为，$|\boldsymbol{wx}+b|$，即分类的确信度，那该点是否正确分类，可以看$\boldsymbol{wx}+b$的符号是否和$y$的符号一致，若一致则表示分类正确，若不一致则分类错误，因此用$y_i(\boldsymbol{wx}+b)$ 来表示分类正确性和可信度，也即是函数间隔的概念。

超平面$(\boldsymbol{w},b)$与样本点$(x_i, y_i)$的函数间隔为

$\hat{\gamma}=y_i(w\cdot x+b)$

超平面关于数据集$T$的函数间隔定义为，数据集中所有点与超平面的函数间隔中最小的那一个，记作

$\hat{\gamma}=\min \limits_{i=1,\cdots,N}\hat{\gamma}_i$

几何间隔

对于函数间隔分析，同比例放大或缩小$w,b$，超平面不发生变化，但是函数间隔值却会之随之放大或缩小，因此为了能保持函数间隔保持确定，可以对函数间隔施加某种约束，可以是归一化约束，即$||w||_2=1$,即是权重向量的2范数，那么添加约束后的函数间隔被称作几何间隔。

超平面$(\boldsymbol{w},b)$关于点$(x_i, y_i)$几何间隔为，

$\gamma = \frac{1}{||w||}y_i(w\cdot x_i +b)$

超平面关于数据集$T$的几何间隔定义为，样本集中所有点与超平面的几何间隔中最小的那一个，记作

$\gamma=\min \limits_{i=1,\cdots,N}\gamma_i$

则函数间隔和几何间隔的关系如下，

$\gamma_i = \frac{\hat{\gamma_i}}{||w||}$

如果$||w||=1$则函数间隔和几何间隔相当，参数$w,b$成比例的改变，几何间隔保持不变，函数间隔同比例变化。

硬间隔对大化

目标函数的确定。

支持向量机学习的基本想法，求解能够正确划分数据集，并且几何间隔最大的分隔超平面

换句话说，我们要寻找一个超平面能够把数据集分开，且分隔确信度很高，这个确信度就是用几何间隔来体现，前面讨论中提到，距离越远，分类确信度越高，因此我们要找一分隔超平面，对数据集$T$的几何间隔最大，超平面对数据集的几何间隔是指所有几何间隔中最小的那个，从而我们可以定义出如下的约束问题，

$\max \limits_{w,b} \gamma \\ s.t. \quad y_i(\frac{w}{||w||}\cdot x + \frac{b}{||w||}) \geq \gamma ,\quad i=1,2,\cdots,N$

换句话说我们要找一个分隔超平面对数据集的几何间隔至少是$\gamma$,根据函数间隔和几何间隔的关系将上式进行改写，

$\max \limits_{w,b} \frac{\hat{\gamma}}{||w||} \\ s.t. \quad y_i(w\cdot x + b ) \geq \hat{\gamma}, i=1,2\cdots, N$

由于函数间隔$\hat{\gamma}$取值不影响优化问题的解，因此这里取$\hat{\gamma}=1$,将其代入上式，最大化$\gamma=\frac{1}{||w||}$,等价于最小化$\frac{1}{2}||w||^2$，因此最终的约束问题可以描述如下，

$\min \limits_{w,b} \frac{1}{2}||w||^2 \\ s.t. \quad y_i(w\cdot x +b ) - 1 \geq 0, i=1,2,\cdots, N$

因此可以得到线性可分支持向量机算法,

输入：线性可分训练集$T=\{(x_1, y_1),(x_2, y_2),\cdots,(x_N, y_N)\}$, 其中$x_i$表示特征向量，$y_i \in \{-1, +1\}，,i=1,2,\cdots,N$,表示样本属于负例或正例
输出：最大间隔分离超平面和分类决策函数
(1) 构造约束优化问题
$$\min \limits_{w,b}\frac{1}{2}||w||^2 \\
s.t. \quad y_i(w \cdot x + b ) -1 \geq 0, i=1,2,\cdots,N$$  
求解最佳参数$w^{*}, b^*$
(2) 根据最佳参数得到分割超平面
$$w^* \cdot x + b = 0$$
(3) 分类决策函数
$$f(x)=sign(w^*\cdot x +b)$$

对偶问题

对于带有约束条件的优化问题通常采用拉格朗日法进行求解，因此也采用此方式，通过求解对偶问题最优解得到原始问题的解。线性SVM的拉格朗日函数如下，

$L(w,b,\alpha) = \frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha_i (y_i(w\cdot x_i +b) - 1) \\ = \frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha_i y_i(w\cdot x_i +b) + \sum_{i=1}^{N}\alpha_i$

先来分析原始问题的情况，约束问题可知，原问题是极小极大问题，所谓“极小”是指求得分割超平面关于数据集的几何距离最小，“极大”是指选取出来的分隔超平面能以最大的确信度分隔数据集。根据拉格朗日对偶性，原始问题的对偶问题是极大极小为 $\max \limits_{\alpha} \min \limits_{w,b}L(w,b,\alpha)$
从而求解问题先求极小部分再求极大。
(1) 求$\min \limits_{w,b}L(w,b,\alpha)$,对参数$w,b$求偏导为0。

$\nabla_wL(w,b,\alpha)=w - \sum_{i=1}^{N}\alpha_i y_ix_i=0 \\ \nabla_bL(w,b,\alpha)=-\sum_{i=1}^{N}\alpha_i=0$

得到，

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

将上面结果代入拉格朗日求解，

$\min \limits_{w,b}L(w,b,\alpha) = -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^{N}\alpha_i$

(2) 求$\min \limits_{w,b}L(w,b,\alpha)$,对参数$\alpha$的极大，

$\max \limits_{\alpha} -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^{N}\alpha_i \\ s.t. \quad \sum_{i=0}^{N}\alpha_i y_i=0 \\ \alpha_i \geq 0 , i = 1,2,\cdots, N$

上式将负号去掉即可转换为求极小值问题，

$\min \limits_{\alpha} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^{N}\alpha_i \\ s.t. \quad \sum_{i=0}^{N}\alpha_i y_i=0 \\ \alpha_i \geq 0 , i = 1,2,\cdots, N$

设$\alpha^{}=(\alpha_{1}^{},\alpha_{2}^{},\cdots,\alpha_{l}^)$为上式的最优解，因此可以求得，分隔超平面参数$w,b$

$w^*=\sum_{i=0}^{N}\alpha_i^* y_ix_i \\ b^* = y_i - \sum_{i=1}^{N}\alpha_i^{*}y_i(x_i\cdot x_j)$

支撑向量

从$w,b$的求解公式中可以看到，他们至于$\alpha_i^* \gt 0$ 对应的$(x_i,y_i)$有关系，这些点被称作支撑向量。

线性支持向量机

思考问题

1. 什么是核函数？
1. 高斯核函数映射到无穷维是怎么回事？
1. 如何理解SVM损失函数？
1. 使用高斯核函数，参数$C$和$\delta$对分类器的影响？
1. SVM 和感知机有和区别联系？