支持向量机

本文最后更新于 1 分钟前，文中所描述的信息可能已发生改变。

支持向量机 概述 ​

支持向量机（SVM）是一种监督学习算法

• 支持向量 就是离分隔超平面最近的那些点。
• 机 就是表示一种算法，而不是表示机器

支持向量机 场景 ​

• 要给左右两边的点进行分类
• 明显发现：选择D会比B、C分隔效果好很多

支持向量机 原理 ​

SVM 工作原理 ​

对于图片中的两堆东西，我们想像成两种炸弹，中间的线需要保证距离最近的炸弹最远。

1. 寻找最大分类间距
2. 转而通过拉格朗日函数求优化问题

• 数据可以通过画一条直线就可以将他们完全分开，这组数据叫线性可分(linearly separable)数据，而这条分隔直线称为分隔超平面(separating hyperplane)
• 如果数据集上升到1024维，就需要1023维来进行分隔数据集，也就是需要 N-1 维的对象来分隔，这个对象叫做超平面(hyperlane)，也就是分类的决策边界。

  线性可分就是能用 超平面 分隔，线性不可分就是不能分隔。

寻找最大间隔 ​

为什么寻找最大间隔 ​

看起来就很安全，又安全又好

怎么寻找最大间隔 ​

点到超平面的距离

• 分割超平面函数间距：$y(x) = w^{T}x + b$
• 分类的结果：f(x) = sign($w^T$x + b)   其中sign表示 >0 为 1，<0 为 -1，=0 为 0 )
• 点到超平面的几何间距：$d(x) = (w^{T}x + b) / ||w||$（ ||w|| 表示 w 矩阵的二范数 => $\sqrt{w^T + w}$，点到超平面的距离也是类似的）
• 点到直线的距离公式：$d = \left | \frac{Ax_0+By_0+C}{\sqrt{A^2+B^2} } \right |$

拉格朗日乘子法

• 。。。。。推导详见参考网站或《统计学习方法》

松弛变量(slack variable)

• 。。。。。详见参考网站

SMO 高效优化算法 ​

• SVM 有很多种实现，最流行的一种实现是：序列最小优化(Sequential Minimal Optimization，SMO)算法。
• 还会介绍一种称为核函数(kernel)的方式将SVM扩展到更多数据集上。
• 注意：SVM几何含义比较直观，但其算法实现较为复杂，牵扯到大量数学公式的推导

序列最小优化 ​

• 创建作者：John Platt
• 创建时间：1996 年
• SMO用途：用于训练 SVM
• SMO目标：求出一系列 alpha 和 b，一旦求出 alpha，就很容易计算出权重向量 w 并得到分割超平面
• SMO思想：是将大优化问题分解为多个小优化问题来求解的
• SMO原理：每次循环选择两个 alpha 进行优化处理，一旦找出一对合适的 alpha，那么就增大一个同时减少一个
  • 这里指的合适必须要符合一定的条件
    1. 这两个 alpha 必须要在间隔边界之外
    2. 这两个 alpha 还没有进行过区间化处理或者不在边界上
  • 之所以要同时改变 2 个 alpha ；原因是有约束条件${\textstyle \sum_{i=1}^{m}} a_i * label_i = 0$，如果只修改一个 alpha ，很可能导致约束条件失效。

SMO 伪代码 ​

创建一个 alpha 向量并将其初始化为0向量
当迭代次数小于最大迭代次数时(外循环)
    对数据集中的每个数据向量(内循环): 
        如果该数据向量可以被优化
            随机选择另外一个数据向量
            同时优化这两个向量
            如果两个向量都不能被优化，退出内循环
    如果所有向量都没被优化，增加迭代数目，继续下一次循环

SVM 开发流程 ​

收集数据: 可以使用任意方法。
准备数据: 需要数值型数据。
分析数据: 有助于可视化分隔超平面。
训练算法: SVM的大部分时间都源自训练，该过程主要实现两个参数的调优。
测试算法: 十分简单的计算过程就可以实现。
使用算法: 几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，对多类问题应用SVM需要对代码做一些修改。

SVM算法特点 ​

• 优点：泛化（由具体的、个别的扩大为一般的，就是说: 模型训练完后的新样本）错误率低，计算开销不大，结果易理解。
• 缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适合于处理二分类问题。
• 使用数据类型：数值型和标称型数据。

核函数(kernel) 的使用 ​

• 对于线性可分的情况效果明显
• 对于非线性的情况也一样，此时需要用到一种叫做和函数(kernel)的工具将数据转化为分类器易于理解的形式

利用核函数将数据映射到高维空间 ​

• 使用核函数可以将数据从某个特征空间到另一个特征空间的映射。（通常情况下，这种映射会将低维特征空间映射到高维空间。）
• 可以把核函数想象成一个包装器 (wrapper) 或者是接口 (interface) ，它能将数据从某个很难处理的形式转换成为另一个较容易处理的形式。
• 经过空间转换后，低维需要解决的非线性问题，就变成了高维需要解决的线性问题
• SVM 优化特别好的地方，在于所有的运算都可以写成内积，也即是两个向量相乘，得到单个标量或者数值，内积替换成核函数的方式被称为核技巧(kernel trick)或者核"变电"(kernel substation)
• 核函数并不仅仅用于支持向量机，很多其他的机器学习算法也都用到核函数。
• 最流行的核函数：径向基函数(radial basis function)，其高斯版本具体公式如下图