课程地址：https://class.coursera.org/ntumlone-001/class
课件讲义：http://download.****.net/download/malele4th/10208897
注明：文中图片来自《机器学习基石》课程和部分博客
建议：建议读者学习林轩田老师原课程，本文对原课程有自己的改动和理解

Lecture 5 : Training versus Testing

目录

上节课，我们主要介绍了机器学习的可行性。首先，由NFL定理可知，机器学习貌似是不可行的。但是，随后引入了统计学知识，如果样本数据足够大，且hypothesis个数有限，那么机器学习一般就是可行的。本节课将讨论机器学习的核心问题，严格证明为什么机器可以学习。从上节课最后的问题出发，即当hypothesis的个数是无限多的时候，机器学习的可行性是否仍然成立？

一 Recap and Preview

我们先来看一下基于统计学的机器学习流程图：


该流程图中，训练样本D和最终测试h的样本都是来自同一个数据分布，这是机器能够学习的前提。另外，训练样本D应该足够大，且hypothesis set的个数是有限的，这样根据霍夫丁不等式，才不会出现Bad Data，保证Ein≈Eout，即有很好的泛化能力。同时，通过训练，得到使Ein最小的h，作为模型最终的矩g，g接近于目标函数。

这里，我们总结一下前四节课的主要内容：
第二节课，我们介绍了如何让Ein≈0，可以使用PLA、pocket等演算法来实现；
第三节课，我们介绍了机器学习的分类，我们的训练样本是批量数据（batch），处理监督式（supervised）二元分类（binary classification）问题；
第四节课，我们介绍了机器学习的可行性，通过统计学知识，把Ein(g)与Eout(g)联系起来，证明了在一些条件假设下，Ein(g)≈Eout(g)成立。

这四节课总结下来，我们把机器学习的主要目标分成两个核心的问题：

Ein(g)≈Eout(g)
Ein(g)足够小

二 Effective Number of Line

如何将无数个hypothesis分成有限类呢？
我们先来看这样一个例子，假如平面上用直线将点分开，也就跟PLA一样。

1 如果平面上只有一个点x1，那么直线的种类有两种：一种将x1划为+1，一种将x1划为-1：

2 如果平面上有两个点x1、x2，那么直线的种类共4种：x1、x2都为+1，x1、x2都为-1，x1为+1且x2为-1，x1为-1且x2为+1：

3 如果平面上有三个点x1、x2、x3，那么直线的种类共8种
但是，在三个点的情况下，也会出现不能用一条直线划分的情况

也就是说，对于平面上三个点，不能保证所有的8个类别都能被一条直线划分。

4 那如果是四个点x1、x2、x3、x4，我们发现，平面上找不到一条直线能将四个点组成的16个类别完全分开，最多只能分开其中的14类，即直线最多只有14种：

经过分析，我们得到平面上线的种类是有限的，1个点最多有2种线，2个点最多有4种线，3个点最多有8种线，4个点最多有14（<24）种线等等。我们发现，有效直线的数量总是满足≤2N，其中，N是点的个数。那么即使M无限大，直线的种类也很有限，机器学习也是可能的。

三 Effective Number of Hypotheses

接下来先介绍一个新名词：二分类（dichotomy）。dichotomy就是将空间中的点（例如二维平面）用一条直线分成正类（蓝色o）和负类（红色x）。令H是将平面上的点用直线分开的所有hypothesis h的集合，dichotomy H与hypotheses H的关系是：hypotheses H是平面上所有直线的集合，个数可能是无限个，而dichotomy H是平面上能将点完全用直线分开的直线种类，它的上界是2N。接下来，我们要做的就是尝试用dichotomy代替M。

四 Break Point

五 总结

本节课，我们更深入地探讨了机器学习的可行性。我们把机器学习拆分为两个核心问题：Ein(g)≈Eout(g)和Ein(g)≈0。对于第一个问题，我们探讨了M个hypothesis到底可以划分为多少种，也就是成长函数mH。并引入了break point的概念，给出了break point的计算方法。下节课，我们将详细论证对于2D perceptrons，它的成长函数与break point是否存在多项式的关系，如果是这样，那么机器学习就是可行的。