Feasibility of Learning
Learning is Impossible？
我們想要在D以外的資料中更接近目标函數似乎是做不到的，隻能保證對D有很好的分類結果。機器學習的這種特性被稱為沒有免費午餐（No Free Lunch）定理。NFL定理表明沒有一個學習算法可以在任何領域總是産生最準确的學習器。不管采用何種學習算法，至少存在一個目标函數，能夠使得随機猜測算法是更好的算法。
Probability to the Rescue
Connection to Learning
下面，我們将罐子的内容對應到機器學習的概念上來。機器學習中hypothesis與目标函數相等的可能性，類比于罐子中橙色球的機率問題；罐子裡的一顆顆彈珠類比于機器學習樣本空間的x；橙色的彈珠類比于h(x)與f不相等；綠色的彈珠類比于h(x)與f相等；從罐子中抽取的N個球類比于機器學習的訓練樣本D，且這兩種抽樣的樣本與總體樣本之間都是獨立同分布的。是以呢，如果樣本N夠大，且是獨立同分布的，那麼，從樣本中 h ( x ) ≠ f ( x ) ) h(x)\neq f(x)) h(x)̸=f(x))的機率就能推導在抽樣樣本外的所有樣本中 h ( x ) ≠ f ( x ) h(x)\neq f(x) h(x)̸=f(x)的機率是多少。
這裡我們引入兩個值 E i n ( h E_{in}(h Ein(h)和 E o u t ( h ) E_{out}(h) Eout(h)。 E i n ( h ) E_{in}(h) Ein(h)表示在抽樣樣本中，h(x)與 y n y_n yn不相等的機率； E o u t ( h ) E_{out}(h) Eout(h)表示實際所有樣本中，h(x)與f(x)不相等的機率是多少。
Connection to Real Learning
也就是說，不同的資料集 D n D_n Dn，對于不同的hypothesis，有可能成為Bad Data。隻要 D n D_n Dn在某個hypothesis上是Bad Data，那麼 D n D_n Dn就是Bad Data。隻有當 D n D_n Dn在所有的hypothesis上都是好的資料，才說明 D n D_n Dn不是Bad Data，可以自由選擇演算法A進行模組化。那麼，根據Hoeffding’s inequality，Bad Data的上界可以表示為連級（union bound）的形式：
其中，M是hypothesis的個數，N是樣本D的數量， ϵ \epsilon ϵ是參數。該union bound表明，當M有限，且N足夠大的時候，Bad Data出現的機率就更低了，即能保證D對于所有的h都有 E i n ≈ E o u t E_{in}\approx E_{out} Ein≈Eout，滿足PAC，演算法A的選擇不受限制。那麼滿足這種union bound的情況，我們就可以和之前一樣，選取一個合理的演算法（PLA/pocket），選擇使 E i n E_{in} Ein最小的 h m h_m hm作為g，一般能夠保證 g ≈ f g\approx f g≈f，即有不錯的泛化能力。
是以，如果hypothesis的個數M是有限的，N足夠大，那麼通過演算法A任意選擇一個g，都有 E i n ≈ E o u t E_{in}\approx E_{out} Ein≈Eout成立；同時，如果找到一個g，使 E i n ≈ 0 E_{in}\approx 0 Ein≈0，PAC就能保證 E o u t ≈ 0 E_{out}\approx 0 Eout≈0。至此，就證明了機器學習是可行的。
但是如果M是無數個，例如之前介紹的PLA的直線具有無數條，那麼是否這些推論就不成立了呢？
總結
本節課主要介紹了機器學習的可行性。首先引入NFL定理，說明機器學習無法找到一個g能夠完全和目标函數f一樣。接着介紹了可以采用一些統計上的假設，例如Hoeffding不等式，建立 E i n E_{in} Ein和 E o u t E_{out} Eout的聯系，證明對于某個h，當N足夠大的時候， E i n E_{in} Ein和 E o u t E_{out} Eout是PAC的。最後，對于h個數很多的情況，隻要有h個數M是有限的，且N足夠大，就能保證 E i n ≈ E o u t E_{in}\approx E_{out} Ein≈Eout，證明機器學習是可行的。