上節課，我們主要介紹了機器學習的可行性。首先，由NFL定理可知，機器學習貌似是不可行的。但是，随後引入了統計學知識，如果樣本資料足夠大，且hypothesis個數有限，那麼機器學習一般就是可行的。本節課将讨論機器學習的核心問題，嚴格證明為什麼機器可以學習。從上節課最後的問題出發，即當hypothesis的個數是無限多的時候，機器學習的可行性是否仍然成立？
我們先來看一下基于統計學的機器學習流程圖：
該流程圖中，訓練樣本D和最終測試h的樣本都是來自同一個資料分布，這是機器能夠學習的前提。另外，訓練樣本D應該足夠大，且hypothesis set的個數是有限的，這樣根據霍夫丁不等式，才不會出現Bad Data，保證E_{in}\approx E_{out}，即有很好的泛化能力。同時，通過訓練，得到使EinE_{in}最小的h，作為模型最終的矩g，g接近于目标函數。
這裡，我們總結一下前四節課的主要内容：第一節課，我們介紹了機器學習的定義，目标是找出最好的矩g，使g\approx f，保證E_{out}(g)\approx 0；第二節課，我們介紹了如何讓E_{in}\approx 0，可以使用PLA、pocket等演算法來實作；第三節課，我們介紹了機器學習的分類，我們的訓練樣本是批量資料（batch），處理監督式（supervised）二進制分類（binary classification）問題；第四節課，我們介紹了機器學習的可行性，通過統計學知識，把E_{in}(g)與E_{out}(g)聯系起來，證明了在一些條件假設下，E_{in}(g)\approx E_{out}(g)成立。
這四節課總結下來，我們把機器學習的主要目标分成兩個核心的問題：
Ein(g)≈Eout(g)
E_{in}(g)足夠小
上節課介紹的機器學習可行的一個條件是hypothesis set的個數M是有限的，那M跟上面這兩個核心問題有什麼聯系呢？
我們先來看一下，當M很小的時候，由上節課介紹的霍夫丁不等式，得到Ein(g)≈Eout(g)，即能保證第一個核心問題成立。但M很小時，演算法A可以選擇的hypothesis有限，不一定能找到使E_{in}(g)足夠小的hypothesis，即不能保證第二個核心問題成立。當M很大的時候，同樣由霍夫丁不等式，E_{in}(g)與E_{out}(g)的差距可能比較大，第一個核心問題可能不成立。而M很大，使的演算法A的可以選擇的hypothesis就很多，很有可能找到一個hypothesis，使E_{in}(g)足夠小，第二個核心問題可能成立。
從上面的分析來看，M的選擇直接影響機器學習兩個核心問題是否滿足，M不能太大也不能太小。那麼如果M無限大的時候，是否機器就不可以學習了呢？例如PLA算法中直線是無數條的，但是PLA能夠很好地進行機器學習，這又是為什麼呢？如果我們能将無限大的M限定在一個有限的mHm_H内，問題似乎就解決了。
我們先看一下上節課推導的霍夫丁不等式： P[|E_{in}(g)-E_{out}(g)|>\epsilon]\leq 2\cdot M\cdot exp(-2\epsilon^2N)
其中，M表示hypothesis的個數。每個hypothesis下的BAD events BmB_m級聯的形式滿足下列不等式： P[B_1\ or\ B_2\ or\ \cdots B_M]\leq P[B_1]+P[B_2]+\cdots+P[B_M]
當M=\infty時，上面不等式右邊值将會很大，似乎說明BAD events很大，E_{in}(g)與E_{out}(g)也并不接近。但是BAD events BmB_m級聯的形式實際上是擴大了上界，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：
如果平面上有三個點x1、x2、x3，那麼直線的種類共8種：
但是，在三個點的情況下，也會出現不能用一條直線劃分的情況：
也就是說，對于平面上三個點，不能保證所有的8個類别都能被一條直線劃分。那如果是四個點x1、x2、x3、x4，我們發現，平面上找不到一條直線能将四個點組成的16個類别完全分開，最多隻能分開其中的14類，即直線最多隻有14種：
經過分析，我們得到平面上線的種類是有限的，1個點最多有2種線，2個點最多有4種線，3個點最多有8種線，4個點最多有14（<2^4）種線等等。我們發現，有效直線的數量總是滿足\leq 2^N，其中，N是點的個數。是以，如果我們可以用effective(N)代替M，霍夫丁不等式可以寫成： P[|E_{in}(g)-E_{out}(g)|>\epsilon]\leq 2\cdot effective(N)\cdot exp(-2\epsilon^2N)
已知effective(N)<2N2^N，如果能夠保證effective(N)<2^N，即不等式右邊接近于零，那麼即使M無限大，直線的種類也很有限，機器學習也是可能的。
接下來先介紹一個新名詞：二分類（dichotomy）。dichotomy就是将空間中的點（例如二維平面）用一條直線分成正類（藍色o）和負類（紅色x）。令H是将平面上的點用直線分開的所有hypothesis h的集合，dichotomy H與hypotheses H的關系是：hypotheses H是平面上所有直線的集合，個數可能是無限個，而dichotomy H是平面上能将點完全用直線分開的直線種類，它的上界是2^N。接下來，我們要做的就是嘗試用dichotomy代替M。
再介紹一個新的名詞：成長函數（growth function），記為m_H(H)。成長函數的定義是：對于由N個點組成的不同集合中，某集合對應的dichotomy最大，那麼這個dichotomy值就是m_H(H)，它的上界是2^N：
成長函數其實就是我們之前講的effective lines的數量最大值。根據成長函數的定義，二維平面上，m_H(H)随N的變化關系是：
接下來，我們讨論如何計算成長函數。先看一個簡單情況，一維的Positive Rays：
若有N個點，則整個區域可分為N+1段，很容易得到其成長函數m_H(N)=N+1。注意當N很大時，(N+1)<<2^N，這是我們希望看到的。
另一種情況是一維的Positive Intervals：
它的成長函數可以由下面推導得出：
這種情況下，m_H(N)=\frac12N^2+\frac12N+1<<2^N，在N很大的時候，仍然是滿足的。
再來看這個例子，假設在二維空間裡，如果hypothesis是凸多邊形或類圓構成的封閉曲線，如下圖所示，左邊是convex的，右邊不是convex的。那麼，它的成長函數是多少呢？
當資料集D按照如下的凸分布時，我們很容易計算得到它的成長函數m_H=2^N。這種情況下，N個點所有可能的分類情況都能夠被hypotheses set覆寫，我們把這種情形稱為shattered。也就是說，如果能夠找到一個資料分布集，hypotheses set對N個輸入所有的分類情況都做得到，那麼它的成長函數就是2^N。
上一小節，我們介紹了四種不同的成長函數，分别是：
其中，positive rays和positive intervals的成長函數都是polynomial的，如果用m_H代替M的話，這兩種情況是比較好的。而convex sets的成長函數是exponential的，即等于M，并不能保證機器學習的可行性。那麼，對于2D perceptrons，它的成長函數究竟是polynomial的還是exponential的呢？
對于2D perceptrons，我們之前分析了3個點，可以做出8種所有的dichotomy，而4個點，就無法做出所有16個點的dichotomy了。是以，我們就把4稱為2D perceptrons的break point（5、6、7等都是break point）。令有k個點，如果k大于等于break point時，它的成長函數一定小于2的k次方。
根據break point的定義，我們知道滿足m_H(k)\neq 2^k的k的最小值就是break point。對于我們之前介紹的四種成長函數，他們的break point分别是：
通過觀察，我們猜測成長函數可能與break point存在某種關系：對于convex sets，沒有break point，它的成長函數是2的N次方；對于positive rays，break point k=2，它的成長函數是O(N)；對于positive intervals，break point k=3，它的成長函數是O(N^2)。則根據這種推論，我們猜測2D perceptrons，它的成長函數m_H(N)=O(N^{k-1}) 。如果成立，那麼就可以用m_H代替M，就滿足了機器能夠學習的條件。關于上述猜測的證明，我們下節課再詳細介紹。
本節課，我們更深入地探讨了機器學習的可行性。我們把機器學習拆分為兩個核心問題：E_{in}(g)\approx E_{out}(g)和E_{in}(g)\approx 0。對于第一個問題，我們探讨了M個hypothesis到底可以劃分為多少種，也就是成長函數m_H。并引入了break point的概念，給出了break point的計算方法。下節課，我們将詳細論證對于2D perceptrons，它的成長函數與break point是否存在多項式的關系，如果是這樣，那麼機器學習就是可行的。
注明：
文章中所有的圖檔均來自中國台灣大學林軒田《機器學習基石》課程。