机器学习——支持向量机SVM之线性模型

目录

一、没有免费的午餐定理

二、支持向量机SVM(support vector machine)

1、线性模型和非线性模型

2、如何在线性模型中画出一条直线(优化过程——vplink)

1)多少条?

2)如何画出最好的直线?

3、如何去描述这个优化的过程(数学描述)

1)几个重要的名词(间隔、支持向量)

2)一些定义(训练数据、标签、超平面等)

>>>问题1:怎么求解w,b?

3)机器学习的任务与步骤(求解w,b)

三、支持向量机的优化问题(求最优划分直线,性能指标为d)

1、优化问题(怎么将问题转化为最优化问题?)

2、转化为最优化问题的过程?

1)由支持向量X0和模型得到距离d的公式

 2)如何取得d最大?——(转化问题的最优化量的思想)

>>>问题2:需不需要计算a?

>>>问题3:支持向量是怎么得到的?如何保证它满足下面的式子?

3)转化后的最优化问题数学描述(dmax——||w||min)

>>>问题4:以上的限制条件中哪些是已知哪些是未知?

>>>问题5:缩放后的w,b怎么求解?

>>>问题6:限制条件为什么大于等于1?

四、总结

1、机器学习与最优化联系与区别

1)区别

2)联系


 


 


 


课程链接:《浙江大学-研究生机器学习课程》

一、没有免费的午餐定理

没有免费的午餐定理:如果我们不对特征空间有先验假设,则所有算法的平均表现是一样的。

机器学习——支持向量机SVM之线性模型_第1张图片

特征差距小的样本更有可能是一类

二、支持向量机SVM(support vector machine)

vplink发明的支持向量机

SVM是最大化间隔的分类算法,是一种进行二元分类的广义线性分类器;SVM也可以通过核方法来对非线性模型进行分类。

1、线性模型和非线性模型

通过一条直线可以将样本分开为两个特征的部分叫线性模型,反之叫非线性模型

机器学习——支持向量机SVM之线性模型_第2张图片

机器学习——支持向量机SVM之线性模型_第3张图片

2、如何在线性模型中画出一条直线(优化过程——vplink)

1)多少条?

机器学习——支持向量机SVM之线性模型_第4张图片

该直线将圆圈和叉区分开,按道理来说有无数条,所以需要找出一条最好的直线

2)如何画出最好的直线?

先定义一个性能指标,比较每一条直线的性能指标,取性能指标最好的那条线作为最好的直线

这里是以d:间隔(margin)作为性能指标进行分析

①最优的情形

机器学习——支持向量机SVM之线性模型_第5张图片

这里的性能指标是距离——将待定的直线向左和向右移动,直到该直线分别与各特征区域的一个或者多个特征值相交时停止移动,测量这时候两条直线的距离,取该距离最大的直线为最优直线备选。

但是最优的直线也有无数条,因为与其平行的直线有无数条,该怎么取舍呢?

这时候将直线在d/2处的直线作为最终的直线,作为最优直线

②不是最优的情形

机器学习——支持向量机SVM之线性模型_第6张图片 标题

3、如何去描述这个优化的过程(数学描述)

如何去描述这个优化的过程(数学描述)?

1)几个重要的名词(间隔、支持向量)

间隔d:margin——最优直线与两边最近特征值的距离和叫做间隔

支持向量X0:support vector——被平行线插到的向量叫做支持向量

机器学习——支持向量机SVM之线性模型_第7张图片

2)一些定义(训练数据、标签、超平面等)

 

训练数据(XN=【XN1,XN2,XN3,,,XNN】T是一个向量)及标签(yi是1或-1):

机器学习——支持向量机SVM之线性模型_第8张图片

机器学习——支持向量机SVM之线性模型_第9张图片

机器学习——支持向量机SVM之线性模型_第10张图片

 

线性模型:(W,b)——待定参数

机器学习——支持向量机SVM之线性模型_第11张图片

W的转置.dot(xi) + b = 0——超平面(Hyperplane)的方程,关于xi的一次线性方程

 

>>>问题1:怎么求解w,b?

机器学习——支持向量机SVM之线性模型_第12张图片

答:超平面方程中X=xi,其中i = 1~N,而xi = (xi1,xi2,...,xin)T,因此根据方程可以得到N个方程,N取决于训练的样本数,n取决于样本数的维数,通过求解N个关于w的一次方程组,即可以求解得到w,b,求解方程组的方法有高斯法等,具体可参考《数值分析》

线性模型最优化的任务——在二维的的时候找直线,在三维的时候找平面,在多维的时候找超平面,这里以二维为例

 

 

线性可分:

机器学习——支持向量机SVM之线性模型_第13张图片

即:

 

3)机器学习的任务与步骤(求解w,b)

任务(已知(xN,yN),未知(W,b)):

通过这些训练数据和标签((xN,yN)),其中XN = (XN1,XN2,...,XNn)是一个向量,N表示训练的样本个数,n表示每一个样本数的维度;在限定的模型(超平面方程)下,求解出待定系数(W,b),最后确定模型,机器学习的过程也就结束了

 

步骤:

a,通过一个方程来限定模型,如用一个超平面来限定多维模型;

b.在限定的模型中确定待定系数

c.通过训练数据和限定的模型(方程)求解出待定系数,最后确定模型

三、支持向量机的优化问题(求最优划分直线,性能指标为d)

1、优化问题(怎么将问题转化为最优化问题?)

机器学习——支持向量机SVM之线性模型_第14张图片

2、转化为最优化问题的过程?

公式1:

1)由支持向量X0和模型得到距离d的公式

机器学习——支持向量机SVM之线性模型_第15张图片

 2)如何取得d最大?——(转化问题的最优化量的思想)

通过缩放求得d的公式(已知w,b,未知a,也就是后来的aw,ab,支持向量X0未知)

机器学习——支持向量机SVM之线性模型_第16张图片

使得d最大的问题转化为求||w||的最小值问题

 

>>>问题2:需不需要计算a?

答:不需要!因为这里主要是引入a来讲解一下缩放的思想,即告诉我们通过a的缩放能够将求解d最大值问题转化为||w||最小值的问题,至于a缩放多少,因为不管a缩放多少,都要假设满足以下式子(至于为什么这么假设,我也不知道,反正肯定是为了方便计算):

最后d的公式为:

机器学习——支持向量机SVM之线性模型_第17张图片

d的公式分子为常数,因此问题dmax依据转化为求||w||min

 

>>>问题3:支持向量是怎么得到的?如何保证它满足下面的式子?

机器学习——支持向量机SVM之线性模型_第18张图片

答:这里只是一个假设,实际上支持向量还未知,为我们最优化时的工作,这里只是相当于下了一个定义,限定了a的值来满足这个假设,最优化的问题就是对缩放后的w进行求解,所以a没必要进行求解,这里也求不出来

 

3)转化后的最优化问题数学描述(dmax——||w||min)

凸函数的定义:《最优化课堂笔记04:非线性规划——凸规划》

凸函数及二次规划问题的求解方法:《最优化课程笔记07——约束问题的非线性规划方法(拉格朗日乘子法和惩罚函数法)》

机器学习——支持向量机SVM之线性模型_第19张图片

>>>问题4:以上的限制条件中哪些是已知哪些是未知?

答:已知:xi,yi——即样本数据,未知——w,b

注意这里要区分开前面通过训练数据求得的w,b,前面的w,b是一个超平面方程,对所有的训练数据都满足,而这里的w,b是在超平面的基础上进行缩放得到的,虽然平面是一样的(由事实1得到):

机器学习——支持向量机SVM之线性模型_第20张图片

但是w,b值已经发生了改变,并且这里要求解的w,b是在限制条件下进行求解的,虽然目标函数中看起来只有w,没有b,但b在限制条件中,如果b的取值不能破坏了约束条件,也是不可以的。

 

>>>问题5:缩放后的w,b怎么求解?

答:先转化为对偶问题,再使用拉格朗日函数进行求解

 

 

>>>问题6:限制条件为什么大于等于1?

答:首先根据线性可分性得到限制条件必然大于等于0,又因为问题dmax转化为||w||min的问题时在支持向量上满足,

所以在非支持向量上有:yi=1时,平面方程的模会大于1;即:

yi=-1时,平面方程的模会小于-1,即:

所以二者相乘就会大于等于1,当然也可以大于等于任何的正整数N,此时a的缩放就应该满足:

结果一致,一般是大于等于1

四、总结

1、机器学习与最优化联系与区别

1)区别

机器学习:通过已知的训练数据在限定的模型下求解出模型的待定系数,得到这个问题的一个确切具体的模型,重点在于求解模型的待定系数w,b,求得的w,b只是满足了将二元分类了,但不一定是最优的分类平面

最优化:求解出问题的最优解,即找到最优的分类平面

2)联系

机器学习包含了最优化,其实机器学习就是在不断地对数据进行优化,得到最优解。起初机器学习是通过现有的训练数据得到一个模型,后面再通过学习(优化)求得最优解。

 

 机器学习——支持向量机SVM之线性模型_第21张图片

非线性模型的最优化问题该怎么求解呢?请看:《机器学习理论——支持向量机SVM之非线性模型》

 

还可以参考:《[机器学习笔记] 支持向量机SVM如何求解最佳模型?》

你可能感兴趣的