前言

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

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

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

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

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 的出現,讓我們可以知道假設集合不會是一個指數型成長的情況,如此依照霍夫丁不等式所說的,我們就可以讓機器學習的理論有充分的證明為可行了。

前言

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

第四講的內容主要是讓我們知道機器學習是否真的可能,並利用數學上的定理來說明機器學習在某些情境之下是可能的,有數學上定理的支持,我們就可以放心的利用機器學習來解決我們所面對的一些問題。

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

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

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

熱身回顧一下

我們先來回顧一下上一講的內容,在上一講我們知道了各式各樣的機器學習方法及名詞,而我們未來會專注於二元分類及迴歸這樣的問題,然後使用大量監督式標示好的資料且定義明確的特徵來進行機器學習。

看看這個問題,想想如何使用學習

有人會問,說了這麼多,如何知道機器學習是不是真的可能?說不定根本無法做到。比如這個問題,g(x)可以回答 +1 還是 -1。

見仁見智的問題無法解

像這樣的問題,你可以回答 +1,因為 +1 的圖都是對稱的,而這個圖是對稱的,所以是 +1。你可以回答 -1,因為 -1 的圖都是左上方黑色的,而這個圖是左上方黑色的,所以是 -1。

套到二元分類的問題

現在我們套到二元分類的問題,給了 Xn 及 Yn,然後機器學習出了 g,我們可以說 g 近似於 f 嗎?

天下沒有白吃的午餐

在驗證 g 的時候,如果是用原本的 D,那我們很容易的說明 g 近似於 f,但是如果資料是用 D 以外的資料來驗證,那我們無法很明確的說明 g 近似於 f,但我們要的其實就是希望 g 在 D 以外的資料也近似於 f,這有可能嗎?

利用罐子取彈珠的例子來說明是否可能

現在想像我們有一個裡面有很多橘色和綠色彈珠的罐子,我們可能無法知道橘色彈珠的真實比例,但我們可以推估出橘色彈珠出現的機率嗎?

取樣看看

我們取樣看看,比如從罐子中取出十顆彈珠,假設現在取出的是三顆橘色七顆綠色,那我們可以說罐子中的比例是 30% 橘色 70% 綠色嗎?可能不能這樣說,有可能不是這樣比例,但很可能 30% 橘色 70% 綠色是一個很接近的比例數字。

Hoeffding 不等式 1

我們可以說取樣出來的結果會很接近真實情況,是因為 Hoeffding’s Inequality 這個定理。這個定理的數字如下圖,這說明了當 N 很大,也就是我們取樣的數字很大,那們 v - u 就會是一個很小的數字,也就是我們預估的 g 跟真實的 f 的差距很小。而當 ε 很大,也就是我們可以容忍的誤差很大的話,那當然我們就可以很容易地說 g 跟真實的 f 的差距很小。只要符合了這個不等式,那就叫做 probably approximately correct(PAC)。

Hoeffding 不等式 2

通常我們不會希望容忍誤差很大,所以通常我們會取 N 很大來推估 g 是否接近 f 的真實情況。

把 Hoeffding 不等式連結到機器學習

當我們現在有一個固定的 h(x)(假設集合 H 的其中一個,他有可能是 g),我們想要知道是否接近 f(x),x 從 X 中取出,如果 h(x) ̸= f(x),就是 h 答錯,就像是罐子中的橘色彈珠,如果 h(x) = f(x),就是 h 答對,就像是罐子中的綠色彈珠,如果取樣的數字很大的話,那我們就可以用部分的已知資料來大概推估 h(x) 在未知資料的表現情況。

把這個誤差推估的概念加進我們的機器學習圖表

把這個誤差推估的概念加進我們的機器學習圖表,任何一個 h 都可以用已知的 Ein 來推估未知的 Eout,如果 N 夠大。

套進 Hoeffding 不等式

我們套進 Hoeffding 不等式,Ein 代表在已知取樣的中 h(x) 跟 f(x) 的誤差,Eout 代表其他未知的資料中 h(x) 跟 f(x) 的誤差,這在 Hoeffding 不等式的定理下,我們知道 N 很大時,Ein 與 Eout 的誤差很接近,所以我們可以說 Ein 與 Eout 是 PAC。

驗證 h(x) 好不好

所以這常常會被機器學習用在驗證得出來的 h(x) 好不好,可以用這個圖來簡單表示,只要 N 夠大,取樣的分佈一致,那他的表現結果好與不好,是可以很明確地用部分已知資料來推估它在其他未知資料表現得好不好。

好死不死取到壞資料的情況

我們還是會有好死不死取到壞資料的情況,但一樣可以用 Hoeffding 不等式說明這個機率很小,但是還是會發生。

如果有很多個 h

我們剛剛都是用一個 h 來推估是否機器學習是可能的,的確單一個 h 的時候,我們可以用取樣的資料來說明 h(x) 是否跟 f(x) 接近。那如果有很多個 h 呢?

一樣套進 Hoeffding 不等式

如果是有限個 h,如 M 個 h,那一樣我們可以用取樣的資料來說明 h(x) 是否跟 f(x) 接近。

將這樣的概念加進去機器學習圖表

如果 H 這個集合只有 M 個,然後取樣的 N 夠大,利用 A 取出 g,如果 Ein(g) 接近 0,那麼 g 就是一個 PAC 的答案了,我可由此可知機器學習是可能的。那如果 M 是無限大呢?這個就要下一講來解答了。

總結

這一張說明了,我們無法直觀地說明得到的 h 是否能就是 f,因為天下沒有白吃的午餐。但我們用定理說明的 h 可以在未知的資料中 probably approximate correct。我們將定理連結到機器學習,就可以驗證 h。然後學習的過程也可以套進這樣的概念,當 H 中的 h 數量非無限的時候,機器學習是可能的。

Fukuball

我是林志傑,網路上常用的名字是 Fukuball。我使用 PHP 及 Python,對機器學習及區塊鏈技術感到興趣。 https://www.fukuball.com

Co-Founder / Head of Engineering at OurSong

Taipei, Taiwan