搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 深度学习与先进智能决策 > 机器学习系列之【支持向量机】

机器学习系列之【支持向量机】

深度学习与先进智能决策 2020-05-20
点下方“ 深度学习与先进智能 决策 ”进 号内搜

以爱与青春为名,陪你一路成长

深度学习与先进智能决策推荐搜索
机器学习
强化学习
深度学习
模仿学习
  • SVM涉及的相关概念

  • SVM算法

  • 凸优化基础

  • 线性可分支持向量机

  • 线性不可分支持向量机

  • 非线性支持向量机

  • 最小二乘支持向量机

  • 参考

  支持向量机(Support Vector Machine)是CortesVapnik1995年首先提出的 ,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够 推广应用到函数拟合等其他机器学习问题中。

  1963年,Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一 组特征子集,使得对特征子集的划分等价于对整个数据集的划分,这组特征子集就被称为 支持向量(Support Vector,SV);

  1971年,Kimeldorf提出使用线性不等约束重新构 造SV的核空间,解决了一部分线性不可分问题;1990年,GraceBoserVapnik等人开始对SVM 进行研究; 1995年,Vapnik正式提出统计学习理论。

SVM涉及的相关概念

  支持向量机和线性分类器(如逻辑回归)都是线性模型。虽然SVM是线性模型,但是它的求解过程要比线性模型困难不少。

  1. 它是一种最大间隔的线性分类器,它只会考虑在 decision bound比较近的这些点,而在逻辑回归问题中,即使离决策边界很远,它还是会产生一个 loss function
  2. 通过核函数可以做非线性的问题。

  对于分类问题,分开两类数据其实有很多种解法,那哪一种解法是最好的呢?也就是说SVM是从线性可分情况下的最优分类面发展而来,最优分类面就是要求分类线不但能将 两类正确分开,且使分类间隔最大(分类间隔最大能够使得算法在测试数据集上取得较好效果,或者说数据本身存在噪声,较大的分类间隔能够取得较好效果)。

机器学习系列之【支持向量机】
SVM最大间隔

  SVM考虑寻找一个满足分类要求的超平面,并 且使训练集中的点距离分类面尽可能的远,也 就是寻找一个分类面使它两侧的空白区域 (margin)最大。这与逻辑回归算法不一样,在逻辑回归算法中所有的点都会影响分类边界,而在SVM 算法中不会,它更多考虑的是支持向量。

机器学习系列之【支持向量机】
支持向量

  过两类样本中离分类面最近的点且平行于最 优分类面的超平面上 的训练样本就叫 做支持向量。

分类任务

  分类任务就是确定对象属于哪个预定义的目标类。分类任务的输入数据是记录的集合,每条记录也称为实例或样例,用元组( ) 表示,其中  是属性的 集合, 是类标记(也称目标属性)。在回归模型中,目标属性值是连续的; 而在分类模型中,目标属性是离散的。

  考虑二分类任务,其目标属性为 ,而线性回归模型参数的预测值 是实值,于是我们需要将实值 通过Sigmoid函数转换为01Sigmoid函数定义如下:

机器学习系列之【支持向量机】
Sigmoid

  Logistic回归:目的是从特征中学习出一个0/1分类模型,这个模型是将特征的线性组合作为自变量,由于自变量的取值范围是( )。因此使用Sigmoid函数将自变量映射到(0,1)上,映射后的值被认为是属于 的概率。假设函数为:

  根据Sigmoid函数的特性,假设:

  上式表示,已知样本 和参数 的情况下,样本 属于正样本( )和负样本( )的条件概率:若 则属于正样本,反之属于负样本。当然在实际操作过程中你可以把这个值设置地大一点,使得在测试过程中效果更好。

分类任务进一步理解

  从上面可以看出, 只和 有关, ,那么 只是用来映射的,真实的类别决定权在于 。当  时, 趋于1,反之趋于0。如果我们只从 出发,那么模型应该尽可能的让训练数据中 的特征 ,而 的特征

  因此Logistic回归就是要学习得到参数 ,使得正例的特征远远大于0,负例的特征远远小于0,而且要在全部训练数据上达到这个目标。

  将目标属性 替换为 ,再将 改写为 ,可以看出:线性分类函数跟Logistic回归的形式化表示 没有区别。将假设函数 中的 做一个简化,将其映射到 上,映射如下:

  • 线性可分数据集

  需要注意的是:对于上述问题我们需要数据集是线性可分的,不然不管如何分类都找不到这样一个平面。

  线性可分数据集:存在某个超平面 能够将数据集的正实例和负实例完全划分 到超平面的两侧,则称为线性可分数据集;否则,线性不可分。

机器学习系列之【支持向量机】
线性可分

  上图中的这些数据就是线性可分的,所以可以用一条直线将这两类数据分开,二维中是一条直线,多维中就是一个超平面。

  这个超平面可以用分类函数 表示,在进行分类时,将 代入 中, 表示数据点在超平面上; 对应 的数据点; 对应 的数据点。

SVM算法

SVM所要解决的问题

  假定给定数据图,圆的为正类,方的为负类,要想通过一个划分超平面(这里是二维,所以是条直线)将不同类别的样本分开。从图中可以看出,能将训练样本分开的划分超平面可能有很多,但是我们应该去选择哪一个呢?

  直观上,我们应该选择中间红色的那个,因为它对于 训练样本局部扰动的“容忍”性最好;

  比如,训练集外的样本可能比图中的样本更接近两类 的划分超平面,这将使许多划分超平面出现错误,而 红色的超平面受到的影响是最小的,也就是说,这个 划分超平面的分类结果是最鲁棒的,对未知样本的泛 化能力最强。

机器学习系列之【支持向量机】
SVM的任务

  在所有的划分超平面中,有一个平面是最好的,它可以尽可能地让所有的样本点都离该划分 超平面最远,这就是SVM要做的。

函数间隔

  有三个实例 均在划分超平面的正类一侧,点 举例超平面较远,若预测为正类,叫比较确信预测是正确的;点 距离超平面较近,若预测为正类就不那么确信了;点 介于 之间,预测其为正类的确信度也在 之间。

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

机器学习系列之【支持向量机】
分类确信度

  可以看出:当一个点 被正确预测时,那么 的符号与类标记 的符号相同,因而所以可用 来表示分类的正确性及确信度;

  对于给定的训练数据集 和超平面( ):

  定义超平面( )关于样本点 函数间隔为

  定义超平面( )关于数据集 的函数间隔为超平面( )关于 中所有样本点的函数间隔的最小值

几何间隔

  • 为平面 的法向量

  取超平面任意点 ,满足 ,将两式相减,得到 ,由于 表示平面上的任意向量,而向量 和它们的点乘为0,说明 是这个平面的法向量。

机器学习系列之【支持向量机】
几何间隔
  • 到超平面 =0的距离 (d为正值)。即

  设 在平面 上的投影为 ,则有 =0;由向量 与平面 的法向量 平行,即两个向量的夹角余弦等于1,可知:

  另外,直接计算其内积,可以得到:

  由于有 ,因此上式等于:

  因此,可以等到: ,从而距离 的计算公式为:

  • 对于给定的训练数据集 和超平面( ):

  定义超平面( )关于样本点( )的几何间隔公式如下,它一般是样本点到超平面的带符号的距离,当样本点被超平面正确分类时,就是样本点到超平面的距离(将每个样本点 带入距离计算公式  )。

  定义超平面( )关于数据集 几何间隔为超平面( ) 关于 中所有样本点( )的几何间隔的最小值  ,表示为距离超平面距离最小的那个样本。此时相当于能够找到支持向量所对应的样本,通过调整参数 让其几何间隔最大,就是SVM所要做的事情。

  几何间隔与函数间隔的关系为: 

  如果超平面的参数 成比例的改变(超平面没有变),函数间隔也按此比例改变, 但是几何间隔不变。

  支持向量的函数间隔为1,SVM的优化目标为:

  约束条件表示的是最大化的一定是支持向量。要求解上述问题我们需要一定的凸优化基础,接下来简要介绍一下所需数学知识部分。

凸优化基础

拉格朗日对偶性 – 原问题

  假设 是定义在 上的连续可微函数,称以下的约束最优化问题 为原问题:

  对于上述约束化问题首先引入拉格朗日函数 ( 将等式和不等式约束融入到一个目标函数中去,从而只用一个函数表达我们的问题。):

  其中, 是拉格朗日乘子,

  • 构建关于 的函数:

  • 假设给定某个违反原始问题约束条件的 ,即存在某个 使得

  若 ,可令 ,使得 ;若 ,可令 使 ,使得 。将其余 均取值为0。即:

  假设给定某个符合原始问题约束条件的 ,即 且  ,则:

  由以上两个式子可以得到:

  则极小化问题  有:

  与原问题等价,即有相同的解。(因为当趋向无穷时,问题无解,因此必须 满足约束条件)。

  • 广义拉格朗日函数的极小极大问题:

拉格朗日对偶性 – 对偶问题

  • 构建关于 和  的函数:
  • 则其极大化问题称为 广义拉格朗日函数的极大极小问题
  • 将其表示为约束最优化问题,称为 原始问题的对偶问题

原问题与对偶问题之间的关系

  • 弱对偶性:若原始问题与对偶问题都有最优解,则对偶问题最优解与原问题最优解具备以下关系:
  • 强对偶性:满足 
  • 强对偶是一个非常好的性质,因为在强对偶成立的情况下,可以通过求解对偶问题来得到 原始问题的解,在 SVM 中就是这样做的。
  • 当然并不是所有的对偶问题都满足强对偶性 ,在 SVM 中是直接假定了强对偶性的成立, 其实只要满足一些条件,强对偶性是成立的,比如说 KKT条件。

  KKT条件:对于原始问题及其对偶问题,假设函数 是凸函数, 是仿射函数,且不等式约束 是严格可行的,即存在 ,对所有 ,则存在 ,使 是原始问题的解, 是对偶问题的解的充分必要条件是  满足下面的Karush-Kuhn-Tucker (KKT)条件: