[學習筆記17] 機器學習基石 - Theory of Generalization :: Bounding Function: Inductive

[Youtube影片24 Theory of Generalization :: Bounding Function: Inductive @ Machine Learning Foundations]

這段教學影片的目的是希望能夠從k較高的限制函數

推導出剩餘尚未推出且k較低的限制函數

前一個筆記16已經將大部分的表都給填完了

接下來問真正的問題出現了，剩下尚未填的空格，是不是與前一格有什麼數學上的關係 ?

Ex. 已知 B(4, 4) = 15 => 請嘗試推導出 B(4, 3) 等於多少 ?

圖一、Estimating B(4,3)

假設今天有一個程式能夠自動的讓 Bounding function B(4,3) 的所有合法情形給找出來

(先不考慮如何撰寫這個程式、得到這個結果)

圖二、求得B(4,3)

今天我們先把這個結果進行重新組織，把相似度極高成雙成對的組合歸類成橘色

其餘無法配對的結果則歸類在紫色

圖三、B(4,3)解的分類

我們從橘色的配對組合可以發現，除了x4這項以外，x1到x3的部分基本上成雙成對的相同

分成這樣有什麼好處?

假設我們把圖三右側的橘色部分看成2 alpha個資料，紫色部分是beta個dichotomies

把x4的資料遮住不看的話，我們可以將資料簡化成圖三左側的alpha + beta個dichotomies

B(4,3) 是指任意三個資料點不能被shatter，而任意三點當然包括了x1~x3這三個資料點

所以即使x4不看(N-1)，這三個資料點一樣不能被shatter

因此，可以得到 alpha + beta 會小於等於 B(3,3) 這個結論

圖四、預估B(4,3)-1

如果今天我們把紫色的部分去除的話，看看會發生什麼事情

因為我們如果加上x4資料項的話，不能夠被任意3個資料點shatter

因此，若去掉x4這項資料(N-1)

至少必須確保x1~x3這三項資料中，不能被任意2個( k-1個)資料點shatter

所以alpha在 N-1 與 k-1 的情況下，不能被任意兩個資料點shatter

圖五、預估B(4,3)-2

從前面的結果可以推得圖六中

最後不等式的結果即 B(N, K) ≤ B(N-1, K) + B(N-1, K-1)

也許我們無法知道確切的數值，但是我們可以填入這個表的上限是多少

B(4,2)的那格的上限5，可以由B(3,1) + B(3,2)  = 1 + 4 得到

因此可以一路求得剩餘部分的上限、上限的上限...etc 的結果

圖六、將所有結果合在一起

Bounding Function 的理論計算式

把B(N, K) ≤  B(N-1, K) + B(N-1, K-1) 這項結果進行延伸

可以由遞回式、數學歸納法可以證明得到圖七中不等式的結果 :


B(N,k)≤∑i=0k−1(Ni)  ( 刮弧()中的意思是排列組合中的C的N取i )


從上式的結果可以發現，式中最高項為N的 k-1 次方，所以會被 k 的數字給限制住

所以如果有break point的話，對於固定的k，B(N,k) 的上限會被多項式N (Poly(N) ) 給限制住

終於可以確保可能的分類結果不會無限制的發散 !

(事實上，這邊的≤，可以透過證明得到其實就是"=" )

圖七、限制函式的上限

我們終於把成長函數的上限，即限制函數給得到 (圖八中橘色式子的部分)

圖八、常見例子的限制函數

課後練習

Q : 1D perceptron的問題, mH(N) = 2N 如何得到 ?