我們現在比起 Growth Function mH(N)
更加在意 Bounding Fuction B(N, k) 這個求得實際 Dichotomies分類種類上限的函數
(其中N是資料點個數，k 是 brak point 發生的資料數)
Bounding Fuction(N, k) 是指，當 break point 為 k 的時候 (須注意 : break point 不只一個 )
實際最大的成長函數 mH(N) 值
圖一、Bounding Fuction
新目標 : Bounding Function B(N,K) 是否小於等於多項式成長函數 Poly(N) ?
Bounding Function 表
下表列出各種不同組合的 Bounding Function 之結果
圖、Bounding Function表
以B(3,2) 為例，先將 (x1, x2, x3) 所有的情況列出
接下來，個別兩兩考慮 (x1,x2) (x2, x3) (x1, x3) 是不是會有超出 break point 的情況
在 B(3,2) 中，break point 發生在 k= 2 的時候
即輸入資料N為 2的時候，就有無法實現的組合出現
從2的N次方進行檢查，所以不可能能夠達到2的2次方等於4的種類
這時候有dichotomies set會被shatter掉而無法被實現
因為都會累積種類到4種，所以第5, 6, 7, 8種的情況都不是有效的二分法組合
圖、Bounding Function表
圖、Bounding Function表
課後練習
選項1 => 答案在下圖中，先前討論過，可以用畫圖來理解
選項2 => mH(4) = 14
選項3, 4 => 對於 2D perceptron問題, N = k = min break point = 4
mH(4) = 14 < B(4,4) = 15，所以選項3是正確的
--------------------------------------------------------------------------------------------------------------------------
尚未理解的問題
Q : Table 中的結果怎麼得到 ?
Ans : 如上述中間的表格解法，親自手解一次會對這些答案更有感覺!
Q : 限制函數 Bounding function B(N, K) 和 成長函數 Growth Function mH(N) 之間的大小關係 ?
Ans : B(N, k ) = 最大可能的 mH(N) 值, 圖一老師的投影片中就有答案~
Q : 有了成長函數 為什麼還需要 限制函數 ?
Ans :
Q : 限制函數、成長函數和Dichotomies之間的關係?
Ans : 用下面所附上課的投影片來作說明
左側是Hypotheses set H中的常見的 h 之一
中間的mH(k)是限制函數在k的數值，而dichonomies set的最大可能即為2的N次方種可能
右側的mH(N)公式是成長函數
沒有留言:
張貼留言