證明時間到了
我們這邊嘗試要證明圖一上面的式子中，空白部分的數字就是下面式子中較複雜的數字
證明中的技巧不太會在後面提到，所以有興趣再推導即可，不會影響對接下來課程的理解 : )
( 詳細的證明在此, Lemma 1 就是 1/2 的來源)
圖一、推導公式
Step 1 : Replace Eout by Ein'
Ein只有有限個，與Data個數N有關。
但是Eout卻是無限! 即使只有些微差義，也還是無限多條線
我們是不是能夠把Eout變成與Ein有關的函數 Ein' ?
現在壞事發生的機率是 Ein 與 Eout 相隔很遠，現在換成 Ein 與 Ein' 相隔很遠
圖二、Ein, Eout, 與 Ein' 的示意圖
目前新的式子中，加入了三個新的項目，分別是
2. Ein'(h) = > Eout(h) 被取代成Ein'(h)
3. ϵ/2 = >同時，數學上會更嚴苛要求｜Ein(h) - Ein'(h)｜ > ϵ/2 (ϵ, 希臘字母epsilon)
資料組D被換成D'，這個D'被稱作ghost data，不是真正存在的資料，而是想像中假設的資料
圖三、步驟一
所以今天我們的資料組只有與 D 和 D' 有關係
如果在D和D'得到的抽樣情形一樣，則Ein'(h)也會和Ein(h)
若 Ein(h) 有 mH(N)種，那麼同樣的，Ein'(h) 也有 mH(N)種
所以我們就在這 2N 個數據 (x1~xN 以及 x'1~x'N ) 中探討我們能夠產生幾種dichotomy
所以個數上限會被 mH(2N) union bound 住
Step2 : Decompose H by kind
觀念複習 : Ein和Eout相距很遠，即抽樣結果與原始群體資料分佈相差過大
抽樣結果不具有統計上的代表性，來稱作壞事(BAD)
若用圖來說明不同階段的話
Early
最早在霍夫丁不等式中，壞事的發生機率是圖三中的圖(a)一個紅圈
Middle
而後來在探討 union bound 的時候，壞事的發生機率是圖三中的圖(b)
即有幾個不同的事件，就有幾個壞事發生的機率，會無窮增長上去
Last
仔細一想之後發現，壞事與壞事之間發生的機率
相似的分割線得到的壞事機率應該重複性(重疊性)會很高
所以修正壞事的發生機率是圖三中的圖(c)那樣疊合在一起
註 : D是指sample的 data set, D'是剩餘的 data set
圖四、步驟二
Step 3 : Use Hoeffding Without Replacement
接下來，有了一個固定的hypotheses，我們想要知道兩次sampling的差異
就如同從 2N 個資料裡面抓N個出來，跟剩餘 N 個進行比較
也相當於從 2N 個資料裡面抓N個出來，跟原始的 2N 個資料進行比較
其中，原始的 2N 個資料就相當於是 (Ein + Ein') / 2
如何知道 sample 後的資料跟原本資料的差別 ? 使用霍夫丁不等式 !
(可複習學習筆記8 與 Learning theory 机器学习原理 )
因為霍夫丁不等式中，包含了
1. Ein(Sample後，手中的資料的統計誤差 Error)
與
2. Eout (原始減去sample數量剩餘的資料統計誤差 Error)
在這邊的霍夫丁是抽出來之後，因為沒有新的彈珠補進去
裡面的資料分佈就會被抽出的彈珠所改變，因此是Hoeffding without replacement
因為資料數只有2N，所以霍夫丁不等式的式子可能會稍微不一樣
圖五、總共只有2N個彈珠
圖六、從2N個資料中進行取樣
圖七、Hoeffding without replacement後的霍夫丁不等式
VC Bound
我們證明到現在，得到了 VC Bound 這個非常重要的不等式 (V與C 是兩位統計學家)
所以可以得到新的壞事發生的機率的不等式
圖八、VC Bound
透過圖六中Eout帶換成Ein ' 等的條件，
我們把霍夫丁不等式推演成VC Bound這個新的不等式
圖九、三個步驟推倒出VC Bound
我們可以得到 2D perceptron 的Break point是4，成長函數在 N=4 的時候就被限制住
一路上後續壞事發生的機率就很小，代表演算法選最小Ein，就會對應到最小的Eout
透過重重的證明，發現 2D perceptron 的學習是可行的 !
表示我們可以從之前的PLA演算法在 2D perceptron 問題中學到東西!
圖十、 Learning with 2D perceptron feasible!
課後練習
這題的 mH(2N) = (2N) + 1，把剩餘的數字輸入進工程計算機即可求解
總結
只要有Break point，就有限制函數能夠限制成長函數，成長函數就會被多項式函數給限制住
圖十一、總結
-----------------------------------------------------------------------------------------------------------------------
證明題
其他學習者證明 VC Bound
沒有留言:
張貼留言