快樂學程式

哈囉，大家好，我是Teresa，上週的筆記提到機器學習似乎不可行，但當統計上的資料還有演算法的選擇是「有限」個時，機器學習還是可行的。

那到底為什麼機器學習可以學到東西？當假說函式集合是無限大的時候，到底會發生什麼事情？

複習機器學習的流程圖，一開始從資料出發，有一個機器學習的演算法，透過資料和它所看到的假說集合，從裡面選擇一個最終的假說函式。

上次加了一個假設是：我們訓練的資料跟最後測試假說的方法都來自同一個分配。

Ein是指在資料上假說的表現；Eout是指未來我們還沒有看過的資料在假說上的表現，我們用同一個分配來描述。

一、假說函數不多的情況

假如假說函式集合不多、資料量又夠多，不管演算法怎麼選擇假說，Ein跟Eout兩者的表現都會長得很像。如果都長得很像，那我們當然要選擇一個Ein最低的，很接近0。因為如果Ein很接近0，那個Eout很大概率機率會很接近0，這樣就達到了學習的效果。

從上述的說明中，機器學習可以分成兩個步驟：

1. 第一個步驟是訓練，訓練是指演算法在跑的時候，我們要確保資料上的表現（Ein）很接近0。
2. 但訓練還不夠，我們要確保這個假說函式在測試未來未知的資料上，Ein跟Eout也很接近。

二、回顧一下，前四集筆記中我們學到的概念：

Ep. 1：提到機器學習想做的事情是有個未知的目標函式，希望演算法能找到假說函式，能和目標函式非常接近，錯誤率要越小越好，（也就是Eout要很接近0）。

Ep. 2：希望機器學習在我們已知的資料上做的盡量好就好，（也就是Ein要很接近0）。

Ep. 3：機器學習是在很特定的設定下做，像是批次的資料、監督式學習、二元分類。

Ep. 4：在假說函式有限個的狀況下，Ein跟Eout會很接近。

機器學習實際上拆成兩個問題：

1. 第一個問題是Ein跟Eout會不會很接近？
2. 第二個問題是如果第一個問題成立，怎麼讓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 學習群的社團。社團中也會有其他學習夥伴和你一起討論、交流、互動哦！