過來人建議，在往下繼續學習前，務必理解清楚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 個點的所有(碎片般的)可能情形都被產生了」。所以
从k=2我们可以知道，任意2个数据点都不能被shatter。还记得shatter的概念吗？意思就是我产生的dichotomies不能完全包含任何2个数据点所有的排列组合。
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 的描述 :
“是把散弹枪，在每个关卡(level N)中，他可以有发小子弹（每发小子弹对应一种dichotomy），而你面临的是个敌人。你得一枪打出去shatter掉所有人。对于这把散弹枪来说，第一关和第二关都还好，第三关6发小子弹shatter不掉8个人，于是它就break了。”
------- 參考資料 : 机器学习笔记-VC Dimension, Part I - 坏掉的散弹枪 (Shatter & Break)
沒有留言:
張貼留言