机器什么时候可以学习?

  1. 云栖社区>
  2. 博客>
  3. 正文

机器什么时候可以学习?

colleen 2018-09-17 22:45:00 浏览402
展开阅读全文

Q:学习的最终目的是什么?
A:学到去解决未知事物的能力。
Q:机器学习的目的是什么?
A:我们期望计算机能够在它没看过的案例中有同样好的表现,得出令人满意的结果。

统计学小故事

img_3eec71e2c0c507413f46d9e263dc5f09.png

我们想知道,一个超级超级大的罐子里橙色弹珠比例μ是多少,但是我们没办法一个个数,因为太大了,所以我们只能用trick做一个小推论。

img_46e9c2479436fdea9e1d073b6c4968c1.png

我们从罐子里抓一把弹珠出来,数一下橙色弹珠的数字,就可以算出橙色弹珠比例ν

那么我们能够从手上已知的橙色弹珠比例ν去推断出整体未知的橙色弹珠比例μ吗?

谁给你的勇气?梁静茹吗?
不,是下面这个

Hoeffding’s不等式

img_d3c94711ee1ee54110e10ec529cc86d3.png

直观来解释这个式子,νμ超过我们错误的容忍范围ϵ的概率P小于等于一个很小的值(该值由我们的样本容量N错误容忍度ϵ

img_d6e0120aea8c67d68a129f69434bf4e7.png

所以,这个不等式告诉我们一个事情,只要我们的样本数量N足够大,大致上νμ会很接近。

img_3f965db6bb9421294727355d4a4fe15a.png

延伸到Machine Learning

现在做个类比,

  • 未知橙色弹珠的分布:当前选定的候选函数h(x)是否与目标函数f(x)相等。
  • 橙色弹珠:h(x) ≠ f(x)
  • 绿色弹珠:h(x) = f(x)
img_dfb8a4b0e6856b29900ed9ae5565a157.png

那么,我们从罐子里抽一把弹珠出来,弹珠数量为N。如果资料量N足够大,而且这些x是随机 独立抽样产生的,我们就通过在一定数量范围N内,已知的当前选定的候选函数h(x)目标函数f(x)的相似程度去推断:在整体上,未知的当前选定的候选函数h(x)目标函数f(x)的相似程度。

img_cfc2f902845340a0217dcbe13acc7c1d.png

该不等式表明,Ein(h)=Eout(h)也是PAC的。如果Ein(h)≈Eout(h)Ein(h)很小,那么就能推断出Eout(h)很小,也就是说在该数据分布P下,hf非常接近,机器学习的模型比较准确。

img_d8f8be846c6f88caf27195caaa057179.png

一般地,h如果是固定的,N很大的时候,Ein(h)≈Eout(h),但是并不意味着模型最终训练结果g≈目标函数f

因为h是固定的,不能保证Ein(h)足够小,即使Ein(h)≈Eout(h),也可能使Eout(h)偏大。所以,一般会通过机器学习算法A,选择最好的h,使Ein(h)足够小,从而保证Eout(h)很小。固定的h,使用新数据进行测试,验证其错误率是多少。

所以,我们现在仅能做到的事情就是,确认当前选择的h(x)的表现好不好,只是一个验证!不是学习!

img_47cec313f75d4e50d6d7eec1f7c40d3a.png

继续讨论(泛化误差上界 )

现在我们有一个Hypothesis Set了!


img_a988037a1b0576dc4945de2fbabd7fe2.png

对包含了很多h的hypothesis set,就不能简单的用Hoeffing结论了。一个小概率事件如果重复多次,其发生概率就会很大(如有150个人每人抛5次硬币,至少有一人五次均正面朝上的概率为99.15%,而单就一个人而言这个概率是1/32),这使得以下情形很有可能发生:基于样本D,在H中挑选出错误率最小的h,但实际上该h在整体上的错误率很大,即该样本D对于该h来说是BAD样本。

img_fbc51dac5260b3a3760a65e0655ae92e.png

根据许多次抽样得到不同的数据集D,Hoeffding’s不等式保证:对于某个候选函数h(x),大多数的D都是比较好的情形(即保证Ein≈Eout),但是也有可能出现Bad Data,即EinEout差别很大的数据集D,这是小概率事件。

img_21840f55fb74c81a59c4d0889e8225fa.png

也就是说,不同的数据集Dn,对于不同的候选函数h(x),有可能成为Bad Data。只要Dn在某个候选函数h(x)上是Bad Data,那么Dn就是Bad Data。只有当Dn在所有的候选函数h(x)上都是好的数据,才说明Dn不是Bad Data,可以自由选择算法A进行建模。那么,根据Hoeffding’s inequality,Bad Data的上界可以表示为连级(union bound)的形式:

img_39d52de7be041733d26a80caf3abe02f.png
The Union Bound定义

img_70a98069ed8f3703dd6a1f3d0b7185e6.png

其中,M是候选函数h(x)的个数(|H|),Nϵ与之前同义。该union bound表明,当M有限,且N足够大的时候,Bad Data出现的概率就更低了,即能保证D对于所有的h(x)都有Ein≈Eout,满足PAC,算法A的选择不受限制。那么满足这种union bound的情况,我们就可以和之前一样,选取一个合理的算法A,选择使Ein最小的hmin作为g,一般能够保证g≈f,即有不错的泛化能力。

所以,如果候选函数h(x)的个数M是有限的,N足够大,那么通过算法A任意选择一个g,都有Ein≈Eout成立;同时,如果找到一个g,使Ein≈0,PAC就能保证Eout≈0。至此,就证明了机器学习是可行的。


结语

img_aad710a9f4405825a8257656a5e05e57.png

但是,如上面的学习流程图右下角所示,如果M是无数个,例如之前介绍的PLA直线有无数条,是否这些推论就不成立了呢?是否机器就不能进行学习呢?这些内容和问题,之后再介绍。

主要介绍了机器学习的可行性。首先引入了可以采用一些统计上的假设,例如Hoeffding不等式,建立EinEout的联系,证明对于某个h,当N足够大的时候,EinEout是PAC的。最后,对于h个数很多的情况,只要有h个数M是有限的,且N足够大,就能保证Ein≈Eout,证明机器学习是可行的。

网友评论

登录后评论
0/500
评论
colleen
+ 关注