The VC Dimension-7 Machine Learning Foundations

Review

• 
• Lecture 6: 總結只要Growth Function出現break point，且N夠大，機器就能有可能學會資料，使的E-out很接近E-in
• Lecture 7: 本節目標是討論VC Dimension
• 
• 統整截至模前的機器學習三步驟：
• 找到一個好的Hypothesis Set （有break point k)
• 資料正確且充足
• 一個好的演算法從訓練資料中找出g function
• （加上一點點運氣）

Terms

• VC Dimension:
• 其實就是k-1（break point - 1），能夠shatter的最大N值（超過N就無法shatter）

Example on 2D PLA

• 
• 左邊紅色部份經過證明，一定會收斂（T:學習夠多次）
• 右邊藍色部份經過證明，E-out接近E-in（N:資料夠多，H:成長函數有upper bound）
• 所以2D PLA可行！！！！！一定可以學習成功（E-out接近E-in接近0）

How about Multi-Dimensions

• D-vc == D(Dimensions) + 1
• eg: 
• 1D PLA: D-vc = 2
• 2D PLA: D-vc = 3
• proof:
• D-vc >= D + 1
  也就是說只要找到一組可以shatter D+1維度即證明
• D-vc <= D + 1
  也就是說必須證明所有D+2維度都不能被Shatter

D-vc 物理意義

• 
• D-vc (VC Dimension): 直覺的想法其實就是DOF（Degree of Freedom），可以操控的維度數量。回顧之前的課程，機器學習不外乎要作兩件事：
• 確保E-in和E-out差不多（可套用學習結果到沒看過得資料上）
• 確保E-in夠小（成功從training data學習）
• 於是D-vc也和之前Hypothesis Set數量M有相當的狀況：
• 太大：學習能力強但是可能會失去一般性
• 太小：學習能力弱但是可容易保有一般性

D-vc 哲學意義

• 透過一些簡單的換算，可以把原本的Hoffding改寫成E-out的upper bound關係式。

• 根據上面的公式，可以推論出一個核心的哲學：

• 下圖舉例，如何根據老闆的需求，概略算出需要的資料量。

• 但實務上需要的資料量和評估出來的資料量會有非常大的落差，通常只需要10倍於VC-Dimension的資料量就很足夠了。

• 實務和理論評估出來的資料量需求會有落差，主要是在推導的過程皆採worse case，找到的upper bound是好幾種upper bound的upper bound...

• 簡言之推出的公式，其實沒什麼實務上的用途，但卻可以大大的了解運作的哲學，提供我們後續機器學習的參考。

• 小複習：
• 定義VC Dimension (其實就是DOF）
• D-vc背後的衍生意義

• NEXT: noise-and-error

REF

• The VC Dimension @ Machine Learning Foundations