複習四種常見的Growth Function
圖一中顯示前面教過的四種不同的Growth Function
我們從它們的成長函數可以看到
它可能是多項式型(Polynimial)增長，也有可能是指數型(Exponential)增長
如圖二和圖三所顯示的曲線可以知道不同函數的增長速率
那現在有一個重要的問題在於，對於一般常見的二維perceptron的分類問題
它是多項式型還是指數型增長 ? (類似演算法中 Big-O 時間複雜度 的問題 )
圖一、成長函數列表
圖二、2的N次方與N平方的比較
圖三、常見之不同函數增長速度圖
Break point概念簡介
我們把第一個有機會突破指數型無窮增長的資料點數叫作 Break point，什麼意思呢?
圖四展示一個例子，當今天我們有四個點，按照這樣分佈的時候
就有無法實現的分類組合出現
因此當資料個點數 k = 4的時候，會存在沒有能夠完全打碎(shatter)分割資料的點
即從 k=4開始是第一個開始出現沒能夠完全打碎的點的資料個數，便稱作break point k = 4
像是4個資料點的最大可能分割上限，只有14種可能，而不是16 ( = 2的4次方)
圖四中提及若 k 是break point，則 k+1, k+2 ... etc 也會是break point
延伸上面的例子，k = 4以後，從 k = 5, 6,7...etc 等都會存在沒能夠實現的組合
同時，成長函數mH就不會呈現exp型無窮的增長 (non-exponential)
能夠分割最大可能類別個數的極限，從break point開始被限制住
即為 exponential 增長的中斷點
圖四、假設模型的Break point
圖三列出來常見函數的成長函數 mH 與 Break point 數
從這些結果裡面，我們是不是能夠找到資料點個數 N 與 break point 數 k 之間的蛛絲馬跡 ?
詳細的證明，就在下一個學習筆記15中
圖三、不同成長函數與break point的關係
總結
截至目前為止，我們把Learning拆成兩個主要的問題，分別是 :
1. Eout(g) 約等於 Ein(g)
2. Ein(g) 約等於零
當這兩點前提條件能夠確保後，就能夠說明 學習 本身就是有效的
再來探討了有效分割的分類情形。理論的分類總數與實際分類總數會有落差
同時也討論到當達到 Break point 的時候，成長函數出現了不會變成exp無窮式增長的一線曙光
圖四、總結
沒有留言:
張貼留言