一方面,线性可分支持向量机只适用于线性可分的训练数据集,对于线性不可分的训练数据集则是无能为力的。
另一方面,即使训练数据集线性可分,线性可分支持向量机强依赖于离分类超平面最近的样本[3],过拟合的风险很大。
这时候就需要有一定容错能力的分类模型,线性支持向量机,或者叫软间隔支持向量机,就可以做到这样的容错性。
这里我采用周志华老师西瓜书[2]的思路来整理这部分。
对于线性可分支持向量机,要求所有样本满足以下约束
而软间隔则允许某些样本不满足这样的约束。
在最大化间隔的同时,不满足约束的样本要尽量少。此时,优化目标可以写为
其中, 是一般化的损失函数, 被称作惩罚参数,调节间隔最大化和参数惩罚这二者关系。
我们先看惩罚参数 。当 值较大时对误分类惩罚较大,特别地,当C取无穷大时,所有样本都要满足式 约束,模型等价于线性可分支持向量机[3];当 取有限值时,模型允许一些样本不满足约束。
接下来讨论损失函数 。当 使用不同的损失函数时的模型状态,周志华老师的西瓜书[2]有简单讨论。当 是合页损失函数时,模型就是线性支持向量机。李航老师《统计学习方法(第二版)》[1]的相关章节证明了线性支持向量机和基于合页损失函数的优化问题的等价性。合页损失函数如下
图1[2]
当 时,式 可重写为
引入松弛变量 ,将上式再重写为
优化问题一:
与线性可分支持向量机类似,线性支持向量机(式 )的拉格朗日对偶函数如下
原问题(式 )是凸优化问题,则优化问题 与原问题等价。
第一步, 求 对 的极小值。
得
将式 代入式 ,可得
第二步, 求 对 的极大值,即得对偶问题。
这里需要注意,式 等号右边表达式没有 ,直接求解对 的极大值即可。对偶问题如下
上式中,因为 不在最优化表达式中,可以利用等式约束消去,简化约束。再把求极大转换成求极小,得到对偶问题如下
优化问题二:
第三步, 求解分类超平面和分类模型。
对于已求解出优化问题二(式 )的最优解 ,则类似于线性可分支持向量机[3]的推导过程。
原问题(式 )是凸优化问题,则满足KKT条件的点是原问题和对偶问题的最优解(具体请参见[4])
根据式 可得
观察式 、 和 ,先看式 ,当 时,有
再看式 ,当 时,有
此时再看式 ,当 时,必有 ,综上讨论,当 时,有
再将式 代入上式,并于式 联立,可得线性支持向量机的最优分类超平面参数为
这里需要注意,在李航老师《统计学习方法(第二版)》[1]相关章节中,和式 相同表达的式子是不严谨的,如果没看到这一段,这句话略过。
线性支持向量机的支持向量会复杂一些。如下图
首先, 定义 的样本点 为支持向量。
其次, 每个支持向量 到其对应的间隔边界的距离为 。推导过程如下。
点到超平面的距离公式为:
先看正类,正类的间隔边界超平面为: ,对应的点到间隔边界超平面的距离公式为: 。对于正例的支持向量,有 ,根据式 ,有 ,代入距离公式,即可到结论。
负类推导过程类似。
再次, 根据以上结论,分析支持向量。
根据上面式 和 ,消去 ,则有
第一种情况, 当 时,则 ,则此支持向量到对应间隔边界的距离 ,即此支持向量在间隔边界超平面上。
第二种情况, 当 且 时,此支持向量到对应间隔边界的距离 ,此支持向量分类正确,在间隔边界与分离超平面之间。
第三种情况, 当 且 时,此支持向量到对应间隔边界的距离 ,此支持向量在分离超平面上。
第四种情况, 当 且 时,此支持向量到对应间隔边界的距离 ,此支持向量分类错误。
这里需要注意,有没有 和 同时成立的点,这里没有找到确定或否定的证据。如果谁有这方面的资料,还烦请告知笔者,先行谢过,联系邮箱:[email protected]。
[1]、《统计学习方法(第二版)》,李航著,清华大学出版社
[2]、《机器学习》,周志华著,清华大学出版社
[3]、 《支持向量机(一)——线性可分支持向量机导出》
[4]、 《凸优化(八)——Lagrange对偶问题》
B、相关目录
[a]、 支持向量机(一)——线性可分支持向量机导出
[b]、 支持向量机(二)——线性可分支持向量机求解
[c]、支持向量机(三)——线性支持向量机
[d]、 支持向量机(四)——核方法
[e]、 支持向量机(五)——SMO算法
Support Vector Machine - 支持向量机,常简称为SVM,是一种监督式学习的方法,可广泛地应用于统计分类以及回归分析。支持向量机属于一般化线性分类器,也可以被认为是提克洛夫规范化(Tikhonov Regularization)方法的一个特例。这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区,因此支持向量机也被称为最大边缘区分类器。
机的意思就是算法,机器学习领域里面常常用“机”这个字表示算法。支持向量意思就是数据集种的某些点,位置比较特殊,我们找这条直线的时候,一般就看聚集在一起的两类数据,他们各自的最边缘位置的点,也就是最靠近划分直线的那几个点,而其他点对这条直线的最终位置的确定起不了作用,所以我姑且叫这些点叫“支持点”(即有用的点),但是在数学上,没这种说法,数学里的点,又可以叫向量,比如二维点(x,y)就是二维向量,三维度的就是三维向量(x,y,z)。所以“支持点”改叫“支持向量”。
支持向量机构造一个超平面或者多个超平面,这些超平面可能是高维的,甚至可能是无限多维的。在分类任务中,它的原理是,将决策面(超平面)放置在这样的一个位置,两类中接近这个位置的点距离的都最远。我们来考虑两类线性可分问题,如果要在两个类之间画一条线,那么按照支持向量机的原理,我们会先找两类之间最大的空白间隔,然后在空白间隔的中点画一条线,这条线平行于空白间隔。通过核函数,可以使得支持向量机对非线性可分的任务进行分类。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。
C是惩罚系数,理解为调节优化方向中两个指标(间隔大小,分类准确度)偏好的权重,即对误差的宽容度,C越高,说明越不能容忍出现误差,容易过拟合,C越小,容易欠拟合,C过大或过小,泛化能力变差。
gamma是选择RBF函数作为kernel后,该函数自带的一个参数。隐含地决定了数据映射到新的特征空间后的分布,gamma越大,支持向量越少,gamma值越小,支持向量越多。支持向量的个数影响训练与预测的速度。
扩展资料:
1、支持向量机(Support Vector Machine, SVM)是一类按监督学习方式对数据进行二元分类的广义线性分类器其决策边界是对学习样本求解的最大边距超平面。
2、SVM使用铰链损失函数计算经验风险并在求解系统中加入了正则化项以优化结构风险,是一个具有稀疏性和稳健性的分类器。SVM可以通过核方法进行非线性分类,是常见的核学习方法之一。