机器什么时候可以学习?

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

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,证明机器学习是可行的。

目录
相关文章
|
6月前
|
自然语言处理 自动驾驶 机器人
机器自动话
机器自动话
55 1
|
6月前
|
机器学习/深度学习 存储 数据可视化
【学习打卡02】可解释机器学习笔记之ZFNet
【学习打卡02】可解释机器学习笔记之ZFNet
|
决策智能
机器博弈 (一) 入门简介
机器博弈 (一) 入门简介
322 0
|
存储 计算机视觉
机器看世界(二)
机器看世界(二)
103 0
机器看世界(二)
|
机器学习/深度学习 数据采集 算法
机器学习笔记
机器学习笔记
|
机器学习/深度学习 人工智能 监控
机器看世界(一)
机器看世界(一)
106 0
|
机器学习/深度学习 算法 数据挖掘
机器为什么能学习|学习笔记
快速学习机器为什么能学习。
机器为什么能学习|学习笔记
|
机器学习/深度学习 算法 数据挖掘
机器为什么能学习
一、为何机器可以学习? 二、举例 三、机器学习跟数据挖掘的关系 四、总结
机器为什么能学习
|
机器学习/深度学习 人工智能 自然语言处理
机器阅读理解 VS 机器问题生成
机器阅读理解 VS 机器问题生成
|
机器学习/深度学习 人工智能 自然语言处理
收藏、退出一气呵成,2019年机器之心干货教程都在这里了
从 2016 年起,机器之心每年都会盘点全年的精华教程。去年就有小伙伴留言说要在 2019 年上半年把 2018 年的教程合集「啃下来」。现在都 2020 了,不知道这位朋友啃完没有?要是 flag 没倒,不妨再来一份?
200 0
收藏、退出一气呵成,2019年机器之心干货教程都在这里了