台大机器学习基石个人笔记（第五、六章）

机器学习 Coursera

---

第四章遗留了一个问题，即当Hypothesis为无限多的时候，抽取一份训练数据（大小为N），能否依据在训练数据上的表现来选择h？

第五章第六章就来解决这个问题，首先回顾一下一份数据是BAD的概率：

$$P|D\ is\ BAD| \le 2Mexp(-2\epsilon^2N)$$
注意到有一个指数项，那么如果我们能证明M是多项式复杂度，则这项还是趋近于无穷小，当然如果M是指数级，这个问题就不可解。这其实从直觉上是对的，如果有一个分类器可以模拟任何一种情况，那么它可能不能模拟新情况，即没有从训练数据中概括的能力。

对于某一种二元分类器（如感知器模型），在训练数据（大小为N）上可能产生的不同组合是有限的（即把X分成正例或者负例）。N个数据最多有$2^N$这么多种不同的组合，但是对于感知器却不能得到这么多的结果，假设对于N个数据可以得到$m_H(N)$这么多种，如果$m_H(N) << N$，则问题解决了。

下面老师举了很多例子来计算它们的$m_H(N)$:

• Positive Rays: $m_H(N) = N + 1$
• Positive Intevals: $m_H(N) = Poly(N)$
• convex set: $m_H(N) = 2^N$

并引入了一个叫做break point的概念，如果存在大小为k的数据集D，H没法涵盖D的所有情况（即$2^D$种可能），则称k为H的一个break point。一般性的我们把k认为是H最小的break point。
很显然，如果没有break point，那么$m_H(N) = 2^N$，那么如果有的话，是不是会有改进的可能？

---

为此，定义一个函数$B(N,k)$ = max $m_H(N)$ when break point = k.
就是在break point为k时，N个样本在H上的最多可能性。
两个初始情况:$B(N,1) = 1, B(N,k) = 2^N$ for k > N
下面要证明一般情况，思路类似动态规划：
对于B(N,k)，考虑从N-1个点出发。可以将B(N,k)根据最后一个点分为两种情况：1，前N-1个点一致，最后一个点不一样，即在最后一个点上成对，共$2a$个。2，最后一个点上找不到成对的点，共$b$个。

$a+b$就是N-1个点的情况，显然最多可能有$B(N-1,k)$这么多种可能。
单独拿出$a$来看，因为最后一个点两两配对了，所以$a$中的点一定不能shatter k-1个（因为这样k就被shatter了），所以$a <= B(N-1,k-1)$
综上所述：$B(N,k) <= B(N-1,k) + B(N-1, k-1)$，复杂度为多项式。
使用B(N,k)替换$m_H(N)$之后，可以证明结论。