Machine Learning 共筆 Week 6

Theory of Generalization

這週首先介紹何謂Shatter:

Shatter: 當資料為N筆時，分類有2^N種組合，此時沒有Break Point，所有的可能都被Hypothesis給shatter掉了；反之，如果有Break Point K，則當N>K時，資料上的分類組合可能種類會遠小於2^N種，因此，資料組合的可能種類會隨著N越大而脫離指數成長。

有了這樣的定義之後，我們再複習一次上一週Break Point的限制，當知道最小的Break Point為k=2時，則在N=3也一定得符合k=2的限制，也得到了N=3時m_H=3<<2³

在這樣的想法下，我們希望能夠有Break point的bounding function B(N, k):當break=k時m_H(N)的最大可能，用這個bounding的好處是，不用再去管Hypothesis是處理哪一種問題，只要是同樣的k值就可以有同樣的bounded。

而藉由歸納的方式，我們可以知道B(N, k) ≤ B(N − 1, k) + B(N − 1, k − 1) ，也推得了B(N,k)上限會小於N^(k-1)個

更進一步，我們透過圖畫的方式來證明:
Step1:先拿另外的N個資料點 D’來計算E’_in可以有很大的機會是跟E’_out相似

Step2:因為step1其實就是再拿了一個D’的資料出來sample，所以可以當作我們的hypothesis處理了2N筆的資料

Step3: 我們可以嘗試把他理解成母體是變成E_in + E_out

因此我們得到了以下的式子，但我們可以從課後練習知道，其實這個bound沒有到那麼的準確(or 小)，因此之後的課程會說明為什麼儘管是這樣，我們仍是要花這麼大的力氣得到這個Bound。