机器学习基石---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不等式可以解决这一问题。

其中：ε为容忍度，当μ和ν差别小于容忍度时，称μ和ν差不多(‘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不等式:

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

  其中我们需要独立同分布与总体的验证数据，把h当做g，验证h的真实性能。(这里有个疑问，验证数据集和训练集的符号都是D，前面讲的h貌似和D无关，所以训练集和验证集是一个意思吗？看成一样，完了后面的Bad Sample才更好解释点)

2.4 Bad Sample & Bad Data

  抛一个正常的硬币50次，如果出现正面40次，反面10次。则ν=0.8，与μ=0.5相差很大。此时采用这次sample的样本均值显然不合理。因此这一次sample，就是一个bad sample。(凡是由于抽样误差所造成样本分布与总体分布相差很大样本，都称之为bad sample。参考[1])

  learning也会遇到这样的问题，比如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[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的概率为:


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

3 Summary

  本文的主要内容是Learning是否能够可行。如果M有限，N足够大，一般而言演算法可以找到一个g，使得Eout很小，从而learning可行。但是M是否有限？演算法是否一定可以找到g，且听下回分解！

4 Ref

[1] http://beader.me/mlnotebook/section2/is-learning-feasible.html
[2] http://blog.****.net/red_stone1/article/details/71082934
                                           2018-01-20 于杭州