SVM

SVM

[TOC]

1 整体概览

  • 什么是SVM
    SVM 是一种二分类模型。它的基本思想是在特征空间中寻找间隔最大的分离超平面使数据二分类
  • 线性可分支持向量机——硬间隔支持向量机
  • 线性支持向量机——软间隔支持向量机
  • 非线性支持向量机——核技巧

2 线性可分支持向量机

2.1 函数间隔与几何间隔

  • 分离超平面:$w^{} \cdot x + b^{}=0$
  • 点到超平面的距离:正的一侧:$\gamma_{i}=\frac{1}{|w|}(w \cdot x_i +b) $ 负的一侧:$\gamma_{i}=-\frac{1}{|w|}(w \cdot x_i +b) $
  • 由于$w \cdot x+b$与类标记y的符号是否一致能代表分类正确,定义:
    • 超平面对于样本点$(x_i,y_i)$的函数间隔:$\hat{\gamma}_{i}=y_{i}\left(w \cdot x_{i}+b\right)$
    • 超平面对于数据集的函数间隔:$\hat{\gamma}=\min \hat{\gamma}_{i}$
    • 超平面对于样本点$(x_i,y_i)$的几何间隔:$\gamma_{i}=y_i\frac{1}{|w|}\left(w \cdot x_{i}+b\right)$
    • 超平面对于数据集的几何间隔:$\gamma=min{ \gamma_{i}}$

2.2 间隔最大化

  • 最大间隔分离超平面可以表示为约束优化问题:

    • 最大间隔求分离超平面
    • 将几何间隔改为函数间隔:

    • 将函数间隔固定为1,最大化改为最小化(得到凸二次规划问题)

2.3 学习的对偶算法

  • 拉格朗日对偶问题

    • 转化为最小约束的问题:

    • 拉格朗日乘子法(带约束的问题转为无约束的问题),这也是损失函数
      在这里,对于系数$\alpha$,非支持向量的系数为0,支持向量的系数大于0

  • 对偶问题求解 —— 求$\min_{w,b} L(w,b,a)$ - 原始问题的对偶问题极大极小问题,后面两部分始终小于0

    • 对w、b求偏导:

      得到:

    • 将其带入拉格朗日函数

  • 对偶问题求解 —— 求$\min_{w,b} L(w,b,a)$对a的极大

    • 对偶问题为

    • 极大转换成极小

    • 假设有解:$\mathrm{a}^{}=\left(\alpha_{1}^{}, \alpha_{2}^{}, \ldots, \alpha_{N}^{}\right)^{\mathrm{T}}$,则最优化的解为:

    • 并可以证明满足KKT的条件。

    • 补充:极小问题满足二次规划问题,通过代入数据集后求解a从而求得w和b

3 线性(不可分)支持向量机与软间隔

3.1 引入软间隔后的问题

  • 引入松弛变量后的约束

  • 引入松弛变量后的目标函数

  • 线性不可分的学习问题变为如下凸二次规划问题:

3.2 对偶问题与求解

  • 拉格朗日函数为

  • 对偶问题求解 —— 求$\min_{w,b,\xi} L(w, b, \xi, \alpha, \mu)$

    • 对各变量的偏导数

    • 偏导数为0的结果

  • 对偶问题求解 —— 对$\min_{w,b,\xi} L(w, b, \xi, \alpha, \mu)$求a的极大

  • 利用等式约束消去u,最终的结果
  • 并可以证明满足KKT的条件。

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

4.1 核函数

  • 非线性带来高维转换(高维空间更容易线性可分)
  • 对偶表示带来内积
  • 核函数的定义

4.2 正定核

  • 定义映射并构成向量空间S
  • 在S上定义内积,构成内积空间
  • 将S完备化构成希尔伯特空间

4.3 常用的核函数

  • 多项式核函数
  • 高斯核函数
  • sigmoid核函数

小结

 SVM算法的主要优点有:

  1. 解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果。
  2. 仅仅使用一部分支持向量来做超平面的决策,无需依赖全部数据。
  3. 有大量的核函数可以使用,从而可以很灵活的来解决各种非线性的分类回归问题。
  4. 样本量不是海量数据的时候,分类准确率高,泛化能力强。

 

SVM算法的主要缺点有:

  1. 如果特征维度远远大于样本数,则SVM表现一般。
  2. SVM在样本量非常大,核函数映射维度非常高时,计算量过大,不太适合使用。
  3. 非线性问题的核函数的选择没有通用标准,难以选择一个合适的核函数。
  4. SVM对缺失数据敏感。

reference:

《统计学习方法》
《机器学习》——西瓜书
Bilibili白板推导
https://www.cnblogs.com/pinard/p/6113120.html

文章作者: 长腿咚咚咚
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 长腿咚咚咚 !
评论
 上一篇
决策树 决策树
1. 决策树[TOC] 1.1 简介决策树是一个分而治之的递归过程。 构建根节点,初始化特征集合和数据集合; 选择最优特征,并划分子集,更新数据集合和特征集合; 继续划分直到所有训练数据基本划分正确。 决策树学习的关键问题:特征选择、
2019-12-02
下一篇 
机器学习/概率图模型-HMM 机器学习/概率图模型-HMM
[TOC] 1 马尔可夫模型1.1 概念导入在某段时间内,交通信号灯的颜色变化序列是:红色 - 黄色 - 绿色 - 红色。 在某个星期天气的变化状态序列:晴朗 - 多云 - 雨天。 像交通信号灯一样,某一个状态只由前一个状态决定,这就是一个
2019-11-28
  目录