[ML] 機器學習基石：第四講 Feasibility of Learning

ML：基礎學習
課程：機器學習基石
簡介：第四講 Feasibility of Learning

如下圖，假設始終有些資料不在 $D$ 中
機器學習是不可能從 $D$ 學到正確的 $g=f$

那麼從機率上來考慮呢？

Hoeffding's Inequality

$$\mathbb{P}[|v-u|>ϵ]\le 2e^{-2{ϵ}^{2}N}$$

• 需為 i.i.d (independent and identically distributed)
• $u$：橘色彈珠在瓶子內的機率
• $v$： 橘色彈珠在取出樣本中的機率
• 收斂跟 $u$ 無關，只跟 $ϵ\mathrm{\&}N$ 有關

對應到 ML 上

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

• $u$ 的機率 $\Rightarrow$ 固定的 $h(\mathbf{x})\ne targetf(\mathbf{x})$ 的機率
• 彈珠 $\in$ 瓶子 $\Rightarrow \mathbf{x}\in \mathbf{X}$
• 橘色彈珠 $\Rightarrow h(\mathbf{x})\ne f(\mathbf{x})$ 
• 綠色彈珠 $\Rightarrow h(\mathbf{x})=f(\mathbf{x})$ 
• $N\Rightarrow D=\{({\mathbf{x}}_{\mathbf{n}},y_n),\cdots \}$

但這只保證固定的 $h$，並未保證從 $H$ 選出的 $g$
固定 $g=h$ 只適用在 驗證 上

簡單多個 $h_n$ 例子

假設有 150個人投硬幣，隨機連丟五次，那麼是否有運氣特別好的人？
理想上硬幣機率都是一樣的，所以無所謂特別運氣好的人
因出現連五個硬幣都是正面的機率 $1-(\frac{31}{32}{)}^{150}>99\mathrm{\%}$
所以極可能出現連五個正面的人，但能說他運氣特別好嗎？或者能說他就是硬幣之神嗎？

故若 $h_n$ 越多，越容易出現 $E_{in}$ OK，但 $E_{out}$ 卻不好的情況

Hoeffding 的意義

如下表，Hoeffding 是保證不同 $D_n$ 下，總共出現 bad 的機率

$${\mathbb{P}}_D[badD]=\sum _{allD}\mathbb{P}(D)\cdot sign[badD]\le 2e^{-2{ϵ}^{2}N}$$

	$D_1$	$D_2$	$\cdots$	$D_{1234}$	$\cdots$	$D_{7895}$	$\cdots$	Hoeffding
$h$	bad					bad		${\mathbb{P}}_D[badD]\le 2e^{-2{ϵ}^{2}N}$

若有 M 個 $h_n$ 呢？

$$\begin{array}{rl}{\mathbb{P}}_D[BADD]& ={\mathbb{P}}_D[badDfor{h}_{1}orbadDfor{h}_{2}or\cdots orbadDfor{h}_m]\\ & \le {\mathbb{P}}_D[badDfor{h}_1]+{\mathbb{P}}_D[badDfor{h}_2]+\cdots +{\mathbb{P}}_D[badDfor{h}_M]\\ & \le 2e^{-2{ϵ}^{2}N}+2e^{-2{ϵ}^{2}N}+\cdots +2e^{-2{ϵ}^{2}N}\\ & =2M{e}^{-2{ϵ}^{2}N}\end{array}$$

	$D_1$	$D_2$	$\cdots$	$D_{1234}$	$\cdots$	$D_{7895}$	$\cdots$	Hoeffding
$h_1$	bad					bad		${\mathbb{P}}_D[badDfor{h}_1]\le 2e^{-2{ϵ}^{2}N}$
$h_2$		bad						${\mathbb{P}}_D[badDfor{h}_2]\le 2e^{-2{ϵ}^{2}N}$
$h_3$	bad	bad				bad		${\mathbb{P}}_D[badDfor{h}_3]\le 2e^{-2{ϵ}^{2}N}$
$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$	$⋮$
$h_M$	bad					bad		${\mathbb{P}}_D[badDfor{h}_M]\le 2e^{-2{ϵ}^{2}N}$
all	BAD	BAD				BAD		?

• 有限的 M, N, and $ϵ$
• 無需知道 $E_{out}(h_n)$
• $E_{in}(g)=E_{out}(g)$ 是 PAC (probably approximately correct)，而不用管 $A$

總結

• $|H|=M$ 有限，$N$ 足夠大，則即使為 $A$ 挑選出來的 $g$ ，仍可保證 $E_{in}(g)\approx E_{out}(g)$
•  故 $E_{in}(g)\approx 0\Rightarrow E_{out}(g)\approx 0$