机器学习算法可行性（机器学习基石）

本文是作者学习台大林轩田教授《机器学习基石》课程后整理的简要笔记（未按课程回目分节），内容大部分来源于林轩田教授的课程资料，其余相关参考链接已标出。

版权所有：CSDN博客 拖延症患者的自愈小记

可行性 - Feasibility

从训练样本学习得到模型去估计未知数据（具象化可以想成从bin中捧出一把marbles,通过marbles中不同颜色的比例估计整个bin中不同颜色的比例），这是典型的以小窥大，必须探讨机器学习如何保证这个“窥”是可行的。机器学习可行性，即希望证明h在样本中的错误率Ein可以和未知数据上的错误率Eout比较接近，这样下一步的工作——降低Ein，才能相应得到小的Eout，进而得到一个和f比较接近的h作为g，达到好的机器学习效果。

一步步来（均以二分问题为例）：

Hoeffding

Hoeffding不等式是数学上已证的，证明了一件事：样本量足够大时，样本中的占比和整体真实的占比非常接近，即所谓probably approximately correct（PAC）

对单个给定的hypothesis，Hoeffding可以作为判定这个h是否好的依据，也就是若该h在样本上错误率很小，则极大概率可以确保它在全体真实数据上错误率也很小

Multi-binhoeffding

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

对于给定的任意D，它是某些h的BAD样本的概率为P，推导可得P正比于样本数据量N、反比于H中h的数量M（用到Hoeffingh和union bound），也就是说，M越小、N越大时，我们可以越放心的在H中选则错误率最小的作为想要的g

(A)

至此，证明了【在M有限、N足够大的条件下】对H中的任意h，Ein ≈ Eout

参考：my.oschina.net/findbill/bl…

VC bound

【在M->∞的情况下】怎样把M转换成有穷且增长较慢的多项式，从而让不等式右边尽可能小，就是下面进一步探讨的问题，突破口是前面证明过程中变形用到的union bound。 从公式可以看出推导后上界很宽松，只有在M个事件没有交集时才会顶界，也就是只要“存在一个h，对于h来说该D是BAD样本”，那么我们就判定它是BAD样本了（类似一票否决的意思），也就是这个上界定高了

Dichotomy：给定样本D，根据样本点是○还是×（代表着Ein是1还是0）将它们分类，如果分类结果是线性可分的（用某h可以分出这个局面），就称这个局面为一个dichotomy（二分/划分，相当于把H中的所有h按照不同的线性分类结果进行分组，或者说一个dichotomy包含了所有可以分出这个局面的h）；D上的所有划分组成了dichotomy set

Growthfunction：对于某个N值，可以取很多大小为N的样本，相应有很多dichotomy set，这些set的大小的最大值，定义为成长函数Growth function：m(N)

至此，M->∞的情况似乎改善了一小步，我们希望用m(N)来取代M，由(A)式得(B)式

(B)

VC bound：实际上并不能直接用m(N)替换掉M，(B)不能用，做一些小改动正确推导得到得(B’)式，即VC bound

(B‘)

Bounding function：growth function的上限函数，记为B(N,k)

得出上限（growth function）的上限（bounding function）的上限（Nk-1）

此时(B’)可以继续推导，VC bound可以改写成

…

(C)

至此，证明了不用考虑M，【在k存在、N足够大的条件下】对H中的任意h，Ein ≈ Eout

▲ VC dimension

Shatter：m(N)最大是2N， m(N)=2N时称H“shatter”（打散）了这N个点（对某个D）

Breakpoint：对于H，使m(N)≠2N成立的N的最小值，记作k（对某个D）

用一个打怪闯关的游戏来理解以上概念：m(N)是把散弹枪，H是玩家，每个关卡（level N）中，玩家有m(N)发子弹，面临的是2N个怪兽，必须一枪打出去shatter掉所有怪兽才能过关；当N从1逐渐增大，m(N)在第N关第一次少于2N，玩家shatter不掉所有怪兽，这个游戏break了，这第N关就是break point

VCdimension：对于H，满足m(N)≠2N的最大的N值，记作dVC（对大小为N的所有D）

① VCdimension = k-1

② N≤dVC时，至少存在一个D被shatter；N≥dVC时，任何D都不能被shatter

意义（不易理解）

(1) 对于D-perceptron而言，其hypothesis参数维度为d+1（阈值作为0维，取w0=1，权重向量w(w0,w1,w2,w3, ..., wd)），这就好比hypothesis set有d+1个旋钮，代表着其自由度；而对于D-PLA，dVC=d+1（证明过程可细看），即dVC和hypothesiss set的自由度Effective‘binary’degrees of freedom联系起来；也可以说dVC反映着Powerfulness of H，dVC越大，hypothesiss set就越强大，也就是可以打散更多的点，对数据的划分更细致

更为一般化一些，dVC与假设参数w 的自由变量数目大约相等...

(2) 将(C)中的k-1代换成dVC，推导可得

Ω(N, H, δ)称为Penalty of model complexity，hypothesis set所要付出的代价，图如下（dVC并不是越大越好，越强大相对应所付错误代价越高）

(3) 另一层含义是样本复杂度Sample complexity

估算出所需样本规模通常为N≈10dVC