Machine Learning Foundations 2: Learning to Answer Yes/No | Cheney Shen

Technology blog

Machine Learning Foundations 2: Learning to Answer Yes/No


 
 

内容:

 
 

线性可分相关处理

详细介绍了 PLA 以及变形:口袋算法

 
 


 
 

上一讲说的就是

 
 

机器学习 通过演算法A学习资料D,从H集合里面选择最符合数据D表现的G

 
 

今天讲的是怎么样的机器学习算法可以做是非题?

 
 


 
 

先来复习一下机器学习流程图

 
 

那么具体的H会长什么样?

 
 


 
 

这里给大家介绍一个模型:

 
 

每个使用者一个x是一个向量,每一个维度表示的是一个衡量值。

我们把维度综合起来算一个分数,分数总和超过一定的数值就过关,给他发信用卡。

 
 

分数 = 加权和(维度x * 维度重要性权值w)

 
 

这里我们用两个值来表示:好的(1)不好的(-1)

这样判断就可以公式化为h:sin(上面的加权和 – 门槛值) 结果就可以来判断好坏

 
 

h 叫做 perceptron(感知器):一个可能的公式G

 
 


 
 

简化:

 
 

把门槛值也当作特殊的 W0(权重)* X0(数值)

由此符号化表示就可以简化为如上面的投影片表示。

要注意的是这样的话就是从0维度开始。

 
 

下面可视化一下h长什么样子

 
 


 
 

最上面是 一个二维的h的示例

然后画出图

圈圈叉叉代表1和-1

h表示的是正负切换位置,就是h = … = 0 二维的情况下就是一条直线。

用直线来划分预测,每一条线就代表一种预测方式。

 
 

Perceptrons(感知器) 就代表了上面的一条线:因此也叫做线性分类器。

 
 


 
 

小测验:感知器用在垃圾邮件分类,下面哪个维度权重高会比较好

 
 


 
 

答案 2

那些字常在垃圾邮件中出现。

 
 


 
 

从 H 选择最好的 g

最好的g就是F, 如果知道F那是最好,可惜并不知道,因此目标就是获得最接近F的G。

 
 

但是我们所拥有的资料就是从F产生的,因此我们可以找一条线完全满足现有的资料所展示的信息。

但是这做法存在的问题:有无限多解。

 
 

因此可以考虑的是:有一条线在手上,然后根据已有数据去修正,让它变得更好。

 
 

用w0看来表示一开始的线。

 
 


 
 

找到某一个点

如果当前的线 wt(第t次的结果) 在这个点上犯了错误:用线判断的结果和数据结果不一致。

那么做修正:

预期是正,结果是负:w+x 结果

预期是负,结果是正:w-x 结果

这就是更新的公式

直到找不到新的错误的点,则表示得到了最终的结果的线,就是g。

 
 

上面就是 PLA 算法的基本原理:知错能改演算法。

 
 


 
 

实现:

 
 

从第一个开始一个一个往后判断再回旋回来,知道走完N个都不存在错误,则表示结束。

还有其他很多方式都可以。

 
 


 
 

举个例子:

 
 

XXOO 已有资料

看能不能通过刚才的方法找到那条线。

 
 


 
 

第一步

找第一个点,只有这一个数据,这个方向是全对的,则就是找从原点(画面中心点)到这个点的向量的向量就是wt。

注意:分割线是向量w的垂线。

 
 


 
 

第一轮的判断结果。

然后在此基础上找错的点,黑色那个点。

然后根据算法:

红色向量,黑色向量 取中间向量

得到w(t+1)

 
 

 
 


 
 

在上面的结果上找错的点

同样方法再去找错误点,再修正。

 
 


 
 

下面就是再看再修正。

这个算法就是一次就看一个点,因此也有可能中间部分步骤的结果反倒更差。

 
 


 
 

 
 


 
 


 
 


 
 

 
 


 
 

 
 


 
 

但是到最后,能得到一个完美的线。

 
 

注意:为了视觉效果,这里给的一个条件就是xi都比x0大。这个条件是只为了视觉效果才这么搞的。

 
 


 
 

问题:

这个演算法一定会停下来么?

就算这个演算法会停下来,但是结果是不是我们想要的 g 最接近 f 么?

 
 


 
 

小测验:

给上面两条,则下面哪一条一定是对的?

 
 


 
 

第三条:两边同时乘上ynxn
 


 
 

接下来看PLA 什么时候会停下来?

 
 

停下来的条件:有一条线可以区分数据。也就是线性可分。

 
 

上面只有图1是线性可分。

 
 


 
 

假设有一条线,看PLA会不会停下来。

 
 

Wf 是目标线:


符合上面橘黄色公式,则表示完美的线性可分,统统切开分隔两边。

 
 

完美切分意味着:


  • 每一个点乘上到线的距离都>0, 犯错误的点到线的距离>=每一个点乘上到线的距离


  • 内积:找出一个错误的点做更新,按照上面的公式做第一步变换,因为大于0再做变换。

 
 

结论:两个向量的内积越来越大。

 
 

这边还不能得出结论:两个向量越来越靠近,因为还存在向量长度的影响。

 
 


 
 

PLA 特性:


有错才更新。

 
 

跟新:


根据上面黄色公式变换,会<=0再变换,中间蓝色这项则表示不会成长数值,红色表示最大涨幅。 yn可以处理掉(正负1平方值都一样不影响结果,最终就看点到分割线的距离的平方。)

 
 

上面两页PPT结果合并起来计算:


就是正规化的内积:就表示两个向量越来越靠近。

同时内积也不会无限上涨,因为正规化内积最大为1.

 
 

因此就证明了这个演算法会停下来。

 
 


 
 

练习:这个PLA跟新多少次停下来?

 
 

R平方:半径平方

row:目标线的法向量和每个点的内积,线性可分则这个值一定大于0

 
 


 
 

答案是2

 
 


 
 

上面证明的结论:

 
 

如果资料线性可分,PLA每次挑一个错误来修正,则PLA会停下来。

 
 

好处:

算法简单

 
 

坏处:

必须要线性可分

而拿到资料的时候我们根本不知道是不是线性可分。也不知道多久会停(上面推倒多久会停包含wf, 而wf我们根本不知道)

 
 


 
 

这里想说:

我们在收集数据的时候本身就可能包含杂讯。

也就是说就算我们原来的f是一条线,则根据资料也得不到一条线。

 
 


 
 

一般来说假设杂讯比较小。也就是说 y f 基本相同,也就是说我们找到的 g 也要基本相同于 f

 
 

也就是说我们要找的是一条犯错误最小的线,而不是不犯错误的线。

 
 


公式表示的就是错误最小,

这是一个np问题。

 
 

机器学习研究方法的方向目前只能是

就是去找比较好的方法,而不是完美的方法。

 
 


 
 

口袋算法(贪心算法)

 
 

手上抓着一个,然后去找下一个,更好保留,不好丢掉,直到你觉得足够好就停下来。

 
 

这方法不需要线性可分这个条件。

 
 


 
 

可以PLA的用口袋算法,损失的是什么?

 
 


 
 

Pocket 比 PLA 慢。

 
 


 
 

总结:

 
 

介绍了线性可分

介绍了对应算法:PLA pocket 算法

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


One Comment

  • Great stuff!! I think it was very close but I guess they gave the win to Jay on the basis of his bigger back. I don#;8217&t think Jay can hold off Phil for much longer though.

Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags