0%

支持向量机SVM总结

发表于 更新于 分类于 ，

对SVM算法的总结

一、背景描述

SVM是寻找一个最优的决策边界，使使用该边界区分的两个类别最近的样本最远。

SVM是一种二分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。（间隔最大化是它的独特之处），通过该超平面实现对未知样本集的分类。

  • 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机。
  • 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机。
  • 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

image-20191019173035500

二、转化为数学问题

回忆解析几何，点（x，y）到直线（Ax+By+C=0）的距离d为

拓展到n维空间

image-20191019173508132

距离d为

其中 w为

对于如下场景

image-20191019173912301

可以有如下推到，将两个类别分开。

image-20191019174203829

可以推导为

image-20191019174233599

从而整个，支持向量的边界为

image-20191019174314659

最后，重新命名，w和b，有

image-20191019174531059

将上述公式进行整合，y取1或者-1，得到：

image-20191019175152796

将上述问题，转化成数学问题：

image-20191019175235482

image-20191101155707698

如何解决上述数学问题呢？引入线性可分支持向量机的对偶算法。

image-20191101155929877

为什么要转为对偶问题？

(a) 目前处理的模型严重依赖于数据集的维度d，如果维度d太高就会严重提升运算时间；

(b) 对偶问题事实上把SVM从依赖d个维度转变到依赖N个数据点，考虑到在最后计算时只有支持向量才有意义，所以这个计算量实际上比N小很多。

三、Soft Margin3和SVM的正则化

image-20191019175918107

为了提高决策函数的泛化能力，需要有一定的容错能力。

image-20191019180334971

数学表达改进，其中C为超参数，平衡第一项与第二项的权重。该形式也是L1正则。

image-20191019180741763

image-20191019180858938

四、核函数

image-20191020122952517

核函数的引入

在 SVM 中引入核方法便可使得 SVM 变为非线性分类器，给定非线性可分数据集 ，如下图所示，此时找不到一个分类平面来将数据分开，核方法可以将数据投影到新空间，使得投影后的数据线性可分。

img

​ image-20191101161129704

核函数的优点

核技巧的好处在于不需要显式的定义特征空间与映射函数，只需要选择一个合适的核函数即可。综上核函数是用来免去显式计算高维变换的，直接用低维度的参数带入核函数来等价计算高维度的向量的内积。

有效的核函数

什么样的函数可以作为一个有效核函数呢？答案是只要满足 Mercer 定理 即可。满足K函数对应的Gram矩阵的半正定性。

常用的核函数

image-20191101161700745

五、SMO（序列最小最优化算法）

如何高效地实现支持向量机的学习？引入SMO

固定其他变量，选择2个变量（一个是违法KKT最严重的变量，另一个是变量的最大化）

第一：两个变量的二次规划求解问题

第二：变量的选择

image-20191101162851332

SVM优缺点

优点：

  1. 非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；

  2. 对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；

  3. 支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量；
    SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。

  4. 小样本集上分类效果通常比较好。
    少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
    ①增、删非支持向量样本对模型没有影响;

    ②支持向量样本集具有一定的鲁棒性;

    ③有些成功的应用中,SVM 方法对核的选取不敏感

    SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。

缺点：

  1. SVM算法对大规模训练样本难以实施。由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间（上面有讲）。有比较多的改进算法及分布式的方法研究（以后补上）。
  2. 用SVM解决多分类问题存在困难。
  3. 传统的SVM就是解决二分类问题的，上面有介绍不少解决多分类问题的SVM技巧，不过各种方法都一定程度上的缺陷。
  4. 对缺失值敏感，核函数的选择与调参比较复杂。

参考&致谢

https://blog.csdn.net/qq_32742009/article/details/81838152

觉得不错？