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

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

如下圖，假設始終有些資料不在 \(D\) 中
機器學習是不可能從 \(D\) 學到正確的 \(g=f\)
那麼從機率上來考慮呢？

Hoeffding's Inequality

$$ \mathbb{P}\left [ \left | v-u \right | > \epsilon \right ]\leq 2e^{-2\epsilon ^2N} $$
  • 需為 i.i.d (independent and identically distributed)
  • \(u\)：橘色彈珠在瓶子內的機率
  • \(v\)： 橘色彈珠在取出樣本中的機率
  • 收斂跟 \(u\) 無關，只跟 \(\epsilon\ \&\ N\) 有關

對應到 ML 上

$$ \mathbb{P}\left [ \left | E_{in}(h)-E_{out}(h) \right | > \epsilon \right ]\leq 2e^{-2\epsilon ^2N} $$
  • \(u\) 的機率 \(\Rightarrow\) 固定的 \(h(\mathbf{x})\neq target\ f(\mathbf{x})\) 的機率
  • 彈珠 \(\in\) 瓶子 \(\Rightarrow\ \mathbf{x}\in\mathbf{X}\)
  • 橘色彈珠 \(\Rightarrow\ {\color{Orange}{h(\mathbf{x}) \neq  f(\mathbf{x})}}\) 
  • 綠色彈珠 \(\Rightarrow\ {\color{Green}{h(\mathbf{x}) =  f(\mathbf{x})}}\) 
  • \(N\ \Rightarrow\ D=\{(\mathbf{x_n},y_n), \cdots \}\)
但這只保證固定的 \(h\)，並未保證從 \(H\) 選出的 \(g\)
固定 \(g=h\) 只適用在 驗證 上

簡單多個 \(h_n\) 例子

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

Hoeffding 的意義

如下表，Hoeffding 是保證不同 \(D_n\) 下，總共出現 bad 的機率
$$ \mathbb{P}_D[bad\ D]=\sum_{all\ D} \mathbb{P}(D)\cdot sign[bad\ D] \le 2e^{-2\epsilon ^2N}$$
\(D_1\) \(D_2\) \(\cdots \) \(D_{1234}\) \(\cdots \) \(D_{7895}\) \(\cdots \) Hoeffding
\(h\) bad bad \(\mathbb{P}_D[bad\ D]\le 2e^{-2\epsilon ^2N}\)

若有 M 個 \(h_n\) 呢？

$$ \begin{align*} \mathbb{P}_D[BAD\ D] &= \mathbb{P}_D[bad\ D\ for \ h_1\ or\ bad\ D\ for \ h_2\ or\ \cdots \ or\ bad\ D\ for \ h_m]\\ &\le\mathbb{P}_D[bad\ D\ for \ h_1]+\mathbb{P}_D[bad\ D\ for \ h_2]+\cdots +\mathbb{P}_D[bad\ D\ for \ h_M] \\ &\le 2e^{-2\epsilon ^2N}+2e^{-2\epsilon ^2N}+\cdots +2e^{-2\epsilon ^2N}\\ &= 2Me^{-2\epsilon ^2N}\\ \end{align*} $$
\(D_1\) \(D_2\) \(\cdots \) \(D_{1234}\) \(\cdots \) \(D_{7895}\) \(\cdots \) Hoeffding
\(h_1\) bad bad \(\mathbb{P}_D[bad\ D\ for \ h_1]\le 2e^{-2\epsilon ^2N}\)
\(h_2\)
bad
\(\mathbb{P}_D[bad\ D\ for \ h_2]\le 2e^{-2\epsilon ^2N}\)
\(h_3\) bad bad bad \(\mathbb{P}_D[bad\ D\ for \ h_3]\le 2e^{-2\epsilon ^2N}\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(h_M\) bad bad \(\mathbb{P}_D[bad\ D\ for \ h_M]\le 2e^{-2\epsilon ^2N}\)
all BAD BAD BAD ?
  • 有限的 M, N, and \(\epsilon\)
  • 無需知道 \(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)\approx0\Rightarrow E_{out}(g)\approx0\)

留言

張貼留言