機器學習基石系列(2) — dichotomy和shatter
在上一篇中我們討論到Hoffeding’s inequality並提出數學證明，是要計算抽取到的資料(或是收集到的資料)用演算法判斷錯誤的量(E_in)和全部的資料(或是現實的資料)用演算法判斷錯誤的量(E_out)相差多少，以及機率。
拿到壞資料的機會是多少?
假設在收集資料，或抽取資料的過程中，有一組資料讓某個演算法在還沒開始學習的狀況下就預測全對。你會很高興的說發現了演算法的解，還是像李組長一樣眉頭一皺，認為案情並不單純?
實際上，根據資料分布的性質，通常總有「例外」，讓演算法判斷錯誤。這是因為資料本身具有雜訊，即使雜訊非常小，也有可能按照正常分布而演算法預測偏離的狀況，因為真實世界的「那個分布」，也就是我們追求的標準答案，常常是找不到的。雜訊及資料的分布之後在講，總之，我們都知道，如果真的讓演算法在選取的資料中預測100分，往往並不見得是好事。矇中的機率還比較高；這時拿這個演算法直接去真實世界的資料測試，結果錯得亂七八糟。
換作前一篇提到的術語，這時E_in和E_out相差很大，大到超過ε的狀況，Hoffeding’s inequlaity被打破了。這時的狀況我們說拿到壞資料了。Hoffeding只保證拿到壞資料(即E_in和E_out相差很大)的機率很小，沒說這種狀況不會發生。
再想像一個狀況。讓150個人同時投擲硬幣，其中至少有一人連續五次結果皆為正面的機率為多少?
乍看之下，會覺得，哇，連五次正面，機率應該很低啦。不過小心，這裡要算的是至少出現一次的機率，而不是算一個人連五次發生的機率。這個命題的逆否命題是沒有人擲出連續五次正面。一個人不連續擲出五次正面的機率為1-(1/2)⁵=31/32。150個人都不連續擲出五次正面的機率是(31/32)¹⁵⁰。最後用1-(31/32)¹⁵⁰才是答案，結果約0.9915，超過99%！
這個連五次擲出硬幣的狀況就像抽到壞資料一樣，在單次抽樣時發生機率很低，但不是不會發生。
對於一個資料集，究竟拿到壞資料的機率是多少?最根本的笨方法，就是窮舉所有壞資料的狀況，計算他們的機率，再把他們加起來。先定義一個針對某資料集做機器學習的所有可能演算法，其集合為一個hypothesis set。這個set裡面有M個hypothesis，裡面有機會存在可以解釋這個資料集分布的演算法。機器學習的過程，就是在裡面選擇一個最能解釋分布的演算法。
如果定義壞資料對於每個演算法的事件彼此獨立且無交集，然後在資料集中抽取一組資料。只要這組資料對於M個hypothesis中，有一個是造成E_in和E_out落差很大，就稱為壞資料。那拿到壞資料的機率是
這個結論比起hoffeding’s inequality多了M，演算法的總數。從這邊看出一個端倪：如果要避免拿到壞資料，可以：
- 樣本數夠多(N越大)
- E_in和E_out設定的相差區間越大，越寬鬆(ε越大)
- Hypothesis數夠少(M越小)
可惜，實際上hypothesis的確實數目是不知道的。不知道確切的M，怎麼評估呢?
將Hypothesis set分類
先來看看簡單的例子：用一條線把資料分成a，和b的兩種。如果有一筆資料，會有幾種分法?
很簡單，兩種。那如果是2筆資料呢?
四種。3 筆?是8種嗎?
其實是6種。為什麼?有兩種畫不出來：只有中間點是+1，兩邊點是0的；以及只有中間是0，兩邊點是1的。不過，只要三個點不是共線，就沒問題了。
每條線的兩側分別為1和0。彼此可以互換，然後三條線可以隨意組合，2³=8。
那如果四個點，是不是只要在平面上就可以有16種可能?
這是其中8種，另外8種組合是相反的。顯然，框紅色的那種分類方式做不到。因此，全部只有14種分類方式。如果四點共線，可以預期會更少。
做到這裡，其實已經可以推論出一個狀況：那就是這些分類的線可以被歸類，至少在二元分類上，我們有辦法把許多的hypothesis歸納成幾種型態，而且這些型態是有限的。除此之外，這個有限的數字，其上限為2^N。我們把這些二元分類的線 — 或hypothesis — 稱作dichotomy。
換一個方式描述壞資料的機率
在式2.中描述拿到壞資料的機率，前提是壞資料對於hypothesis是獨立事件。例如，某組資料對第一個hypothesis是壞資料，就不會對其他hypothesis是壞資料。實際上，這件事往往重複：若某組資料對其中一個hypothesis是壞資料，也會對另一個hypothesis是壞資料；而且，通常還蠻容易發生的。壞資料限縮機器學習在hypothesis set的選擇，它讓選項變少了。幸好，不少時候這個概況在hypothesis set裡面是重疊的。
像右圖的發生機率比左圖大。我們來評估一下右圖：之前用M來代表所有hypothesis的數量，現在用一個m_H來代替M，描述右圖這種局部重疊的狀況。先把原本hypothesis set裡面的所有hypothesis按照前面說的dichotomy的方法分類，可以得到另一種描述hypothesis set的方法：H(X_1,X_2,X_3,…X_N)是所有dichotomy的集合。一個dichotomy代表一種分類方法，裡面可能有好幾個hypothesis。這樣描述的好處是它有一個上限：2^N，而原本的hypothesis set其數量是無法估計的。
然而，即使如此dichotomy set的數量仍被資料數N影響，仍然不固定。要擺脫資料量的限制，可以先在一群資料中抓一把，算dichotomy的數量；然後再抓一把，算dichotomy的數量，如此反覆之後，就可以得到一組dichotomy set，其中的最大值即為m_H。
m_H有個名字叫growth function，會隨著資料量增加(grow)。上限是2^N。為了計算m_H，我們來做一些實驗，先從最簡單的狀況開始思考：把所有x放在一維空間，就是一條線上。然後把資料分成+1和0，這次遵守方向性，即往右才是正，往左分就變成負的，所以要只分+1出來就要把往左的分類取消。先從上面圖1開始試試看：
總共有4種。三個點把整個區間分成四塊，分隔線可以放在任一塊上構成一種dichotomy。推廣到N個點的話就是N+1種，或寫成
如果現在不是positive ray，而是改成positive interval：任兩條線把整個區間分成兩種，+1和0。一樣，拿圖1來測試：
總共是7種。值得一提的是，你畫不出只有中間那點是1，兩邊點是0，然後兩邊點以外又是1的這種。同樣是三點區分一條線成四塊，這次換成要擺兩條線了。除此之外，兩條線可以相疊，表示沒有1的區間，就像最上面的藍線。這一種雖然乍看之下放在四個區間會有四種排列，可是其實結果是一樣的：三筆資料都被分到0；所以其實只算一種組合。除此之外，其他狀況都是兩條線不相疊的組合，這個計算就簡單了：
推廣到N筆資料，我們知道dichotomy的數量應為
在一維空間上，無論是positive rays或positive intervals，我們都可以推算出m_H，而且其數字都遠小於2^N，表示機器學習是可行的，因為可以有效抑制拿到壞資料的機率。
看完一維空間，來看看二維空間：
首先是圖2，可以看到其數量<2³=8。表示在某些情況下，二維空間是可以計算m_H的，也<2^N。
現在換一種資料的排列方式。
這是一個分布在凸多邊形的資料。如果把這個凸多邊形想成一個函數，那就可以稱作是凸函數了。當然，凸函數有其數學定義，不過這邊暫時不討論。或者，你可以想成一個凸函數的圖長這樣，如果這樣思考會讓你比較心安的話。我們要關注的是dichotomy會長什麼樣子：注意，現在是二維空間，分隔線也進展到不再只是直線了，可以包括曲線。一個點和兩個點的分隔，只要把點圈起來就可以了：
三個點就把他連起來，例如：
三個點以上的都可以這樣做。如此一來，他沒有不能被畫出來的dichotomy，也就是說，他的m_H為：2^N。
從資料的角度來看，如果每一筆資料的任意組合都有hypothesis可以做到，表示dichotomy可以達到最大值2^N，我們稱作擊倒(shatter)。這表示沒有一種組合可以難倒hypothesis set，所有要求都可以做到，就像這個凸多邊形的狀況。
反過來說，如果有些狀況是沒有dichotomy可以符合的，例如positive interval再三個點的時候提到的那種狀況，就表示資料無法被shatter；這時就叫break point。所有做不到的資料數目都是break points，但通常，我們最關心的是最小的break point，這會到下一篇討論。
總結
這一篇提到兩個重點：dichotomy和shatter的概念，並引伸出growth function和break point。
在這篇裡面提到四種狀況的growth function(m_H)，他們分別為：
- Positive rays：N+1
- Positive intervals：1/2N²+1/2N+1
- Convex function：2^N
- 某種2D perceptron：≦2^N
他們的break point最小值：
- Positive rays：2
- Positive intervals：3
- Convex function：沒有(無限大)
- 某種2D perceptron：4
在1跟2，growth function都和N的(break point最小值-1)次方有關。究竟2D perceptron的growth function會不會和N³有關?下回分曉。
