上節課，我們主要介紹了機器學習的可行性。首先，由NFL定理可知，機器學習貌似是不可行的。但是，随後引入了統計學知識，如果樣本資料足夠大，且hypothesis個數有限，那麼機器學習一般就是可行的。本節課将讨論機器學習的核心問題，嚴格證明為什麼機器可以學習。從上節課最後的問題出發，即當hypothesis的個數是無限多的時候，機器學習的可行性是否仍然成立？
一、Recap and Preview
我們先來看一下基于統計學的機器學習流程圖：
該流程圖中，訓練樣本D和最終測試h的樣本都是來自同一個資料分布，這是機器能夠學習的前提。另外，訓練樣本D應該足夠大，且hypothesis set的個數是有限的，這樣根據霍夫丁不等式，才不會出現Bad Data，保證Ein≈Eout，即有很好的泛化能力。同時，通過訓練，得到使Ein最小的h，作為模型最終的矩g，g接近于目标函數。
這裡，我們總結一下前四節課的主要内容：第一節課，我們介紹了機器學習的定義，目标是找出最好的矩g，使g≈f，保證Eout(g)≈0；第二節課，我們介紹了如何讓Ein≈0，可以使用PLA、pocket等演算法來實作；第三節課，我們介紹了機器學習的分類，我們的訓練樣本是批量資料（batch），處理監督式（supervised）二進制分類（binary classification）問題；第四節課，我們介紹了機器學習的可行性，通過統計學知識，把Ein(g)與Eout(g)聯系起來，證明了在一些條件假設下，Ein(g)≈Eout(g)成立。
上節課介紹的機器學習可行的一個條件是hypothesis set的個數M是有限的，那M跟上面這兩個核心問題有什麼聯系呢？
我們先來看一下，當M很小的時候，由上節課介紹的霍夫丁不等式，得到Ein(g)≈Eout(g)，即能保證第一個核心問題成立。但M很小時，演算法A可以選擇的hypothesis有限，不一定能找到使Ein(g)足夠小的hypothesis，即不能保證第二個核心問題成立。當M很大的時候，同樣由霍夫丁不等式，Ein(g)與Eout(g)的差距可能比較大，第一個核心問題可能不成立。而M很大，使的演算法A的可以選擇的hypothesis就很多，很有可能找到一個hypothesis，使Ein(g)足夠小，第二個核心問題可能成立。
二、Effective Number of Line
我們先看一下上節課推導的霍夫丁不等式：
當M=∞時，上面不等式右邊值将會很大，似乎說明BAD events很大，Ein(g)與Eout(g)也并不接近。但是BAD events Bm級聯的形式實際上是擴大了上界，union bound過大。這種做法假設各個hypothesis之間沒有交集，這是最壞的情況，可是實際上往往不是如此，很多情況下，都是有交集的，也就是說M實際上沒那麼大，如下圖所示：
也就是說union bound被估計過高了（over-estimating）。是以，我們的目的是找出不同BAD events之間的重疊部分，也就是将無數個hypothesis分成有限個類别。
如何将無數個hypothesis分成有限類呢？我們先來看這樣一個例子，假如平面上用直線将點分開，也就跟PLA一樣。如果平面上隻有一個點x1，那麼直線的種類有兩種：一種将x1劃為+1，一種将x1劃為-1：
如果平面上有兩個點x1、x2，那麼直線的種類共4種：x1、x2都為+1，x1、x2都為-1，x1為+1且x2為-1，x1為-1且x2為+1：
也就是說，對于平面上三個點，不能保證所有的8個類别都能被一條直線劃分。那如果是四個點x1、x2、x3、x4，我們發現，平面上找不到一條直線能将四個點組成的16個類别完全分開，最多隻能分開其中的14類，即直線最多隻有14種：
三、Effective Number of Hypotheses
再來看這個例子，假設在二維空間裡，如果hypothesis是凸多邊形或類圓構成的封閉曲線，如下圖所示，左邊是convex的，右邊不是convex的。那麼，它的成長函數是多少呢？
四、Break Point
上一小節，我們介紹了四種不同的成長函數，分别是：
五、總結
本節課，我們更深入地探讨了機器學習的可行性。我們把機器學習拆分為兩個核心問題：Ein(g)≈Eout(g)和Ein(g)≈0。對于第一個問題，我們探讨了M個hypothesis到底可以劃分為多少種，也就是成長函數mH。并引入了break point的概念，給出了break point的計算方法。下節課，我們将詳細論證對于2D perceptrons，它的成長函數與break point是否存在多項式的關系，如果是這樣，那麼機器學習就是可行的。