[ML] 機器學習基石：第五講 Training versus Testing

ML：基礎學習
課程：機器學習基石
簡介：第五講 Training versus Testing

$$\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 2\cdot M\cdot e^{-2{ϵ}^{2}N}$$

	讓 $E_{out}(g)\to E_{in}(g)$	讓 $E_{in}(g)\to 0$
小 M	Yes	No，太少選擇
大 M	No	Yes

需取一個合適的 $M$，但若 $M=\mathrm{\infty }$ 則必定不會收斂，那麼 $M$ 有限嗎？

是否存在一個有限的 $M=m_H$ 呢？

如下，若取聯集，事實上是高估錯誤，有許多重疊的部分

$$\mathbb{P}[{\mathit{B}}_{\mathit{1}}or{\mathit{B}}_{\mathit{2}}or\cdots or{\mathit{B}}_{\mathit{M}}]\le \mathbb{P}[{\mathit{B}}_{\mathit{1}}]or\mathbb{P}[{\mathit{B}}_{\mathit{2}}]or\cdots or\mathbb{P}[{\mathit{B}}_{\mathit{M}}]$$

例：$H=\{alllinesh\in {\mathbb{R}}^2\}$ 無限多條線，但二分法下表現的種類有限
一個點，只有兩種

兩個點，只有四種

三個點，八種 跟 六種

四個點，最多十四種

得證：二分法下，$M\le 2^N$

成長函數

$$\begin{array}{rl}H& =\{hypothesish:\mathbf{X}\to \{\mathrm{x},\mathrm{o}\}\}\\ h({\mathbf{x}}_{\mathbf{1}},{\mathbf{x}}_{\mathbf{2}},\cdots ,{\mathbf{x}}_{\mathbf{N}})& =(h({\mathbf{x}}_{\mathbf{1}}),h({\mathbf{x}}_{\mathbf{2}}),\cdots ,h({\mathbf{x}}_{\mathbf{N}}))\in \{\mathrm{x},\mathrm{o}{\}}^N\\ H({\mathbf{x}}_{\mathbf{1}},{\mathbf{x}}_{\mathbf{2}},\cdots ,{\mathbf{x}}_{\mathbf{N}})& \Rightarrow \mathrm{所}\mathrm{有}\mathrm{可}\mathrm{能}\mathrm{的}\mathrm{組}\mathrm{合}\\ m_H(N)& =\underset{{\mathbf{x}}_{\mathbf{1}},{\mathbf{x}}_{\mathbf{2}},\cdots ,{\mathbf{x}}_{\mathbf{N}}\in \mathbf{X}}{max}|H({\mathbf{x}}_{\mathbf{1}},{\mathbf{x}}_{\mathbf{2}},\cdots ,{\mathbf{x}}_{\mathbf{N}})|\end{array}$$

	hypotheses $H$	dichotomies $H({\mathbf{x}}_{\mathbf{1}},{\mathbf{x}}_{\mathbf{2}},\cdots ,{\mathbf{x}}_{\mathbf{N}})$
例如	$h\in {\mathbb{R}}^2$	$\left\{oooo,ooox,ooxx,\cdots \right\}$
大小	$\mathrm{\infty }$	$m_H(N)\le 2^N$

例子：
Positive Rays

$$m_H(N)=N+1$$

Positive Intervals

$$\begin{array}{rl}{m}_H(N)& =(\genfrac{}{}{0ex}{}{N+1}{2})+1\\ & =\frac{1}{2}{N}^2+\frac{1}{2}N+1\end{array}$$

Convex Sets

$$\begin{gathered} m_H(N)=2^N \\ shatteredbyH \end{gathered}$$

$m_H(N)$ 上升速度

$$\mathbb{P}[|E_{in}(g)-E_{out}(g)|>ϵ]\le 2\cdot m_H(N)\cdot e^{-2{ϵ}^{2}N}$$

定義 break point k：從 k 開始，無論是 k+1, k+2, ... 永遠 $m_H(k)<2^k$

• positive rays: $m_H(N)=N+1=O(N)$ 
• break point at 2 
• positive intervals: $m_H(N)=\frac{1}{2}{N}^2+\frac{1}{2}N+1$ 
• break point at 3 
• convex sets: $m_H(N)=2^N$ 
• no break point 
• 2D perceptrons: $m_H(N)<2^N$ in some cases 
• break point at 4 
• 若是 5, 6, 7, ... 也都擁有 4 個點，若 4 個點都無法 shatter，那麼它們也無法

推測 (下一講證明)：

• no break point: $m_H(N)=2^N$ 
• break point k: $m_H(N)=O(N^{k-1})$