台大-林轩田老师-机器学习基石学习笔记5
上一节课，我们通过严谨的推倒知道了当样本数据足够大、假设集合可选择且有限，就知道这样的学习一般是可行的。
此外我们通过之前的课程的学习，还知道了机器学习的几个特定的条件：
1、 训练样本和测试样本是来自同一个集合
2、 假设集是丰富但有限的
3、 使用数据集是希望通过训练让Ein更小。
老师还给出了前四节课的详细知识点：
1、 知道了学习的定义——找出最好的g（映射函数（矩））
2、 知道了缩小Ein可以用PLA和pocket算法来实现
3、 知道了我们机器学习的核心是监督式的批处理数据的二分类问题
4、 知道了当D和H满足一定要求Ein和Eout的关系才能是近似。
那么这节课就是：为什么机器可以学习到东西
我们看看训练和测试过程示意图：
到了这里学习就变成两个问题：
~Ein和Eout到底会不会被保证很接近
~Ein如何变得更小
我们需要的是：权衡M，H集合的H的数量。因为上面的两个问题，我们需要有一个界限给M，这里提供了个联级上限：
我们担心M无穷大的时候，右边大于1
但是
使用联级的时候，没有考虑到世界上不好的dataset是重叠的，应该是在1以内的，所以我们的bound过分估计了
所以我们的目标是找出不同的Bad Event的重合部分，也就是将无数个h分成有限的集合（这里着重分为两类？【这里应该是只可以分成两类，才能进行下面的推倒呀】）
三个点在一条直线，划分，以及四个点的情况：
2^4-2=14种
猜想：
下面我们希望的是，在N有一定大小时，可以让effective(N)<<2^N这个时候即使M无限，我们的机器学习依旧是可行的。
下面进一步考察一个假设集可以产生多少dichotomy二分
我们现在又转化为有几个不同的二分划分
做这些准备是为了：替换掉M
所以需要知道挑选最大的dichotomy set——作为M的上限。
（要理解就是）数据集合上对数据的二分方式的集合。
这个函数是有限的，最多不会超过2^N
这时候引入一个新名词：成长函数（growth function），记为mH(H)。成长函数的定义是：对于由N个点组成的不同集合中，某集合对应的dichotomy最大，那么这个dichotomy值就是mH(H)，它的上界是2：
1、 正射线：
成长函数：（N+1）<2^N
2、 interval
带间距线性点阵
3、 那如何算凸四边形的成长函数
所有的函数在圆圈边上：我们采用圆内接多边形的方法解决这个问题。
总结一下：
对于这些计算的成长函数，我们更加关心，2D perception的成长函数，本文之前提到过了。根据引入短点的概念，可以推断出来：
一旦K是断点，那么K+1、K+2……均是断点所以，你在k做不出，k+1及以上就做不出来了。
于是我们有了以下的结论与推论，O（N^k-1）
那么对于详细的2Dperception的BP的计算留给下一节课了。我们希望他的BP与成长函数有着线性的关系。