Machine Learning Foundations 4: Feasibility of Learning

Machine Learning Foundations 4: Feasibility of Learning

 
 


 
 

这里探讨的是:机器学习是否是可行的

 
 

一开始说机器学习做不到

但是加上一些统计上的假设,譬如资料的产生方式,表现衡量方法,就可以做推论做验证,就是机器学习。

 
 


 
 

上一节主要说的是机器学习的分类

这一节首先说什么情况下机器学习做不到,在做不到情况下怎样处理可以变的做得到。

 
 


 
 

首先看个小问题:

 
 

上面三张属于 -1 类,下面三张属于 +1 类

则下面的你会判断属于哪一类

 
 


 
 

答案是非常多的,根据不同的分类方式得到的结果是不同的。

 
 


 
 

再来一个例子:

 
 

输入是一个三个维度的向量,输出还是正负1

然后给了你5笔资料,则g会是怎样的?

 
 

做法可以是:

列出所有的可能性,然后标注5比资料,然后找一条线来区分资料。(类PLA算法)

 
 


 
 

你会发现符合5个资料的结果非常多,用他们再用来预测其他,结果会完全不一样。

 
 

想一下你会发现:

我们想要的不是把已知的都答对,而是对于未来的结果答对的最多。

我们如果不增加假设上面的问题就无法用机器学习解决

 
 


 
 

益智问题

 
 


 
 

答案:4

无答案

 
 


 
 

现在我们有个问题了,就是上面的问题机器学习做不到

 
 

因此我们现在要考虑的是:我们怎么去做推论

 
 

例如图:

有一堆弹珠,想知道里面的橘色弹珠比例占多少?

 
 


 
 

方法:

随机的抓一把弹珠,数一下看比例,就大概是罐子里橘色弹珠的比例。(推论)

 
 

所有数据 》 取样 》 样本结果v 》 数据结果u

 
 


 
 

U != V, 但是大概率情况下两者接近

 
 

接下来看数学表示:

 
 


 
 

定理: uv差距大于e的可能性很小

(具体可以见概率论)

 
 


 
 

右边这项与u无关,因此这个定理与我们不知道的假设无关,以保证准确

e设的大一点,右边的几率就更小

因此样本e够大的话,可以做出推论,uv基本类似

 
 


 
 

计算题

 
 


 
 

答案是 3

 
 


 
 

弹珠事件模型

  1. 不知道的橘色的真正占比 – 函数表示就是f,预测h是否与f一样
  2. 一堆弹珠(橘色弹珠,绿色弹珠)
  3. 做抽样

 

对应到 机器学习模型

  1. 目标f就是橘色真正占比,我们不知道,因此取值到某个x点上面。今天新来一个顾客,我们定义h来预测新来的这个的结果是不是橘色,看是否正确。
  2. 弹珠x,在这个x上面,h是否等于f,一样就是橘色,不一样就是绿色。我们就可以通过这个规则来标识弹珠。要做到这一点我们首先需要有一个固定的h。

    换句话说就是:我们手上有一个固定的预测函数h,就可以把任一弹珠x预测结果是橘色还是绿色。

    这样做的好处是:今天如果我们抓了100个球,就会有100次判断结果。

    这样就和我们的已有资料对应起来:我们已知的部分弹珠的结果加上正确的标记。

    这样就可以检查h的预测结果对不对。

 
 

结论:

如果我们的资料量够大,就相当于我们抓了一把够大的弹珠,

如果我们所有资料的x是独立的从某个地方取样出来,就相当于我们独立的从罐子里抽弹珠

那么我们大概可以说整体的h,f不一样的几率是多少,就相当于整个罐子里面h,f不一样的几率是多少。不仅仅是看得到的样本。

 
 


 
 

我们有一个几率来做从罐子里面取样,这个取样会用在两个地方:

  1. 取样产生了我们的资料
  2. 我们用这个同样的几率来衡量hf的相似程度

h就是从整个H里面的一个样本,然后我们就可以使用我们手上的资料来看hf是否一样。

 
 

Eout 就是来衡量 hf 在整个罐子里面到底一不一样

Ein 就是说在已有的sample上面 hf一不一样

 
 


 
 

这样原来的几率衡量公式可以改写成Eout、Ein的形式

 
 

说明:

这个公式对个个例子都是对的

我们不需要知道Eout,其实就是我们不需要知道f,P

 
 

这样我们就知道了:

如果Ein/Eout相似,Ein很小,那么Eout也就很小,那么如果继续从P产生资料的话 hf 还是相似。

 
 


 
 

从上面得到我们已经有的保证:

如果资料量足够大的话,固定的h的 Ein/Eout 相似。

 
 

那么在此基础上我们是否可以说 gf 是否相似,是否可以说是好的学习。g是h集合

是:选了一个固定的h有 Ein 很小,可推论到 gf 相似

否:问题是只有那个h可以做到,g可能包含很多其他的h,大部分其他h都会导致 Ein 很大。

 
 

因此:

真正的学习是有选择的选好的h

 
 


 
 

改了一下流程:重点是我们需要确认结果好不好

 
 

我们一样有资料,但是没有经过选择。

我们可以验证这个h的表现到底好不好。验证方法是再找一堆资料(verifying examples)看看这个h在这堆资料上面的表现到底好不好。这堆资料的产生和判断hf好不好的方式是一致的,那么你就可以确认这个h表现好不好。

 
 


 
 

联系:股票

 
 


 
 

答案 2

 
 

你可以选择未来的100天测试,如果其和过去十年类似,那么就可以赚大钱了。

 
 


 
 

上面讲到一个h的时候我们可以做验证

如果我们今天有很多个h的时候,则么办。

 
 

例子:

如果今天你有十个罐子,其中一个罐子抽出来全是绿色(全对),你要不要选他()是不是最好的答案。

 
 


 
 

举例丢铜板也是一样,你可以自己动手尝试一下。

 
 

譬如上课的这150个人每人丢5次,很可能出现丢五次五次都是正面,但问题是这个人的这块铜板真的比别人的好么?

 
 

你分析一下你会发现:

完全公平的铜板,上面这个情况,至少一个人出现5次正面的几率大于 99%,

但是如果你去选这150个铜板,你就会存在偏见,想去选那全对的(5次正面)的铜板。

 
 

所以:

上一节说道不好的这件事情很小,但是,这里你会发现:有选择的时候,这些选择会恶化不好的倾向。

 
 

解释:

原来只有一颗铜板,五个正面的几率是 1/32

现在你有150个选择,五个正面的几率是 > 99/100

这个五个正面的表现是不能正确反映分布的不好的倾向。

 
 


 
 

那什么是不好的资料

 
 

对于一个h

 
 

不好的sample例

铜板Eout就是1/2,但是五次正面在很多次的情况下会出现的几率很高,出现的时候Ein=0,差很远。

 
 

不好的data

表面看Ein很小,但事实Eout很大

 
 

好不好:Ein/Eout 的差距大不大

 
 

Hoeffding small 意思是:

把所有可能的资料列出一排(穷举),不好的资料加起来的几率很小。

 
 


 
 

如果今天有很多h,不好的几率会变成什么样子?

 
 

不好的资料:

演算法不能自由自在的做选择,就是很可能选到不好的那个。也就是说存在一个h的Ein/Eout差得非常远。

 
 

上图:

Hoeffding 告诉我们一行一行,bad加起来的几率不大。

竖着看,只要一列上面有一个不好的,就是overfitting,也就是说D1126才是好的,才是我们可以拿来使用的资料。

然后,我们更关心的是这个竖着的不好的资料发生的几率是多少?!也就是打问号的地方值是多少?

 
 


 
 

Pd(bad):表示的是只要对一个h来说是不好的资料的概率

 
 

如上图推导计算上限。

 
 

说明:

结论作用于各种例子都对。

我们不需要知道Eout是多少,也就是不需要知道p

每一个资料集都是安全的。也就是说,不管你怎么去做选择,你一定能选到一个g的Ein/Eout差不多。

 
 

因此:

最合理的演算法,就是选一个Ein(g)最小的g,因为这样基本表示 Ein/Eout接近。

 
 


 
 

于是我们终于可以做到一点点的learning了

 
 

意思是:

如果今天我们的h有有限多种选择,资料够多,那么不管我的演算法怎么选,Ein/Eout都会接近。

演算法就是找一个Ein最小的,就可以包装Eout也很小,就是期望的结果。

 
 

问题是:大部分情况下h是无限的,下面就会讲。

 
 


 
 

问题

 
 


 
 

答案是1

 
 


 
 

总结:

一开始说机器学习做不到

但是加上一些统计上的假设,譬如资料的产生方式,表现衡量方法,就可以做推论做验证,就是机器学习。

下面要讲是的h无线多的情况。