哈囉，大家好，我是Teresa，上週的筆記提到機器學習似乎不可行，但當統計上的資料還有演算法的選擇是「有限」個時，機器學習還是可行的。
那到底為什麼機器學習可以學到東西？當假說函式集合是無限大的時候，到底會發生什麼事情？
複習機器學習的流程圖，一開始從資料出發，有一個機器學習的演算法，透過資料和它所看到的假說集合，從裡面選擇一個最終的假說函式。
上次加了一個假設是：我們訓練的資料跟最後測試假說的方法都來自同一個分配。
Ein是指在資料上假說的表現；Eout是指未來我們還沒有看過的資料在假說上的表現，我們用同一個分配來描述。
一、假說函數不多的情況
假如假說函式集合不多、資料量又夠多，不管演算法怎麼選擇假說，Ein跟Eout兩者的表現都會長得很像。如果都長得很像，那我們當然要選擇一個Ein最低的，很接近0。因為如果Ein很接近0，那個Eout很大概率機率會很接近0，這樣就達到了學習的效果。
從上述的說明中，機器學習可以分成兩個步驟：
- 第一個步驟是訓練，訓練是指演算法在跑的時候，我們要確保資料上的表現（Ein）很接近0。
- 但訓練還不夠，我們要確保這個假說函式在測試未來未知的資料上，Ein跟Eout也很接近。
二、回顧一下，前四集筆記中我們學到的概念：
Ep. 1：提到機器學習想做的事情是有個未知的目標函式，希望演算法能找到假說函式，能和目標函式非常接近，錯誤率要越小越好，（也就是Eout要很接近0）。
Ep. 2：希望機器學習在我們已知的資料上做的盡量好就好，（也就是Ein要很接近0）。
Ep. 3：機器學習是在很特定的設定下做，像是批次的資料、監督式學習、二元分類。
Ep. 4：在假說函式有限個的狀況下，Ein跟Eout會很接近。
機器學習實際上拆成兩個問題：
- 第一個問題是Ein跟Eout會不會很接近？
- 第二個問題是如果第一個問題成立，怎麼讓Ein越小越好。
三、假說函式集合有限的數量
那在假說函式集合有限的情況下，這個有限的數量（M）是多少，跟這兩個問題有什麼關係？
這個數量M有兩種可能性，一種是相對小的數字，另一種是相對大的數字。
如果是相對小的數字面對上述的第一個問題時，這個M很小的話，不好的事情（Ein 跟 Eout 很不接近）發生的機率就很小；但演算法的選擇就會變得有限，不是每一個問題都能找到 Ein 很小的假說函式。
如果是相對大的數字，問題就會反過來，不好的事情機率增加，但比較有機會找到適合的假說函式。因此，選擇正確的假說函式集合很重要。
Ep. 4 提到的 Hoeffding’s Inequality 推導的方式是當對某個假說函式來說只要有 Ein 跟 Eout 差得很遠的情況發生時，我們就用聯集的方式來避免讓演算法選到這個假說函式。
但問題來了，用聯集的方式當我們加無限多個項的時候，每一個項都不接近0，就有可能加成很大的數字，遠比1來的大。我們能夠用聯集的方式相加是因為 Ein 跟 Eout 差得很遠的情形通常不太會重疊，但實際上當兩種假說函式很接近的時候，它們的資料集合是很接近的，（只要函式不要太糟，Eout就會很接近），也就是說 Ein 跟 Eout 差得很遠的情況會被重複計算，過分估計，而無法處理無限大的狀況。
如果要找出重疊的部分，第一步是把無限多個假說函式分成有限多類。那如何分類呢？
四、「線」的假說函式分類
我們考慮平面上所有的線是我們的假說函式，平面上的線有無限多條，如何歸類？
我們的資料是有限筆，如果只有一筆資料的情況下，我們只會有兩種線而已（實質有三種），一種會說點是紅色的，一種會說成黑色的（如下圖）。
以上面四張圖可以得知：如果我們只從輸入的點看出去時，得到的線的種類是有限的(effective number of line)。
從2D的角度來看，點絕對會小於2N。
如果可以用這個有限數字來取代假說函式的數量(M)的話，而這個數又比2N小很多的話，那麼當N很大的時候，Ein跟Eout差得很遠的情形機率就會很小，會很接近0，那麼我們就可以學到東西了。
如果要用線以外的假說函式集合，要怎麼說有幾種假說函式呢？
五、線以外的假說函式分類
如果我們有N個點，一個函式假說集合可以產生了幾種二分的組合（dichoyomy)。
假說函式集合和二分的組合的差別在前者對每個點做取值；後者只針對N個特定的點做取值。
兩者大小：前者可能是無限多條（如果是線的話），後者是有幾種不一樣的組合，最多就是2N種，因為每個點的值不是圈就是叉。
不同的資料會有不同的dichoyomy集合，我們用最大的dichoyomy集合(m)來當作衡量的依據。
假說函式集合的性質是N（點的個數）的函數，把它稱做成長函數，例如剛剛線的例子中，假說函式集合的數量就是有效的線的數量(effective number of line)，一定會是有限的。
（一）Positive Rays
如果我們要做的是Positive Rays，輸入的值是一維的實數，點都在數線上，接著取一個門檻值，若比門檻值大，假說函式就輸出+1；如果比門檻值小，就輸出-1。
如果用這個函式假說集合，如果給不一樣的N個點，可以切出多少種dichoyomy？
成長函數的答案會是N+1，因為如果把門檻值取在不同的區塊裡，都會產生出一種dichoyomy。
（二）Positive interval
那如果今天要做的是Positive interval：在某個範圍內表示+1，範圍外表示-1，這種函式假說集合，成長函數會是如何？
答案是12N2+12N+1。這兩種例子都遠比2N來的小，如果能把M取代掉的話，就是好事。
（三）Convex Set
如果回到平面的輸出空間，對應到Convex Set，凸的幾何裡面是+1，外面是-1，這種函式假說集合，成長函數會是如何？
一個很極端的可能是，所有輸出的點排在圓圈的邊上，這樣不管要做出什麼樣的dichoyomy，我們可以用一個多邊形，來把想要輸出為+1的點連起來，把多邊形外擴一點，就可以利用這樣的凸多邊形順利預測裡面的點是+1，外面的點是-1。每一種dichoyomy都做得出來代表成長函數會是2N。
如果我們想用成長函數取代原本的M，若成長函數是多項式的話，後面的exp….就會減少得快，當N夠大的時候，Ein跟Eout差得很遠的機率就會很小，很可能接近0，但如果像Convex Set，成長函數是指數的時候就不見得能確保了。
六、Break Point(停止點)
成長函數第一個看起來有希望的點，這樣的點稱做Break Point(停止點)。
在線性的狀況下，4個點的時候就沒辦法做出所有的dichoyomy，4就被稱為停止點。也就是成長函數的值比可能的最大值還要來的小。
Break Point(停止點)也和成長函數的成長速度有關，讓我們下集再繼續吧～
| 成長函數 | Break Point(停止點） | |
Positive Rays | N+1 | 2 |
Positive interval | 12N2+12N+1 | 3 |
| Convex Set | 2N | 沒有 |
| 2D perceptrons | 2N | 4 |
機器學習EP. 5到此結束囉～如果喜歡、想追蹤我更多筆記，可以加入程式小白的 JS Python 學習群的社團。社團中也會有其他學習夥伴和你一起討論、交流、互動哦！
