第七章 支持向量机

引入

SVM三要素概述
支持向量机是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机。

支持向量机还包括核技巧,这使他成为实质上的非线性分类器。

支持向量机的学习策略就是间隔最大化,可形式化为求解一个凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题。

支持向量机的学习算法就是求解凸二次规划的最优化算法。

支持向量机的种类有

由简至繁对应别名对应数据集状态
线性可分支持向量机硬间隔支持向量机(硬间隔最大化)线性可分
线性支持向量机软间隔支持向量机(软间隔最大化)近似线性可分
非线性支持向量机-(核技巧及软间隔最大化)线性不可分

关于核函数
当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时,核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。

核函数可以学习非线形支持向量机,等价于隐式地在高维的特征空间学习线性支持向量机。

线性可分支持向量机与硬间隔最大化

线性可分支持向量机

考虑二分类问题。
假设有

  1. 假设输入空间与特征空间为两个不同的空间,输入空间为欧氏空间或离散集合,特征空间为欧氏空间或希尔伯特空间。
  2. 训练数据集线性可分。

学习的目标是在特征空间找到一个分离超平面。

当训练数据集线性可分的时候,存在无穷多个分离超平面。感知机采用的是误分类最小的策略,求得分离超平面,此时的解有无穷多个。线性可分支持向量机采用间隔最大化求最优分离超平面,这时,解是唯一的。

定义7.1(线性可分支持向量机)给定线性可分训练数据集,通过间隔最大化等价地求解相应的凸二次规划问题学习得到的分离超平面为第七章 支持向量机
以及相应的分类决策函数第七章 支持向量机称为线性可分支持向量机。

函数间隔和几何间隔

一般来说,一个点距离分离超平面的远近可以表示分类预测的确信程度。

定义7.2(函数间隔)对于给定的训练数据集第七章 支持向量机和超平面第七章 支持向量机,定义超平面第七章 支持向量机关于样本点第七章 支持向量机的函数间隔为第七章 支持向量机
定义超平面第七章 支持向量机关于训练数据集第七章 支持向量机的函数间隔为第七章 支持向量机关于第七章 支持向量机中所有样本点第七章 支持向量机的函数间隔之最小值,即第七章 支持向量机

虽然函数间隔能表示点到超平面的一种距离,但是是由缺陷的。如果成比例地改变系数的话,超平面不变,函数间隔会改变。因此我们需要对超平面的法向量加约束。此时的函数间隔称为几何间隔。

定义7.3(几何间隔)对于给定的训练数据集第七章 支持向量机和超平面第七章 支持向量机,定义超平面第七章 支持向量机关于样本点第七章 支持向量机的几何间隔为第七章 支持向量机
同理能得到第七章 支持向量机

于是,函数间隔和几何间隔的关系是第七章 支持向量机

间隔最大化

支持向量机的学习策略是正确划分数据且几何间隔最大。

不仅能将正负例分开,而且对最难分的点实例点(离超平面最近的点)也有足够大的确信度。

最大间隔分离超平面

基于间隔最大化的约束最优化问题表示为:
第七章 支持向量机

考虑函数间隔和几何间隔的关系的话,上述式子可以用函数间隔表示:
第七章 支持向量机

因为函数间隔的取值对优化的解不产生影响,所以不妨可以假设其为1,那么目标函数就成了最大化第七章 支持向量机,即最小化第七章 支持向量机。于是,最优化问题可以表示为:第七章 支持向量机

这是一个凸二次规划问题。

算法7.1(线性可分支持向量机学习算法——最大间隔法)
输入:线性可分数据集;
输出:最大间隔分离超平面和分类决策函数。
(1) 构造并求解约束最优化问题。
(2)由此得到分离超平面和分类决策函数。

至此,我们一共学习的七个模型中,有四个需要用最优化的知识求解,即感知机、逻辑斯蒂回归、最大熵模型以及支持向量机。

定理7.1(最大间隔分离超平面的存在唯一性)若训练数据集第七章 支持向量机线性可分,则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

支持向量和间隔边界

在线性可分情况下,训练数据集的样本点中与分离超平面最近的样本点的实例称为支持向量。支持向量是使约束条件等号成立的点,即第七章 支持向量机

第七章 支持向量机

注意到支持向量所在的超平面是相互平行的,分离超平面位于他们中间。间隔依赖于分离超平面的法向量第七章 支持向量机,等于第七章 支持向量机

第七章 支持向量机称为间隔边界

学习的对偶算法

支持向量机这篇博客中介绍得很清楚,此处不再赘述。

总结来说:

  1. Lagrange乘子法将约束问题转化为无约束问题;
  2. 因为minmax不方便求解,所以需要转化为对偶形式。两者之间的解只在特定条件下等价;
  3. 计算过程先是通过导数得到第七章 支持向量机的值,然后代入式子。之后将max转化为min之后求解第七章 支持向量机。最后将第七章 支持向量机代入第七章 支持向量机

定理7.2第七章 支持向量机是对偶最优化问题的解,那么存在下标第七章 支持向量机,使得第七章 支持向量机,并可按照下式求得原始最优化问题的解第七章 支持向量机

算法7.2

  1. 构造并求解约束最优化问题;
  2. 按照定理7.2计算第七章 支持向量机
  3. 求得分离超平面。

定义7.4(支持向量)考虑原属最优化问题及对偶优化问题,将训练数据集中,对对应于第七章 支持向量机的样本点第七章 支持向量机的实例第七章 支持向量机称为支持向量。

为什么第七章 支持向量机就行呢?这是因为这个i啊,他满足约束条件,自然和我们之前的支持向量定义满足了。

线性支持向量机与软间隔最大化

线性支持向量机

线性可分问题的支持向量机学习方法,对线性不可分训练数据是不适用的,因为上述方法的不等式约束并不能成立。

训练数据中存在特异点,线性不可分意味着某些样本点不能满足函数间隔大于等于1的约束条件(第七章 支持向量机)。为了解决这个问题,引入了松弛变量第七章 支持向量机,使得函数间隔加上松弛变量大于等于1,这样约束条件就变为了第七章 支持向量机
同时,对每个松弛变量第七章 支持向量机,支付一个代价第七章 支持向量机,目标函数变为了第七章 支持向量机C大时对误分类的惩罚大,反之小。

这一目标函数包含两层含义,分别是:第一项尽量小即函数间隔大;第二项尽量小即误分类点数少。C是调和二者的系数。

线性不可分的线性支持向量机可以写为如下形式的凸二次规划:
第七章 支持向量机

因为该问题是一个凸二次规划问题,因而解是存在的。可以证明第七章 支持向量机是唯一的,但第七章 支持向量机不唯一,而是存在于一个区间。

定义7.5(线性支持向量机) 对于给定的线性不可分的训练数据集,通过求解凸二次规划问题,得到的分离超平面为第七章 支持向量机以及相应的分类决策函数第七章 支持向量机称为线性支持向量机。

学习的对偶算法

此处同样参照先前的链接。

定理7.3第七章 支持向量机是对偶问题的一个解,若存在第七章 支持向量机的一个分量第七章 支持向量机第七章 支持向量机,则原始问题的解与定力7.2的形式一致。

算法7.3 和 算法7.2保持一致,也是先求第七章 支持向量机,再求第七章 支持向量机,最后得到分离超平面。

支持向量

在线性不可分的情况下,将对偶问题的解第七章 支持向量机中对应于第七章 支持向量机的样本点的实例称为支持向量。

软间隔的支持向量或者在间隔边界上,或者在间隔边界与分离超平面之间,或者在分离超平面误分类一侧。

所谓支持向量,应该是能影响超平面分类的向量。

在软间隔支持向量机中,间隔边界依然是满足第七章 支持向量机的,不过我这个支持向量不一定在它上面了。

准确来说,它应该在函数间隔第七章 支持向量机的位置,这个支持向量离间隔边界的几何距离为第七章 支持向量机

位置关系参数情况
在间隔边界上第七章 支持向量机
在间隔边界和分离超平面之间第七章 支持向量机
在分离超平面上第七章 支持向量机
误分类第七章 支持向量机

这些参数是怎么得到的呢?

我们关注一下原始优化问题的Lagrange函数:第七章 支持向量机

进行简单的改写:第七章 支持向量机

首先,第七章 支持向量机,超过的话,就说明,这个点在间隔边界外,不存在需要松弛变量的情况。

合页损失函数

线性支持向量机还有另一种解释,就是最小化以下目标函数:第七章 支持向量机

目标函数的第一项是经验损失或经验风险,函数第七章 支持向量机

这就是定理7.4:线性支持向量机原始最优化问题等价于最优化上述目标函数。

第七章 支持向量机

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

核技巧

非线性分类问题

第七章 支持向量机

如果能用第七章 支持向量机中的一个超曲面将正例正确分开,则称这个问题为非线性可分问题。

非线性问题往往不好求解, 希望能用解线性分类问题的方法解决这个问题,所采取的方法是进行一个非线形变换,将非线形问题转化为线性问题。

比如说,我们可以通过一个非线形变换,将上图中的椭圆转变为下图中的之前。

第七章 支持向量机

以这个问题为例,我们不妨设原空间为第七章 支持向量机第七章 支持向量机,新空间为第七章 支持向量机第七章 支持向量机

我们定义映射为第七章 支持向量机

于是,原空间中的椭圆就变为了新空间中的直线第七章 支持向量机

这个例子说明,用线性分类方法求解非线性分类问题分为两个步骤:

  1. 首先使用一个变换将原空间的数据映射到新空间;
  2. 然后在新空间里用线性分类学习方法从训练数据中学习分类模型。

将核技巧应用到支持向量机的基本思想是:通过一个非线性变换将输入空间对应于一个特征空间(希尔伯特空间),使得在输入空间中的超曲面模型对应于特征空间中的超平面模型。

核函数的定义

定义7.6(核函数)两个空间还是惯例,如果存在一个从第七章 支持向量机的映射第七章 支持向量机使得对所有第七章 支持向量机,函数第七章 支持向量机满足条件第七章 支持向量机
则称第七章 支持向量机为核函数,第七章 支持向量机为映射函数,其中的运算是内积(注意,这里的第七章 支持向量机和之前的那个椭圆无关)。

核技巧的基本思想是:在学习与预测中只定义和函数,而不显式地定义映射函数第七章 支持向量机。这是因为,直接计算第七章 支持向量机比较容易。

值得一提的是,这个希尔伯特空间一般是高维甚至无穷维的。

第七章 支持向量机

核函数表示的是两个希尔伯特空间中的向量的内积。

核技巧在支持向量机中的应用

线性支持向量机的目标函数可化为为第七章 支持向量机

同样,分类决策函数也变成了第七章 支持向量机

在实际应用中,往往需要依赖领域知识来选择核函数,核函数选择的有效性需要通过实验验证。

正定核

不构造映射第七章 支持向量机,能否直接判断一个给定的函数第七章 支持向量机是不是核函数?

通常所说的核函数是正定核,判断一个正定核的充要条件是:设第七章 支持向量机是对称函数,则第七章 支持向量机是正定核函数的充要条件是对任意第七章 支持向量机第七章 支持向量机对应的Gram矩阵(这个东西在感知机的对偶形式见过,就是样本之间的内积矩阵):第七章 支持向量机
是半正定矩阵。

非线性支持向量机

从非线性分类训练集,通过核函数与软间隔最大化,或凸二次规划,学习得到的决策函数第七章 支持向量机这称为非线性支持向量机,第七章 支持向量机为正定核。

线性可分支持向量机的两个支持向量对应的第七章 支持向量机是相等的,因此得到的第七章 支持向量机是唯一的。因为要求是第七章 支持向量机,所以线性支持向量机对应的第七章 支持向量机和前一种是一致的,但是因为第七章 支持向量机不一样,所以b也会有好多。

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
上一篇 2022年5月30日 上午11:10
下一篇 2022年5月30日 上午11:12

相关推荐

本站注重文章个人版权,不会主动收集付费或者带有商业版权的文章,如果出现侵权情况只可能是作者后期更改了版权声明,如果出现这种情况请主动联系我们,我们看到会在第一时间删除!本站专注于人工智能高质量优质文章收集,方便各位学者快速找到学习资源,本站收集的文章都会附上文章出处,如果不愿意分享到本平台,我们会第一时间删除!