林轩田老师-机器学习基石学习笔记2

2017/11/09 learning note 共 2121 字,约 7 分钟

第一节课中,主要讲解的是机器学习的基本思路和相关的应用,算是一种对机器学习的大致介绍和简单的科普。到了第二讲,林老师将重点放在了PLA算法上,通过这个算法让机器学习的演算法大门正式打开了。

对于机器学习,类似人的成长一般,一般是先学会判断是和不是,所以这一讲是介绍一种可以回答是非题的机器学习演算法——PLA。

引入一个银行信用卡的例子,对于银行要对如下的用户进行判断要不要允许其办理信用卡。

机器学习的思路是,通过分析这名用户之前的所有用户的案例,设定评判标准即可。那么用数学的表示法应该是:把一个(信用卡)使用者看成是一个多维度的向量,包括了这个使用者一个个的特征(features),用来计算一个值,这个将其称为得分,当这个得分>门槛值(阀值)时,就是合格的。这个分数的计算方法,这里使用的是赋权的方法,给每个纬度一个权重,用于计算最后的分数。

每一组设置的权值和门槛值,成为一个简单的h(hypothesis),权值的不同或者是门槛的不同构成的h(hypothesis)历史上是被称为(类神经网络)感知器。在我看来,试想一下我们在评判一个人的时候,对他的各方面的属性是不是有一种侧重,这种侧重就体现在权值的大小中,这种类似人脑的思维方式就是人工智能正如连接流派一般,组成神经网络的一种思维方式。

这个时候我们不妨让我们的用户属性和权值构成两个向量:

这个算式还不算好看,因为我们还需要单列一个门槛值的变量进行单独考虑,这个时候我们可以通过转化门槛值的表达方式,得到一个新的权值集合和属性集合

那么x是表示用户的属性的向量的,w是改变后的权值列表,对其作转置的运算和x取内积就可以得到我们潜在的x->y的映射。【x,y的概念第一讲的时候有叙述】

那么,我们式子列出来,h到底长什么样呢,不同的w对应就是一个h,假设x和w的纬度只有2,那么就是一个二维平面上的一个线性分类器,所以我们剩下的任务就是找到一个最好的线,来对使用者进行区分:


到了这里就是一个如何设计一个演算法的问题了。我们知道,data是从f(目标函数)产生的,如果g(best h)和f足够像,就必须保证遍历过的data必须都满足g。对于上图,就是让o和x被一条线完全分开就好。

那么,在此直接介绍这个分类器的演算过程:

1、一开始选择一条线。初始状态w0【开始】

2、若这个线不好,则一定可以找到一个点,不在满足范围内。【找error】

3、纠正规则:W+Yx【纠正】

4、更新到不再犯错【遍历】

这个演算法就被称为PLA(perception learning algorithm)

正所谓【知错能改善莫大焉】A fault confessed is half redressed

表述,很简单,但是PLA算法纠结该如何实现呢?这边给出一个循环法:

之后林老师对于这个方法进行了现场操作。【略】这个写法的核心是:每一次都遍历全部点,并对第一个错误的点进行矫正,之后再一次进行循环遍历。

这个纠正的方式是:

平面几何的基本思路,往哪边歪了就把他往反向方向纠正

那么,肯定有个这样的问题,这个算法会停下来吗?这个算法真的可以找出有效值嘛?

我们看一下这个演算,看看能不能得到这个式子:

【tips:二式,两边同乘yn,xn】。这样我们就知道了,这个演算法是在去尝试着实现做好某件事情。

那么,PLA一定可以找到有效值吗,如果上面的式子的变化不断增大呢?

当然,每个算法都有自己的局限性,PLA算法什么时候会停下来呢。

1、数据是线性可分的。这个可以将其划分的线,将会是我们的目标。

所以我们开始考察wf和wt+1,查看是否接近,内积越来越大(证了一半)。

1、数据算法的演化是有错才更新

向量长度也要考虑。为了这一点我们必须让有错才更新作为我们的假设基础。

同样经过类似的推理我们也可以判断算法的收敛性:

由于这个算法的核心是【有错才更新】所以始终是越来越接近目标函数的,因此可以到下面的推倒,利用

由于每个点都会与那个分隔线有一定距离,那么,可以有上式。

即T次更新,两个正规化的向量的乘积会比根号T乘以一个常量。

这个证明他的确表示两个向量的内积,这样就是说,这个算法会停下来!

1、wt Gets More Aligned with wf ,越来越接近目标函数(此处为目标向量)

2、wt Does Not Grow Too Fast ,具有算法收敛性

补充:

其中T是

一句话总结:算法会停且增长不会太快。

现在开始总结PLA算法的优缺点:

优点:

1、易实现、速度快、多少纬度都适用。

2、涉及假设,数据集是线性可分且算法有错才更新,后者不是坏事,前者很难保证,且不知道假设对不对,算法复杂度也难以衡量。

那么在接下来的课程中,会就数据不是线性可分、数据有噪音等方面进行讲解【一两节课后】

比如如果不是线性可分,那我们尽量保证最优

pocket algorithm算法:随机选取点,使用贪心原则,保持最佳h。

文档信息

Search

    Table of Contents