Press "Enter" to skip to content

机器学习总结(2)—分类中的代数模型

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

前言

 

过去几个月,一直在学习机器学习模型,输入只是学习的一部分,输出可以帮助自己更熟练地掌握概念和知识。把一个复杂的事物简单的讲述出来,才能够证明真正弄懂了这个知识。所以我将在博客中尽量简单地把这些模型讲述出来,以加深自己的掌握,也为他人提供一点点参考。在此感谢大神刘建平Pinard的博客,如有任何疑惑可参考该神博客,这只是我的狗尾续貂之作。

 

正文

 

本篇介绍分类模型中的代数模型,分类模型我个人认为,根据基本数学方法进行分类,有代数模型,树模型,概率模型,其他。具体分类情况如下:

 

 

代数模型的意思是,我们总是运用Xθ+b=y的或者类似的形式来求得分类和回归的结果。这里样本矩阵(m*n),θ是我们要求的系数(n*1),乘积结果就是m个样本的回归结果。尽管我们后面可能进行激活函数的变换,但基本的数学方法就是如此。

 

1.线性回归

 

基本思想

 

线性回归的基本思想在二维平面的展现就是:用一条直线来尽量拟合图中的点,让所有点到这条直线的距离最小,我们的目的是求得这样一条直线y=θx+b,在二维里θ是一个数,但在多维上,就是一个向量了。

 

 

输入

 

输入是样本矩阵和样本的y(这个叫标签值)。比如一个如下的样本:

 

 

输出

 

输出是系数向量θ

 

θ的解释:在本例里θ是一个形如(θ1,θ2,θ3,θ4)的向量,他们分别与身高年龄等特征相乘最后相加,得到发量y‘(y’跟实际的y是有差距的,毕竟我们是拟合得来的,我们的目的就是通过损失函数的优化,让差距最小)。

 

θ的作用:当得到一个新的样本,有身高、年龄、性别、体重,我们用θ可以预测到发量,这就是回归。

 

损失函数

 

模型的损失我们用均方差来度量,(y’-y) 2 (这个也好解释,就是预测的y值与实际y值得差距),我们想得到一个θ让所有样本的均方差和最小,于是我们对θ求偏导等于0。

 

损失函数:所有样本的均方差和 (前面的1/2只是为了求导方便而添加的,不会影响求导结果:比如y=x 2 和y=2x 2 求导y’=0结果都一样)

 

优化方法

 

优化方法就是求极值的方法,对于线性模型,我们可以用梯度下降和最小二乘:

 

梯度下降: (随便另一个初始θ,a是迭代步长,可以自己设定),迭代数次后θ变化不大,就可以得出结果了。

 

这里求梯度是标量对向量的求导,运用的到公式主如下,非常简单就可以计算出来

 

 

最小二乘: (是一种求解析解的方法,可以直接得到结果,但最小二乘有一些局限性)

 

伪代码

 

输入特征矩阵X和y值

 

设定一个初始θ

 

循环

 

直到θ变化很小

 

输出θ

 

2.逻辑回归

 

基本思想

 

逻辑回归的基本思想在二维平面上借鉴线性回归,我们想要一条线把二维平面上的两类点尽量分开。我们再把结果y用一个函数g(激活函数)投射到一个有限的空间(0-1)里面去,这样我们就能通过判断g(Y)的值来判断类别。比如g(Y)>0.5是1类,g(Y)<0.5是0类。(为什幺要用这个激活函数?个人理解它非常适合我们的1、0概率模型)

 

 

这个函数g我们用sigmoid激活函数。它的基本形式是 (这里z就是y的意思),这个函数形式可以让y值无穷大时接近1,无穷小时接近0,y取0时接近为0.5。它的导数有很好的性质:

 

用矩阵形式表示 (算出来是一个向量)

 

输入

 

输入还是X和y,这时候y就是0和1的值了,二分类嘛

 

输出

 

我们想得到一个θ,让分类结果尽量正确。

 

损失函数

 

由于是y是0,1构成,不再是连续值,所以不能使用均方差了。于是我们用最大似然法来得到损失函数,最大似然法的基本思想就是求得θ,让P(概率)尽量大。单个样本的概率分布式为 ,y只能取0和1。

 

对所有样本来说,概率分布为: (其实就是把各个样本的概率乘起来,极其简单)

 

我们要最大化这个函数,就等于最小化-L(θ)这个函数

 

于是损失函数为:(加了个对数,为了方便计算,因为对数可以把乘法转化为加法)

 

 

(E是全为1的向量)

 

(这里再说一说极大似然法,举个简单的例子,我有两个硬币(100元的硬币,1元的硬币),分别抛出,我想得到1,0的观测结果(1是正面),我用力度θ可以控制正反面的概率,于是我当然要求一个θ让100元的硬币正面概率大,让1元的反面概率大,这样相乘的结果才能最大概率接近我想要的。这就是极大似然,求出现概率最大时,θ等于多少)

 

(同时再说一下这里极大似然的几何意义,最大概率,也就是所有点尽可能离分界线远远的)

 

优化方法

 

还是用梯度法:

 

 

 

伪代码

 

输入特征矩阵X和y值

 

设定一个初始θ

 

循环

 

直到θ变化很小

 

输出θ

 

3.感知机

 

基本思想

 

感知机的基本思想和逻辑回归类似,在二维平面上,用一条线分开两类,在三维平面上,用一个平面分开两类。所以使用感知机的数据必须是线性可分的数据。与逻辑回归不同,逻辑回归让所有点尽量远离分隔线,感知机让误分类的样本距离分隔线尽量近,让误分类样本离超平面的距离尽量小(当没有误分类点时,感知机存在多个超平面都可以正确分类)。并且用的激活函数也不同,感知机用了最简单的激活函数:

 

(θ和x均为向量,这个激活函数有利于我们区分误分类点)

 

 

 

输入

 

感知机的输入,依然是X样本集,y是1和-1的标签(设立-1的标签有利于我们设置损失函数)

 

输出

 

得到合适的超平面的参数θ

 

损失函数

 

我们用误分类点到超平面的距离作为损失函数,并求它的最小值,那幺哪些是误分类点呢: 的点就是误分类点,因为对于误分类点,y和θ*x一定异号。判断好了哪些是误分类点后,把他们跟超平面的距离加起来,总的距离为: (这个公式理解起来很容易,把-y和求和符号除开,就是点到线的距离公式,-y只是为了保证式子为正,求和符号为了求得所有误分类点距离,对了||θ|| 2 表示2范数,就等于θ向量中每个数的平方和求平方根)

 

观察式子,式子的分子分母同时存在θ,很显然当θ增大N倍,分母分子同样增大N倍,整体不变。由于我们不关心具体求导等于多少,只关心什幺时候是极值,所以我们可以固定分母或者分子为1,然后求另一个即分子自己或者分母的倒数的最小化作为损失函数,这样可以简化我们的损失函数。

 

于是损失函数为:

 

优化方法

 

我们采用随即梯度下降法(SGD),每次更新只用一个误分类样本进行梯度迭代更新:

 

(批量迭代是这样)

 

(随机迭代的更新公式,yx在误分类样本中随机选择)

 

伪代码

 

输入X和y(1,-1)的样本集

 

1.设定初始θ,迭代步长a(感知机不唯一,所以初始值和步长会影响超平面)

 

2.判断误分类样本集M

 

3.在误分类样本中随机选择1个样本

 

4.更新

 

5.检查训练集里是否还有误分类的点,如果没有,算法结束,输出 。如果有,继续第2步

 

(感知机还有一个对偶的算法形式,可以简化算法,就是提前计算好Gram矩阵,每次调用内积就行了,由于我是讲基本原理,这里就不赘述了,有兴趣请自行搜索)

 

4.支持向量机

 

基本思想

 

支持向量机的基本思想与感知机类似,但是在超平面的规定上进行了一些优化。感知机想要误分类点到超平面的距离最近,最好为0也就没有误分类点了。在没有误分类点时,感知机存在多个超平面都可以进行有效分类。而支持向量机则考虑在那幺多个超平面中,哪个最好呢?于是选择一个超平面,让支持向量到超平面的间隔最大。所以这里支持向量机的基础条件是不存在误分类点。

 

什幺叫支持向量:支持向量就是正确分类后,那些距离超平面很近的点。更通俗来说,比如一个栏杆把学生分为了男生女生,最靠近栏杆的学生就是支持向量,而这个最靠近的学生跟栏杆的垂直距离叫间隔。

 

(间隔的度量,这里我们用几何间隔,几何间隔就是求点到线的正常公式,还有一个函数间隔就是只取这个公式的分子部分 ,分子部分就是函数间隔,函数间隔可以用来判断分类正确与否,用来做约束条件,跟感知机一样)

 

 

(中间实线为最优超平面)

 

输入

 

输入与感知机一样,样本X和分类y(1,-1)

 

输出

 

输出最佳的超平面参数θ

 

损失函数

 

我们要最大化,支持向量到超平面的距离(几何间隔),我们最大化这个距离的目标函数为:

 

(min的目的是找支持向量,max的目的是最大化支持向量和超平面的距离,约束条件是在正确分类的点的情况下。勘误:w范数下面应该有个2,这里的分母w意思是分子的w中的元素添加上b,参看感知机用一个θ就完全表示了)

 

很明显,这个函数极其难优化,因为不同的w,我们要选不同的样本点的xi,但是我们经过一系列abaaba的操作后,就可以简化为下面的式子,我们的 损失函数 为:

 

 

(这里是abaaba操作,可以不看,具体操作如下:我们注意到与感知机一样,分子上下都有w,可以同时缩放w和b而不影响求最大值,那幺我们同时放大N倍,使得N*y(wx+b)=1,于是我们整个公式就相当于求 ,单看这个公式,前面的公式不要去想,公式成这样以后,1代表了函数间隔,我们前面说了正确分类的点,距离要大于函数间隔,因此约束条件相应改变。注意,这里求距离的时候,我们已经没有选择用哪个点的xi了,公式里没有xi了,我们把函数间隔就设置为1)

 

优化方法

 

对于上面这个式子,它叫做不等式约束条件下的最优化,又叫KKT条件问题,解决这种问题的方法我们有一个套路叫“拉格朗日函数法”,把有约束优化问题转化无约束优化问题:

 

 

 

对于上述式子,我们通过 对偶形式转换 , 求w,b偏导数为0来得到w,b关于a的式子 ,并把 总方程 转化为 只关于ai 的式子:

 

 

通过SMO算法求 a向量 , 最终可解得w,b

 

 

这里说一下求b的方法,找出S个支持向量,判断条件是a向量(形状为m*1)里面ai>0的点对应的i这个样本,就是支持向量,对于这个支持向量有公式如下:

 

,于是我们可以计算出每个支持向量的b,然后求均值,其实这里b值应该都一样,只是为了以后算法改进软间隔的健壮性求个均值。

 

(这是一个解析法+迭代法的优化,求偏导为0是解析法,smo是迭代法)

 

伪代码

 

输入跟感知机一样,X样本和y(1,-1)

 

1.构造一个约束优化问题,即上面只关于a的哪个式子

 

2.用SMO法求a

 

3.求出w,

 

4.求出b:找出支持向量,运用公式求出每个支持向量的b,求均值

 

输出一个w和b,也就是θ

 

 

算法改进(关于软间隔和硬间隔)

 

上述算法只能应对线性完全可分的情况,但如果数据大部分是线性可分,但是存在异常点,导致不能线性可分了,如

 

 

又或者,异常点没有达到不可分的底部,但会严重挤压间隔空间,如:

 

 

如果没有蓝点,那幺我的超平面间隔就会宽且合理,有了这个异常点让分隔变得异常窄。

 

如何处理这两种情况呢?SVM引入软间隔的方法来解决,相对来说,我们上面的方法就是硬间隔

 

硬间隔的最大化条件为

 

软间隔引入一个松弛变量ξi,使得约束成为 ,这样对于异常点,只要我们ξi变大,就能抵消异常点的伤害了,但是如果所有点都加大松弛变量,不就乱套了吗,于是我们对于松弛变量的变大也要有惩罚, ,这样我们就可以得到合适的应对误分类点的方法了。C是惩罚系数,要自己规定,C越小,就越可以容忍误分类点,具体设置可以通过网格搜索确定。

 

关于软间隔的损失函数优化问题,其实与硬间隔类似,任然求偏导,得到a的表达式,用SMO求a,得解。

 

算法改进(非线性问题)

 

SVM算法内容实在是多啊

 

对于非线性问题,我们的基本思想是,投影到高维平面去,增加维度,就可以变成线性的,比如y=x+x 2 这个非线性问题,我们把x 2 设为x2,那幺y=x1+x2这个线性问题,问题就得到了解决。

 

看看我们的目标函数最终形态:

 

 

关于维度的问题,只出现在了xi*xj这个向量内积上,于是比如本来xi是1维非线性,我们用一个函数把它投射到2维线性可分,于是公式变成: ,但是当维数太高,比如1万维,太难以计算,于是我们就用上了 核函数!

 

核函数的基本思想是要让我们能用低纬向量计算,却产生高维向量线性可分的结果。如何计算?那就涉及到我们用哪个核函数了,现有的核函数有:

 

多项式核函数:

 

 

高斯核函数:

 

 

sigmoid核函数:

 

 

其中参数都需要自己调整,以适应高维可分性。

 

于是我们的目标函数变成:

 

 

代入到我们的算法当中,就可求解,至此SVM的优化结束

 

本章完结撒花,后续还有神经网络,矩阵分解

 

找出所有的S个支持向量,即满足 α s > 0 对 应 的 样 本 ( x s , y s ) αs>0对应的样本(xs,ys) ,通过  y s ( ∑ i = 1 m α i y i x T i x s + b ) = 1 ys(∑i=1mαiyixiTxs+b)=1 ,计算出每个支持向量 ( x x , y s ) (xx,ys) 对应的 b ∗ s bs∗ ,计算出这些 b ∗ s = y s − ∑ i = 1 m α i y i x T i x s bs∗=ys−∑i=1mαiyixiTxs . 所有的 b ∗ s bs∗ 对应的平均值即为最终的 b ∗ = 1 S ∑ i = 1 S b ∗ s

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注