MLF Lecture 6 Theory of Generalization
機器學習基石(Machine Learning Foundations)笔记第六弹
Restriction of Break Point
受最小突破点 k 的限制，随着 N 增大， mh(N) ≪ 2N ，下面通过画图枚举 dichotomies( x1, x2…xn 数值(O 或 X)的排列组合)，研究 mh(N) 受 k 的限制情况
N = 3, k = 2 的时候，可以找到一个 4 dichotomies 的"解"（不唯一）满足任意 两个 x 组合不发生 shatter 的情况:
而 5 dichotomies 一定无法满足条件:
Table of Bound Function
为了进一步研究 k 对 mh(N) 的限制性质，并试图发现其间的函数关系，我们定义 bounding function B(N,k) 代表 breakpoint = k 下 mh(N) 的最大值
于是我们得到 bounding function 的一张表
由以下性质可以得到表的右上部分：
- N < k 时， break point 的约束无效(N 个数据中选不出 k 个点），所以 B(N, k) = 2N
- N = k 时，除了 N 个点不能**shatter**外无其他限制， B(N, k) = 2N − 1
但关键的地方正是左下部分，很明显，这需要用递归的思想解决
Left Bottom Of Bound Table
下面的证明描述都只是大体的思路(sketch of proof)
以对 B(4, 3) 为例，针对下图是这个解，我们可以 x4 拆分出来，将 x1, x2, x3 相同而 x4 不同的分为一组（图中用橙色标出），组数 α ;剩下的各自单独为一组（用紫色标出），组数 β
于是有 B(4, 3) = 2α + β
遮住 x4 不看，去掉条重复的橙色条目，由 k=3 可知 α + β < B(3, 3)
具体见下图：
遮住 x4 不看，再去掉紫色的部分，注意到如果 x1, x2, x3 中存在两组 x 可以 shatter ，由于每个橙色条目一定对应 x4 的两种情况，那么一定会存在 3 组 x 满足 shatter 的情况；所以此时 no "shatter" any 2
即: α < B(3, 2)
具体见下图：
用类似的方法，可以得到 B(N,k)的递推不等式: B(N, k) ≤ B(N − 1, k) + B(N − 1, k − 1)
用数学归纳法可以证明:
这里用到二维的数学归纳法，步骤：
取 N, k 最小能取到的值，证明其满足条件
固定 N，证明 B(N,k)成立下 B(N+1,k)也成立
固定 k，证明 B(N,k)成立下 B(N,k+1)也成立
Bad Bound for General H
我们实际能证明的 Bad Bound 需要在原来设想的式子上增添一些常数
What we want:
Actually, when N large enough,
A Pictorial Proof
这一部分其实并不能算是证明，只是一个结合图形的说明。
Step 1: Replace Eout by E′in
为了将 infinite 的 Eout 用有限的量代替，我们假设还有一组测试数据 D′ (ghost data)，然后可以做出一张关于数据的概率分布图，两边的是 E′in 和 Ein ，中间的是 Eout
由图像及数学证明可得，属于 E′in 的面积大于 1/2，可以得 Ein − Eout > ϵ 的 $\frac{1}{2}$ 不超过 $E_{in} - E'_{in} > \frac{\epsilon}{2}$ 概率。
得:
ce & P \end{aligned}
于是我们完成了转化：
Step 2: Decompose ℋ by Kind
经过第一步的处理，**infinite** 的 ℋ 变为 |ℋ(x1, …, xN, x′1, …, x′N)| 种。再利用 ****union bound**** ，可以得这 2N 个点上的 Dichotomy 最多有 mℋ(2N) 种。
于是有:
color{red}{2} m_{H}(2N) P \end{aligned}
Step 3: Use Hoeffding without Replacement
这部分没有理解，就直接记录课件内容了 想象一个有 2N 个球的管子，取 N 个给 Ein,留下的 N 个给 $E'in$，有:
这属于无放回的 Hoeffding，于是有:
color{red}{2}m_{H}(2N)2exp(-2( )N ) \end{aligned}
Vapnik-Chervonenkis(VC) Bound
到此，我们成功得到了以下这个被称为 VC Bound 的不等式:
ce & m_{H}(2B)exp (- ^2N ) \end{aligned}
对 2D perceptrons 来说，由于其 break point 为 4，所以 mℋ(N) = O(N3) ，进而得到二维感知器的学习是可能的。