Lecture 5 : Training versus Testing

视频地址：https://www.youtube.com/watch?v=SEYAnnLazMU

---

测试与训练

用期末考试举例。
测试：

训练：

M$M$ 从哪里来？
不好的事件 Bm${\mathcal{B}}_m$ 是 ’ |Ein−Eout|>ϵ$|E_{in}-E_{out}|>ϵ$ ‘

联合边界：

可以在 M$M$ 上进行改进吗？
不好的事件非常重叠。

蓝线和绿线是两个分界面。

替代 M$M$
用输入点的有限集合来替代所有的输入空间，并且计算二分法(假设)的数量

二分法：微型假设
一个假设 h:X→{−1,+1}$h:\mathcal{X}\to \{-1,+1\}$
一个二分 h:{x1,x2,⋯,xN}→{−1,+1}$h:\{{\mathbf{\text{x}}}_1,{\mathbf{\text{x}}}_2,\cdots ,{\mathbf{\text{x}}}_N\}\to \{-1,+1\}$

假设集 |H|$|\mathcal{H}|$ 的数量无限的。
二分集合 |H(x1,x2,⋯,xN)|$|\mathcal{H}({\mathbf{\text{x}}}_1,{\mathbf{\text{x}}}_2,\cdots ,{\mathbf{\text{x}}}_N)|$ 的数量最多为 2N$2^N$

The growth function
计算了 N$N$点上最多的二分集

growth function满足 : mH(N)≤2N$m_{\mathcal{H}}(N)\le 2^N$

• mH(3)=8$m_{\mathcal{H}}(3)=8$
• mH(4)=14$m_{\mathcal{H}}(4)=14$ (当+1点在对角线上时无法分割)

---

examples

1.射线

2.区间

3.凸集

根据下图理解：

N$N$ 个点被凸集“shatter”了

当 mH(N)$m_{\mathcal{H}}(N)$ 替代 M$M$时会怎样？
只需证明 mH(N)$m_{\mathcal{H}}(N)$ 是多项式

---

break point

定义： 如果没有大小为 k$k$ 的数据集可以被 H$\mathcal{H}$ ‘shatter’,那么 k$k$就是 H$\mathcal{H}$ 的一个break point

对于2维的感知机，break point是 k=4$k=4$

继续前面的例子：

• 对于射线 mH(N)=N+1$m_{\mathcal{H}}(N)=N+1$ , break point 是 k=2$k=2$
• 对于区间 mH(N)=12N2+12N+1$m_{\mathcal{H}}(N)=\frac{1}{2}{N}^2+\frac{1}{2}N+1$ , break point 是 k=3$k=3$
• 对于凸集 mH(N)=2N$m_{\mathcal{H}}(N)=2^N$ , break point 是 k=∞$k=\mathrm{\infty }$

---

结论

没有break point ⟹mH(N)=2N$⟹m_{\mathcal{H}}(N)=2^N$
有break point ⟹mH(N)$⟹m_{\mathcal{H}}(N)$ 是 N$N$ 的多项式