飞桨PaddlePaddle|李宏毅机器学习特训营之支持向量机(二)

16
四月
2021

SVM支持向量机(二)

  • 1. Linear SVM
  • 2. 对偶问题
  • 3. 核函数
  • 4. 深度学习和SVM
  • 参考文献

在SVM支持向量机(一)中,我们介绍了SVM的损失函数 hinge loss。本文将介绍SVM的另一个亮点 kernel trick。在介绍 kernel trick 之前,我们先来介绍线性可分的SVM。

1. Linear SVM

Linear SVM 使用线性回归的假设函数作为假设函数 f(x)。使用 hinge loss 作为损失函数,此外还加入了正则项。hinge loss 和 正则项都是凸函数,因此损失函数也是凸函数。此时,也可以使用梯度下降法寻找模型的最优的参数。
在这里插入图片描述
下面给出梯度下降法的推导过程,为了简化推导,省去了正则项。
在这里插入图片描述

首先让损失函数对 w 求偏导数,f(x) 和 w 存在函数关系,因此先让损失函数对f(x)求偏导,再让 f(x) 对 w 求偏导,再将二者做乘积。下面引入slack variable的概念,将 hinge loss 表示为松弛因子。
在这里插入图片描述
当损失函数L最小化时,两个红色实线框中的条件可以完全等价,下面的红色实线框中的约束条件,就是常用的"软间隔支持向量机"。每个样本都有一个对应的松弛变量, 用以表征该样本不满足约束的程度。

2. 对偶问题

由于SVM目标函数的结构特殊,因此还可以通过求解与原问题等价的对偶问题得到原始问题的最优解,这就是线性可分条件下支持向量机的对偶算法。经过拉格朗日函数的推导,可以得到 w* 的表达式。本课程中,老师从深度学习的角度解读了w* 的表达式。w* 可以表示为样本点的线性组合。α通常是稀疏的,α 不为 0 的 x 被称为支持向量。下面来做具体推导:

在这里插入图片描述
参数 w 的更新公式如上图所示,将 c(w) 带入 w 的更新公式,如下图所示。如果将 w 初始化为0,则 w 等于 -η * ∑ cⁿ(w) xⁿ ,即xⁿ 的一个线性组合。因此 w* 可以表示为样本点的线性组合。由于hinge loss 对 f(x) 求偏导通常为0,因此 c(w) 也通常为0,进而 α* 也通常是稀疏的。

在这里插入图片描述
下面继续来求解 w*。具体推导过程如下图所示:
在这里插入图片描述

  1. 首先,将 w 的表达式带入到 f(x) 中,得到新的假设函数。对应新点 x 的预测,只需要计算它与训练数据点的内积即可,内积还可以用核函数K来代替。
  2. 现在只有 α 是未知的,我们需要找到最优的 α ,使 loss function最小化。这里就涉及到了kernel trick。
    在这里插入图片描述

3. 核函数

核函数是特征空间的隐式映射。在线性不可分的情况下,支持向量机首先在低维空间中完成计算,然后通过非线性映射(核函数)将输入空间映射到一个高维特征空间,最终在高维特征空间中构造最优分类超平面,从而把平面上本身不好分的非线性数据分开,如下图所示。
在这里插入图片描述
在核函数出现之前,我们使用原始的方法,建立非线性学习器。首先使用一个非线性映射将数据变换到一个特征空间F,然后在特征空间使用线性学习器分类。对偶形式就是线性学习器的一个重要性质,这意味着假设可以表达为训练点的线性组合,因此决策规则可以用测试点和训练点的内积来表示。
如果有一种方式可以 在特征空间中直接计算内积〈φ(xi )· φ(x) 〉,就像在原始输入点的函数中一样,就有可能将两个步骤融合到一起建立一个非线性的学习器,这样直接计算法的方法称为核函数方法。
有时直接计算核函数可能比先做特征变换再对变换后的特征做内积要快。下面给出了一个实例。
在这里插入图片描述
在这里插入图片描述
如果 x 有INF维,则效果更明显,直接计算核函数更快。下面给出一个RBF核函数的例子。
在这里插入图片描述

4. 深度学习和SVM

下面我们来讨论下深度学习和SVM的关系。对于分类问题,深度学习模型一般先将特征 x 做特征变换,得到Φ(x),然后再通过线性分类器分类。SVM则是先将输入特征空间基于核函数映射到高维空间,然后再通过线性分类器(hinge loss)分类。其实二者很相似。
在这里插入图片描述

参考文献

  1. 支持向量机通俗导论
  2. 《机器学习》周志华
  3. 李宏毅机器学习特训营的课程链接
    课程连接
TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员