SVM

支持向量机（SVM）——原理篇

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

svm知乎话题

https://www.zhihu.com/topic/19583524/top-answers

学习SVM，这篇文章就够了！（附详细代码）

https://www.jiqizhixin.com/articles/2018-10-17-20

机器学习算法（一）SVM

https://blog.****.net/qq_31347869/article/details/88071930

SVM 原理详解，通俗易懂

https://blog.****.net/DP323/article/details/80535863

学习内容

SVM 硬间隔原理
SVM 软间隔
SMO 求解SVM
代码设计

1、硬间隔

本文是需要一定基础才可以看懂的，建议先看看参考博客，一些疑惑会在文中直接提出，大家有额外的疑惑可以直接评论，有问题请直接提出，相互交流。

SVM-统计学习基础

一开始讲解了最小间距超平面：所有样本到平面的距离最小。而距离度量有了函数间隔和几何间隔，函数间隔与法向量$w$和$b$有关，$w$变为$2w$则函数间距变大了，于是提出了几何距离，就是对$w$处理，除以$||w||$，除以向量长度，从而让几何距离不受影响。

但是支持向量机提出了最大间隔分离超平面，这似乎与上面的分析相反，其实这个最大间隔是个什么概念呢？通过公式来分析一下，正常我们假设超平面公式是： $$ w^{T}x+b=0 // 超平面 $$ $$ \max \limits_{w,b} \quad \gamma \ s.t. \quad y_i(\frac{w}{||w||}x_i+\frac{b}{||w||}) > \gamma $$ 也就是说对于所有的样本到超平面距离都大于$\gamma$，那这个$\gamma$如何求解，文中约定了概念支持向量：正负样本最近的两个点，这两个点之间的距离就是$\gamma$，那么问题来了，这中间的超平面有无数个，如何确定这个超平面呢？于是我们可以约束这个超平面到两个最近的点的距离是一样的。上图中两个红色菱形点与一个蓝色实心圆点就是支持向量，通过这个求解目标，以及约束条件来求解这个超平面。书中有完整的公式装换以及证明这个超平面的唯一性。

这里要讲解一个样本点到直线的距离，正常我们可能难以理解公式里$y$去哪里了，拿二维空间做例子，正常我们说一个线性方程都是$y=ax+b$，其中a和b都是常量，这个线性方程中有两个变量$x$和$y$，转换公式就是$y-ax-b=0$，从线性矩阵的角度来思考问题就是 $y$是$x_1$，$x$是$x_2$，用一个$w^T$来表示这两者的系数，用$b$代替$-b$，所以公式就变为了： $$ w^{T}x+b=0 $$ 于是任意一个样本点到超平面的距离是： $$ r = \frac{|w^{T}x+b|}{||w||} $$ 也就是说约束条件中要求$>\gamma$，其实就是大于支持向量到超平面的距离。

通过一个例子来看看：这里例子中有$w_1,w_2$，这是因为坐标点是二维的，相当于样本特征是两个，分类的结果是这两个特征的结果标签，所以这里的$w$就是一个二维的，说明在具体的应用里需要根据特征来确定$w$的维度。

对偶讲解

其实原始问题是这样的： $$ \max \limits_{w,b} \quad \gamma \ s.t. \quad y_i(\frac{w}{||w||}x_i+\frac{b}{||w||}) > \gamma $$ 利用几何距离与函数距离的关系$\gamma = \frac{\hat{ \gamma}}{||w||}$将公式改为： $$ \max \limits_{w,b} \quad \frac{\hat{ \gamma}}{||w||} \ s.t. \quad y_i(wx_i+b) > \hat{\gamma} $$ 函数间隔是会随着$w与b$的变化而变化，同时将$w与b$变成$\lambda w与\lambda b$，则函数间隔也会变成$\lambda \gamma$，所以书中直接将$\gamma=1$来转换问题。同样的问题又改为： $$ \max \limits_{w,b} \quad \frac{1}{||w||} \ s.t. \quad y_i(wx_i+b) >1 $$ 求解最大值改为另一个问题，求解最小值： $$ \min \quad \frac{1}{2} ||w||^2 \ s.t. \quad y_i(wx_i+b) >1 $$ 这就是一个对偶问题的例子，也是书中支持向量机模型的一个目标函数转换的过程，大家可以看看了解一下这个思路。其实书中利用拉格朗日乘子来求解条件极值，这一块在高等数学中多元函数的极值及求解方法中有提到。为了加深记忆，手写了后面的推导过程：

软间隔

硬间隔是方便用来分隔线性可分的数据，如果样本中的数据是线性不可分的呢？也就是如图所示：有一部分红色点在绿色点那边，绿色点也有一部分在红色点那边，所以就不满足上述的约束条件：$s.t. \quad y_i(x_i+b) >1$，软间隔的最基本含义同硬间隔比较区别在于允许某些样本点不满足原约束，从直观上来说，也就是“包容”了那些不满足原约束的点。软间隔对约束条件进行改造，迫使某些不满足约束条件的点作为损失函数，如图所示：这里要区别非线性情况，非线性的意思就是一个圆圈，圆圈里是一个分类结果，圆圈外是一个分类结果。这就是非线性的情况。