機器學習基石系列(3) —bounding function 和 VC theory
終於來到本系列課程的第一個重點了。前面兩篇依序提到Hoffeding’s inequality、dichotomy和shatter、以及break point的觀念。
dichotomy上限的上限?
在前一篇我們提到過growth function(m_H)的定義，是指在某一個資料數及排列的狀況下能找到dichotomy數量的最大值。而且提到，其值不可能超過2^N，其中N是資料數目。現在我們進一步來看m_H。
break point指的是開始無法shatter的資料數目。例如若有一個資料分布，其break point是2，則表示N=2時無法找到dichotomy滿足讓兩個點都可以任意被分類的情況。任意被分類是什麼意思?如下：
從上圖可以看到，如果用數學的方法講，就是任意兩個點都可以排成○和╳的任意排列組合。所以不能被任意被分類，從m_H的角度來說就是不能滿足2^N個數量的意思。而且因為m_H是dichotomy數量的上限，所以在這個資料分布的狀況下，無論任意取哪幾個，只要數量符合break point，就沒辦法達到m_H=2^N。在breakpoint以下則一定可以滿足2^N；而超過break point的數量也一定不能滿足2^N。聽起來很像在繞口令，不過簡單一句話講就是：
若 break point=N，則此資料的 m_H在 n≧ N時都＜2^n
我們把 break point 的growth function(m_H)稱為 bounding function，以表示其上限。從此數目開始，m_H不再為2^N。由於m_H本身是dichotomy的上限，所以 growth function 就是「dichotomy 的上限的上限」。為什麼要這麼執著這個數字呢?因為它是開始讓 dichotomy 數量成長受限的關鍵，還記得嗎?只要能確保dichotomy的數量有限，接著再套用Hoffeding’s inequlity，就可以讓E_in和E_out的落差收斂，壞資料的機率降低，機器學習有機會成功。
bounding function的另一個好處是可以無視資料分布。什麼意思?不同的資料分布有可能有相同的break point，例如positive interval和1D perceptron兩種資料分布的break point都是3，我們可以把它寫成
B(N,3)
B是bounding function，而N是資料數，k是break point。如此一來，我們可以專注在探討bounding function的數目上，而不再被資料分布限制。
目前已知的B值：
- 若k=1，則無論N為多少，B=1。因為只要多一條dichotomy，這個點就被shatter了。
- N<k時B=2^N。
- N=k時B<2^N，其上限為2^N -1。
- 根據前面的實驗，若K=2，B(2,2)=3；B(3,2)=4。
根據這些條件做出表格：
幾乎完成一半了。不過，顯然還沒填的地方才是關鍵XD這邊插敘一下關於B(4,4)，在我們上一篇的實驗中能找到的m_H是14，但這邊寫的是15。想說明 bounding function 是 m_H 的上限，而非一定要達到的值。它比較寬鬆，就像瘦下來之後穿以前的褲子一樣(喂)
表格中的空白區域，我們從B(4,3)開始。根據實驗，總共可以找到11種可能，符合「4筆資料，但任三筆不能被shatter」的條件。
把這些項目整理一下：分成X_1~X_3一致，而X_4有○、╳的，以及X_4只找的到○、╳其中一種的。然後重新排列如下：
所以可以大略看出來有一致的有四大組共八項(稱為α組)，不一致的有三組(β組)。這七組依然符合「任三筆資料不能shatter」的條件。如果把X_4去掉，則這七項也還是符合條件的，因為本來就是說任三項不能被shatter，所以去掉一項，剩下三項當然還是不能shatter。
等等，三項資料，然後任三項不能被shatter...那不就是B(3,3)嗎?沒錯，就是B(3,3)。回頭查一下表格，果然，B(3,3)=7。
現在看α組。由於這個組在X_4已經被shatter，如果還要符合任三筆不能被shatter的條件，那X_1~X_3中任兩點就不能被shatter，否則加上X_4就會違反條件。所以這組是B(3,2)。查一下，B(3,2)=4。
α是B(3,2)=4，α+β是B(3,3)=7，兩者相加2α+β=11，就是B(4,3)。從這個原則，我們可以歸納B(N,k)=B(N-1,k-1)+B(N-1,k)。
任三筆不能被shatter，反過來就是說任0筆、任1筆、任2筆可以被shatter的情況加總。所以從這個角度來看，可以說
推廣到i=k時，
其實在老師的課堂中，等號應該是寫小於等於，因為一開始到現在我們無法證實α組就是B(3,2)，還是說只是「任兩筆不能被shatter」的一種情況。同理，α+β也還沒證實就是B(3,3)。不過老師有說這個可以證明，所以我先把小於拿掉了。老師有提供一個提示，就是要證明大於等於的方向(不成立)。
總之，bounding function也有一個界限，如果說bouding function是dichotomy的上限的上限，那bouding function的界限就是growth function上限的上限了。
dichotomy → growth function → bounding function → B(N,k)
現在，回頭來看看式1。它的展開式最高次項是 N-1，表示這是一個多項式。所以我們除了把表格填完，還找到 bounding function 的規則，而且確定它是一個多項式，在N大的時候可以收斂，不會無限增加，機器學習是可行的。
VC theory
我們再回顧一次用m_H代替M的Hoffeding’s inequality式子：
不過，實際上正確的式子是這樣：
這個式子叫做Vapnik-Chervonenkis theory，是兩位統計學家所提出的。詳細的推導過程，在一本書裡面。翻了一些參考資料，看起來還是做概念性的證明就好了。以下的推導將不嚴謹，只就一些概念闡述，不過對於理解式子的演變應該還是有幫助的。
取代E_out
這式子不好計算的原因是E_out，E_in是已知，但E_out幾乎未知(他就是解)。如果能取代它，式子會容易一些。運用verification的概念，把E_out用另一組抽樣資料代替，這組資料我們稱它為ghost data。得到的結果當然不是E_out，是他的替代品；由於也是抽樣的，就把它叫E_in’。
如果E_in離E_out很遠，E_in’也有很大機率離E_out很遠。經過推演，式子變成
由於不強調證明本身的嚴謹，就不仔細敘述這中間的變化了。
代入m_H
E_in和N筆資料有關，E_in’和另外N筆資料有關。如果能證明對於同一個hypothesis set，在這兩組資料的dichotomy一致，則E_in和E_in’就會一致，就可以進一步收斂式2。
把hypothesis set (H)分成兩大類，第一大類內含(X_1, X_2, X_3,…X_N)，第二大類內含(X_1', X_2', X_3',…X_N’)，兩大類分別對應E_in和E_in’。在總dichotomy的數量上，兩大類各自有上限m_H(N)，我們再用union bound把兩大類合為一個hypothesis set，其上限為m_H(2N)。
為什麼要這麼麻煩把hypothesis set搞成這樣?因為我們抽樣了兩次，現在第二次的抽樣代替的是外面的實際資料。又，前面提到過實際上若某以資料對其中一個h是壞資料，其有很大機率對其他某些h也是壞資料。所以就一組資料而言，其壞資料應該是集中的。我們分兩大類後，各自的大類裡面不要用union bound求壞資料的機率，而在最後 — 因為目前還不確定E_in和E_in’的關係 — 才在兩大類合併的時候使用union bound。相關示意圖如下：
最早的時候我們只看一個h，然後看E_in和E_out的關係。我們知道，對於一個h，拿到壞資料的機率很低(Hoffeding’s inequality)。後來我們引進了multi-bin Hoffeding’s inequality，對於每一個h，只要有一筆資料是壞的，就算拿到壞資料，所以用union bound的概念；但實際上，如果一筆資料對於一個h是不好的，那它很有可能對其他h也是不好的，這就是(c)的狀況。
把式2.移項之後用m_H(2N)代入，我們要看的還是整個hypothesis set，只是現在這個H是由兩個大類組成，分別歸屬E_in和E_in’。
等式的左邊是式2.的右項，本來是指對於整個hypothesis set。現在我們看的是裡面單一個h，然後這些h在單一大類裡利用dichotomy的概念，也就是m_H，避開union bound不合實際(壞資料應該要會重複)的狀況；之後再兩大類合併時再使用union bound。
比較E_in和E_in’
我們進行了兩次抽樣，分別形成E_in和E_in’。兩次都抽N筆資料，總共2N。換個方式看，可以想成總共就只有 2N 筆資料，先抽N筆，然後跟剩下N筆比較(概念一)；或是抽了N筆，跟整個 2N 筆資料的平均比較(概念二)。
第一個概念就是
概念二則是
跟平均的差距要扣一半。這裡我們改使用概念二代換概念一，也就是抽出的資料和平均比較。
抽出的資料和原本的比較，這邊可以使用 Hoffeding’s inequality了。只是這邊有些不同：原本的是抽完資料會放回去(抽出的資料仍算在裡面)，現在是抽完不放回去了(抽出的資料不算在裡面)。這叫做 Hoffeding without replacement。它的差別是母群體小，ε也比較小。把ε/4代入Hoffeding’s inequality，得到
就是我們看到的樣子了。
最後要提醒，VC theory在推導的實際過程中使用許多近似值，因此其估算並不準確。它的精神是提供一個上限，這個上限可以收斂，不會往無限大的方向擴張，幫助我們建立機器學習的信心。換句話說，在某個情況下，VC theory的值可以很大，但實際上可能很小。這個之後有機會再說明。
