SVM简单学习记录

第一部分：阅读专著学习基本概念

间隔与支持向量

分类学习的基本想法就是，基于训练集D，在样本空间中找到一个划分超平面，将不同的样本分开。

例如，在平面坐标系中找到一条线，使两种不同的类别的样本完美地被区分开，并能够以这条线继续正确划分更多的新样本。

这条线得尽量居中，“容忍度”更高。

在超平面两侧，距离平面最近的点到平面的距离和称为支持向量。要使支持向量最大，才能让超平面的“容忍度”更高。

由于latex打公式过于麻烦，且我并未完全理解数学推导的含义，所以这里仅仅写一点浅陋的通俗理解。作为阅读书籍的笔记。

对偶问题

以上为SVM的基本型，要求解超平面方程中的参数，来使支持向量最大。这是一个约束问题，可使用拉格朗日乘子法求解，得到对偶问题，过程中由拉格朗日乘子法的KKT条件可得：最终模型只与支持向量有关。

原问题关于超平面的本身的参数，但对偶问题就仅关于 \(\boldsymbol{\alpha}\) 了（每条样本都有一个拉格朗日乘子，\(\boldsymbol{\alpha}\)就是全部拉格朗日乘子组成的向量）

最终使用SMO算法求解

SMO算法

先固定\(\alpha_i\)以外的其他所有参数，然后求\(\alpha_i\)上的极值。具体步骤：

• 选取一对需更新的变量 \(\alpha_i\) 和 \(\alpha_j\)
• 固定 \(\alpha_i\) 和 \(\alpha_j\) 以外的参数，求解对偶问题式获得更新后的 \(\alpha_i\) 和 \(\alpha_j\)

启发式规则：使选取的两变量所对应的样本之间的间隔最大。

核函数

前面假设样本都是线性可分的，即存在这么一个超平面。但是现实中可能并不存在，对此可以将样本从原始空间映射到高维空间，使得在这个高维的样本空间中线性可分。

映射之后，求解约束问题涉及到计算样本之间映射之后的内积，由于特征空间维数可能很高，所以计算困难。于是使用核函数来代表内积，避免直接计算。

于是，核函数选择成为SVM的最大变数，常用的核函数有线性核、多项式核、高斯核（正态分布密度函数的右半）、拉普拉斯核、sigmoid核。

核也可以组合得到。

软间隔

对于是否线性可分的问题，即使我们找到了一个合适的特征空间能够使样本都线性可分，这也可能是过拟合导致的。

要缓解这个问题，一个办法是允许SVM在一些样本上出错，因此引入软间隔概念。

在软间隔下，正确分类的约束没了，转而在优化目标中使用“损失函数”，常见的有hinge、指数、对率损失。

优化目标中有一个常数C，当C无穷大时，退化为硬间隔，当C为有限值时，允许一些样本不满足约束，也就是划分错误。

推导得到的学习模型有一个共性：具有结构风险和经验风险，C用于对二者进行折中。从这一角度来说，结构风险成为正则化项，C称为正则化常数。各种范数Norm就是常用的正则化项。

支持向量回归

具有一个间隔带，落入间隔带的样本不计入损失。

核方法

基于核函数的学习方法

数学能力浅薄，难以充分理解瓜书，只能滤出以上寥寥几行文字

第二部分：阅读代码学习实现

线性SVM简单示例

代码来源：机器学习实战教程（八）：支持向量机原理篇之手撕线性SVM

文中的代码主要实现了简单的SMO算法，单次迭代流程如下：

1. 计算误差i和误差j，根据误差i判断KKT约束，不符合的才优化
2. 计算\(\alpha_j\)的上下界约束范围
3. 计算\(\eta\)，二次优化问题的二阶导数，用于计算\(\alpha_j\)的更新步长，如果非负，优化无意义，跳过
4. 根据误差调整 \(\alpha_i\) 和 \(\alpha_j\)
5. 用新的 \(\alpha_i\) 和 \(\alpha_j\) 更新偏置b

文中选取 \(j\) 的方式是随机，并未使用启发式规则。代码中更新\(\alpha\)的算式为： \[ \alpha_j^{new}=\alpha_j^{old}+\frac{y_j(E_i-E_j)}{\eta} \] 所以启发式规则的实际表现就是：选取\(|E_i-E_j|\)最大的 \(j\)

非线性SVM简单示例

代码来源：机器学习实战教程（九）：支持向量机实战篇之再撕非线性SVM

使用高斯核。SMO优化相同，在线性时，预测函数为： \[ f(\boldsymbol{x})=\sum_{i=1}^m{\alpha_iy_i\boldsymbol{x}_i^T\boldsymbol{x}+b} \] 使用核函数后变成： \[ f(\boldsymbol{x})=\sum_{i=1}^m{\alpha_iy_i\kappa(\boldsymbol{x}, \boldsymbol{x}_i)+b} \] 所以之前线性中出现\(\boldsymbol{x}_i^T\boldsymbol{x}\)的地方都要替代成核函数。

使用sklearn，只需要new一个SVC类就好，真是方便。。