前言

本系列部落格文章將分享我在 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 是可以從數據中得到學習效果的。

前言

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

在第四講中我們了解了在有限假設集合的情況下機器學習是可能的，而第五講就是想要將有限假設集合可以推廣出去，讓我們在無限的假設集合裡也可以透過一些理論慢慢收斂到一個多項式集合，如此我們就可以放心的利用機器學習來解決我們所面對的一些問題。

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

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

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

熱身回顧一下

我們先來回顧一下上一講的內容，在上一講我們知道了機器學習在足夠的資料及有限的假設集合這種情況下是可行的。

更新機器學習流程圖

如果假設集合 H 是有限 M 個，然後資料量夠多 N，不管我們的演算法 A 是什麼，我們由定理可以知道 Eout 跟 Ein 是很接近的。所以如果 A 找到了一個假設 g 讓 Ein 近似於 0，那我們就可以說 Eout 大概就會是 0，因此機器學習在這樣的情況下是可行的。

有了這樣的概念，我們擴充了我們的機器學習流程圖。從輸入資料中去訓練機器學習，然後得到 Ein 近似於 0，之後再從同一個資料分佈中去測試機器學習的結果，如此可以證明機器有學習到技能。

機器學習的兩個核心問題

機器學習有兩個核心問題，我們希望 Eout 跟 Ein 是很接近的，這個意思就是說，我們希望後來測試學習的結果，會跟訓練時得到的結果很接近，這樣我們才能說機器有學習到技能。

另一個就是，我們希望 Ein 可以很小，也就是訓練的過程中，我們希望機器就可以得到很好的效果，也就是誤差很小。

那之前我們所說的有限集合 M 在這邊扮演什麼角色呢？

Ｍ 的兩難

如果假設集合 M 很小，我們可以保證 Eout 可以接近 Ein，但是因為假設集合小，可以挑選的選擇就少，也因此 Ein 可能會是一個不小的值，也就是誤差會大。

如果假設集合 M 很大，我們可以會得到一個比較好的 Ein，也就是誤差比較小，但是 M 太大我們就無法保證 Eout 會跟 Ein 接近，也就是我們無法保證學習的結果，那機器就白學了。

所以 M 是在哪個值剛好能同時解決這個兩個問題就是一個重點。

Ｍ 從哪裡來？

從上一講的定理證明中，我們知道 M 是從當較大的誤差發生的情況累積出來的，所以如果假設集合越大，那累積出來的就一個越大的數字，如果是無限集合，那就沒有上限，但如果是有限集合的話，那就會有個上限。

大誤差發生的情況有很多時候是重疊的

但其實那個上限值我們是高估的，因為許多種大誤差發生的情況都可能是很相似的情況，所以其實這些大誤差發生的情況有很大一部份是重疊的。

那我們可以轉一個想法，我們可以把無限的假設集合依照它們的類型來分類嗎？這樣就可以轉換成一個有限的集合。

一個點的時候有幾種線

之前的 PLA 演算法其實有無限多的假設集合 H，所以在平面上分類一個點的線有無限多條，但是如果說有幾種線，那就只有兩種，一種線是將 x1 分成 o 的，一種線是將 x1 分成 x 的。

兩個點的時候有幾種線

以此類推，兩個點的時候，平面上會多多少種分類這兩個點的線呢？答案是四種線。

四個點的時候有幾種線

再以此類推，四個點的時候，平面上會多多少種分類這四個點的線呢？我們會發現下圖中有兩個組合已經無法找到直線可以做好分類，我們最多只能找到 14 條可以分類四個點的線。

Effective Number of Lines

這個故事告訴我們，隨著輸入變多，線的種類會慢慢變成不是指數型成長。依這樣的概念，我們將原本無限多的線轉變為有限多的不同種類的線，我們就可以用這個有限多的不同種類的線的數字來取代 M，這個數字會小於 2 的 N 次方。

這樣我們就可以再套到霍夫丁的定理，知道這樣的過程機器學習的解決會是有效可行的。

Dichotomies

這樣的過程就是將原本無限多的線，轉換成分種類的線 Dichotomies，一個 Dichotomy 就是一種分類組合，在二元分類裡這樣組合的上界就是 2 的 N 次方，我們可以用這個數字來取代無限大的 M。

找出問題的成長函數

了解這樣的特性之後，我們只要找出我們要解的問題的成長函數，而這個成長函數不會無限增加，那機器學習就可以證明是可行的。

四種成長函數

我們這邊列出了四種成長函數，分屬不同的問題，PLA 是屬於 2D perceptrons，mH 會小於 2 的 N 次方，代進霍夫丁不等式，由於是指數型成長，並無法保証式子會成立。所以我們希望能證明 PLA 的 mH 會是一個多項式，這樣才能保證霍夫丁不等式成立。

Break Point 的概念

Break Point 指的是，當下一個輸入出現時，Dichotomies 組合不再是指數型成長的的那個點，在 2D perceptrons 這邊從我們剛剛的例子可以知道 break point 出現在 4 個輸入時。

四種成長函數的 Break Points

我們知道 positive rays 的 break point 出現在 2，他的成長函數是 big O N，positive intervals 的 break point 出現在 3，他的成長函數是 big O N 平方，那麼在 2D perceptrons 時，我們知道 break point 出現在 4，那他的成長函數是 big O N 三次方嗎？我們可以推廣成一個通式嗎？這就是下次課程的內容了。

總結

機器學習可能的兩個核心問題是 Ein 近似於 0，且 Eout 跟 Ein 要接近。PLA 無限多的線我們可以轉換成 Effective Number of Lines 也就是轉換成 Effective Numbers of Hypotheses，M 無限集合也就轉為 mH 的有限集合，然後觀察 break point 的出現，讓我們可以知道假設集合不會是一個指數型成長的情況，如此依照霍夫丁不等式所說的，我們就可以讓機器學習的理論有充分的證明為可行了。