前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習技法（Machine Learning Techniques）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 機器學習基石系列 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

從機器學習基石課程中，我們已經了解了機器學習一些基本的演算法，在機器學習技法課程中我們將介紹更多進階的機器學習演算法。首先登場的就是支持向量機（Support Vector Machine）了，第一講中我們將先介紹最簡單的 Hard Margin Linear Support Vector Machine。

線性分類回憶

回憶一下之前的課程中，我們使用 PLA 及 Pocket 來學習出可以分出兩類的線。

哪條線最好？

但其實可以將訓練資料分類的線可能會有很多條線，如下圖所示。我們要怎麼選呢？如果用眼睛來看，你或許會覺得右邊的這條線最好。

為何右邊這條線最好？

為何會覺得右邊這條線最好呢？假設先在我們再一次取得資料，可以預期資料與訓練資料會有點接近，但並不會完全一樣，這是因為 noise 的原因。所以偏差了一點點的 X 及 O 再左邊這條線可能就會不小心超出現，所以就會被誤判了，但在右邊這條線就可以容忍更多的誤差，也就比較不容易 overfitting，也因此右邊這條線最好。

如何描述這條線？我們可以說這條線與最近的訓練資料距離是所有的線中最大的。

胖的線

我們希望得到的線與最近的資料點的距離最大，換的角度，我們也可以說，我們想要得到最胖的線，而且這個胖線還可以將訓練資料分好分類。

Large-Margin Separating Hyperplane

這種胖的線名稱就叫 Large-Margin Separating Hyperplane，原本的問題就可以定義成要找最大的 margin，而且還要分好類，也就是 yn = sign(wTXn)。

最大的 margin 可以轉換成點與超平面之間最小的距離 distance(Xn, w)，然後 yn = sign(wTXn)，就代表 Yn 與 score 同號，所以可以轉換成 YnwTXn > 0，我們需要求解滿足這些條件的超平面。

點與超平面的距離 - 符號解釋

點與超平面的距離怎麼算呢？在這邊的推導，我們需要暫時將 w0 分出來，寫成 b，所以我們之前熟悉的 wTXn 在這邊暫時變成 wTxn + b，以方便推導。

點與超平面的距離 - 推導

如果我們現在有一個超平面 wTx + b = 0，假設 x’ 與 x” 都在這個超平面上，也就是 wTx’ + b 及 wTx” + b 都會是 0，如此就會得到 wTx’ = -b 及 wTx” = -b。現在我們將 wT 與 (X”- X’) 相乘，由於剛剛的式子，我們會得到 0。(X”- X’)是一個在 wTx + b = 0 超平面上的向量，W 與這個向量相乘會是 0 就代表 w 是這個超平面的法向量，要算 x 與超平面的距離，就是將 (x-x’) 這個向量投影到 w，就可以算出點與超平面的距離了，公式如下所示。

分開訓練資料的超平面

由於我們要求的事可以分開訓練資料的超平面，因此已有 yn(wTXn+ b) > 0 這個條件，也因此距離公式中的 |wTx+b| 可以用 yn(wTXn + b) 來取代，這樣會比較容易求解。

減少超平面解的數量

觀察一下下圖中所有求解的條件，我們可以再進一步簡化。假設我們要找的是 wTx + b = 0 這個超平面，我們對這個超平面進行縮放其實是沒有任何影響的，現在我們也將 wTx + b 進行放縮，讓它跟 yn 相乘會是 1，也就是 yn(wTXn + b) = 1，這樣原本的 margin(b,w) 就是可以轉換成 1 除以 w 的長度，我們只要求讓這個值最大的平面就可以了。

再次簡化問題

經過上述的推導，我們的問題變成求滿足(1) max 1/||w|| 及 (2) min yn(wTXn + b) = 1 這兩個條件的超平面，但這樣我們好像還是覺得有些複雜不會解，可以再這麼簡化呢？

min yn(wTXn + b) = 1 這個條件我們可以讓它的限制再鬆一點，只要 yn(wTxn+b)>=1 就好了，理論上保證最後得到的解，一定會有等於 1 的情況，而不會全部都大於 1。

另外 max 1/||w|| 我們改成 min ||w||，||w|| 是 wTw 開根號，我們可以不理根號然後乘上 ¹⁄₂ 以方便後面的推導，所以轉換成 min ¹⁄₂(wTw)。

解一個簡單的問題來看看

現在我們求解的條件變成求 min ¹⁄₂(wTw) 且 yn(wTXn + b)>=1 的超平面，我們用一個簡單的例子來求解看看。如下圖所示，我們可以找出 w1 = 1, w2 = -1, b = -1 滿足我們的條件，這個超平面就是 x1 - x2 - 1，這個超平面也稱為 Support Vector Machine（SVM）。

支持向量機（Support Vector Machine）

從上面這個簡單例子，讓我們來了解一下支持向量機。首先，這個向量可以由 margin 的公式得出 marging 的寬度值。我們會發現有些點會剛好在這個 margin 的邊界上，這些點就是所謂的支持向量（Support Vector）。這些支持向量可以標出胖線的位置，其他的點則無法，所以其他的點在這個問題上是不重要的點。

所以 SVM 的意思就是：透過 Support Vector 的協助來學習出最胖的超平面。

實際上怎麼解這個問題？

我們剛剛只是從一個簡單的例子來解 SVM，那實際上怎麼解這個問題呢？之前我們學過 gradient descent，在這邊好像沒用，因為有很多限制，我們不能讓演算法自由自在的計算 gradient descent。

但這個問題其實有現存的方法可以解，觀察所有的限制式就會發現 SVM 可以用二次規劃（quadratic programming）來找出最佳解。

二次規劃

我們把 SVM 的限制式，跟二次規劃的限制式做一個比較，就發現可以將問題轉換成二次規劃的相關參數，找出 SVM 問題在二次規劃時的 u, Q, p, a, c，我們就可以把這些參數丟到 QP Solver 來幫我們解 SVM。

目前各語言都有提供 QP Solver，但是介面參數可能會不相同，要自己讀文件去了解各個參數，自己做轉換。

第一個 SVM

使用 QP Solver 你就可以解第一個學會的 SVM，這個 SVM 是 hard margin（需要訓練資料線性可分），且學習出來的是線性模型，如果要做非線性模型，只要將資料做非線性轉換就可以了。

探討一下其中的理論

為何胖的超平面會比較好呢？除了我們前述用例子說明之外，有沒有什麼理論基礎呢？其實如果觀察 SVM 的限制式，我們把它拿來與正規化做比較，會發現 SVM 與正規化實際上做的事情很類似，也因此兩個方法都有避免 Overfitting 的能力。

SVM 的優勢

SVM 的優勢在哪呢？之前我們學過可以將資料做特徵轉換到高維度，讓假設集合變多，可以學習更複雜的模型，但這很可能會造成 overfitting。但簡單的模型假設集合太少，無法學習複雜的模型。

我們希望可以讓假設集合不是太多，但又可以學習較複雜的模型，SVM 就可以兩全其美，他比起正規化更好的地方就在於正規化需要對原來的演算法作調整，但 SVM 本身就像是一個具備正規化的演算法。

總結

在這一講我們了解了 SVM，且知道 SVM 的特性就是去找出可以將訓練資料分好的一條最胖的超平面。而實務上我們會用二次規劃的工具來解 SVM。

前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習基石（Machine Learning Foundations）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 第十五講 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

在上一講中，我們了解了如何使用 Cross Validation 來幫助我們客觀選擇較好的模型，基本上機器學習所有相關的基本知識都已經具備了，這一講是林軒田老師給的三個錦囊妙計，算是一種經驗分享吧～

第一計 奧卡姆剃刀

資料的解釋應該要越簡單越好，我們應該要用剃刀剃掉過分的解釋，據說這句話是愛因斯坦說的。

如下圖，我們在使用機器學習時，也希望學習出來的模型會是左較簡單的模型。在直覺上我們會覺得左圖會比右圖夠有解釋性，當然理論上也證明如此了。

較簡單的模型

什麼是叫簡單的模型呢？較教簡單的模型，就是看起來很簡單，假設較少、參數較少，假設集合也比較好。

簡單比較好

那為什麼簡單會比較好呢？除了之前數學上的解釋之外，我們可以有這樣直觀的解釋：如果一個簡單的模型可以為數據做一個好的鑒別，那就代表這個模型的假設很有解釋性，如果是複雜的模型，由於它永遠都可以把訓練資料分的很好，這樣其實是沒有什麼解釋性的，也因此用簡單的模型會是比較好的。

所以根據這一計的想法，我們應該要先試線性模型，然後盡可能了解自己是不是已經盡可能地用了簡單的模型。

第二計 避免取樣偏差

取樣有可能會有偏差，VC 理論其中的一個假設就是訓練資料與測試資料要來自於同一個分佈，否則就無法成立。如果取樣有偏差，那機器學習的效果就會不好。

處理取樣偏差

要避免取樣偏差，要好好了解測試環境，讓訓練環境跟測試環境可以儘可能接近。舉例來說，如果測試環境會使用時間軸近期的資料，那訓練時要想辦法對時間軸較近的資料做一些權重的調整，在做 Validation 的時候也應該要選擇時間軸較近的資料。

另一個例子，其實信用卡核卡問題也有取樣偏差的風險，因為銀行只會有錯誤核卡，申請人刷爆卡的記錄，卻沒有錯誤不核卡，但該位申請人信用良好的資料。因此搜集到的資料本身就已經有被篩選過了，也因此可以針對這個部分在做一些優化。

第三計 避免偷看資料

之前我們的課程中有說過，我們可能會因為看過資料而猜測圈圈會有最好的效果，但這樣就會造成我們的學習過程沒有考慮到人腦幫忙計算過的 model complexity，所以我們要避免偷看資料。

資料重複利用地偷看

其實使用資料的過程中，我們就不斷地偷看資料，甚至看別人論文時，也是在累積偷看資料的過程，所以需要了解到這個概念，有可能讓你的機器學習受到影響。

處理資料偷看

實際上偷看資料的情況很容易發生，要做到完全不偷看資料很難，所以我們可以做的就是，一開始就將測試資料鎖起來，學習的過程中完全不用，然後使用 Validation 來避免偷看資料。

如果說希望將自己的 Domain Knowledge 加入假設，應該一開始就加進去，而不是看完資料再加進去。然後，要時時刻刻會實驗的結果存著懷疑之心，要有一種感覺這樣的結果可能受到的資料偷看污染的影響。

Power of Three

除了三個錦囊妙計，林軒田老師將機器學習的重點整理成 Power of Three，帶我們整個回顧一下。

第一個是機器學習有三個相關領域，Data Mining、Artificial Intelligence、Statistics。

• Data Mining 是從大量的數據裡面找出有趣的特性，它跟 ML 是高度相關的。
• Artificail Intelligence 是想讓機器做一些有智慧的事，ML 是實現 AI 的一種工具。
• Statistics 是從數據裡做一些推論的動作，是 ML 的一種工具。

三個理論保證

• Hoeffding 不等式，針對單一個 hypothesis 保證錯誤率在某個上界，我們會用在 Testing。
• Multi-Bin Hoeffding，針對 M 個 hypothesis 保證錯誤率在某個上界，我們會用在 Validation。
• VC Bound，針對所有的 hypothesis set 保證錯誤率在某個上界，我們會用在 Training。

三個模型

• PLA/Pocket，用在二元分類，由於是 NP-Hard 的問題，我們使用特殊的方法來優化。
• Linear Regression，線性迴歸很容易優化，可以用公式解。
• Logistic Regression，用來計算機率，使用遞迴的方式優化。

三個重要工具

• Feature Transform，可以轉換到高維空間，將 Ein 變小。
• Regularization，與 Feature Transform 相反，讓模型變簡單，VC Dimenstion 變小，但 Ein 會變大。
• Validation，留下一些乾淨的資料來做模型的選擇。

未來的方向

底下所有機器學習相關的關鍵字都是未來可以去學習的，將在後續的機器學習技法課程中講解。大致上有三個方向，一個是更多不一樣的轉換方式，不只有多項式的轉換；一個是更多的正規化方式；最後一個是沒有那麼多的 Label，比如說無監督式的學習等等。

前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習基石（Machine Learning Foundations）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 第十四講 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

在上一講中，我們進一步了解了如何透過正規化（Regularization）來避免 Overfitting，但正規化這個方法會有一個參數 lambda，這個 lambda 我們又要如何選擇呢？在這一講將會學習到使用 Validation 這個方法來幫助我們選擇比較好的 lambda 值，同理，這個方法也可以幫助我們用於選擇各種不同的學習模型。

許多學習模型可以使用

經過了前面 14 講，我們已經學會了許多學習模型，在演算法上我們有 PLA、Pocket、Linear Regression、Logistic Regression 可以做選擇；然後在模型學習的過程中，我們可以指定演算法要經過幾次的學習，每次學習優化的過程要走多大步；我們也可以有很多種線性轉換的方式將模型轉換到更複雜的空間來進行學習；如果模型太過複雜了，我們也有很多種正規化的方法來讓模型退回叫簡單的模型，並可透過 lambda 這個參數來調整退回的程度。

我們可以任意組合，但組合完之後我們要怎麼判斷哪個組合未來在做預測時效果會比較好呢？

用 Ein 來做選擇

如果我們用 Ein 來做選擇，那就永遠會選擇到比較複雜的模型，這在上一講中我們已經知道這很可能會有 Overfitting 發生。所以用 Ein 來做選擇是很危險的。

用 Etest 來做選擇

使用 Etest 來做選擇，基本上理論上是可行的，但 Etest 實際在我們訓練的過程中是不能拿來用的，直接拿 Etest 來幫助我們選擇模型其實是一種作弊行為。所以用 Etest 來做選擇也是不可行的。

引進 Eval

既然用 Ein 或 Etest 來做選擇是不可行的，那如果我們把我們手中的資料 D 保留一份下來作為 Dval，然後在訓練的過程中都不使用 Dval，等訓練完之後，在挑選各種模型的時候再用 Dval 來做選擇，那這樣會是一個比較安全的做法。

這有點像是我們在練習時，會把一些練習題留下來，等考試之前再驗證看看自己的成果如何，機器學習也用上了這個概念。

進一步了解 Dval

所以有了 Dval 的概念之後，我們就會把拿到的資料先分成 Dtrain 及 Dval，Dtrain 用來做訓練得出 g-，Dval 用來做驗證。在霍夫丁不等式的理論中，我們可以保證 Eout(g-) 會跟 Eval(g-) 很接近。所以用 Eval 來選擇最好的模型是可行的。

選出 Eval 表現最好的模型

所以現在當我們有很多個模型需要做選擇時，每個會用訓練資料先得出各自最好的 g-，然後我們再用驗證資料計算 Eval，Eval 表現最好的模型就是我們要的。不過 g- 使用的訓練資料較少，也因此未來的表現也可能因為訓練資料少而受影響。所以我們選出了最好的模型之後，會再將所有的資料使用進去訓練出一個最好的 g。

驗證資料的影響

我們用一些實驗來看驗證資料的影響，用 Ein 來選的話，Eout 就會是上面那條黑實線，因為 Ein 永遠會選擇最複雜的模型。然後用 Etest 來選模型，當然會得到最好的 Eout 值，但這是作弊。紅色的線代表我們用 g- 直接來做預測，當驗證資料越多的時候，g- 的 Eout 值就變高了，有時甚至比 Ein 選出來的模型還差。藍色的線代表我們用驗證資料選出模型之後，再將全部的資料丟進去訓練出 g，如此得到的效果都會比用 Ein 來選好。

那要保留多少驗證資料

從上面的實驗，我們會知道驗證資料的多寡也會影響選出來的模型，所以我們應怎麼選擇保留多少驗證資料呢？實務上我們目前都是用 ¹⁄₅ 的資料作為驗證資料。

一個極端的例子

我們從 Eout(g) 及 Eout(g-) 及 Eval(g-) 的關係中觀察，如果我們的驗證資料 k 越小，那 Eout(g) 與 Eout(g-) 就會越接近；但驗證資料 k 越大，那 Eout(g-) 及 Eval(g-) 就會越接近；有沒有方法可以讓 Eout(g) 跟 Eout(g-) 很接近，卻又可以讓 Eval 可以正確地挑出最好的模型。

這個方法就是 leave-one-out cross validataion，每次只保留一個資料作為驗證資料，重複這個過程，直到所有的資料都做過驗證資料，並將所有的 Eval 做平均之後，Eval 最好的那個模型就會是我們想要的模型。

用一個簡單的例子來說明 Leave One Out

我們用一個簡單的例子來說明 Leave One Out Cross Validation 選擇模型的效果。假設現在我們有三個點，現在有兩個模型要做選擇，一個是線性模型，一個是常數模型。從下圖我們可以看出常數模型的 Eloocv 會比較小，所以我們就會用常數模型作為我們最後訓練完的結果。

這也告訴我們，當資料很少的時候，有時選擇簡單的模型效果反而會比較好。

理論上也有保證

我們剛才都是以實驗上的角度來說明 cross validation 是有效果的，這邊有一個理論推導也可以支持這個結果。推導 Eloovc 的期望值時，最後可以得到跟 Eout(N-1) 平均相等。

Leave-One-Out Cross Validation 的缺點

雖然 Leave-One-Out Cross Validation 在理論上的確可以讓我們得到的結果很接近真實得到的 Eout，但這個方法也有缺點。如果我們有 1000 個資料，那我們就每個模型都要訓練一千次來計算出各自的 Eloocv，這樣計算量會非常大。

然後觀察下圖 Eloovc 的曲線，我們可以看出隨著 Feature 值的上升，Eloocv 值不會是一個穩定下降再上升的曲線，它會有跳動的情況發生（例如多個模型表現都很好的情況），所以有時會造成選擇的盲點。

因此實務上我們都不會使用 Leave-One-Out Cross Validation 這個方法來選擇模型。

分份數的概念

Leave-One-Out Cross Validation 很像是把 D 個資料分成 D 分來做 cross validation，那我們可以將份數變少，比如說分成 5 份或 10 份做 cross validation，這樣就可以大大減少計算量了。

目前實務上都是分 10 份，使用 10-fold cross validation。

一些提醒

Cross Validaton 是用來做模型的選擇，基本上也會是用風險，因此 validation 表現的結果很好，也不是百分之百未來做預測時效果都會很好。還是要記得觀察未來的預測情況。

總結

由於我們已經學會了很多機器學習的方法，有許多地方可以調整我們學習的模型，所以在眾多的學習模型中哪個是最好的，我們也需要有一個方法來幫助我們做選擇，這個方法就是 Cross Validation。

前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習基石（Machine Learning Foundations）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 第十三講 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

在上一講中，我們更進一步的了解了什麼是 Overfitting 是因為 stochastic noise 及 deterministic noise 而造成，與簡易地介紹了幾個簡單的方法來避免 overfitting，這一講將介紹一個比較內行的方法來避免 overfitting，這個方法叫做正規化（Regularization）。

正規化

正規化（Regularization）的想法，就是我們了解 overfitting 發生時，有可能是因為我們訓練的假設模型本身就過於複雜，因此我們能不能讓複雜的假設模型退回至簡單的假設模型呢？這個退回去的方法就是正規化。

退回簡單模型就像是加了限制

假設我們現在是一個 10 次多項式的假設集合，我們想要退回成為較為簡單的 2 次多項式假設集合，其實可以想成就像是 2 次以上的項的係數都是 0，也就像是我們為求解的過程加上了一些限制，希望 2 次以上的項的係數都是 0。

使用較鬆的限制

直接將高維的項次設成 0 可能不是一個好方法，通常我們會希望由學習的過程來決定哪些項次要是 0，這樣的得到的學習效果可能會比較好。所以我們的限制就改成，希望不為 0 的係數不超過三個，由機器從資料來學習出最好的 w，這樣可能會得到比較好的結果。而這樣的限制並不是平滑的函數，所以這是一個 NP Hard 的問題。

換個方式得出較為平滑的限制

所以我們需要換個方式得出較為平滑的限制，這樣在演算法上會比較容易求解，在 Regression 這個問題上，我們可以把限制改為 ||w^2|| <= C 來代表 w 不超過三個係數不為 0，這個含義就像是讓 w 限制在某些值裡面，也許他不一定代表 w 不超過三個係數不為 0，但它可能可以包含，而且 C 的值是一個連續的數，求解上會比較容易。

Regularized Linear Regression

加上 ||w^2|| <= C 這個限制的線性迴歸（Linear Regression）就是正規化線性迴歸（Regularized Linear Regression），如何求解優化這個問題呢？

使用 Lagrange Multiplier

讓我們用微觀的角度來看求解優化這個問題，原來沒有限制的時候，我們使用梯度下降法來求解，只需要讓目標函數沿著提度的反方向走，直到梯度為 0。加入了限制之後，這代表 w 需要在一個紅色的球裡面滾動，如圖所示。由圖來看，我們的解應該都是在求的邊界附近，只要梯度與 w 不是平行的，目標函數就可以再向谷底滾動一點點，可以得到更好的解。如此往下推，最佳的結果就是梯度與 w_reg 是平行的時候。所以使用梯度下降法解這個問題，就是去求解 w_reg 及 lamda，然後讓 w_reg 與梯度平行即為最佳解。（而這個 lamda 就是 Lagrange Multiplier）

Ridge Regression

有了上式的概念之後，我們只要知道 lamda，就可以很容易地求出 w_reg。這個式子經過整理之後，能夠直接得出最佳解，這個方法在統計上就稱為是 Ridge Regression。

擴增錯誤

我們將上式進行積分，可以得到下圖中的式子，在意義上我們要優化的除了 Ein 之外，也要考慮到擴增出來的錯誤。由於 WTW 是正的，lambda 及 N 也是正的，因此在優化求解的時候可以保證 WTW 不能太大。這個方法可以對模型複雜度進行懲罰，讓 Ein(W) 在解空間受到了限制。給定 C 跟給定 lamda 對我們來說可能是一樣的，使用這個角度所推導出來的式子對我們來說更容易求解。

如何求 lambda

現在就剩下，改如何給定 lambda 呢？總歸一句話，我們可以做實驗來決定。我們只要知道 lambda 的性質就好，選越大的 lambda 代表懲罰越多，這就代表 w 長度值越小，這其實就就代表 C 越小（限制越多）。

Legendre Polynomials

有一個小細節要注意，之前學過將空間轉換到高維度以求得更小 Ein 的方法，都可以配合正規化來避免 overfitting。不過單純轉換到高次，由於高次的維度 xi 值乘很多次，Regularizer 可能會過度懲罰這些高次項，因此我們需要使用 Legendre Polynomials 來進行高次轉換，讓高次項不會在訓練過程中被過度懲罰。

如何選擇最好的 lambda

如何選擇最好的 lambda？剛剛說要透過實驗，那麼怎麼做實驗呢？這就是下一次的課程了。

總結

在這一章我們學會了如何使用正規化這個方法來避免 overfitting，在核心概念上就像為解空間加上了限制，也因此可以避免過度優化。

前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習基石（Machine Learning Foundations）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 第十二講 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

在上一講中，我們了解了如何使用非線性轉換來讓我們的機器學習演算法可以學習出非線性分類模型，也了解了這樣的方法可能會讓模型複雜度變高，造成 Overfitting 使未來 Eout 效果不佳的情況，所以要慎用此方法。在這一講中將更進一步說明什麼是 Overfitting，並講解如何避免 Overfitting。

Bad Generalization 無法舉一反三

我們來看個例子，現在我們使用一個二次多項式加上一點 noise 產生資料點，由於有 noise，我們是無法學習出一個二次多項式讓 Ein 為 0。但如果我們使用了非線性轉換到四次多項式來進行學習，我們可以找到一個 w 讓 Ein 為 0，看起來可能會像是圖中的紅線。但可想而知紅線的 Eout 可能會非常高，如此我們的機器學習是失敗的，無法舉一反三。

Overfitting 過度優化

其實這就是一種過度優化，當我們發現 Eout - Ein 很大時，就是發生了 Bad Generalization。

我們觀察圖中的 dvc*，當 dvc* 越來越高時，Ein 會下降，但 Eout 會上升，這時就是產生了 Overfitting。

當 dvc* 往左時，Ein 會上升，Eout 也會上升，這時就是產生了 Underfitting。

Underfitting 不會很常發生，因為我們會追求低的 Ein，因此可以避免 Underfitting，但 Overfitting 卻常常發生，因為追求低 Ein，會讓我們不小心進入陷阱。

Case Study ¹⁄₂

我們再來看一個例子，我們現在有兩個 target function，一個是 10 次多項式加上一些 noise，一個是 50 次多項式然後沒有 noise，現在我們使用一個 2 次多項式及一個 10 次多項式來逼近學習這兩個 target function，以觀察 Overfitting 現象。

Case Study ²⁄₂

結果我們發現，當我們將學習模型由 2 次多項式轉換到 10 次多項式時，無論是在 10 次或 50 次多項式的資料點都會產生 Overfitting，Ein 變小了，但是 Eout 卻變得非常大！

Learning Curve

我們將 Ein 及 Eout 的變化畫成圖示，我們可以看出 10 次多項式的模型在資料點 N 趨近于無限大時，的確可以得到很低的 Eout，但在資料點不夠多的情況下，Eout 卻會比原來的 2 次多項式模型高很多，圖中灰色的區域會很容易產生 Overfitting。

Noise 的影響

會產生 Overfitting 其實就是 Noise 的影響，尤其當資料點不夠多的情況下影響會很大，在有 Noise 的情況下，複雜的學習模型會去模擬 Noise，因此也就會造成未來在做預測時反而會不準確。所以在有 Noise 的情況下，有時簡單的模型反而會有好的效果。

Noise 除了我們一般所知的 stochastic noise 之外，還有另一種 Noise，當我們要學習的模型越複雜時，這其實對我們的學習演算法也是一種 Noise，這就是 deterministic noise。我們將這兩個 Noise 與 Data N 的數量畫成圖來觀察 Overfitting，我們可以得到四個結論：

1. 當 data 越少時，Overfitting 越容易發生
2. 當 stochastic noise 越大時，Overfitting 越容易發生
3. 當 deterministic noist 越大時，Overfitting 越容易發生
4. 當使用的學習模型越複雜時，因為他會模擬 Noist，Overfitting 越容易發生

避免 Overfitting 的方法

我們有幾個方法來避免 Overfitting：

1. 先從簡單的模型開始學習，再慢慢使用複雜的模型，這在上一講有說過了。
2. 使用資料清洗（Data Cleaning/Pruning），將錯誤的 label 修正，或直接刪除錯誤的數據。
3. 製造資料（Data Hinting），使用合理的方法將原來手的的資料變得更多，比如在數字識別的這個問題將已有的數字透過平移、旋轉來製造出更多資料。
4. 正規化（Regularization），下 14 講的主題。
5. 驗證（Validation），第 15 講的主題。

總結

在這一講中，我們更了解了什麼是 Overfitting，也觀察到 Overfitting 是很容易發生的，也介紹了一些避免 Overfitting 的方法。

前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習基石（Machine Learning Foundations）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 第十一講 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

在上一講中，我們將線性分類的模型擴展到可以進行多元分類，擴展的方法很直覺，就是使用 One vs One 及 One vs All 兩種分解成二元分類的方式來做到多元分類。在這一講中將講解如何讓線性模型擴展到非線性模型，讓我們可以將機器學習演算法的複雜度提高以解決更複雜的問題，並說明非線性模型會有什麼影響。

線性假設

之前的演算法目前都是基於線性的假設之下去找出分類最好的線，但這在線性不可分的情況下，會得到較大的 Ein，理論上較大的 Ein 未來 Eout 效果也會不佳，有沒有辦法讓我們演算法得出的線不一定要是一條直線以得到更佳的 Ein 來增加學習效果呢？

圈圈可分

我們從肉眼觀察可以發現右邊的資料點是一個「圈圈可分」的情況，所以我們要解這個問題，我們可以基於圈圈可分的情況去推導之前所有的演算法，但這樣有點麻煩，沒有沒其他更通用的方法？

比較圈圈可分及線性可分

為了讓演算法可以通用，我們會思考，如果我們可以讓圈圈可分轉換到一個空間之後變成線性可分，那就太好了。我們比較一下圈圈可分及線性可分，當我們將 Xn 圈圈可分的資料點，透過一個圈圈方程式轉換到 Z 空間，這時資料點 Zn 在 Z 空間就是一個線性可分的情況，不過在 Z 空間線性可分，在 X 空間不一定會是圈圈可分。

Z 空間的線性假設

觀察在 Z 空間的線性方程式，不同的參數在 X 空間會是不同的曲線，有可能是圓、橢圓、雙曲線等等，因此我們了解在 Z 空間的線會是 X 空間的二次曲線。

一般化二次假設

我們剛剛是使用 x0, x1^2, X2^2 來簡化理解這個問題，現在將問題更一般化，將原本的 xn 用 Phi 二次展開來一般化剛剛個問題，這樣的 Z 空間學習出來的線性方程式在 X 空間就不一定會是以原點為中心，這樣所有的二次曲線都有辦法在 Z 空間學習到了，而起原本在 X 空間的線性方程式也會包含在按次曲線中。

好的二次空間假設

所以原本的問題可以透過這樣的非線性轉換到二次 Z 空間進行機器學習演算法，在 Z 空間的線性可分就可以對應到 X 空間的二次曲線可分。

非線性轉換的學習步驟

了解了這樣的思路之後，非線性轉換的學習步驟就是先將資料點透過 Phi 轉換到非線性空間，然後使用之前學過的線性演算法進行機器學習，由於學習出來的 Z 空間線性方程式不一定能轉回 X 空間，我們實務的上做法是將測試資料透過 Phi 轉換到 Z 空間，再進行預測。

非線性模型是潘朵拉的盒子

學會了特徵轉換使用非線性模型就像打開了潘朵拉的盒子，我們可以任意的將資料轉換到更高維的空間來進行機器學習，如此可以得到更低的 Ein，但這對機器學習效果不一定好，因此要慎用。

代價一：更高的計算及儲存代價

我們可以將資料點進行 Q 次轉換，這樣原本的資料點會有 0 次項、1 次項、2 次項 …. Q 次項，每筆資料的維度都增加了，理所當然計算量及儲存量也都變高了。

代價二：更高的模型複雜度

進行了 Q 次轉換後，資料的為度更高了，理論上 VC dimention 也跟著增加了， VC dimention 代表著模型複雜度，在之前的課程中我們知道較複雜的模型會讓 Eout 變高。

可能會面臨的問題

我們用下圖來說明我們可能會面臨的問題，左圖雖然不是線性可分，但一眼看來其實也是一個不錯的結果，右圖可以得到完美的 Ein，但會覺得有點過頭，我們會面臨的問題就是要如何抉擇左邊或右邊？較高的 Q 次轉換會造成 Eout 與 Ein 不會很接近，但可以得到較小的 Ein，較低的 Q 次轉換可以保證 Eout 跟 Ein 很接近，但 Ein 的效果可能不好，怎麼選 Q 呢？

用看的選有風險

就上述的例子我們可以用圖示來觀察，而使用較低的 Q 次轉換，但如果為度很高，我們是無法畫成圖來看的，而且用看圖的方式，我們可能會不小心用我們的人工運算，直接加上圈圈方程式來降低 VC dimention，這也可能會造成 Eout 效果不佳，因為 VC dimention 是經過人腦降低的，會讓我們低估 VC dimention 複雜度，所以我們應該要避免用看資料的方式來調整演算法。

多項式結構化

我們將 Q 次轉換用下面的式子及圖示結構化，我們可以發現 0 次轉換的假設會包含在 1 次轉換的假設中，1 次轉換的假設會包含在 2 次轉換的假設中，一直到 Q 次轉換這樣的結構，表示成 H0, H1, H2, …., Hq。

假設集合結構化

從 H0 包含於 H1、H1 包含於 H2 …. Hq-1 包含於 Hq 這樣的關係中，我們可以推論 d_vc(H0) <= d_vc(H1) … <= d_vc(Hq)，而在理論上 Ein(g0) >= Ein(g1) … >= Ein(gq)，從之前學過的理論可知，out of sample Eout 在 d_vc 很高、Ein 很低的情況下，不一定會是最低點。

線性模型第一優先

所以依據理論，我們不該為了追求 Ein 低、訓練效果好來做機器學習，這樣是一種自我欺騙，我們要做的應該是使用線性模型為第一優先，如果 Ein 很差，則考慮做二次轉換，慢慢升高 d_vc，而不是一步登天。

總結

在這一講中我們打開了潘朵拉的盒子，學會了使用非線性轉換來得到更好的 Ein，但這會付出一些代價，會讓計算量增加、資料儲存量增加，若一次升高太多模型複雜度，還會造成學習效果不佳，Eout 會比 Ein 高很多，所以要慎用。最好的學習方式就是先從線性模型開始，然後再慢慢升高模型複雜度。

前言

本系列部落格文章將分享我在 Coursera 上台灣大學林軒田教授所教授的機器學習基石（Machine Learning Foundations）課程整理成的心得，並對照林教授的投影片作說明。若還沒有閱讀過 第十講 的碼農們，我建議可以先回頭去讀一下再回來喔！

範例原始碼：FukuML - 簡單易用的機器學習套件

我在分享機器學習基石課程時，也跟著把每個介紹過的機器學習演算法都實作了一遍，原始碼都放在 GitHub 上了，所以大家可以去參考看看每個演算法的實作細節，看完原始碼會對課程中的數學式更容易理解。

如果大家對實作沒有興趣，只想知道怎麼使用機器學習演算法，那 FukuML 絕對會比起其他機器學習套件簡單易用，且方法及變數都會跟林軒田教授的課程類似，有看過課程的話，說不定連文件都不用看就會使用 FukuML 了。不過我還是有寫 Tutorial 啦，之後會不定期更新，讓大家可以容易上手比較重要！

熱身回顧一下

在上一講中我們了解了 Logistic Regression 演算法並了解了如何使用 Logistic Regrssion 來預測心臟病發病機率這樣的問題，這一講中將延伸之前學過的演算法，在理論上說明 Linear Regression 以及 Logistic Regression 都可以用來解 Binary Classification 的問題。學會了 Binary Classification 之後，我們也可以用這樣的技巧來解 Multi-Classification 的問題。

比較之前學過的演算法

比較之前學過的演算法，三個算法最後都會得到一個線性函數來輸出 scroe 值，但 PLA 做 Linear Classification 是一個 NP-hard 的問題，Linear Regression 及 Logistic Regression 則相對較容易求解，我們可以使用 Linear Regression 或是 Logistic Regression 演算法來解 Linear Classification 的問題嗎？

將三個演算法的 Error Function 整理一下

依據各個 Error Function 的算法，我們都可以整理成 ys 的形式，在物理意義上，我們可以說 y 代表正確性，s 代表正確或錯誤程度多少。

畫成圖來瞧瞧

我們以 ys 為橫坐標，error 為縱坐標，把這三個函數畫出來。 0/1 error 在 ys <= 0 時 error 是 1，squre error 在 ys << 1 或 ys >> 1 時會很大，cross-entropy error 在 ys 很小時， error 也會變得很大，但當 squre error 跟 cross-entropy error 很小時，他們 ys 區間所對應的 squre error 也會很小，因此我們可以從這樣的圖得知 squre error 跟 cross-entropy error 都是 0/1 error 的上界。

套用至 VC Bound 理論

將這樣的 Error 上界關係套用 VC Bound 理論，只要 Logistic Regression 或 Linear Regression 的 E_in 小，那 Linear Classfication 的 E_out 就會小，因此理論上我們可以使用 Logistic Regression 及 Linear Regression 來代替 Linear Classfication。

使用 Regression 來做分類

依據以上的理論，我們可以用 Regression 來代替 PLA/Pocket 做分類，會比較有效率（PLA 是一個 NP-hard 的問題），比較一下三個演算法，(1) PLA 在線性可分的時候可以得到一個最佳解，但資料常常不會是線性可分，所以就會用 Pocker 來替代。（2）Linear Regression 可以很快的優化求解，但當 |ys| 很大的時候，positive direction 及 negative direction 的 bound 都太鬆，E_out 可能會效果不好。(3) Logistic Regression 可以用 gradient descent 求解，但在 negative direction 的 bound 會太鬆，E_out 可能會效果不好。

以據上述的特性，我們可以使用 Linear Regression 跑出一個 w 作為 (PLA/Pocket/Logistic Regression) 的 w0，然後再使用 w0 來跑其他模型，這樣可以加快其他模型的優化速度。然後實務上拿到的資料常常不是線性可分的，所以我們會比較常使用 Logistic Regression 而不是 PLA/Pocket。

優化 Logistic Regression

實務上我們會比較常使用 Logistic Regression，但 Logistic Regression 比起 PLA 比較沒有效率，因為 Logistic Regression 在決定優化方向時，會觀察所有的資料點再做決定，時間複雜度是 O(N)，但 PLA 每次只看一個點，時間複雜度是 O(1)，我們可以讓 Logistic Regression 優化到 O(1) 嗎？

隨機梯度下降

我們可以使用隨機梯度下降的方式讓 Logistic Regresiion 優化到 O(1)，這樣的方法就是每次只透過隨機選取一個資料點（xi, yi）來取梯度，然後再用這個梯度對 w 進行更新，這種優化方法就叫做隨機梯度下降。

原來的演算法是用所有的資料點在算梯度，然後取平均，再更新 W，隨機梯度下降是不用每次算所有的點，每次只算一個點來代替所有點的平均。可以這樣做的背後原理，我們可以想成隨機取一個點取很多次之後，大概就是跟所有的點做平均差不多，所以我們可以用隨機梯度下降取代原本的梯度下降。

隨機梯度下降與 PLA 的關係

將隨機梯度下降與 PLA 算式放在一起觀察，可以發現隨機梯度是一個軟性的 PLA，每次調整 0~1 ynxn，但 PLA 只有調與不調，比較硬。

多元分類

我們現在已經會 Binary Classification 了，那 Multi-Classification 的問題要怎麼解呢？

一次分一個類別出來

既然我們會二元分類，我們可以一次分一個類別出來，讓現在要分類出來的資料是 o，其他資料設成 x 來做分類。以這個例子就是先把正方形變成 o，其他變成 x。

結合所有的二元分類

結合所有的二元分類模型之後，我們就可以做多元分類了，不過會有一些區域有模糊地帶。

使用軟性二元分類來解模糊地帶的問題

在這邊我們可以使用軟性二元分類來解模糊地帶的問題，比如將所有的二元分類模型用 Logistic Regression 來訓練，就能讓每個分類器預測出資料是屬於哪一類的百分比，這樣我們就可以從所有的分類器裡面找出百分比最大的那個來預測這個資料點是屬於哪一類，而解決模糊地帶的問題。

One-Versus-ALL (OVA) Decomposition

這樣的方法就是 One-Versus-ALL (OVA) Decomposition，每次把一個類別和非這個類別的當成兩類，用 Logistic Regresion 分類，當分類器輸入某個點，就看這個點在哪一個類別的機率最大。不過這個方法的缺點是，當類別很多的時候，比如 k=100，那每次用 logistic Regression 分類時正樣本和負樣本的差別就會非常大，訓練出來的結果可能會不好。

一次只比較兩個類別

我們可以用一次只比較兩個類別這樣的方法來解決 OVA 樣本資料差距過大的問題。

投票預測分類

這樣的方法，每次只取兩個類別來做訓練，如果一共有 K 類的話，就要做 C(K, 2) 次的 Logistic Regression。當一個資料點輸入做預測時，就用這 C(K, 2) 個分類器給所有 K 個類別投票，取票數大的作為輸出結果。

One-Versus-One (OVO) Decomposition

這樣的方法就是 One-Versus-One (OVO) Decomposition，這種方法的好處是可以應用在任何 Binary Classification 方法，缺點是效率可能會低一些，因為要訓練 C(K,2) 個類別，不過如果類別很多且每個類別的樣本量都差不多的時候，OVO 的方法不一定會比 OVA 方法效率低。

總結

在第十一講中，我們比較了 PLA、Linear Regression 及 Logistic Regression，然後理論上這三個演算法都可以應用在 Linear Classifition 上，然後也學會了使用 Stochastic Greadient Descent 來讓 Logistic Regression 跟 PLA 演算法的計算時間複雜度一樣。學會了 Binary Classification 之後，我們也可以將這樣的方法運用 OVA 及 OVO 的方式來解 Multi-Classification 的問題。