Why Can Machines Learning?

按例放上学习进度:D

Roadmap

前面的4课解决了机器能学习的条件，即when，
现在开始思考机器能学习的原理。

一、Recap and preview

首先整理下之前get到的知识:P

目前，我们已经知道了，当h的个数M有限时，且N足够大，A选中的那个g,会有Ein(g)≈Eout(g)（现成资料D里的g的错误率可以推出机器预测未知的资料的出错率，并且很接近哦）；当A选择的g,Ein(g)≈0的时候，Eout(g)≈0是PAC的。Eout(g)≈0,就是说机器是可以学习的。
整个flow里可以理解为train（训练已有资料）和test（用新的资料来测试结果）两部分。

learning可以说是在bath的D,监督式学习，二元分类器等条件下，通过保证Ein(g)≈Eout(g)和Ein(g)≈0，使g≈f （Eout(g)≈0）。

那么learning可以分为2个核心问题:

• Ein(g)≈Eout(g)?
  (M finite，N large)
• Ein(g)≈0?

关于上面的两个问题:

• 如果M很小，从公式可以推出，P[BAD]小，但是，选择也变得小了，那么不一定找得到Ein(g)≈0的优秀线
• 如果M很大，选择多了，可P[BAD]也大了 :(

emmmm……
所以用合适的M超级重要呢~
前面的讨论都是M有限的情况，如果M无限大呢?

解决方案是，用一个有限的m去替换无限的M：）

所以，现在问题变成：怎么找到一个合适的m来替代M?

二、Effective number of lines

先考虑为什么公式在infinite情况下不可行的？

每种BAD在独立来看都是不一样的，但是union bound 后就会有重叠部分，叠加infinite个独立p后变得无限大，此时就变得无意义了。

BAD重叠可以理解为h1≈h2
总之，B1,B2,B3……这些BAD其实是重叠了的，但是union bound公式是没有考虑重叠的，把每个BAD当成独立的来计算，造成了无限大的上限。所以此时infinite个h是无法计算的。
好嘛，既然是因为重叠了才不可计算，那就想办法找出重叠部分:D

先考虑这样一个问题:
如果平面上只有一个x,那么会有多少条h呢？
显然是可以分为两种，一种是把x划分为+1那边的，一种是把x划分到-1那边的。

那么，有2个点的时候呢？

可以根据把x1,x2划分到那一边算出有4种h。
那么3个点的时候呢？

对的，8种。
这时候你有一个猜想，哇，好像是2^n呢……
然而，如果3个点是在一条线上的呢?

emmm……
对的，有的情况无法用一条直线划分，所以这时候只有6条h.

当有4个点时，也会出现无法划分的时候。

总的来说，结论如下:

我们把这种有效的条数称为effective number of lines
从1,2,3,4个x可以发现它们的h总是有个上限的,没有重叠部分的，最大不会超过2^{N(每个点的情况都是两种，所以最多不会超过2}N)。所以,D里面的N个点的最大不会超过2^N条h。
那么是不是可以用effective（N）来替代那个无限的M呢？

三、Effective number of Hypotheses

现在引入一个概念dichotomy:
把点x,划分到+1,-1的集合。

hypotheses H 与dichotomies H(x1,x2,...,Xn)的区别如图。
前面说到effective(N)的概念，effective（N）正是dichotomies H(x1,x2,...,Xn)的h的个数呢。
既然dichotomies H(x1,x2,...,Xn)是没有重叠部分的，那么可以作为替换M的候选了。

|H(x1,x2,...,Xn)|是依赖x的(比如上面提到的3个x的时候，摆放不同会有不同的结果，6和8），现在我们除去对x的依赖，只讨论|H(x1,x2,...,Xn)|的max，把这称为成长函数(Growth Function)。
那么，怎么计算成长函数呢？

第一种情况:
把直线上一部分划分为+1,像射线一样，N个点可以把一条线划分为N+1个块，这时有N+1条线可以划分。

第二种情况:
一部分划分为+1。
此时N个点还是把线分为N+1块，既然是取部分划分为+1,那么取两个块作为线的端点，所以一共Nx(N+1)/2种，还有一种是全部取为+1，所以
N(N+1)/2+1.

第三种情况:
凸的部分划分为+1。

此时可以凸边形做出来 ,即连点，突边形外内的都是里的都是+1,其他为-1.
所有点都可以这种方法划分出来，所以是2^N*.
总结：

四、Break point

通过得到的式子可以看出，当成长函数为多项式时效果比较好，指数时效果不好。

在二维下，
3个x时存在shatter(原意打碎，破坏，在这里可以理解为全部命中，比如3个x,有8种可能，存在8种都可行的状态，即命中）,这时有6和8的情况，所以是'存在'。
4个x时不存在shatter,因为最多只有14种。
可以推出，自4以后都是不存在shatter的。
假设k为inputs的个数，
当k个inputs让H不存在shatter时，称k为break point.
在二维下，4就是break point.
k+1,k+2,k+3……也是break point

五、Summary

总结:

• 复习之前4个课程的知识
• 当M无限大时，因为union bound是把每个BAD加起来，没有考虑除去重叠部分造成了无限大，如果用eddective（N）替代M也许能解决这个问题
• 介绍了4种成长函数，其中多项式的替换效果比较好
• 介绍了break point , 比如4
• 总的来说解决了M 无限时的情况，大题的思路是找出一个有限的且有效的m去替代M,最后，我们找到了多项式的成长函数来替换

以上:D
注明:以上图片都来自Cousera台大林轩田老师的《机器学习基石》哦 QwQ