公开课 | 机器学习基石05 Training versus Testing
统计机器学习流程图
在学习统计机器学习流程图(Learning Flow)过程中，涉及到两个核心问题：
1. Eout(g) 是否能够和 Ein(g) 足够解决？
上篇解决了在|H|=M是有限的条件，并且样本独立同分布时，N 充分大时，机器学习演算法A任意选出的g，都能够保证 Eout(g) = Ein(g)。现有问题是需要解决当|H|无穷大的情形。
2. Ein(g) 是否能够足够小？ - 训练 Train
M的权衡
分析一下两种情况：
1. 当 M 很小时，数据量足够大时，P(BAD Case) 会比较小；但是选择余地会很小，不一定 Ein 足够小。
2. 当 M 很大时，即便数据量足够大时，P(BAD Case) 可能会很大；好处就是有足够多的 h 可以选择，确保存在 h，Ein 足够小。
接下来三讲会最终解决机器学习的可行性，即便 |H| 是 ∞。
先看下解决的思路，对于 M = ∞ 是否可以引入 m_H 代替 M，减少 ∞ 这个上界。
为了找到 m_H，有必要理解之前 M 的来源。
定义 BAD events，其中 Bm 是指指定 hm 发生坏事情的概率。
假设 A 在 M 个 h 中随意选择，坏事情发生的概率上界记为：P(B1 or B2 or ... or B_M)。
假设最坏的情形(假定所有 hypothesis 没有重叠)，由 Union bound 法则可知：
显然，M = |H| = ∞ Union Bound 法则不再使用。
一个好消息
好消息是：Hypothesis 通常是重叠的(overlapping)，所以 Union bound 是 over-estimating，这就是我们的突破口: 我们可以将 Hypothesis 进行分组，将无限多的 Hypothesis 分成有限类。
简单情形: Effect Number of Lines
在 2d 的平面中，当有 1 个点，直线可以分成 2 类；当有 2 个点，直线可以分成 4 类；当有 3 个点，最多可以分成 8 类； 当 4 个点时，最多可以分成 14 类。
这样引入了 Effect Number of Lines = effect(N) 的概念：
定义：effective(N) = Maximum kinds of lines with respect to N inputs x1,x2,...,xn。
利用 grouping 的思想：
我们希望 effective(N)<< 2^N 来代替 M。
Dichotomies 的引入
先看定义：
h(x) 推广到n个点。h(x1, x2,..., xn) 本质是多元函数，自变量是任意n个点。|H(x1, x2,..., xn)| 可以代替 M。
|H(x1,x2,...,xn)| 具体的数据集(x1,x2,...,xn)有关，讨论起来不方便，有必要去除数据集的因素，取最大的那个值作为成长函数 mH(N)。这样的话，m_H(N) 只与H 和 N有关了。mH(N) 的求解是一个典型的动态规划问题。
下面介绍几种典型的X的成长函数。
Positive Rays
Positive Intervals
Convex Sets
总结：
成长函数 m_H(N) 分为两种：
1. Polynomial : good
2. Exponential : bad
转自：机器学习小蜜蜂
阅读伙伴公众号更多精彩内容，点击 “ 阅读原文 ”