[學習筆記15] 機器學習基石 - Theory of Generalization :: Restriction of Break Point

[Youtube 影片 22 Theory of Generalization :: Restriction of Break Point @ Machine Learning Foundations]

過來人建議，在往下繼續學習前，務必理解清楚Shatter觀念!

Theory of Generalization - 舉一反三理論 (機器如何能做到呢?)

前情提要

前一個影片提到，M可能會成長到無窮大

需要找到成長函數 mH 取代 M，而且該mH長得很慢

先複習以下不同情形 Break point 的觀念

Positive Ray : o x 這種情形不合理

所以兩個資料點就會出現違反定律，即無法shatter的資料組合

所以他的Beak Point 是 "2 "，出現Beak Point表示收斂的情形出現一束曙光

後續的 k+1 的點，也是會收斂

圖、不同情形的break point

進入下面的主題之前，我們先來複習之前所提到 Shatter 的觀念 : P

Shatter觀念複習

Shatter是指說，當某個dichonomies set出現無法實現的分類情形時，當下的輸入資料數N

即為break point k，此時這個 dichonomies set被這樣的組合給shatter

別人筆記內容 : 

林軒田老師 : 大家對 break point 的討論很好，不過注意到 shatter 的原意是「打碎」，在此指「N 個點的所有(碎片般的)可能情形都被H$\mathcal{H}$產生了」。所以mH(N)=2N的情形是「shatter」。

从k=2我们可以知道，任意2个数据点都不能被shatter。还记得shatter的概念吗？意思就是我产生的dichotomies不能完全包含任何2个数据点所有的排列组合。 

------- 以上節錄自 : 机器学习笔记-VC Dimension, Part I

Q : 考慮一個問題，當k為2的時候，最大的mH(3)是多少?

1 dichotomy

1個 dichonomy的時候，檢查過(x1,x2), (x2,x3), (x1,x3)的種類

不會被任意兩個資料點給shatter

2 dichotomies

2個 dichonomy的時候，不會被任意兩個資料點給shatter

3 dichotomies

3個 dichonomy的時候，不會被任意兩個資料點給shatter，依舊相安無事

4 dichotomies

OK，問題來了。

我們檢查任兩個資料點的組合時，發現這種分類法會產生 (x2,x3) 4種排列組合的種類

即產生了所有2的N次方種的排列組合可能，因此發生了shatter !

違背 k = 2 的情形，任意兩個點不能被shatter的原則。這種情況不合法。

因此更換成下面的dichotomy，補上合法的情況

5 dichotomies

 

5 dichotomies可以很快的就看出來，不管再怎麼增加新的dichotomies

都會有任兩個資料點被shatter掉的情形。因此最多只有4種dichotomies

Break Point 的限制

接下來考慮Break Point的限制

需檢查 (x1,x2) 這兩行是不是同時有 oo ox xo xx 這四種情形兼有的情況出現

會被不能實現的組合給 shatter

同理，也同時檢查 (x2, x3) (x1, x3) 這兩行組合

圖、自毀承諾的情形

任兩個點不能shatter，因此最多只能有4種

圖、最多四種dichotomies

所以 最大可能的mH(3) =  B(3,2) = 4 

想法延伸

從成長函數 mH(N) 跟 break point數 k 之間的關係，我們得出一些端倪 

後面的幾個影片能夠推論出以下的結論

mH(N)  <=  給定k後最大可能的 mH(N)  <= N的多項式

圖、Break Point的限制

課後練習

這題的問題就是 B(3,1) 

由於 k 是 1，這個假設模型甚至不能shatter一個資料點

所以任"一"個資料點可能都會被shatter

從右下角的圖可以看到，如果今天我加入第二個dichonomy

我們可以看到 x3 這行會同時存在 O 和 X

違反了 break point k = 1這項已知條件

所以這題的答案只有一種可能就是選項1的1種可能

----------------------------------------------------------------------------------------------------

問題 

Q : Shatter 的明確定義 ??? 

Ans : Shatter(打碎)是指N個輸入的資料點都能夠被正確分類且執行，沒有不能被分類的情況。林軒田老師 : N 個點的所有(碎片般的)可能情形都被H產生了

另一個學習者對於 shatter 的描述 : 

“mH是把散弹枪，在每个关卡(level N)中，他可以有mH(N)发小子弹（每发小子弹对应一种dichotomy），而你面临的是2N个敌人。你得一枪打出去shatter掉所有人。对于mH(N)=2N这把散弹枪来说，第一关和第二关都还好，第三关6发小子弹shatter不掉8个人，于是它就break了。”m

H(N)=mH(N)= N2N2N2N2N2N2N2N

------- 參考資料 : 机器学习笔记-VC Dimension, Part I - 坏掉的散弹枪 (Shatter & Break)

[學習筆記14] 機器學習基石 - Training versus Testing :: Break Point

[Youtube影片21 Training versus Testing :: Break Point @ Machine Learning Foundations]

複習四種常見的Growth Function

圖一中顯示前面教過的四種不同的Growth Function

我們從它們的成長函數可以看到

它可能是多項式型(Polynimial)增長，也有可能是指數型(Exponential)增長

如圖二和圖三所顯示的曲線可以知道不同函數的增長速率

那現在有一個重要的問題在於，對於一般常見的二維perceptron的分類問題

它是多項式型還是指數型增長 ? (類似演算法中 Big-O 時間複雜度 的問題 )

圖一、成長函數列表

圖二、2的N次方與N平方的比較

圖三、常見之不同函數增長速度圖

Break point概念簡介

我們把第一個有機會突破指數型無窮增長的資料點數叫作 Break point，什麼意思呢?

圖四展示一個例子，當今天我們有四個點，按照這樣分佈的時候

就有無法實現的分類組合出現

因此當資料個點數 k = 4的時候，會存在沒有能夠完全打碎(shatter)分割資料的點

即從 k=4開始是第一個開始出現沒能夠完全打碎的點的資料個數，便稱作break point k = 4

像是4個資料點的最大可能分割上限，只有14種可能，而不是16 ( = 2的4次方)

圖四中提及若 k 是break point，則 k+1, k+2 ... etc 也會是break point

延伸上面的例子，k = 4以後，從 k = 5, 6,7...etc 等都會存在沒能夠實現的組合

同時，成長函數mH就不會呈現exp型無窮的增長 (non-exponential)

能夠分割最大可能類別個數的極限，從break point開始被限制住

即為 exponential 增長的中斷點

圖四、假設模型的Break point

圖三列出來常見函數的成長函數 mH 與  Break point 數

從這些結果裡面，我們是不是能夠找到資料點個數 N 與 break point 數 k 之間的蛛絲馬跡 ? 

詳細的證明，就在下一個學習筆記15中

圖三、不同成長函數與break point的關係

總結

截至目前為止，我們把Learning拆成兩個主要的問題，分別是 :

1. Eout(g) 約等於 Ein(g)

2. Ein(g) 約等於零

當這兩點前提條件能夠確保後，就能夠說明 學習 本身就是有效的

再來探討了有效分割的分類情形。理論的分類總數與實際分類總數會有落差

同時也討論到當達到 Break point 的時候，成長函數出現了不會變成exp無窮式增長的一線曙光

圖四、總結

[學習筆記13] 機器學習基石 - Training versus Testing :: Effective Number of Hypotheses

[Youtube 影片20 Training versus Testing :: Effective Number of Hypotheses @ Machine Learning Foundations (機器學習基石)]

原始的Hypotheses H，如果從Perceptron的資料分類方法來看

無窮多個的Perceptron就有無窮多個分類結果

Ex. 光是2D平面的分類，我可以在任何位置，用任何旋轉角度對資料進行分類

圖一、Perceptron分類示意圖

Dichotomy : 二分法

Dichotomy 指的是資料的二分法

上一個筆記12中有提到，若能從分種類的角度來看的話，可以收斂成為有限種類的可能

圖一、資料點二分分類

找到欲解決問題的成長函數

假設今天有一個二分法分類器能夠將資料點二分成 o (+1) 以及  x  (-1)

其中選出最大(max)的 Dichotomies set 當作衡量的依據，取作mH

這個 mH函數 叫作 成長函數 (Growth Function)

mH(N) 就是指資料個數為N的時候，最多分類個數的 Dichotomies set 中的分類個數

未來就是用來取代有限但很可能很大的 hypotheses個數M (學習筆記12有提到M)

而且成長函數的結果是有限的，同時會被2的N次方所限制住

圖二、Growth Function

Growth Function案例分析

Positive Rays

今天如果有一個一維的資料，我們設定一個門檻值(Threshold) a

當如果數據大於a的話，則標記為+1；反之，則為-1

這個相當於一個一維的Perceptron分類問題，最多的可能為 N+1 種(遠小於2的N次方)

右下角就是分類結果的示意圖

圖三、Positive Rays

但是，如果是一個區間(Interval)的話，總共有幾種不同的可能?

就相當於N個2種不同物體，作不盡相異物的排列的問題

可以以 C 的 N+1 取 2 (已包含全部都是o的情況)再加上 1(全部都是x的情況)

                N+1
mH =   (　       )  +1  = (N平方 + N)/2 +1  = N平方/2 + N/2 + 1
                   2      

把圖四 mH 的結果給推導出來

一般來說N個資料點，總共有2的N次方種分類可能

若N很大的話，2的N次方所算出來的結果還是可能很大

因此，最終我們推導得到的結果是mH會遠小於 2的N次方

N個數據可能的結果不會非常大，對於我們來說是個好消息!

圖四、Positive Intervals

第三個課本中的例題是如何算成長函數

如果今天我們有ㄧ個凸角(convex)，我們就算是+1

圖五、convex hypotheses

所以若今天我們要計算convex的成長函數的話，我們可以用多邊形的想法來進行計算

如果今天有N的點，我們隨機選取其中的點，而且每個點都可以被計入dichotomies set

所以這個例子的 成長函數 mH 就是 2 的N次方

圖六、convex hypotheses的Growth function

這從N個點被Hypotheses h給打碎了 (shattered)。

在這個case中，我們可以說這些N個資料點能夠被假設模型 h 打碎

shatter意思是指，這N個資料點的二分法分類，能夠百分百的被假設模型組合 H 實現出來

沒有不能被實現的情況

[學習筆記12] 機器學習基石 - Training versus Testing :: Recap and Preview

[Youtube 影片19 Training versus Testing :: Recap and Preview]

Where Did M come from ? 

我們今天把所有不好事件的機率加總起來之後，就可以得到不好事件機率的上限

但是如果今天 hypotheses個數 M 是無窮大的話該怎麼辦 ? 

(總不能讓不好事件機率P[BAD]的最大發生機率變成無窮大吧 ? )

圖一、不好機率事件的聯集(Union Bond)

Where Did Uniform Bound Fail

根據Perceptron分類方法中的情形，若某一條線與另一條線位置與斜率皆很接近

它們的分離狀況很接近

因此如果採用這兩個接近的預測模型h1與h2，它們的 Ein 與 Eout也會很接近

而它們錯誤的情形就像圖二中，右上角的圓形一般，它們的錯誤範圍重複疊合的區域很大

所以，壞事情發生的機率並不是無窮迭加上去，而是像圓圈的疊合圖

因此，我們要想辦法找出疊加的區域來進行後續的分析

圖二、不同不好事件的重疊示意圖

第一步 問題分類

而找到疊加的區域的第一步就是把看似無窮多的事件中，進行分類的動作

首先，如果是有無窮多的Perceptron，就有無窮多個線能夠對資料點進行分類

那如果只有一個資料點，這些線只有兩種分類方式 : 是或是不是

即2的一次方次，即2種結果分類結果

圖二、一個資料點的分類

第二步 不同資料個數進行種類分類

若有兩個資料點，則有2的2次方次，即4種結果

圖三、兩個資料點的分類

那有三個資料點的話，是不是都是2的三次方，即8種有效的結果呢?

看看下面圖四的例子就知道，如果我今天有三個資料點排在同一條直線的話

我如果用線性的Perceptron分類器，有其中兩個結果便無法得到

(非線性分類器現在暫時不談)

所以只有6種可行的分類結果

圖四、三個資料點的情形

同樣的情形也會發生在四個資料點的分類上，只有14種是有效結果

圖五、四個資料點的情形

第三步 找到有效的數字N (effective N)

從前面的結果可以知道，實際能夠得到的結果比理論的還要小 (Ex. 6 < 2的三次方 = 8 )

如果今天這個有效的數字N (effective N) 比2的N次方小很多

同時能夠讓exp() 這項變得很小

那麼壞事發生的最大機率就變小了!

而這個N就能夠

1. 取代可能很大的hypotheses個數 M

同時

2. N 遠小於分類種類最大上限個數，即2的N次方 (N筆資料，就有2的N次方種分類可能)

圖六、有效數字N

[學習筆記11] 機器學習基石 - Training versus Testing :: Recap and Preview

在前面的假設條件是假設模型H (Hypotheses set H)是有限

但是接下來可能會遇H是無限的情況，該怎麼辦 ? 

圖一、複習第一部分的學習流程

別急，之後會慢慢解決這個問題

圖二顯示出機器學習四大部分中第一部分探討的兩個核心問題

1. 我們如何能夠確保Eout 能夠接近 Ein ??? 

重要性 => 確保樣本的一致性，取樣後的部分資料 與 剩餘資料 資料分佈是相同的

2. Ein 是否足夠小 ???

重要性 => 從我取樣的樣本中，套用其中一組合適的h，學習出來的準確性夠高，錯誤率夠小

圖二、兩個核心問題

那 M的樣本多寡 就會是一個關鍵點，如果M取得太小，可以選擇的h就很少

M若取得太大，由霍夫丁不等式可以知道，BAD資料發生的機率就變大了

Q : 那M到底該怎麼選擇 ?

圖三、M的抉擇

所以我們的目標就是要找到一個有限數量值的mH，

使得霍夫丁不等式上限不會太大，即不要讓壞事發生的機率變大

否則無窮大的M會讓壞事發生機率變成無窮大...

圖四、待完成事項

[學習筆記10] 機器學習基石 - Feasibility of Learning :: Connection to Real Learning

老師提供了一個情境題給大家思考一下

如果今天我們手上有許多罐的彈珠，如圖一所示

裏面的橘色與綠色彈珠的比例不盡然相同

假設我們目前使用的假設模型h，剛好百分之百符合某一罐的分佈狀況，我們要不要採用??? 

(這時候就應該要有警覺，我們採用的標準是什麼?)

圖一、不同罐彈珠

換另一個情況來作說明，老師嘗試讓大家用另一個角度看同一個問題

如果今天150位修課的同學，同時丟五次銅板

其中一位剛好丟出五次正面，剛好跟手上的資料分佈狀況相同

請問他的擲銅板技術特別好嗎???

由圖三的Ans結果可以看到簡單的計算式

即使使用正反面出現機率相同的硬幣，當N變大的時候，150個硬幣中的其中一個硬幣

丟出5次都正面這種異端狀況，經計算發現出現的機率會 > 99% !

如果選到這種取樣資料，造成Ein與Eout差距很大，會讓我們的決策結果變得更糟!!!

我們在這邊稱呼它為BAD的取樣資料

圖二、圖一的簡化情形-銅板實驗

(再次複習霍夫丁不等式)

霍夫丁能夠保證的事情是這些取樣的結果是不好的(BAD)的機率很低

並且，在將這些情況的機率都加起來之後，這些不好的情況發生機率很小(samll)

圖三、不同實驗組BAD資料的示意圖

當如果有許多個hypotheses，我們該怎麼選擇 hypotheses h，

讓我們的演算法能夠自由的(可以想成隨機的)進行選擇(意思就是每個h都能夠被採用)?

重點在，如果A採用的 h 在D1到Dn，如果有其中一組的表現是BAD

則該hypotheses便不能夠使用

在這麼多組資料中，只有D1126使用了所有的hypotheses h1 到 hm

都沒有出現 Ein 與 Eout 相差過遠的 BAD 資料組

因此，D1126這個資料組可以被選來當作實驗資料組

圖四、資料與假設模型之間的關係

今天有很多筆不同的資料(D1到DM)與假設模型(h1到hM)之間的關係，按照聯集的觀念

把個別所有人M筆資料的機率不等式加起來，就是總BAD資料的機率不等式

已下是結合霍夫丁不等式的數學式推導，可以知道會產生BAD資料的邊界(Bound)是多少

以及與邊界和資料筆數的關係為何。

圖五、結合霍夫丁不等式之推導

--------------------------------------------------------------------------------------------

小結

經過了前面的這些努力

在假設模型庫H有限的情況，而且資料足夠的情況底下

我的Ein(取樣資料的誤差) 與 Eout(剩餘資料的誤差)，在不管採用哪個hypotheses g

我的 Ein 與 Eout 都會非常接近。

如果今天我的學習演算法A選了一個假設模型g，使得Ein最小而且約等於零

透過上述統計上的假設，可以知道學習這件事情是可能的

這時終於可以開始進行學習的動作。

--------------------------------------------------------------------------------------------

後記 : 

Q : 有關於Ein 和 Eout這一切的推論都是從霍夫丁不等式出發

難道霍夫丁不等式就一定是正確的嗎? 

[學習筆記1] 機器學習技法 - Linear SVM :: Large-Margin Separating Hyperplane

SVM 介紹課程

MIT OCW 16. Learning: Support Vector Machines