当前课程知识点:机器学习概论 >  第七章 支持向量机(I) >  7.2 线性支持向量机 >  线性支持向量机(3)

返回《机器学习概论》慕课在线视频课程列表

线性支持向量机(3)在线视频

下一节:线性支持向量机(4)

返回《机器学习概论》慕课在线视频列表

线性支持向量机(3)课程教案、知识点、字幕

这个对偶问题到底是什么意思呢 我们其实看到

根据我们刚才的KKT条件 我们原来是这样的一个

我们现在就是会发现有这个条件 这是KKT条件之一 就是αi

然后乘以 刚才是y乘以f(x)-1 它们这个东西是等于0的

这是KKT条件给出来的 它是什么意思 αi乘以后面这一项等于0

那就意味着这两项任何有一个等于0 这个等式就满足的 对吧

所以如果αi不等于0 那么也就意味着后面这一项必须等于0

后面这一项必须等于0也就意味着 yi乘以fi 就是f(xi)等于1

yi乘以f(xi)等于1是什么呢 就是正例的这条分界面

所以其实就意味着 当αi不等于0的时候

我们重复一下 αi不等于0的时候 因为你要整个等式

两项相乘等于0 那么后面的这一项就应该等于0 它要等于0

就意味着yi乘以f(xi)等于1 它是什么呢 它就是正例的这一条边界

就分界面 就是正例的这个边界 那么也就意味着这个时候

什么叫正例的边界 就是它在正例的边界上也就意味着xi

它就在这个margin的边界上 在正例的这一边

那另外就是如果 所以我们把这个xi叫做support vectors

就是它支持了这个正例 就是我们根据KKT条件得到的

这个是Support Vector Machine的命名的由来

为什么叫Support Vector 因为你会发现

这个事实上是在Vapnik 他在1999年的一个工作

一个paper publication里面直接提到了这一点的

然后我们把这个也在最后列到了reference里面 感兴趣的同学可以看一看

就是支持向量机这类方法最核心的这个名字 为什么当时叫这个名字

它就最核心的强调了这一类学习器它的关键

就是怎么样从支持向量里面去构成解 而不是

而跟其他的这些点没有那么大的关系

因为到这里决定这个分界面的边界的 就是这个xi的支持向量

然后还有呢 那你除了这个等于0之外

你也可以这个不等于0 那么前面αi等于0 αi等于0呢

就意味着你的这个x和y对最后的f(x)没有影响

就是它对这个f(x)根本就没有任何影响

那其实我们把这种情况叫做一个sparse solution

就是一个非常稀疏的solution

就是因为你这个分类面其实它不是由所有的那些点决定的

分界面以外的点都不影响 只有分界面上的点才会产生影响

所以这个的复杂度 这个算法的复杂度

主要和你有多少个支持向量有关

支持向量越多 因为只有支持向量会决定你的这个分界面在哪里

所以支持向量越多 越有影响 这个是我们这个SVM算法的

最最重要的特点之一 我们今天大家强调的第一个特点

就是我们要求它的最大margin 然后我们去解决这个优化

最大margin的优化问题的时候呢 我们会发现这个不好解

那我们在优化问题 是用拉格朗日函数法来去解的 解的时候

我们把它变成了一个对偶问题 在对偶问题 因为它符合KKT条件

就会发现解答这个对偶问题的时候 原来基于这个KKT条件

我们会发现这个分界面 只和支持向量有关 和其他的点都没有关系

这也是这个算法非常重要的特点之一 也是这个算法的名称的由来

所以我们稍微总结一下 那这个时候我们就有了solution了

就是这个问题的解 关于我们这个原来的这个问题

我们是用对偶问题来求解 这个求解是 我们要

因为你要想找到这个分界面 无非就是线性的

无非就是要知道法向量和偏移量 这两个得到了 你的f(x)就出来了

那么法向量等于什么呢 法向量我们刚才已经解过了

它等于Σ yi*αi*xi 然后再这里本来它应该是对所有的i

但是在这里面我们会发现 当这个αi等于0的时候

这个和x,y没有关系 所以我们只要对那些αi不等于0的点

去求就可以了 所以注意到从这一步到这一步 我们是它求和的范围变了

我们只要去对那些αi不等于0的点来求就可以了

这个由KKT条件来决定的 这是第一个 我们的法向量

你就可以这样计算出来 所以这个αi它是一个很稀疏

它是一个非常稀疏的一个变量

第二个就是偏移量Bias 就是b的这一类项 b

其实就是我们从这个可以得到

b它就等于y减去法向量和x之间的那个内积

然后对于所有的αi大于0 然后我们其实就可以通过一些二次规划

的方法来去求解 最终得到的超平面f(x)是什么呢 这个f(x)就等于

法向量w和x的内积加上b然后把法向量代进来

事实上它就是等于yi乘以αi 然后再乘以一个xi和x的(内积)

这个x 这个没有下标的x指的是我要去预测的时候

你分类的时候你训练完了 你这个东西就有了

然后预测的时候新的x来了 那么你就看这个x和

你已经知道的这个边界上面的这个xi的点 支持向量的点做内积

然后乘以αi 乘以yi 加起来 就是对所有的边界上的点

这个加起来 再加上一个偏移量就ok了 这是我们做预测的过程

因此这个问题就解完了

事实上吧 就其实我们会 事实上呢 这个东西它其实是一个定值

一个就行 但是我们其实实际在计算的时候 保险起见

大家还是会把所有的支持向量加到一起 算一个平均值

然后我们再次强调一下 从这个里面就会发现 我们现在

你要找到的这个超平面 就是分类的这个超平面

它其实只和支持向量有关 和非支持向量的数据点是没有关系的

这个我们在今天的课上强调了 已经重复了好多遍

就说明它是很强调的一个 非常重要的特色

所以总结一下 目前为止 我们研究了什么问题呢

研究了这个SVM 它在一个 在线性可分的问题下

支持向量机这个问题是说 我会希望找到这样的一个分类面

然后这个分类面它能够有最大的间隔

然后我们现在最重要的就是你只要知道它的支持向量是什么

然后我原始要解决的问题是要让这个法向量

因为法向量决定的方向对吧 我不同的线的时候

就是原来你这个点在这 就是如果我的分类面是这样的话

你其实它的法向量是垂直的 是这个方向

所以你法向量决定了你的这个线的方向 你如果法向量是这个方向

就意味着你找到的那条线是这个位置 是这个样子的

所以你的法向量的这个决定了那么其实你的这个线的方向

你的分类面的方向就决定了 然后再加上位移就决定了它到底

因为方向有了 你可能会有这么多种 无穷多个

然后你的那个b的那一项 就确定了到底是其中的哪一条 哪一个面

那么我们原始的是想要找到这样的一个东西 使得间隔最大

间隔最大我们也就会发现 事实上是想让这个(w的)模是最小

那么它最小的时候 我们不太好求 那么就找了一个对偶问题

通过对偶问题 我们会发现 其实我们就是要去找这个αi αj

然后和 就是任何我们支持 就是我们在这个边界上面的

这个支持向量 任何的支持向量点 由它来决定

就是αi和αj拉格朗日系数 乘以 yi yj两个 任何两个向量

它们两个的output的y值 然后以及两个向量

它们x向量之间的内积 它们加到一起它是最小

再减去Σ αi的和 它们是最小的 就可以了

然后其中要有两个约束 就是yi乘以αi的之和是等于0的

还有第二个约束是说αi是大于等于0的一个 这个系数

拉格朗日的系数是大于等于0的 所以这个问题呢

我们就刚才说已经解决完了 但是有的时候我们问题不一定是

线性可分的 就是如果不是这么理想的情况下怎么办呢

如果说SVM只能够解决线性可分的问题 那么它的有效性

就会大打折扣 你看我们之前的决策树学习 我们没有说

它必须得是线性可分 尤其是我们前面刚刚给大家介绍过的KNN

那你通过KNN的算法 你都可能找出来对我们上节课

跟大家说过的voronoi图的这样的一种分割的分界面 非常非常的

就不一定是一个线性可分的

那么SVM能不能解决一些非线性可分的问题 不是这么理想情况呢

我们来看一看对于线性不可分的情况怎么办 线性不可分的情况

我们先告诉大家说 其实我们回顾一下

线性可分其实就是我们希望找到min的最小的这个法向量的模

乘以1/2的模 然后还需要有约束条件yi乘以fxi

它大于等于1 这是保证它是0训练误差的

机器学习概论课程列表:

第一章 绪论

-1.1 课程介绍

--课程介绍(1)

--课程介绍(2)

-1.2 机器学习的背景

--机器学习的背景

-1.3 什么是机器学习

--什么是机器学习

-1.4 机器学习系统设计

--机器学习系统设计(1)

--机器学习系统设计(2)

-第一章作业

-第一章课件

第二章 决策树学习(I)

-2.1 决策树的基本概念

--决策树的基本概念

-2.2 决策树的实例和发展历史

--决策树的实例和发展历史

-2.3 经典决策树算法ID3

--经典决策树算法ID3(1)

--经典决策树算法ID3(2)

--经典决策树算法ID3(3)

-2.4 过拟合和前剪枝

--过拟合和前剪枝

-第二章作业

-第二章课件

第三章 决策树学习(II)和贝叶斯学习

-3.1 下午茶时间:勒索软件

--下午茶时间:勒索软件

-3.2 后剪枝

--后剪枝

-3.3 决策树的改进和归纳学习假设

--决策树的改进和归纳学习假设

-3.4 贝叶斯学习的背景

--贝叶斯学习的背景

-3.5 极大似然假设、朴素贝叶斯和最小描述长度

--极大似然假设、朴素贝叶斯和最小描述长度

-第三章作业

-第三章课件

第四章 马尔可夫模型和隐马尔可夫模型

-4.1 下午茶时间:微博的垃圾检测

--下午茶时间:微博的垃圾检测

-4.2 马尔可夫模型

--马尔可夫模型

-4.3 隐马尔可夫模型

--隐马尔可夫模型

-4.4 评估问题

--评估问题(1)

--评估问题(2)

-4.5 解码问题

--解码问题

-4.6 隐马尔可夫模型的应用

--隐马尔可夫模型的应用

-第四章课件

-第四章作业

第五章 假设检验

-5.1 下午茶时间:图灵奖

--下午茶时间:图灵奖(1)

--下午茶时间:图灵奖(2)

-5.2 假设评估

--假设评估(1)

--假设评估(2)

--假设评估(3)

-5.3 置信度和置信区间

--置信度和置信区间(1)

--置信度和置信区间(2)

--置信度和置信区间(3)

-5.4 有限数据下的比较

--有限数据下的比较

-第五章课件

-第五章作业

第六章 基于实例的学习

-6.1 下午茶时间:黑洞照片

--下午茶时间:黑洞照片

-6.2 基于实例的学习的基本概念

--基于实例的学习的基本概念

-6.3 最近邻算法

--最近邻算法

-6.4 K邻近算法

--K近邻算法

-6.5 KD树

--KD树

-6.6 距离加权的K近邻算法

--距离加权的K近邻算法

-第六章课件

-第六章考试

第七章 支持向量机(I)

-7.1 支持向量机的背景

--支持向量机的背景

-7.2 线性支持向量机

--线性支持向量机(1)

--线性支持向量机(2)

--线性支持向量机(3)

--线性支持向量机(4)

--线性支持向量机(5)

-第七章课件

-第七章作业

第八章 支持向量机(II)和无监督学习

-8.1 核函数支持向量机

--核函数支持向量机:向量空间

--核函数支持向量机:核函数(1)

--核函数支持向量机:核函数(2)

-8.4 支持向量机总结

--支持向量机总结

-8.5 无监督学习简介

--无监督学习简介(1)

--无监督学习简介(2)

-8.6 层次聚类

--层次聚类

-8.7 K-means聚类和K-medoids聚类

--K-means聚类和K-medoids聚类

-第八章课件

-第八章作业

线性支持向量机(3)笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。