共计 2812 个字符，预计需要花费 8 分钟才能阅读完成。
反对向量机(SVM)
[toc]
一、什么是反对向量机
反对向量机在高纬或有限维空间中结构 超平面 或超平面汇合，其能够用于分类、回归或其余工作。直观来说，分类边界间隔最近的训练材料点越远越好，因为这样能够放大分类器的 泛化误差。
https://zh.wikipedia.org/zh-cn/%E6%94%AF%E6%8C%81%E5%90%91%E9…
外面波及到几个概念：1、超平面；2、泛化误差；3、反对向量
- 什么是超平面呢？
如果咱们是在用反对向量机来解决二分类问题吧。咱们构想如果在一个直角坐标系外面存在两个不同类别：黑点和紫点。当初咱们须要将他们进行拆散，你会怎么做？你或者会说：这还不简略间接画一条线不久完事了吗？看来你明确什么是 超平面，好的咱们看下图：
那么到底是蓝色好呢？还是黄色好呢？这就是咱们要提的第二个概念——泛化误差
- 什么是泛化误差
认真看图可能会相对蓝色最佳呀，为什么呢？因为箭头标记的点他是间隔最短的呀！听起来仿佛很有情理，然而，咱们个别试验都是取局部样本进行测试，因为训练集的局限性或噪声的因素，训练集外的样本可能比图中的训练样本更靠近两个类的分隔界，这将使许多划分超平面呈现谬误，而黄色的超平面受影响最小。这就是咱们要思考的——泛化误差！直观了解就是：在新退出样本点的时候超平面仍旧能够很好的划分数据点。
- 什么是反对向量
咱们将超平面别离加减常数 C 这样的话咱们的超平面就会产生挪动然而挪动多少呢？当咱们挪动到接触样本数据点，而这些样本数据点就决定了咱们的 距离间隔 （卖个关子），他们就叫 反对向量
说了那么多，怎么求这个超平面方程呢？(可能会波及许多的数学知识，想间接理解代码间接跳过这部分)
二、数学实践
机器学习算法和数学知识离不开关系，我尽可能的简化数学知识，当然如果只想要代码也能够，然而得晓得如何 调参
反对向量机的有效性取决于核函数、核参数和软距离参数 C 的抉择
2.1 数学准备常识
- 两直线间隔
$$
设存在两平行直线：A_0x+B_0y+b_0=0；A_0x+B_0y+b_1=0；则他们之间的间隔为:\\d=\frac{|b_1-b_0|}{\sqrt{A_0^2+B_0^2}}
$$
- 二次布局问题
形如：
$$
min\;\;c^Tx+\frac{1}{2}x^TQx\\subject\;to:Dx\geqslant d\\Ax=b
$$
如果 Q≥0 时，那么此时就是凸优化问题
- 拉格朗日乘子法
拉格朗日乘子法是一种将束缚优化问题转化为无约束优化问题的办法，咱们当初要求解如下优化（最小化）问题：
$$
minf(x)\;\;s.t.\;g(x)=0
$$
也就是求解 f(x)在约束条件 g(x)= 0 的条件下的最小值的问题。那么咱们能够引入拉格朗日函数：
$$
L(x,\alpha)=f(x)+\alpha g(x)\;\;\; \alpha 记作拉格朗日乘子
$$
形象了解拉格朗日乘子法 – 知乎 (zhihu.com)
- KKT 约束条件
Karush-Kuhn-Tucker (KKT)条件 – 知乎 (zhihu.com)
2.2 线性可分反对向量机
- 什么是线性可分？
不说概念，直观了解就是：咱们能够间接通过一条直线或
者一个立体去划分数据集，那这就叫线性可分反对向量机！比如说：咱们有训练数据集：
$T=[(x_1,y_1),(x_2,y_2)]$
当初咱们须要找到一条直线划分他们，我想你会立马想到
$ax+by+c=0$
这个方程。很好那么咱们推广到 n 个点的状况。
给定训练数据集:
$$
T=[(x_1,y_1)……(x_n,y_n)]
$$
这种状况下怎么办呢？同样的办法咱们假如超平面方程为：
$$
w^Tx+b=0\\ 其中 w，b 都是模型参数, 留神此时 w 就不是一个数字而是一个向量！
$$
那么的话咱们方程也有了，接下来问题就转化成求解 $w,b$ 参数具体的值的问题了。再次回顾咱们 2 元的点到直线间隔公式：$d=\frac{|ax+by+c|}{\sqrt{a^2+b^2}}$ 同样的情理咱们推到到多维状况：
$$
d=\frac{|w^Tx+b|}{||w||}
$$
不要遗记咱们的出发点是什么：二分类！也就是说咱们要将咱们的点划分开来，这样的话是不是在超平面的某一侧是 a 类另外一侧则是 b 类，还记得咱们后面提到的 距离间隔 吗？咱们设：
$$
\begin{cases}
w^Tx_i+b\geqslant1,y_i=1\\
w^Tx_i+b\leqslant1,y_i=-1
\end{cases}\\\text{这样的话两个超平面的间隔就是}r=\frac{2}{||w||}
$$
超平面间隔就能够类比两平行直线之间间隔
这样的话咱们就是找到最大“距离”也就是说计算：
$$
max\frac{2}{||w||}简化计算记作 min\frac{1}{2}||w||^2\\
subject\;to\;y_i(w^Tx_i+b)\geqslant1,\;i=1,2….n
$$
利用拉格朗日乘子法进行求解：
$$
公式 1\;\;L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\alpha_i(1-y_i(w^Tx_i+b))\\||w||^2=w^Tw
$$
此时咱们对 w，b 别离计算偏导并且令其为 0 失去:
$$
公式 2\;\;w=\sum_{i=1}^{m}\alpha_iy_ix_i\;\;\sum_{i=1}^{m}\alpha_iy_i=0
$$
将公式 2 代入公式 1 失去：
$$
公式 3\;\;max\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_iy_ix^T_i\alpha_jy_jx_j
$$
计算步骤如下：
上述过程须要满足 KKT 条件：
$$
\begin{cases}
\alpha_i\ge0\\y_if(x_i)-1\ge0\\\alpha_i(y_if(x_i)-1)=0
\end{cases}
$$
后续更新核函数、python 代码、算法流程、以及如何求解，自己忙于筹备考试临时没工夫更新，忙过这段将全副机器学习算法补充结束
三、Python 代码
先上 sklearn 代码，后续手撸源代码
https://scikit-learn.org/stable/modules/svm.html
四、评估
长处
- 能够解决高维问题，即大型特色空间；
- 解决小样本下机器学习问题；
- 可能解决非线性特色的相互作用；
- 无部分极小值问题；（绝对于神经网络等算法）
- 无需依赖整个数据；
- 泛化能力比拟强；
毛病
- 当观测样本很多时，效率并不是很高；
- 对非线性问题没有通用解决方案，有时候很难找到一个适合的核函数；
- 对于核函数的高维映射解释力不强，尤其是径向基函数；
- 惯例 SVM 只反对二分类；
- 对缺失数据敏感；
五、算法流程
七、参考
https://zhuanlan.zhihu.com/p/440297403
李航《统计学学习办法(第二版)》
《西瓜书》