Coursera机器学习基石笔记week5
Training vs Testing
Recap and Preview
简单回顾一下前面几节课的内容:
- 第一节课,介绍了机器学习的定义,目标是找到最好的g,使gf,保证
- 第二节课,介绍了如何让,即使用PLA、pocket algorithm来实现
- 第三节课,介绍了机器学习的分类
- 第四节课,介绍了机器学习的可行性,通过统计学知识,证明了在一些假设前提下,证明了
那么总的来说机器学习就是为了使
当M很小的时候,由上节课介绍的霍夫丁不等式,得到,即能保证第一个核心问题成立。但M很小时,演算法A可以选择的hypothesis有限,不一定能找到使足够小的hypothesis,即不能保证第二个核心问题成立。当M很大的时候,同样由霍夫丁不等式,与的差距可能比较大,第一个核心问题可能不成立。而M很大,使得演算法A的可以选择的hypothesis就很多,很有可能找到一个hypothesis,使足够小,第二个核心问题可能成立。
从上面的分析来看,M的选择直接影响机器学习两个核心问题是否满足,M不能太大也不能太小。
Effective Number of Lines
如果平面上只有一个点x1,那么直线的种类有两种:一种将x1划为+1,一种将x1划为-1:
平面上有两个点时,直线的种类有4种:
但是在平面有三个点的情况也会出现不能用一条直线划分的情况:
也就是说,对于平面上三个点,不能保证所有的8个类别都能被一条直线划分。那如果是四个点x1、x2、x3、x4,我们发现,平面上找不到一条直线能将四个点组成的16个类别完全分开,最多只能分开其中的14类,即直线最多只有14种:
Effective Number of Hypotheses
dichotomy(二分类)就是将空间中的点(例如二维平面)用一条直线分成正类(蓝色o)和负类(红色x)。令H是将平面上的点用直线分开的所有hypothesis h的集合,dichotomy H与hypotheses H的关系是:hypotheses H是平面上所有直线的集合,个数可能是无限个,而dichotomy H是平面上能将点完全用直线分开的直线种类,它的上界是。接下来,我们要做的就是尝试用dichotomy代替M。
成长函数(growth function),记为。
成长函数就是让我们找最大的dichotomy。也就是找之前对应effective lines的数量最大值。
针对一维的Positive Rays:
若有N个点,则整个区域可分为N+1段,很容易得到其成长函数。注意当N很大时,,这是我们希望看到的
针对一维的Positive Intervals:
它的成长函数可以由下面推导得出:
上面的成长函数中,蓝色的表示在N+1个节点中选择两个端点进行切割,两个端点之间为+1即,红色的表示不选择端点进行切割,即所有的节点都是-1.
这种情况下,,在N很大的时候,仍然是满足的。
再来看这个例子,假设在二维空间里,如果hypothesis是凸多边形或类圆构成的封闭曲线,如下图所示,左边是convex的,右边不是convex的。那么,它的成长函数是多少呢?
当数据集D按照如下的凸分布时,我们很容易计算得到它的成长函数。这种情况下,N个点所有可能的分类情况都能够被hypotheses set覆盖,我们把这种情形称为shattered。也就是说,如果能够找到一个数据分布集,hypotheses set对N个输入所有的分类情况都做得到,那么它的成长函数就是。
Break Point
我们已经知道:
对于2D perceptrons,我们之前分析了3个点,可以做出8种所有的dichotomy,而4个点,就无法做出所有16个点的dichotomy了。所以,我们就把4称为2D perceptrons的break point(5、6、7等都是break point)。令有k个点,如果k大于等于break point时,它的成长函数一定小于2的k次方。
break point的定义就是使 的k的最小值。那么根据该定义,我们可以得出:
通过观察,我们猜测成长函数可能与break point存在某种关系:对于convex sets,没有break point,它的成长函数是2的N次方;对于positive rays,break point k=2,它的成长函数是O(N);对于positive intervals,break point k=3,它的成长函数是。则根据这种推论,我们猜测2D perceptrons,它的成长函数。如果成立,那么就可以用代替M,就满足了机器能够学习的条件。
总结
本节课,我们指出针对N个训练数据,最多只有个hypothesis,由此引出了成长函数。针对不同的情况,成长函数也各有不同。对于我们学习的2D perceptrons,我们发现从某点开始是少于次的。由此又引出break point的概念。