SVM

概述

SVM应用广泛，包括

1. 有监督学习

   1. 线性二分类与多分类(Linear SVC)

   2. 非线性二分类与多分类(SVC)

   3. 普通连续型变量的回归(SVR)

   4. 概率型连续变量的回归(Bayesian SVM)

2. 无监督学习

   1. 支持向量聚类(Support Vector Clustering)

   2. 异常值检测(One-class SVM)

3. 半监督学习

   1. 转导支持向量机(Transductive SVM)

应用

1. 文本分类

2. 图像分类

   1. 手写数字

   2. 人脸识别

   3. 图像分割

3. 蛋白质分类

原理

在样本的假设空间中找出一个超平面作为决策边界，使模型在数据上的分类误差尽量接近于小，尤其是在未知数据集上的泛化误差尽量小。

超平面：在几何中，超平面是一个空间的子空间，它是维度比所在空间小一维的空间。 如果数据空间本身是三维的，则其超平面是二维平面，而如果数据空间本身是二维的，则其超平面是一维的直线。 在二分类问题中，如果一个超平面能够将数据划分为两个集合，其中每个集合中包含单独的一个类别，我们就说这个超平面是数据的“决策边界“。

边际(margin)：决策边界往两个类别平移，直到碰到离这条决策边界最近的数据点之间的距离。

过拟合：边际很小的情况。在训练集表现很好却在测试集表现糟糕的模型。

支持向量机：找出边际最大的决策边界，来对数据进行分类的分类器。又叫最大边际分类器。

三层理解

最优化问题：最小化损失函数来求解决策边界

一、损失函数

1. 定义决策边界的数学表达，并基于此表达定义分类函数

2. 为寻找最大边际引出损失函数：

对非线性数据的解决

1. 软间隔：添加松弛系数作为惩罚项，以允许部分样本点在边界之内存在

2. 使用非线性转化来升高原始数据的维度，使用核函数在低维空间中进行计算，以求解出高维空间中的线性超平面

二、拉格朗日函数

1. 为求解能够使边际最大化的w和b，引入拉格朗日因子a

2. 引入拉格朗日对偶函数，使求解w和b的过程转化为对a的求解（KKT）

3. 使用SMO或梯度下降等方法求解a，再根据a解出w和b，最终找出决策边界和分离决策函数

三、使用数学证明过程一和过程二

核技法（Kernel Trick）

一种能够使用数据原始空间中的向量计算来表示升维后的空间中的点积结果的数学方法。具体表现为：$K(u,v)=\phi(u)\cdot\phi(v)$ 这个原始空间中的点积函数K(u, v)被叫做核函数

解决三个问题

1. 无需担心 $\phi$ 是什么，因为非线性SVM中的核函数都是正定核函数(positive definite kernel functions)，它们都满足美世定律(Mercer's theorem)，确保了高维空间中任意两个向量的点积一定可以被低维空间中的这两个向量的某种计算来表示（多数时候是点积的某种变换）
2. 使用核函数计算低维度中的向量关系比计算原本的 $\phi(x{i})\cdot\phi(x{test})$ 要简单太多了
3. 因为计算是在原始空间中进行，所以避免了维度诅咒的问题

核

常用核函数——来自西瓜书

核函数怎么选

1. 如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM

2. 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel

3. 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况

优缺点

1. 优点

   1. 效果好：一旦确定好核函数和超参，分类效果（正确性）非常好

   2. 速度快：接受训练后，对新的观测数据，只需判断坐标点位于分界线的哪一侧即可

   3. 分类和回归：通过将分类输入转换成数值输入，可以令SVM同时支持分类数据和数值数据

2. 缺点

   1. 没有通用的配置：迁移到不同的业务场景时，需要自行通过大量数据集以交叉验证等方法确认核函数和超参

   2. 可解释性：存在向高维空间的变换，分类过程就像一个黑盒，难以解释

参考

1. 《集体智慧编程》

2. 支持向量机通俗导论（理解SVM的三层境界）

3. 核函数和非线性SVM

4. 从软间隔到线性支持向量机