反对向量机（SVM）
反对向量机（support vector machines, SVM）是一种二分类模型，它的根本模型是定义在特色空间上的距离最大的线性分类器
SVM的的学习策略就是距离最大化，可形式化为一个求解凸二次布局的问题
- 长处:泛化错误率低，计算开销不大，后果易解释
- 毛病:对参数调节和核函数的抉择敏感，原始分类器不加批改仅实用于解决二类问题
分隔超平面
下面将数据集分隔开来的直线称为分隔超平面 ( separating hyperplane)
在下面给出的例子中，因为数据点都在二维立体上，所 以此时分隔超平面就只是一条直线。然而，如果所给的数据集是三的，那么此时用来分隔数据的就是一个立体
不言而喻，更高维的状况能够依此类推。如果数据集是1024维的，那么就须要一个1023维的对象来对数据进行分隔，该对象被称之为超平面(hyperplane)，也就是分类的决策边界
散布在超平面一侧的所有数据都属于某个类别，而散布在另一侧的所有数据则属于另一个类别
线性可划分
存在一个划分超平面能将训练样本正确分类
而事实人物中，原始样本空间内兴许并不在一个能正确划分两类样本的超平面，如下图
对这样的问题, 可将样本从原始空间映射到一个更高维的特色空间, 使得样本在这个特色空间内线性可分
例如在上图中， 若将原始的二维空间映射到一个适合的三维空间, 就能找到一个适合的划分超平面
比方想要将下图的红点和蓝点变成线性可分的，那么就将映射$y = x$变成映射$y=x^2$，这样就线性可分了
距离(margin)
对于任意一个超平面，其两侧数据点都间隔它有一个最小间隔（垂直距离），这两个最小间隔的和就是距离margin
Hard Margin SVM
当训练数据线性可分时，通过硬距离最大化，学习一个线性的分类器，即线性可分反对向量机
svm尝试寻找一个最优决策边界，间隔两个类别最近的样本间隔最远
在样本空间中，划分超平面可用如下线性方程来形容：
$$w^Tx+b=0$$
其中
$$\boldsymbol{w}=\left(w_{1};w_{2};\ldots;w_{d}\right)$$
为法向量, 决定了超平面的方向; $b$ 为位移项, 决定了超平面与原点之间的间隔
样本空间中任意点$x$到超平面 $(w, b)$ 的间隔可写为
$$r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|}$$
假如超平面 $(w, b)$ 能将训练样本正确分类, 即对于
$$\left(\boldsymbol{x}_{i}, y_{i}\right) \in D$$
若 $y_{i}=$ $+1,$ 则有
$$\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b>0$$
若 $y_{i}=-1,$ 则有
$$\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b<0$$
令
$$\left\{\begin{array}{ll}\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1, & y_{i}=+1 \\\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1, & y_{i}=-1\end{array}\right.$$
如上图所示, 间隔超平面最近的这几个训练样本点使上式的等号成立, 它们被称为“反对向量”(support vector), 两个异类反对向量到超平面的间隔之和为
$$\gamma=\frac{2}{\|\boldsymbol{w}\|}$$
显然, 为了最大化距离, 仅需最大化
$$\|\boldsymbol{w}\|^{-1}$$
这等价于最小化
$$\|\boldsymbol{w}\|^{2}$$
$$\begin{array}{l}\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m\end{array}$$
这就是反对向量机(Support Vector Machine, 简称 SVM)的基本型
Soft Margin SVM
当训练数据近似线性可分时，通过软距离最大化，学习一个线性反对向量机，又称为软距离反对向量机
后面咱们是假设所有的训练样本在样本空间或特色空间中是严格线性可分的，即存在一个超平面能把不同类的样本齐全离开，然而事实工作中很难确定这样的超平面（不论是线性超平面还是通过核变换到高维空间的超平面），所以引入松弛变量，容许一些样本出错，但咱们心愿出错的样本越少越好，所以松弛变量也有限度
具体来说，后面介绍的反对向量机的模式要求所有样本满足束缚，即所有的样本必须划分正确，这称为硬距离，而软距离则是容许某些样本不满足束缚
$$y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1$$
如下图红色圈出了不满足束缚的样本
当然, 在最大化距离的同时, 不满足束缚的样本应尽可能少. 于是, 优化指标可写为
$$\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right)$$
其中 $C>0$ 是一个常数,
$$\ell_{0 / 1}$$
是“0/1损失函数”
$$\ell_{0 / 1}(z)=\left\{\begin{array}{ll}1, & \text { if } z<0 \\0, & \text { otherwise }\end{array}\right.$$
引入“松他变量" (slack variables)
$$\xi_{i} \geqslant 0$$
可将上式重写为
$$\min _{\boldsymbol{w}, b, \xi_{i}} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i}$$
对偶问题
当初的指标函数是二次的，约束条件是线性的，所以它是一个凸二次布局问题
这个问题能够用现成的QP (Quadratic Programming) 优化包进行求解
此外，因为这个问题的非凡构造，还能够通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）失去原始问题的最优解，这就是线性可分条件下反对向量机的对偶算法
这样做的长处在于：
- 一者对偶问题往往更容易求解
- 二者能够天然的引入核函数，进而推广到非线性分类问题
具体来说, 对每条束缚增加拉格朗日乘子 $\\alpha_{i} \\geqslant 0,$ 则该问题的拉格朗日函数可写为
$$L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)$$
其中 $\\alpha=\\left(\\alpha_{1} ; \\alpha_{2} ; \\ldots ; \\alpha_{m}\\right) .$ 令 $L(\\boldsymbol{w}, b, \\boldsymbol{\\alpha})$ 对 $\\boldsymbol{w}$ 和 $b$ 的偏导为零可得
$$\begin{aligned}\boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\0 &=\sum_{i=1}^{m} \alpha_{i} y_{i}\end{aligned}$$
即可将 $L(\\boldsymbol{w}, b, \\boldsymbol{\\alpha})$ 中的 $\\boldsymbol{w}$ 和 $b$ 消去, 就失去的指标函数对偶问题
$$\max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}$$
非线形SVM
当训练数据线性不可分时，通过应用核技巧(kernel trick)及软距离最大化，学习非线形反对向量机
非线性SVM算法原理
对于输出空间中的非线性分类问题，能够通过非线性变换将它转化为某个维特色空间中的线性分类问题，在高维特色空间中学习线性反对向量机
令 $\\phi(x)$ 示意将 $x$ 映射后的特征向量, 于是, 在特色空间中划分超平面所对
应的模型可示意为
$$f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b$$
其中 $\\boldsymbol{w}$ 和 $b$ 是模型参数，有
$$\begin{array}{l}\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\\text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m\end{array}$$
其对偶问题是
$$\max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)$$
$$\begin{array}{ll}\text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\& \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m\end{array}$$
因为在线性反对向量机学习的对偶问题里，指标函数和分类决策函数都只波及实例和实例之间的内积，所以不须要显式地指定非线性变换，而是用核函数替换当中的内积
有了这样的函数，咱们就不用间接去计算高维甚至无穷维特色空间中的内积，于是上式可重写为
$$\begin{array}{ll}\max _{\boldsymbol{\alpha}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\\text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\& \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m\end{array}$$
常见的核函数
$$\begin{aligned}&\text { 线性核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\\&\text { 多项式核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\right)^{d} \quad d \geqslant 1 \text { 为多项式的次数 }\\&\text { 高斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}}{2 \sigma^{2}}\right) \quad \sigma>0 \text { 为高斯核的带宽(width) }\\&\text { 拉普拉斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|}{\sigma}\right) \quad \sigma>0\\&\text { Sigmoid 核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\tanh \left(\beta \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}+\theta\right) \quad \text { tanh 为双曲正切函数, } \beta>0, \theta<0\end{aligned}$$
二分类扩大到多分类问题
SVM 扩大可解决多个类别分类问题
one-vs-rest
对于每个类，有一个以后类和其余类的二类分类器（one-vs-rest）
将多分类问题转化为 n 个二分类问题
svm解决回归问题
当初咱们来思考回归问题，传统回归模型通常间接基于模型输入 $f(x)$ 与实在输入 $y$ 之 间的差异来计算损失, 当且仅当 $f(\\boldsymbol{x})$ 与 $y$ 完全相同时, 损失才为零
与此不同 $,$ 反对向量回归(Support Vector Regression, 简称 SVR)假如咱们能容忍 $f(x)$ 与 $y$ 之间最多有 $\\epsilon$ 的偏差, 即仅当 $f(\\boldsymbol{x})$ 与 $y$ 之间的差异绝对值大于 $\\epsilon$ 时才计算损失
如图所示, 这相当于以 $f(x)$ 为核心, 构建了一个宽度为 $2 \\epsilon$ 的距离带, 若训练样本落入此距离带, 则认为是被预测正确的
于是, SVR 问题可形式化为
$$\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{c}\left(f\left(\boldsymbol{x}_{i}\right)-y_{i}\right)$$
其中 $C$ 为正则化常数, $\\ell_{\\epsilon}$ 是图 6.7 所示的 $\\epsilon$ -不敏感损失 $(\\epsilon$ -insensitive loss $)$ 函数
$$\ell_{\epsilon}(z)=\left\{\begin{array}{ll}0, & \text { if }|z| \leqslant \epsilon \\|z|-\epsilon, & \text { otherwise }\end{array}\right.$$
参考
[机器学习算法（一）SVM]()
机器学习-周志华
反对向量机（SVM）——原理篇
Machine Learning in Action by Peter Harrington