ML——支持向量机

支持向量机（SVM）是一种二类分类模型，其基本模型是定义在特征空间上的间隔最大的线性分类器，利用间隔最大化的学习策略，SVM可形式化为一个求解凸二次规划的问题。SVM学习方法包含由简至繁的模型：

间隔与支持向量

分类学习最基本的思想就是基于训练集D在样本空间中找到一个划分超平面，即 $w^Tx+b=0$ ，其中w为法向量，决定了超平面的方向，b为位移项，决定了超平面与原点之间的距离。样本空间中任意点到超平面 $(w,b)$ 的距离为：

$r=\frac{\vert w^Tx+b \vert }{||w||}$

能将训练样本划分开的超平面可能有多个，选择位于两类训练样本正中间的划分超平面，因为这个超平面的分类结果最鲁棒，对未见示例的泛化能力最强。

若超平面能将训练样本分类正确，即对于 $(x_i,y_i)\in D$ ，有硬间隔：

$\begin{cases}w^Tx_i+b\geq +1& {y_{i} =+1}\\w^Tx_i+b\leq -1& {y_{i} = -1}\end{cases}$

如下图所示，距离超平面最近的这几个训练点使上式等号成立，它们被称为“支持向量”，两个异类支持向量到超平面的距离之和，即间隔为：

$\gamma =\frac{2}{||w||}$

欲找到具有“最大间隔”的划分超平面，就是要在w和b的约束下使 $\gamma$ 最大，而最大化，等价于最小化，于是得到了SVM的基本型：

$\mathop{\min}_{w,b} \frac{1}{2} ||w||^2 \\\ s.t.y_i(w^Tx_i+b)\geq 1, i=1,...,m$

对偶问题

SVM基本型是一个凸二次规划问题，可使用拉格朗日乘子法求解其对偶优化问题，Lagrange函数为：

令Lagrange函数对w和b的偏导分别为0，再考虑约束得到SVM基本型的对偶问题为：

解 $\alpha$ ，求出w、b，得到模型：

$f(x)=w^Tx+b=\sum_{i=1}^m \alpha _iy_ix_{i}^Tx+b$

上述过程应满足KKT条件，即

训练完后，大部分的训练样本无需保留，最终模型仅与支持向量有关。二次规划算法求解对偶问题的规模正比于训练样本数，实际任务中会增大开销，因此提出SMO算法。

SMO算法

步骤：1）选取一对需要更新的变量αi和αj；2）固定αi和αj以外的参数，求解对偶问题获得更新后的αi和αj。不断执行1)和2)直至收敛。

只要选取的αi和αj有一个不满足KKT条件，目标函数就会在迭代后减小。KKT条件违背程度越大，变量更新后可能导致的目标函数值减幅越大。且考虑到模型复杂度，SMO采用启发式：使选取两变量对应样本之间的间隔最大，因为变量差别越大，对其进行更新会带给目标函数值更大的变化。

核函数

当原始数据线性不可分时，SVM会选择一个核函数，将训练数据映射到高维空间，使样本在这个特征空间线性可分。若原始空间是有限维时，一定有一个高维特征空间使样本线性可分。

令 $\phi (x)$ 为将x映射后的特征向量，此时超平面为 $f(x)=w^T\phi (x)+b$ ，对偶问题为：

由于 $\phi (x_i)$ 所处特征空间维数很高，直接计算内积非常困难，引入核函数 $\kappa (x_i,x_j)=\phi (x_i)^T\phi (x_j)$ ，即xi与xj在特征空间内积等于其在原始空间通过计算的结果。此时问题变为：

$\kappa$ 是核函数当且仅当对任意数据 $D=\left\{ x_1,x_2...x_m \right\}$ ，“核矩阵（对称阵）”K总是半正定的。

常用核函数：

核函数的选择

软间隔与正则化

现实任务很难让训练数据完全线性可分，即便找见合适的核函数满足线性可分，也很难断定是不是过拟合造成的。因此，引入软间隔，允许SVM在一些样本上出错。

相较于所有样本都要划分正确的硬间隔，软间隔允许某些样本不满足约束 $y_i(w^Tx_i+b)\geq 1$ 。

在最大化间隔函数同时不满足约束条件的样本应尽可能少，优化目标为：

其中C为常数， $l_{0/1}$ 为0/1损失函数，，但其非凸、非连续、数学性质不太好，常用一些函数将其替代称为“替代损失”，如下图：

采用hinge损失并引入松弛变量 $\xi _i$ $\geq 0$ ，可得到“软间隔SVM”：

类似于硬间隔SVM，也可以用Lagrange乘子法对软间隔SVM求解。

支持向量回归（SVR）

传统回归模型基于模型输出和真实输出间的差别计算损失，当二者完全相同时损失为0。而SVR假设能容忍这二者之间最多有 $\epsilon$ 的偏差。

于是SVR问题可形式化为：

$\mathop{\min}_{w,b} \frac{1}{2} ||w||^2 \ +C\sum_{i=1}^ml_\epsilon (f(x_i)-y_i)$

其中C为正则化参数， $l_\epsilon$ 为 $\epsilon$ -不敏感损失函数：

$l_\epsilon =0,\vert z \vert \leq \epsilon ;l_\epsilon =\vert z \vert ,otherwise$

引入松弛变量 $\xi _i$ 和 $\hat{\xi _i}$ ，目标函数为：

Lagrange乘子法得到SVR的解为： $f(x)=\sum_{i=1}^m(\hat{\alpha _i} -\alpha _i)x_i^Tx+b$ 对于b，实践中通常选取多个（或所有）满足条件 $0<\alpha _i<C$ 的样本求解b后取平均值。考虑特征映射 $w=\sum_{i=1}^m(\hat{\alpha _i} -\alpha _i)\phi (x_i)$ ，带入SVR得： $f(x)=\sum_{i=1}^m(\hat{\alpha _i} -\alpha _i)\kappa (x,x_i)+b$