前言

本系列部落格文章將分享我在 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 的問題。

前言

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

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

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

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

熱身回顧一下

在上一講中我們了解了如何使用線性迴歸的方法來讓機器學習回答實數解的問題，第十講我們將介紹使用 Logistic Regression 來讓機器學習回答可能機率的問題。

可能性問題

我們用心臟病發生的機率這樣的問題來做為例子，假設我們有一組病患的數據，我們需要預測他們在一段時間之後患上心臟病的「可能性」為何。我們拿到的歷史數據跟之前的二元分類問題是一樣的，我們只知道病患之後有或者沒有發生心臟病，從這樣的數據我們用之前學過的二元分類學習方法可以讓機器學習到如何預測病患會不會發病，但現在我們想讓機器回答的是可能性，不像二元分類那麼硬，所以又稱軟性二元分類，即 f(x) = P(+1|x)，取值的範圍區間在 [0, 1]。

軟性二元分類

我們的訓練數據跟二元分類是完全一樣的，x 是病人的特徵值，y 是 +1（患心臟病）或 -1（沒有患心臟病），沒有告訴我們有關「患病機率」的訊息。回想在二元分類中，我們使用 w*x 得到一個「分數」之後，再利用取號運算 sign 來預測 y 是 +1 或是 -1。對於目前這個問題，如果我們能夠將這個「分數」映射到 [0, 1] 區間，似乎就可以解這個問題了～

Logistic 假設

我們把上面的想法寫成式子，就是 h(x) = theta(wx)，映射分數到 [0, 1] 的 function 就叫做 logistic function，用 theta 來表示

Logistic 函式

Logistic regression 選擇使用了 sigmoid 來將值域映射到 [0, 1]，sigmoid 是 f(s) = 1 / (1 + exp(-s))，f(x) 單調遞增，0 <= f(x) <= 1。

如何定義 Logistic Regression 的 Error Function

那麼對於 Logistic 假設，我們要如何定義 Logistic Regression 的 Error Function E_in(h)？回顧一下之前學過的方法，Linear Classificaiton 是使用 0/1 Error，Linear Regression 是使用 Squared Error。

Logistic Regression 的目標是找到 h(x) 接近 f(x)＝P(+1|x)，也就是說當 y=+1 時，P(y|x) = f(x)，當 y=-1 時，P(y|x) = 1-f(x)。我們要讓 Error 小，就是要讓 h(x) 與 f(x) 接近。

使用 Likelihood 的概念

我們知道資料集 D 是由 f(x) 產生的，我們可以用這樣的思路去想，f(x) 跟 h(x) 生成目前看到的資料集 D 的機率是多少，用這種 Likelihood 的概念，我們只要在訓練過程讓 h(x) 跟 f(x) 產生資料集 D 的機率接近就可以。

不過我們並不知道 f(x)，但我們可以知道 f(x) 產生資料集 D 的機率很高，因為確實就是由 f(x) 產生的。

簡而言之就是產生目前所看到的資料集是一個我們不知道的 f(x)，f(x) 可能會產生出很多種資料集，我們看到的只是其中之一，但 f(x) 是我們無法知道的，我們可以去算 g(x)，從眾多的 g(x) 去算出那一個最可能產生我們目前看到的資料集，這就是去算 max likelihood，之後我們就可以說 g(x) 跟 f(x) 很像～

所以我們只要計算讓 h(x) Likelihood 越高越好。

將 Likelihood 套用到 Logistic Regression

所以現在問題轉換成了計算 h(x) 越高越好了，得到最高 likelihood 機率值的就是我們所要的 g(x)。

式子就是 g = argmax likelihood(h)

likelihood(h) 的式子可以描述成 P(x1)h(x1) x P(x2)(1-h(x2)) … P(xn)h(1-h(xn))

又因為 sigmoid 性質 1-h(x) = h(-x)，所以 likelihood(h) 的式子可以描述成 P(x1)h(+x1) x P(x2)(-h(x2)) … P(xn)h(-h(xn))

將式子做一些轉換

likelihood(h)＝P(x1)h(+x1) x P(x2)(-h(x2)) … P(xn)h(-h(xn))，我們要計算的是 max likelihood，所以 max likelihood(h) 正比於 h(score) 連乘，正比於 theta(yn)theta(wxn) 連乘。

我們取上 ln，不會影響計算結果，所以取 ln 做後續的推導。

Cross-Entropy Error

如果 max Likelihood 轉換成 Error，作為 Logistic Regression 的 Error Function，就會是求 min 的 -ln theta(ynwxn) 連加，代進 sigmoid theta，就會得到 ln(1+exp(-ywx))，這又稱為 Cross-Entropy Error

最小化 E_in(W)

機器學習的訓練過程就是最小化 E_in(W)，推導出 Cross-Entropy Error 之後，就可以將 E_in(W) 寫成如下圖所示，該函數是連續、可微，並且是凸函數。所以求解最小值就是用偏微分找到谷底梯度為 0 的地方。

微分過程

E_in(W) 梯度為 0 無法容易求出解

和之前的 Linear Regression 不同，這個 ▿Ein(w) 不是一個線性的式子，要求解 ▿Ein(w)=0 是很困難的。

使用 PLA 優化的方式最佳化

這種情況可以使用類似 PLA 利用迭代的方式來求解，這樣的方法又稱為梯度下降法（Gradient Descent）

逐步優化

要尋找目標函數曲線的波谷，可以想像成一個人站在半山腰，每次都選擇往某個方向走一小步，讓他可以距離谷底更近，哪個方向可以更近谷底(greedy)，就選擇往這個方向前進。

所以優化方式就是 wt+1 = wt + ita(v)，v 代表方向（單位長度），ita 代表步伐大小。

找出 min Ein(wt+ita(v)) 就可以完成機器的訓練了。

轉換成線性

min Ein(wt+ita(v)) 還是非線性的，很難求解，但在細微的觀點上決定怎麼走下一步，原本的 min Ein(wt+ita(v)) 可以使用泰勒展開式轉換成線性的 min Ein(Wt) + ita(V)▿Ein(w)。

Gradient Descent 梯度下降

所以我們真正要求解的是 v 乘上梯度如何才能越小越好，也就是 v 與梯度是完全相反的方向。想像一下：如果一條直線的斜率 k>0，說明向右是上升的方向，應該要向左走，反之，斜率 k<0，向右走才是對的。如此才能逐步降低 E_in，求得 min Ein。

ita 參數的選擇

解決的方向的問題，代表步伐大小的 ita 也很重要，如果步伐太小，到達山谷的速度會太慢，如果步伐太大，則會很不穩定，E_in 會一下太高一下太低，有可能也會無法到達山谷。理想上在距離谷底較遠時，步伐要大一些，接近谷底時，步伐要小一些，所以我們可以讓步伐與梯度數值成正相關，來做到我們想要的效果。

完整的 Logistic Regression Learning Algorithm

先初始化 w0，第一步計算 Logistic Regression 的 Ein 梯度，然後更新 w，wt+1 = wt - ita(V)▿Ein(wt)，直到 ▿Ein(wt+1) = 0 或是足夠多的回合之後回傳最後的 wt+1。（每回合計算的時間複雜度與 Pocket PLA 一樣）

總結

第十講中我們了解了當要用 Logistic Regression 解可能性這樣的問題的時候，我們使用的 sigmoid 來將函數做轉換，因此導出了 cross-enropy error function，最佳化無法直接用偏微分的方式求出解，所以使用了 Gradient Descent 這樣的方式來逐步優化來求出解。

前言

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

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

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

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

熱身回顧一下

在第八講中我們機器學習流程圖裡加入了 error function 及 noise 的概念，並了解在這樣的情況下機器學習還是可行的。前面花了很大的篇幅在說機器為何可以學習，接下來是要說明機器是怎麼學習的。本篇以眾所皆知的線性迴歸為例，從方程式的形式、誤差的衡量方式、如何最小化 Ein，讓我們對線性迴歸在機器學習上的應用有些理解。

信用卡額度問題

回到信用卡這個例子，假設我們現在需要的是判定要發多少信用額度給申請者，這種問題的答案就從發不發卡變成了一個實數，這就是線性迴歸的問題。

線性迴歸

將上述問題寫成線性迴歸式就如下圖，其實與 perceptron 很像，但不用再取正負號。

圖解線性迴歸

圖解線性迴歸問題就會如下圖所示，找一條線或超平面來讓所有的資料點與之的差距最小。

線性迴歸的錯誤衡量

線性迴歸的錯誤衡量一般是使用平方錯誤，所以在計算 Ein 的過程是算出平均平方錯誤最小的值，而 Eout 的差距就可以用平方錯誤來計算效果。最小的 Ein 如何計算呢？

整理成矩陣的形式

我們將 Ein 的式子整理成矩陣的形式，推導過程如下。

最小的 Ein

整理成這種式子的 Ein 理論上已知是個連續、處處可微的凸函數，所以計算最小的 Ein 就是去解每一個維度進行偏微分為 0 所得到的值。他的物理意義就是在這個凸函數中這個點在各個維度都無法再下滑。

最小的 Ein 就是計算 Ein 的梯度

這就是在計算 Ein 的梯度，我們將原本的式子展開後，並對這個式子做偏微分。對矩陣的偏微分的理解我們可以從 1 個維度慢慢推廣，如此就可知 XTXw - XTy = 0 時可以得到最佳解。

線性迴歸最佳解

有上所得到的結果，如果 X^TX 是有反矩陣的話，那就可以很容易的算出 (X^TX)-X^Ty 是我們得到的最佳解，其中 (X^TX)-X^T 又稱為 pseudo-inverse，但如果 X^TX 是 singular，那就無法這樣算出一個最佳的 pseudo-inverse，但還是有辦法得出一個 pseudo-inverse，記為 X+，通常我們會用內建的數學方法得出 pseudo-inverse。

線性迴歸機器學習演算法

如此線性迴歸機器學習演算法就會是這樣，第一步，特徵資料組成一個矩陣 X，答案組成一個向量 y，第二步，計算 X 的 pseudo-inverse，第三步，將 X pseudo-inverse 與 y 做內積，如此就可以得到最佳解 W。

線性迴歸到底是不是機器學習演算法

由於好像是用一個式子就算出答案，所以有人會懷疑線性迴歸到底是不是機器學習演算法，線性迴歸在本質上的確跟遵循機器學習流程，在計算 psedo-inverse 的過程其實就有學習調整的過程，只是我們直接用別人寫好的函式沒辦法看出來，另外，機器學習其實就是想要做到 Eout 好，如果 Eout 好那就是一個機器學習演算法。

分析線性迴歸的 Ein 與 Eout

用一些理論來分析線性迴歸的 Ein 與 Eout，Ein 平均可以推導到 noise level x (1-(d+1)/N)，第一步推導如下圖，我們又稱 XX+ 為 hat matrix H，因為它讓真實的答案 y 變成了預測的答案 y hat，所以就叫 hat matrix H。

Hat Matrix H 的物理意義

y hat 物理意義就是 X 的線性組合，原本有很多個 y hat，可以組成一個線性組合空間，迴歸分析就是在算 y - yhat 最小的，Hat Matrix H 就是把 y 投影到 yhat，然後 I-H 可以將 y 線性轉換到 y - yhat，代表真實答案與預測答案的差距。其中數學上有個性質 trace(I-H) = N-(d+1)，這個沒有證明，只有用自由度來說明。

用這樣的物理意義來證明 noise level x (1-(d+1)/N)

我們用這樣的物理意義來證明 noise level x (1-(d+1)/N)，我們可以想成 y 是從 f(x) 加上一些 noise 得出來的，這個 noise 被 I-H 線性轉換到 y-yhat，如就可以計算出 Ein 平均會是 noise level x (1-(d+1)/N)。

有趣的是 Eout 會是 noise level x (1＋(d+1)/N)，但證明很複雜。

學習曲線

Ein 跟 Eout 都會隨著 N 越大而收斂，而且 Ein 及 Eout 的差距會被 bound 住，所以也有 VC bound 的性質，因此迴歸分析的確可以達成機器學習效果。

線性分類跟線性迴歸

分類 y 是 +1 或 -1，迴歸是實數；分類的假設集合要取 sign，迴歸不用；分類是 0/1 錯誤，迴歸是平方錯誤；分類是個 NP-hard 的問題，不容易算出最佳解，但迴歸可以容易算出最佳解，我們可以把分類問題轉成用迴歸來解嗎？

直覺來想，我們可以算出迴歸解之後，再取 sign，那就變成分類模型了，理論上可以嗎？

觀察分類與迴歸的錯誤衡量

觀察分類與迴歸的錯誤衡量我們可以發現迴歸的平方錯誤曲線是壓在分類的0/1錯誤曲線上的，也就是說平方錯誤一定會比較大。

使用 VC bound 理論將迴歸套用到二元分類

使用 VC bound 理論將迴歸套用到二元分類，可以知道迴歸錯誤會是上界，如果迴歸可以得到 Ein 小，那 Eout 就會小，因此可以將迴歸套用在二元分類上，這樣會比算 PLA 有效率，雖然效果不一定比較好。

我們也可以將迴歸用在先期計算，先計算出最好的 PLA 初始線，然後再進行 PLA 演算法，如此就可以增加 PLA 的效能。

總結

當我們要機器回答實數解的時候，那就是線性迴歸問題。而線性迴歸演算法可以用 pseudo-inverse 很快地算出來，Ein 與 Eout 的差距會隨著 N 越大而收斂，而且在理論上我們可以用線性迴歸來解分類問題。

前言

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

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

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

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

熱身回顧一下

在第七講中我們定義了 VC Dimension，就是最大的 non-break point，當 d_vc 是有限的，且資料 N 夠大，Ein 很小的時候，理論上機器學習是可以達成目標的。

重溫機器學習流程圖

重溫機器學習流程圖，大致的理論我們都已經完備了，但這時又會想，如果資料來源有雜訊（noise）又會如何呢？

雜訊（Noise）是什麼

雜訊是什麼呢？以之前的銀行發卡的例子來說明，比如該發卡未發卡、不該發卡卻發了卡、或是一開始收集的基本資料就是錯的，這些就會是我們搜集到資料時的雜訊，在有雜訊的情況下 VC bond 還會正常運作嗎？

用彈珠顏色會改變來代表雜訊來看 VC bound

之前在推導 VC bound 時是用彈珠來說明，我們可以用不固定顏色的彈珠來代表雜訊推導 VC bound（以 pocket algorithm 可以想成是 o 和 x 在同一線上，所以無法確定 o 或 x，這就是雜訊），也就是資料來源會多了一個 y ~ P(y|x)這個條件，從之前的理論推導中，我們了解了訓練資料跟測試資料都來自同一個資料分佈的話，那 VC bound 就會成立。

新的機器學習流程圖

所以新的機器學習流程圖就可以容忍雜訊。也因此可以容忍雜訊的 pocket algorithm 就有理論基礎了。

錯誤衡量

接下來探討如何衡量 g 跟 f 是否很接近，我們使用 E_out(g) 來衡量，這個衡量方式有三個特點：1. 使用 out of sample 來衡量 2. 用 point-wise 的方式一個點一個點衡量 3. 如果是二元分類的問題就會使用 0/1 error 來衡量。但其實也不一定要遵照這三個特點，有很多不同的方法被提出來，只是我們同常還是會這樣來做錯誤衡量。

兩個重要的 Pointwise 錯誤衡量

有兩個重要的 Pointwise 錯誤衡量方式可以記起來，一個是 0/1 錯誤，這個可以用在分類上；一個是平方錯誤，這個通常用在迴歸問題上，不同的錯誤衡量方式會怎麼影響機器學習呢？

Ideal Mini-Target

從下面可以例子，我們可以從資料來源 P(y|x) 及 error function 了解它們如何互相影響，在 0/1 錯誤的情況下，選擇 y=0.2 會得到最小的 error 0.3，但在平方錯誤的情況下，選擇 y=1.9 才會得到最小的 error 0.29，機器學習的過程也會在 P(y|x) 及 error function 的關係去找出 ideal mini-target f(x)。

再次更新機器學習流程圖

所以選擇用什麼 error function 也會影響機器學習的結果。

錯誤衡量的選擇

錯誤衡量的選擇也還會有其他考量，具體了解一下錯誤，在 0/1 error 這種 error function，會有 false reject 及 false accept 這兩種錯誤，我們會同等的看待這兩種錯誤，只要出錯，那 error 就是 1。

錯誤有權重：超級市場指紋辨識

但實際的世界可能會有這種情況，錯誤是有權重的，我們可以用超級市場指紋辨識給優惠這種例子來說明，如老顧客有優惠，新顧客沒有優惠，如果指紋辨識 false reject 老顧客沒優惠，那就會失去這位老顧客，影響較大，我們可以給這個錯誤較大的權重。但新顧客 false accept 就沒什麼大不了，虧點小錢而已，錯誤的權重應該比較小。

錯誤有權重：CIA 指紋辨識

但如果是在 CIA 機密文件的指紋辨識上，那就反過來了，有權限的人 false reject 沒有什麼大不了，但沒權限的人 false accept 那就會出大問題。

最後更新機器學習流程圖

將這樣的概念套用到機器學習流程圖上面，其實就是在演算法 A 這邊對權重的情況作一些調整。

將錯誤權重套用到演算法

如何將錯誤權重套用到演算法呢？我們用 CIA 指紋辨識這個例子來說明，我們可以直接將 false accept 的錯誤乘上 1000 倍，但這其實只做了一半。

更嚴謹一點

因為資料量沒有變，卻讓 error 直接乘上 1000 倍並不嚴謹，所以我們可以用下面這個方式來想，假設沒權限（false accept 錯誤）的資料複製了 1000 筆相同的資料下去訓練，這樣 false accept 乘上 1000 倍就合理，但實務上我們不會真的複製 1000 筆資料進去，而是在演算法上面多去使用沒權限（false accept 錯誤）的資料做運算的機率大了 1000 倍，這樣就很像虛擬的放大資料。用這樣的方式去調整演算法才比較嚴謹。

結語

在這一講中，我們了解了有雜訊的情況下，機器學習理論上還是可以運作的，並且介紹了錯誤衡量（error measure）的方式也會影響演算法挑選的結果，如果 error measure 有權重的話，那調整演算法時也要嚴謹些，直接在 error function 乘上權重並不夠嚴謹。這一講完備之後，機器學習的基礎理論已經告一段落了，下一講將開始介紹其他機器學習演算法。（我們目前只會 PLA 及 Pocket PLA）

前言

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

在第六講我們可以知道 Break Point 的出現可以大大限縮假設集合成長函數，而這個成長函數的上界是 B(N, k)，且可推導出 B(N, k) 是一個多項式，經過一些轉換與推導我們可以把無限的假設集合代換成有限的假設集合，這個上界我們就稱之為 VC Bond。因此可以從數學理論中得知 2D perceptrons 是可以從數據中得到學習效果，而且也不會有 Ein 與 Eout 誤差過大的情況發生，而這一講將進一步說明 VC Bond。

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

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

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

熱身回顧一下

上一講，我們從 break point 的性質慢慢推導出成長函數是一個多項式，因此我們可以保證 Ein 與 Eout 的差距在 N 資料量夠大的情況下不會因為假設集合的無限累積而差距變得很大。

將成長函數寫得更簡潔一點

目前我們知道假設集合的成長函數是 B(N, k) 這個多項式，實際算出來的值如左圖，其實我們可以直接用 N 的 k-1 次方來表示，實際算出來的值如右圖，總之 B(N, k) 會小於 N 的 k-1 次方，所以我們可以直接用 N 的 k-1 次方來表示成長函數。

VC Bond 告訴我們什麼

將 VC Bond 簡化的成長函數 N 的 k-1 次方帶進上一講的霍夫丁不等式裡，式子可以簡化成下圖。這個式子告訴我們：1. 當成長函數有 break point k，也就是說假設集合很好，2. N 的資料量夠大，也就是說有足夠的好資料集，3. 如果我們有一個演算法可以找出一個 g 讓 Ein 很小，也就是說我們有好的演算法，那麼我們大概就可以說我們讓機器可以學到技巧了。

（當然還是要有好運氣，因為有可能壞事情還是會發生，只是機率較低）

VC Dimension

我們將最大的非 break point 的維度稱之為 VC Dimension。所以 d＿vc 就是 k-1。

定義好 VC Dimension 之後

定義好 VC Dimension 之後，之前舉的 break point 例子就可以改寫成 vc dimension，其中 2D perceptrons 的 vc dimension 就是 3（break point 是 4）。

VC Dimension 與機器學習

我們回到機器學習的概觀圖，vc dimension 的概念告訴我們，當我們有有限的 d＿vc 時，此時演算法所找出的 g 會讓 Eout 與 Ein 很接近。而且不用管用的演算法 A 是什麼、資料 D 是從哪種資料分佈產生的、也不用管 target f 到底是什麼。

對應到 2D PLA

我們把這樣的概念對應到 2D PLA，2D PLA 會從線性可分的資料集 D 中找出一個 g 讓 Ein 為 0。然後 VC Dimention 告訴我們 2D PLA 的 d＿vc 是 3，在資料集 N 夠大的情況下可以保證 Ein(g) - Eout(g) 的差距很小，因此我們就可以說 2D PLA 的 Eout(g) 也會接近 0，這也就是說我們讓機器學習到技巧了。

VC Dimention 跟 Perceptrons 的關係

我們知道 1D perceptron 的 d＿vc 是 2，2D Perceptron 的 d＿vc 是 3，所以我們會猜，d-D 的 perceptrons 的 d＿vc 會不會是 d+1，理論上證明這樣的想法是對的，證明的方法有兩個步驟，第一步證明 d＿vc >= d+1，第二步證明 d＿vc <= d+1，這邊不詳述證明細節。

模型複雜度

我們將新的霍夫丁不等式做一些轉換，將右式表示成 δ（壞事情發生的機率），那 1-δ 就代表是好事情發生的機率，就就是 Ein(g) - Eout(g) <= ε，我們可以知道 d＿vc 會影響壞事情（Ein 與 Eout 差距大）發生的機率，d＿vc 越高，就代表假設集合模型複雜度越高，但也可能讓壞事情發生的機率變高。

模型複雜度圖示

從式子中我們可以看出機器學習的模型複雜度關係如下圖，當 d＿vc 上升時，Ein 會下降，但 Ω 會上升，當 d＿vc 下降時，Ein 會上升，但 Ω 會下降，所以 Eout 要最小 d＿vc 一定是在中間，也就是我們的模型複雜度不能太高也不能太低。

樣本複雜度

從新的霍夫丁不等式我們也可以來算一下樣本複雜度，比如現在我們需要壞事情 Ein 與 Eout 的差距 > ε＝0.1 的機率 <= δ=0.1，且已知 d＿vc=3，這樣我們會需要多少個樣本呢？理論上我們會大概需要 10000 X d＿vc 個樣本點，也就是說 2D perceptrons 大概就需要 30000 個樣本點。但實務上發現只要大概 10 x d＿vc 個樣本點就足夠了。

總結

在第七講中我們定義了 VC Dimension，就是最大的 non-break point，然後在 perceptrons 這樣的模型中，d＿vc 剛好等於 d+1，物理意義上可以想成可以調整的自由度有幾個維度。引進 VC Dimension 的概念之後，我們可以了解到機器學習的模型複雜度及樣本複雜度關係。

前言

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

在第五講中我們了解了如何將 PLA 無限的假設集合透過 Dichotomy、Break Point 這樣的方式轉換成有限的集合，在第六講中我們將更進一步去推導其實這個假設集合的成長函數會是一個多項式，如此我們就可以完全相信PLA 機器學習方法的確在數學理論上是可行的了。

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

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

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

熱身回顧一下

我們先來回顧一下上一講的內容，在上一講我們知道了成長函數似乎跟 break point 有些關係，這一講我們將慢慢導出這樣的關係其實是一個多項式。

從 break point 找其他線索

從上一講提到的 break point 我們知道了成長函數至少會小於 2 的 N 次方，且如果 break point 在k取到了，那 k+1, k+2,… 都會是 break point。

由例子觀察 break point

這邊林軒田教授用了一連串的例子說明了如果 H 有Break Point k，那當 N 大於 k 時，mH(N) 成長函數會大大縮減（以 binary classification 這個問題來說，所有的 H 為 2 的 N 次方個）。

既然知道 mH(N) 成長函數會大大縮減，那究竟能縮減到什麼程度？會不會是一個多項式的形式呢？

Bounding Function

接下来，引出了 Bounding Function 的概念，Bounding Function 的意義就是為了看在 N 個樣本點的情況下，如果 Break Point 為 K，那 mH(N) 會縮減到什麼程度的一個函式。

值得一提的是，這裡的 Bounding Function B(N, K) 只與 N 和 K 有關，與假設集合 H 無關，這樣在 Binary Classification 這個問題下，無論是 positive intervals 還是 1D perceptrons 他們的 Bounding Function 就都會是一樣的，如果我們能夠得到 Bounding Function 的結果，那就可以推廣到各個 Binary Classification 的問題。

所以我們新的目標就是找出 B(N, K) 是不是小於等於 poly(N) 了。

推導 Bounding Function 數學式

從以下投影片的 Dichotomies 例子可以導出 Bounding Function 的一個上界，所以 B(N, k) 會是小於等於 B(N-1, k)+B(N-1, k-1)。（詳細過程可以參考影片）

Bounding Function 定理

Bounding Function 的上界出現了我們想要的多項式形式，這裡得出了一個定理，只要 Break Point 存在，那 mH(N) 成長函數一定能夠被一個多項式包含住，我們可以用投影片中的式子來表示 B(N, k)。

事實上式子中的”小於等於”可以直接是”等於”，這已有證明，但不在這次課程範圍，有興趣可以去找其他資料來看。

找出 break point 就能算出成長函數

有了 Bounding Function 定理，我們就可以透過找出 break point 來算出假設集合的成長函數，比如上一講中我們說 PLA 2D perceptrons 的成長函數小於 2 的 N 次方，現在我們可以說PLA 2D perceptrons 的成長函數小於等於 B(N, 4)，因為 2D perceptrons 的 break point 出現在 4。

把 Bound Function 的定理引入 Hoeffding 不等式

有了上面的推導，我們知道 mH(N) 是可以在某種條件下（Break Point k）被 Bound 住。現在回到 Hoeffding 不等式的 union bound 形式，把 Bound Function 的定理概念引入這個 Hoeffding 不等式可以慢慢推導出投影片中下面的式子。

直觀的想法我們可以把 mH(N) 的上界直接代進 Hoeffding 不等式，但理論上我們不能這樣做，因為目前 Eout(h) 是無限個，因此我們需要做一些轉換才能購買 B(N, k) 引入這個 Hoeffding 不等式。

第一步把 Eout(h) 轉換成有限個

第一步我們需要把 Eout(h) 轉換成有限個，這裡沒有做嚴格的證明，只個了直觀的解釋，假設還有一筆資料 D‘（數量也是 N），得到的結果為 Ein‘，那 Ein 與 Eout 發生 BAD（差距很大），應該跟 Ein 與 Ein‘ 發生 BAD 的情況接近。

所以這個無限的 Eout(h) 就轉換成有限個的 Ein‘(h) 了。

第二步整理式子中的成長函數 mH(N)

利用第一步的结果，再直觀想像一下：為了產生 Ein‘ 我們多了 N 個樣本點，所以成長函數中的 N 就變成了 2N 了。

我們可以想像就樣的結果其實就是我們用了 Bound Function 這個定理，將原本無限的 Union Bound 限縮在一個 BAD overlap 的空間。

第三步代進 Hoeffding 不等式

接下來代進 Hoeffding 不等式就完成了。這樣的轉換就像是 2N 個樣本，現在抽了 N 的樣本出來，這 N 個樣本跟原來 2N 個樣本的真實情況相比發生 BAD 的機率會是多少。這樣還是一個 Hoeffding 不等式，只是就像罐子變小、誤差變小、不放回抽樣的 Hoeffding 不等式。

Vapnik-Chervonenkis（VC）bound

這最終的式子就是 Vapnik-Chervonenkis（VC）bound，它將 Eout 用 Ein’ 來代換，然後將假設集合專換成分類（使用 Bound Function 證明為一個多項式），然後再代進 Hoeffding 不等式。

在 2D perceptrons 中，break point k=4，mH(N) 是 O(N3)，由 VC bound 可知 2D perceptrons 是可以從數據中得到學習效果。

總結

從這一講中，我們可以知道 Break Point 的出現可以大大限縮假設集合成長函數，而這個成長函數的上界是 B(N, k)，且可推導出 B(N, k) 是一個多項式，經過一些轉換與推導我們可以把無限的假設集合代換成有限的假設集合，因此可以從數學理論中得知 2D perceptrons 是可以從數據中得到學習效果的。