机器学习基石 5 Training versus Testing
Recap and Preview
回顾一下机器学习的流程图：
机器学习可以理解为寻找到 \(g\)，使得 \(g \approx f\)，也就是 \(E_{out}(g) \approx 0\) 的过程。为了完成这件事情，有两个关键的步骤，一个是保证 \(E_{out}(g) \approx E_{in}(g)\)，另一个是保证 \(E_{in}(g) \approx 0\) （这两件事情通常由 “训练” 以及 “测试” 这两个过程来完成），当这两件事情都得到保证之后，我们就可以得到 \(E_{out}(g) \approx 0\)，于是完成了学习。
\(M\)（hypothesis 的数目）的取值对这两个问题有影响：
- \(M\) 太小，能保证 \(E_{out}(g) \approx E_{in}(g)\)，但是不能保证 \(E_{in}(g) \approx 0\)；
- \(M\) 太大，能保证 \(E_{in}(g) \approx 0\)，但是不能保证 \(E_{out}(g) \approx E_{in}(g)\)。
下面将尝试解决 \(M\) 较大时，\(E_{out}(g) \approx E_{in}(g)\) 的问题。
Effective Number of Lines
对于这个式子，\(M = \infty\) 时，右侧的值很大，\(E_{out}(g) \approx E_{in}(g)\) 不能保证，于是我们尝试用一个合适的数 \(m_H\) 代替式子中的 \(M\)，使无穷变成有限。
第一个式子中的 \(M\) 来源于 “Union Bound”
其中 \(P[B_M]\) 表示的是第 \(M\) 个假设函数 \(h_M\) 在数据集上发生坏事情（即存在 BAD DATA，\(E_{out}(h_M) \neq E_{in}(h_M)\)）的概率。
然而当 \(M\) 很大时，假设集中存在许多相似的假设函数 \(h\)，它们发生坏事情的概率和情形都很接近，这样使用 “Union Bound” 来计算整个假设集发生坏事情的概率，便存在许多重复的地方，于是算出来的概率会比实际的高很多（over-estimating）。
我们以二元分类来阐述怎么解决这个问题：我们根据分类结果，对 \(h\) 进行分类。
| 1 | 2 类：\(\{o\}\)、\(\{x\}\) |
| 2 | 4 类：\(\{oo\}\)、\(\{ox\}\)、\(\{xo\}\)、\(\{xx\}\) |
| ... | ... |
| N | \(2^{N} 类\) |
对于一个大小为 \(N\) 的数据集，任意一个假设函数 \(h\) 都属于上述 \(2^N\) 个等价类之间的一个，因此我们可以用 \(2^N\) 来代替原不等式中的 \(M\)。
Effective Number of Hypotheses
我们把上面提到的等价类的概念起一个名字叫做 Dichotomy。
具体的 Dichotomy 的 size 与这 \(N\) 个数据的具体取值有关（但是不会大于 \(2^N\)），为方便讨论我们取最大那个 size 来分析，取名为 growth function，记作 \(m_H(N)\)。
接下来我们需要计算 \(m_H(N)\)，首先考虑几种不同的模型的 \(m_H(N)\)
- Positive Rays：\(m_H(N) = N + 1\)
- Positive Intervals：\(m_H(N) = {{N+1} \choose 2} + 1\)
- Convex Sets：\(m_H(N) = 2^N\)
总结如下：
Break Point
我们希望 \(m_H(N)\) 是多项式形式而不是指数形式的，这样才能保证 \(E_{out}(g) \approx E_{in}(g)\)：
我们引入一个概念叫 break point，定义如下所示
于是上面所提到的四种模型的 break point 如下所示：
我们猜测 \(m_H(N)\) 与 break point 有下面的关系：
- no break point：\(m_H(N) = 2^N\)
- break point \(k\)：\(m_H(N) = O(N^{k-1})\)
如果猜测成立，那么在有 break point 的情况下，\(m_H(N)\) 便是一个多项式形式，这样就能保证 \(E_{out}(g) \approx E_{in}(g)\) 了。