Support Vector Machines 支持向量机

总结

前置请看 拉格朗日算子。
定义在特征空间上的间隔最大的线性分类器。核技巧使其成为实质上的非线性分类器，等价于隐式地在高维的特征空间中学习线性支持向量机。

适用问题：二类分类
适用数据类型：数值型和标称型数据。
优点：泛化错误率低，计算开销不大，结果易解释。
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题。
模型-知识表示：分离超平面，核技巧
模型-目标策略：极小化正则化合页损失，软间隔最大化
模型-损失函数：合页损失
模型-优化算法：序列最小最优化算法 SMO
可能的坑：非平衡数据集、
标签：Linear Model,

SVM 包含构建由简至繁的模型：

• 当训练数据线性可分时，通过硬间隔最大化 hard margin maximization，学习一个线性的分类器，即线性可分支持向量机 linear support vector machine in linearly separable case，又称为硬间隔支持向量机。
• 当训练数据近似线性可分时，通过软间隔最大化 soft margin maximization，也学习一个线性的分类器，即线性支持向量机 linear support vector machine，又称为软间隔支持向量机。
• 当训练数据线性不可分时，通过使用核技巧 kernel trick 及软间隔最大化，学习非线性支持向量机 non-linear support vector machine。

推倒

发现一篇比较好的讲解，放在前面。

线性可分支持向量机与硬间隔最大化

线性可分支持向量机

给定特征空间上的训练数据集，$T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_N, y_N) \}$，其中，$\mathbf{x} \in \mathcal{X} = \mathbf{R}^n$, $y \in \mathcal{Y} = \{ +1, -1 \}$, $i = 1,2, \ldots,N$。
给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为$$\mathbf{w}^* \cdot \mathbf{x} + b^* = 0$$ (法向量$\mathbf{w}$决定了超平面的方向，位移项$b$决定了超平面与原点之间的距离)，以及相应的分类决策函数 $$f(x) = sign(\mathbf{w}^* \cdot \mathbf{x} + b^*)$$称为线性可分支持向量机。

函数间隔和几何间隔

一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。y的符号表示分类是否正确，距离表示确信度。
对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为$$\hat\gamma = y_i(w \cdot x_i + b)$$。定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i, y_i)$的函数间隔之最小值，即$$\hat\gamma = \min_{i=1,\ldots,N}\hat\gamma_i$$。
函数间隔成比例改变时，超平面并没变，因此可以对分离超平面的法向量$w$加某些约束，如规范化，使得间隔是确定的。于是与上述对应的几何间隔分别为$$\gamma_i = y_i(\frac{w}{| w |} \cdot x_i + \frac{b}{| w |})$$和$$\gamma = \min_{i=1,\ldots,N}\gamma_i$$。其中$\|w\|$为$w$的$L_2$范数，L2范数是指向量各元素的平方和然后求平方根。

间隔最大化

SVM 的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。
从原始问题演进：最大化几何间隔$\gamma$ = 最大化$\frac{\hat\gamma}{\|w\|}$ = 最大化$\frac{1}{\|w\|}$ (因为函数间隔的取值不影响最优化问题的解因此可直接令其为1) = 最小化$\frac{1}{2}{\|w\|}^2$ (改为最小化是为了符合凸优化问题的一般格式)

线性可分支持向量机学习算法——最大间隔法 maximum margin method

可以证明最大间隔分离超平面的存在唯一性。

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量 support vector，是使约束条件式等号成立的点。由下文可知，也就是训练数据中$\alpha^* \gt 0$的实例点。
$H_1: w \cdot x + b = 1$，$H_2: w \cdot x + b = -1$，在$H_1$和$H_2$上的点就是支持向量，两者之间的距离称为间隔 margin，等于$\frac{2}{\|w\|}$。(即函数间隔为1的情况下)(样本空间中任意点$x$到超平面$(w,b)$的距离可写为$r = \frac{|\mathbf{w}^T\mathbf{x} + b|}{\|\mathbf{w}\|}$。)

学习的对偶算法

对原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题 dual problem 得到原始问题 primal problem 的最优解，这就是线性可分支持向量机的对偶算法 dual algorithm。
优点：对偶问题更容易求解；自然引入核函数，进而推广到非线性分类问题。
原始最优化问题，等价于$\min_x \max_{w,b} L(w,b,\alpha)$：

写成对应的拉格朗日函数形式，引入$\mathbf{\alpha}$，每个样本有一个$\alpha$：

求得对偶问题$\max_{\alpha} \min_{w,b}L(w,b,\alpha)$，过程是上式对$\mathbf{w}$和$b$求偏导为0(计算里层的min)并代回(然后负号变正号于是max变min)：

求得该对偶最优化问题的解，$\alpha^*$。
根据两者相等时要满足 KKT 条件，从对偶最优化问题的解求得原始最优化问题的解$w^*, b^*$。

即可求出分离超平面和分类决策函数。

总结，此算法称为线性可分支持向量机的对偶学习算法：

例题

线性支持向量机与软间隔最大化

现实中训练数据是线性可分的情形较少，训练数据往往是近似线性可分的，这时使用线性支持向量机，或软间隔支持向量机。线性支持向量机是最基本的支持向量机。
对于噪声或例外，通过引入松弛变量$\xi_i$，使其”可分” (函数间隔加上松弛变量大于等于1，同时对每个松弛变量支付一个代价)，得到线性支持向量机学习的凸二次规划问题，其原始最优化问题是：

此为线性支持向量机。
可以证明$w$的解是唯一的，但$b$的解可能不唯一，而是存在于一个区间。
可以看出，当$C$无穷大时，上式迫使所有样本均满足约束，等价于硬间隔；当$C$取有限值时，允许一些样本不满足约束。

学习的对偶算法

对应的拉格朗日函数是：

通过求$L(w,b,\xi,\alpha,\mu)$对$w,b,\xi$的极小(偏导为0)并代回，得到对偶问题：

求得对偶问题的解$\alpha^*$。
根据对偶问题最优解得到原始问题最优解，KKT：

总结，此算法称为线性支持向量机学习算法：

对于线性支持向量机学习来说，其模型为分离超平面$w^* \cdot x + b^* = 0$及决策函数$f(x) = sign(w^* \cdot x + b^*)$，其学习策略为软间隔最大化，学习算法为凸二次规划。

支持向量

如图，分离超平面由实线表示，间隔边界由虚线表示，正例点由$\circ$表示，负例点由$\times$表示。图中还标出了实例$x_i$到间隔边界的距离$\frac{\xi_i}{\|w\|}$(点到分离超平面距离$\frac{1 - \xi_i}{\|w\|}$)。

软间隔的支持向量$x_i$或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。
若$\alpha^*_i \lt C$，则$\mu_i \gt 0$，进而$\xi_i = 0$，支持向量$x_i$恰好落在间隔边界上；若$\alpha_i^* = C$，则$\mu_i = 0$，$0 \lt \xi_i \lt 1$，则分类正确，$x_i$在间隔边界与分离超平面之间；若$\alpha_i^* = C$，$\xi_i = 1$，则$\xi_i$在分离超平面上；若$\alpha_i^* = C$，$\xi_i \gt 1$，则$x_i$位于分离超平面误分一侧。

合页损失函数

目标函数的第1项是经验损失或经验风险 empirical risk，用于描述模型与训练数据的契合程度，函数$L(y(w \cdot x + b)) = [1 - y(w \cdot x + b)]_+$称为合页损失函数 hinge loss function。下标$+$表示以下取正值的函数。


目标函数的第2项是正则化项，结构风险 structural risk，用于描述模型的某些性质。
$L_p$范数 norm 是常用的正则化项，其中$L_2$范数倾向于w的分量取值尽量均衡，即非零分量个数尽量稠密，而$L_0$范数和$L_1$范数则倾向于w的分量尽量稀疏，即非零分量个数尽量少。
原本可以用0-1损失函数的，不满足约束的样本就扣1。但0-1损失函数非凸、非连续，数学性质不太好，使用合页损失函数替代，称为替代损失。合页损失函数是0-1损失函数的上界。

三种常见的替代损失函数：

SVM 与 logistic regression 比较
如果此处不用hinge损失函数，用对率损失函数，发现几乎得到了logistic regression。实际上SVM 与 logistic regression的优化目标相近，性能也相当。
对率回归的优势主要在于其输出具有自然的概率意义，即在给出预测标记的同时也给出了概率，而SVM的输出不具有概率意义。
对率回归能直接用于多分类任务，SVM 为此则需要进行推广。
另外，由于hinge损失有平坦的0区域，使得 SVM 的解具有稀疏性，而对率损失是光滑的单调递减函数，不能导出类似支持向量的概念，因此对率回归的解依赖于更多的训练样本，其预测开销更大。

非线性支持向量机与核函数

核技巧

对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。
由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例与实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数来替换当中的内积。
核函数表示，通过一个非线性变换后的两个实例间的内积。具体地，$K(x,z)$是一个核函数，或正定核 positive definite kernel function，意味着存在一个从输入空间$\mathcal{X}$到特征空间$\mathcal{H}$的映射$\phi(x): \mathcal{X} \rightarrow \mathcal{H}$，对任意$x,z \in \mathcal{X}$，有$K(x,z) = \phi(x) \cdot \phi(z)$。
直接求$K(x,z)$比求$\phi$容易，核函数和映射函数是1:n的关系。

正定核

对称函数$K(x,z)$为正定核的充要条件如下：对任意$x_i \in \mathcal{X}, i = 1,2,\ldots,m$，任意正整数$m$，对称函数$K(x,z)$对应的Gram矩阵是半正定的。

常用核函数

一些经验，对文本数据通常采用线性核，情况不明时可先采用高斯核。




此外，也可通过函数组合得到：

非线性支持向量分类机

所以，在线性支持向量机学习的对偶问题中，用核函数$K(x,z)$替代内积，求解得到的就是非线性支持向量机。

非线性支持向量机学习算法：

序列最小最优化算法 SMO

todo，未细看。
sequential minimal optimization
要求解的二次规划问题的规模正比于训练样本数，开销很大。
SMO 算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足 KKT 条件为止。这样通过启发式的方法得到原二次规划问题的最优解。因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数很多，但在总体上还是高效的。


整个 SMO 算法包括两个部分：求解两个变量二次规划的解析方法；选择变量的启发式方法。

Ref

[1] 统计学习方法
[2] Support vector machine - Wikipedia
[3] 机器学习 - 周志华
[4] 机器学习实战
[5] SVM using Platt’s SMO
[6] https://zhuanlan.zhihu.com/p/29865057