Q:学习的最终目的是什么?
A:学到去解决未知事物的能力。
Q:机器学习的目的是什么?
A:我们期望计算机能够在它没看过的案例中有同样好的表现,得出令人满意的结果。
统计学小故事
我们想知道,一个超级超级大的罐子里橙色弹珠比例μ
是多少,但是我们没办法一个个数,因为太大了,所以我们只能用trick做一个小推论。
我们从罐子里抓一把弹珠出来,数一下橙色弹珠的数字,就可以算出
橙色弹珠比例ν
。
那么我们能够从手上已知的橙色弹珠比例ν
去推断出整体未知的橙色弹珠比例μ
吗?
谁给你的勇气?梁静茹吗?
不,是下面这个
Hoeffding’s不等式
直观来解释这个式子,ν
跟μ
超过我们错误的容忍范围ϵ
的概率P小于等于一个很小的值(该值由我们的样本容量N
和错误容忍度ϵ
)
所以,这个不等式告诉我们一个事情,只要我们的样本数量N足够大,大致上ν
跟μ
会很接近。
延伸到Machine Learning
现在做个类比,
- 未知橙色弹珠的分布:
当前选定的候选函数h(x)
是否与目标函数f(x)
相等。- 橙色弹珠:h(x) ≠ f(x)
- 绿色弹珠:h(x) = f(x)
那么,我们从罐子里抽一把弹珠出来,弹珠数量为N。如果资料量N足够大,而且这些x是随机 独立抽样产生的,我们就通过在一定数量范围N内,已知的当前选定的候选函数h(x)
与目标函数f(x)
的相似程度去推断:在整体上,未知的当前选定的候选函数h(x)
与目标函数f(x)
的相似程度。
该不等式表明,Ein(h)=Eout(h)
也是PAC的。如果Ein(h)≈Eout(h)
,Ein(h)
很小,那么就能推断出Eout(h)
很小,也就是说在该数据分布P
下,h
与f
非常接近,机器学习的模型比较准确。
一般地,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)的表现好不好,只是一个验证!不是学习!
继续讨论(泛化误差上界 )
现在我们有一个Hypothesis Set了!
对包含了很多h的hypothesis set,就不能简单的用Hoeffing结论了。一个小概率事件如果重复多次,其发生概率就会很大(如有150个人每人抛5次硬币,至少有一人五次均正面朝上的概率为99.15%,而单就一个人而言这个概率是1/32),这使得以下情形很有可能发生:基于样本D,在H中挑选出错误率最小的h,但实际上该h在整体上的错误率很大,即该样本D对于该h来说是BAD样本。
根据许多次抽样得到不同的数据集D
,Hoeffding’s不等式保证:对于某个候选函数h(x)
,大多数的D
都是比较好的情形(即保证Ein≈Eout
),但是也有可能出现Bad Data,即Ein
和Eout
差别很大的数据集D
,这是小概率事件。
也就是说,不同的数据集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)的形式:
其中,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
。至此,就证明了机器学习是可行的。
结语
但是,如上面的学习流程图右下角所示,如果M是无数个,例如之前介绍的PLA直线有无数条,是否这些推论就不成立了呢?是否机器就不能进行学习呢?这些内容和问题,之后再介绍。
主要介绍了机器学习的可行性。首先引入了可以采用一些统计上的假设,例如Hoeffding不等式
,建立Ein
和Eout
的联系,证明对于某个h,当N
足够大的时候,Ein
和Eout
是PAC的。最后,对于h个数很多的情况,只要有h个数M
是有限的,且N
足够大,就能保证Ein≈Eout
,证明机器学习是可行的。