机器学习基石---Why Can Machines Learn(Part1)

机器学习基石---Why Can Machines Learn(Part1)

台大《机器学习基石》课程Week4-7讲的主要是机器学习算法为什么可行。看的稀里糊涂的，结合相关资料，做个总结，梳理下思路~

ML的框架如下:

1 符号表示

f:X→Y:X表示输入空间，可以理解为样本特征；Y表示输出空间，在二分类模型中可以理解为目标变量；f为未知真理Or规律。即在李航《统计学习方法》中所说的”统计学习关于数据的基本假设是同类数据具有一定的统计规律性”。现在唯一知道的是f在D中的表现情况，而目标则是希望演算法A找到找到一个与f类似的函数，称之为g，使得g在训练数据D上的表现与f接近，并且能够在D之外的未知数据上表现依旧出色。 D:(x1,y1,...,(xN,yN))为训练集。 H:hypothesis set，一个有限or无限的方程or函数的集合。演算法A从H中挑选方程。 A:学习算法，在H中找到一个与f最接近的一个方程。 g:final hypothesis A在H中挑选的最好的方程。

2 Feasibility of Learning

2.1 机器学习是否可行

X={0,1}3,Y={o,x}1。如下图所示，我们可以找到一个g，在训练集上，其与f的表现相同。但是在训练集D之外的表现，我们无法保证。这一特性称之为”No Free Lunch”。那么机器学习可行吗？

2.2 统计学上的一个例子

1/n的正态分布。看下面的问题。

如上图所示:

bin:一个装满橙色和绿色小球的罐子

μ:罐子中orange小球的占比

1−μ:罐子中green小球的占比

sample:从罐子中随机抽样一次

N:抽样大小，即抽出的小球数

ν:样本中orange小球的占比

1−ν:样本中green小球的占比

那么ν可以代替或者某种程度衡量μ吗？概率论中的Hoeffding不等式可以解决这一问题。

P[|ν−μ|>ε]≤2exp(−2ε2N)

其中：ε为容忍度，当

μ和 ν差别小于容忍度时，称 μ和 ν差不多(‘PAC’,probably approximately correct)。当 μ和 ν差别大于容忍度时，称 μ和 ν差很多。差很多这件事发生的越小越好，最大不超过不等式右边。相同的 ε时，如果N足够大，那么我们可以有较大的概率说 μ和 ν差不多。

2.3 类比Learning

h，可按照如下方式标记:

1 . 如果h(xn)≠f(xn)，即判断不一致，标记第n个小球为orange

2 . 如果h(xn)=f(xn)，即判断一致，标记第n个小球为green

按照之前sample小球的方式，我们可以利用sample中orange的占比估计总体中orange的占比。即可以推断h在未知数据集上的表现。记h(xn)≠f(xn)为error。记sample中出现orange(即训练集D中出现error)的比例为Ein，在总体中出现error的比例为Eout。那么对于某一个固定h:

* Eout(h)=εx∼P[h(x)≠f(x)],其中ε为数学期望

* Ein(h)=1N∑Nn=1[h(x)≠f(x)]

由Hoeffding不等式:

P[|Ein(h)−Eout|>ε]≤2exp(−2ε2N)

当不等号右边这个上界足够小，可以说h在sample和总体中表现差不多(不等式的本来含义是差很多的概率很小，反之)。此时我们只能说Ein(h)≈Eout，并不能认为h是一个好的learning，因为Ein可能很大。因此需要添加一个验证流程。如下图所示:

其中我们需要独立同分布与总体的验证数据，把h当做g，验证h的真实性能。(这里有个疑问，验证数据集和训练集的符号都是D，前面讲的

h貌似和D无关，所以训练集和验证集是一个意思吗？看成一样，完了后面的Bad Sample才更好解释点)

2.4 Bad Sample & Bad Data

ν=0.8，与μ=0.5相差很大。此时采用这次sample的样本均值显然不合理。因此这一次sample，就是一个bad sample。(凡是由于抽样误差所造成样本分布与总体分布相差很大样本，都称之为bad sample。参考[1])

h1是一个很好的方程，但是sample的都是orange ball,那么演算法A不会选择；反之，h2是一个不好的方程，但是sample的都是green ball，此时由于Ein很小，演算法可能会选择h2作为g。对于任意h，bad sample会造成|Ein(h)−Eout|>ε,对应sample的样本称之为bad data。

A可以自由的挑选方程(h)，我们希望所有的hypothesis都不会遇到Bad Sample。回到最原始的Hoeffding不等式:

P[|Ein(h)−Eout|>ε]≤2exp(−2ε2N)

我们可以说P[BadDforh]≤2exp(−2ε2N),即hoeffding不等式对某一个固定h，可以使得其在任意一个sample上出现bad data的概率很小。那么对于所有hypothesis而言，出现Bad Data的概率呢。先看一个直观的例子，150个人抛硬币，每个人抛5次，至少出现有一个人连续5次硬币都朝上的概率为1−(3132)150>99%。把150个人看做hypothesis，抛掷行为相当于sample，则对于整个hypothesis set出现bad sample Or bad data的概率很大。演算法可以自由的选择

h，则希望大部分的sample对所有的hypothesis都不是bad sample。那么出现bad sample的概率为:

PD[BadD]=PD[BadDforh1orBadDforh2or…orBadDforhM]≤PD[BadDforh1]+…+PD[BadDforhM]≤2exp(−2ε2N)+…+2exp(−2ε2N)=2Mexp(−2ε2N)

由此，hypothesis set的大小对learning的有关。M有限，数据量越大，出现bad sample的概率越小。这样就可以保证D对所有的h都有Ein≈Eout，满足PAC，演算法可以自由选择。如果可以选择到

Ein很小的 h，那么能保证Eout也很小，说明有不错的泛化能力。

3 Summary

g，使得Eout很小，从而learning可行。但是M是否有限？演算法是否一定可以找到g$g$，且听下回分解！

4 Ref

​​[1] ​​                                            2018-01-20 于杭州

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。