林轩田老师-机器学习基石学习笔记5

2017/11/09 learning note 共 1206 字,约 4 分钟

上一节课,我们通过严谨的推倒知道了当样本数据足够大、假设集合可选择且有限,就知道这样的学习一般是可行的。


此外我们通过之前的课程的学习,还知道了机器学习的几个特定的条件:

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^3-2=6种

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与成长函数有着线性的关系。

文档信息

Search

    Table of Contents