机器学习课程_笔记07

自己的数学知识丢太久了,这一课看了好几篇,最后结合视频及网上的分析文档终于看懂了,汗。。。

最优间隔分类器(optimal margin classifier)

如果训练集是线性可分的, 就是说用超平面可以分隔正负样本. 我们要找到最大的几何间隔. 我们可以转化为下面的优化问题:

即,找到一个超平面,在将正负样本分开的同时,使超平面到正负样本间的距离尽可能大。

由于w和b可随意缩放,约束条件||w||=1,使得函数间隔等于几何间隔。但是这个约束本身是一个非凸性约束。(非凸性:是指系统有多个稳定的平衡态。)要求解的参数w在一个球体表面,如果想得到一个凸优化问题,必须保证如梯度下降算法这种局部最优值搜索算法不会找到局部最优值,而非凸性约束不能满足这个条件,所以需要改变优化问题。因此转化为更好的一个问题:

我们的目标变成要最大化

,并且去掉了约束条件||w=1||,但是

仍然是非凸性的.

因此,加上规模的限制,对训练集的函数间隔设置为1:

至此,我们得到最终的最优间隔分类器

此时,我们的优化问题变为一个凸二次目标函数。

原始/对偶优化问题(KKT)(primal/dual optimization problem)

拉格朗日二元性

考虑下式:

即最小化函数f(w),并满足约束条件hi(w)=0,可以将hi写成0向量我们可以通过拉格朗日乘数法的方法解决:

1、创建拉格朗日算子:

即等于原始目标函数加限制函数的线性组合,其中参数β称为拉格朗日乘数。

2、对下式求偏导数置为0,即可求出解w和β:

原始问题

拉格朗日乘数法的一般形式,也称为原始问题

考虑下式:

创建拉格朗日算子:

此时α和β为拉格朗日乘数,定义:

上式中的“p”表示“原始问题”(primal),

如果w违反了约束条件,即

那么上式变成:

分析上式,若gi(w)>0,那么只要使αi无穷大,θp(w)就会无穷大;若hi(w)0,只要使βi相应取无穷大(hi(w)>0)或无穷小(hi(w)<0),θp(w)也会无穷大。

反之,若w满足约束条件,那么θp(w) = f(w),所以可得:

那么,求min f(w)就是求下式的值,定义为p*:

对偶问题

与上面原始问题有略微差别,我们定义:

对其取最大值,即给出对偶优化问题,定义为d*:

显然,我们有:

在某些条件下,会有

,因此我们可以通过解决原始问题来解决对偶问题.

原始问题和对偶问题获得相同解的条件:

  1. 令f为凸函数(凸函数的hessian 矩阵是半正定的,H>=0,即开口朝上的碗状函数)
  2. 假设hi为仿射函数((affine,和线性是一样的,只不过是加了截距),即
  1. 假设gi是严格可执行的,即存在w,使得对于所有i,gi(w)<0

在上述条件下,存在w,α,β,其中w是原始问题的解,α,β是对偶问题的解,并且:

此外,还要满足以下条件:

这些条件被称为KKT条件。(KKT是三个人名的缩写),如果

满足KKT条件,那么就是原始问题和对偶问题的解。

其中,

称为KKT对偶补充条件。即就是:

如果αi>0 ,那么 gi(w)=0,但是一般来说αi>0 <=> gi(w)=0。

当gi(w)=0,称gi(w)为活动约束。

使用对偶方法求解SVM最化间隔分类问题

前面,我们有了最优间隔分类器如下:

约束条件可以写为:

通过KKT条件,αi>0 => gi(w,b)=0 => y(i)(wTx(i)+b)=1,即函数间隔为1

给出例子如下图:

图中的圈和叉即正负样本,实线即w,b确定的分割的超平面,最小的间隔是离决定边界最近的点,上图中有三个看出有三个样本的函数间隔为1,其他样本的函数间隔大于1,虚线即为函数间隔为1的点所构成的线。

过KKT条件,这些函数间隔为1的样本对应的拉格朗日乘数一般不等于0, (因为根据KKT对偶补充条件,只有

,函数边界才等于 1).这三个点被称为支持向量(support vector),由此可见,支持向量的数量比训练样本数量小很多

所以,总结为:αi>0。这个函数间隔为1的样本称为支持向量。因为支撑向量数量很少,所以多数的αi=0,那么反推可得,αi=0,对应的样本不是支撑向量。

对最优间隔优化问题构建拉格朗日算子,有:

由于这个问题只有不等式约束,所以没有β。

对w求偏导并设为0

推出:

w就是输入特征向量的线性组合。对b求偏导:

将w代入拉格朗日算子,得到:

根据对b求偏导的结果,最后一项为0,得到:

将上式表示为W(α),对偶问题就是:

运用梯度下降法或极大似然法解上面这个对偶问题,即可求出参数α。求出α后,代入

即可求出w。

求出α和w后,容易求出b,因为w决定了超平面的斜率,那么根据最优间隔,将α和w代入原始问题,就容易求出b了,如下式:

再得到:

定义出了超平面,而函数间隔为1的样本对应的拉格朗日乘数\(\alpha_i\)才不等于0,所以这个公式的直观理解就是,找到最差的样本(离得最近的正负样本,也就是支持向量),接着,就只需要计算x和支持向量的内积就可以求出超平面的位置。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

人脸识别经典算法:特征脸方法(Eigenface)

特征脸方法基本是将人脸识别推向真正可用的第一种方法,了解一下还是很有必要的。特征脸用到的理论基础PCA在之前的文章中已经讲过了。直接上特征脸方法的步骤:...

7635
来自专栏文武兼修ing——机器学习与IC设计

RCNN学习笔记系统结构模型训练

RCNN使用Selective search算法代替滑动框,该算法可以提取类别无关的物品候选区域。该算法分为以下步骤:

982
来自专栏瓜大三哥

BP神经网络

BP(Back Propagation)神经网络是1986年由以Rumelhart和McCelland为首的科学家小组提出的,是一种按误差逆传播算法训练的多层前...

2919
来自专栏人人都是极客

Peter教你谈情说AI | 05用梯度下降法求线性回归模型

监督学习指的是人类给机器一大堆标示(label)过的数据,通常指机器通过学习一系列(, )数据,X代表输入数据(特征Feature),Y代表输出数据,然后自我推...

1261
来自专栏机器之心

资源 | 从全连接层到大型卷积核:深度学习语义分割全指南

选自qure.ai 机器之心编译 参与:路雪、蒋思源 语义分割一直是计算机视觉中十分重要的领域,随着深度学习的流行,语义分割任务也得到了大量的进步。本文首先阐...

4626
来自专栏pydata

ScatNet

散射卷积网络(ScatNet)通过卷积网络对图像的小波系数做级联运算,运用深度学习的思想,生成树状结构的散射系数,使用散射系数作为特征进行学习。 理解和分析sc...

1552
来自专栏marsggbo

Andrew Ng机器学习课程笔记--week3(逻辑回归&正则化参数)

Logistic Regression 一、内容概要 Classification and Representation Classification Hyp...

2195
来自专栏懒人开发

(5.1)James Stewart Calculus 5th Edition:Areas and Distances

通过图中的 y = f(x) ,可以大致知道: 有界且连续的函数f(x),有 a <=x <= b,有 f(x) >=0 也就是

1445
来自专栏人工智能

BP神经网络

BP(Back Propagation)神经网络是1986年由以Rumelhart和McCelland为首的科学家小组提出的,是一种按误差逆传播算法训练的多层前...

2839
来自专栏计算机视觉战队

卷积神经网络就是这么简单就能学会

卷积神经网络和前几次介绍的神经网络非常相似:它们都是由神经元组成,神经元中有具有学习能力的权重和偏差。每个神经元都得到一些输入数据,进行内积运算后再进行激活函数...

1382

扫码关注云+社区

领取腾讯云代金券