這一章節主要探討的是機器學習的可行性。如果在某些情況下，機器學習做不到，是否可以加入其他的假設，或是用其他的方法使它可行。

Learning is Impossible?

• Controversial Answers
  什麼樣的問題機器無法解？比如這個問題，給你六張圖，問另一張圖的 $g(x)$ 是 $+1$ 還是 $-1$？

像這樣的問題，你可以說它是 $+1$，因為 $y_{n} = +1$ 的圖型都是對稱的，而這個圖是對稱的，所以是 $+1$。你也可以說是 $-1$，因為 $y_{n} = -1$ 的圖左上那一格都是黑色的，而這個圖是左上那格也是黑色的，所以是 $-1$。

• A Simple Binary Classification Problem
  這個題目給了 $X_{n}$ 和 $Y_{n}$，機器學到了 $g$，那麼這個 $g$ 和理想的 $f$ 接近嗎？

把可能的 256 種函數都放到 Hypothesis set $H$ 裡，然後請機器選一個在這五筆資料 $D$ 上都和 $f$ 一模一樣的 $g$。問題是，這個 $g$ 是好的嗎？

如果我們用原本的 $D$，那可以很容易說明 $g$ 近似於 $f$，但是如果看 $D$ 以外的資料，那我們如果要說明 $g$ 近似於 $f$ 是非常困難的。

我們想要的一直都是在沒有看過的資料裡，找到一個和 $f$ 相近的 $g$。但是這個例子似乎告訴我們想要的事情是做不到的，天下沒有白吃的午餐。

Probability to the Rescue

• Inferring Something Unknown
  有沒有什麼工具或方法可以對未知的東西做推論？

假如我們現在有一個罐子，裡面有很多橘色和綠色的彈珠，那我們有辦法推估出橘色彈珠的比例嗎？

用取樣的。隨機取十顆彈珠，裡面有三顆是橘色的，那我們可以說罐子裡橘色彈珠出現的機率大概是 $30%$。在我們手上的彈珠中 (in-sample)，橘色彈珠的比例是 $\nu $，它可以告訴我們有關還在罐子裡 (out-of-sample) 的那些彈珠的資訊。

這些資訊並沒有告訴我們罐子裡彈珠的比例，但是它告訴我們罐子裡的彈珠有很大的機率是 $30%$ 的橘色和 $70%$ 的綠色。那在數學上，$\mu $ 和 $\nu $ 又分別說明什麼呢？

• Hoeffding’s Inequality
  我們現在有罐子裡的比例 $\mu $ 和手上樣本的比例 $\nu $，如果今天取了很大的一把 $N$ 個彈珠，$\mu $ 和 $\nu $ 會很接近。

Hoeffding’s Inequality 則說明了當 $N$ 很大，$\mu - \nu $ 就會是一個很小的數字，也就是說 $\mu $ 和 $\nu $ 相減差很遠的機率很小。只要符合這個不等式，就叫做 Probably Approximately Correct (PAC)，差不多是對的。

如果容忍誤差 $\epsilon $ 很大，這個式子不成立的機率也會變小。所以我們不希望 $\epsilon $ 太大，這時候我們就會取很大的 $N$。也就是說如果 $N$ 越大，就有越大的機率可以得到 $\nu \approx \mu$。

Connection to Learning

這小節主要是把前一節提到的抽彈珠的問題，轉化成機器學習的問題。

• Connection to Learning
  在機器學習裡，首先要有一個假設集合 $H$，現在我們從 $H$ 裡面取出其中一個固定的 $h(x)$。把一顆顆的彈珠想像成空間裡一個個 $x$，如果拿到的 $x$，使得 $h(x) \neq $f(x)$，就算這個 $h$ 答錯，像罐子裡的橘色彈珠；反之如果這個 $x$ 使 $h(x) = $f(x)$ 成立，它就答對，是綠色彈珠。當取樣的數字很大，我們就可以用已知的部分資料，來推估 $h(x)$ 在未知資料上的表現。

• Added Components
  把上述的概念轉成元件加進去一開始的機器學習流程圖，有一個未知的機率分佈 $P$ on $X$，這個機率用來取樣產生了 training examples，同樣的機率也可以去衡量 $h$ 和 $f$ 是否接近。

• The Formal Guarantee
  接下來我們把剛剛提到的 $E_{in}$ 和 $E_{out}$ 套進 Hoeffding’s Inequality。$E_{in}$ 是 in-sample error，代表在已知樣本中 $h(x)$ 和 $f(x)$ 的誤差，$E_{out}$ 則是 out-of-sample error，代表已知樣本以外、其他未知的資料中的錯誤。

Hoeffding’s Inequality 告訴我們當 $E_{in}$ 和 $E_{out}$ 很接近， $E_{in}$ 又很小的時候，$E_{out}$ 也會很小，代表當資料繼續由 $P$ 產生的時候，$h$ 和 $f$ 很接近。

• Verification of One $h$
  機器學習的演算法選的是 $g$，前述的保證是在一個固定的 $h$ 上面，如果要做真的學習，必須靠演算法選出一個 $h$ 成為最後輸出的 $g$。

如果選到的 $E_{in}(h)$ 很小，那麼就可以推論出 $g$ 和 $f$ 差不多。但事情不會這麼簡單，通常選到的 $h$ 它的 $E_{in}(h)$ 可能都很大，所以得到的是 $g$ 和 $f$ 不接近。到這邊其實並沒有做到真正的學習，而是驗證 Verification，驗證 $h$ 的表現。

用 verifiying examples 來驗證 $h$ 在這份資料上表現得如何。如果用來取樣的 $P$ 和評斷 $h$ 好不好的分佈一致，那麼既可以確認這個 hypothesis 究竟好不好。

Connection to Real Learning

當只有一個 $h$ 的時候可以做驗證，如果有很多個 $h$ 的時候呢？

• Multiple $h$
  假設有十個 $h$，其中有一個在已知的資料上全對，那是否要選這個 $h$？

想像成丟銅板，如果 150 個人每人拿一個銅板，連續丟五次，我們很有可能找到其中一個人丟了五次都是正面，那這代表什麼？

把銅板想成資料，不好的銅板機率是 $\frac{1}{2}$，$E_{in}$ 是 $0$。不好的資料則是 $E_{in}$ 和 $E_{out}$ 差很遠。而 Hoeffding’s Inequality 在這裡可以說明如果把所有可能的資料 $D$ 都列出來，出現不好的資料的機率加起來非常的小。

• Bad Data fro many $h$
  好的資料是不管演算法怎麼選都對，不好的資料就是演算法沒有辦法自由自在地做選擇（會踩到雷）。剛剛的資料都是用一個 $h$ 來推估，那如果有很多 $h$ 呢？

• Bound of BAD Data
  如果是有 $M$ 個（有限多個） $h$，我們一樣可以用取樣的方式來說明 $h(x)$ 和 $f(x)$ 是否接近。

當資料量夠大，我們可以選到一個好的 $g$，這個 $g$ 的 $E_{in}$ 和 $E_{out}$ 是接近的。合理的做法是選一個 $E_{in}$ 最小的 $g$。

• The ‘Statistical’ Learning Flow
  如果 $H$ 只有 $M$ 個，且取樣的資料 $N$ 夠大，不管演算法怎麼選，$E_{in}$ 和 $E_{out}$ 都會接近。如果 $E_{in}(g)$ 接近 $0$，那麼就可以推出來機器學習是可能的。

但如果 $M$ 是無限大的呢？？下一章告訴你。

Summary

• Learning is Impossible? absolutely no free lunch outside $D$
• Probability to the Rescue: probably approximately correct outside $D$
• Connection to Learning: verification possible if $E_{in}(h)$ small for fixed $h$
• Connection to Real Learning: learning is possible if $\left |H \right|$ is finite and $E_{in}(g)$ is small
• Slides: http://www.csie.ntu.edu.tw/~htlin/mooc/doc/04_present.pdf