Definition of VC Dimension

定義

假設最小的 break point 為k, 則最大的 non - break point 為 k-1, 即 VC Dimension

• $H$ 能夠 shatter 的最多 input
• $d_{VC} = min(k) - 1$

意義

假設 $H$ 的 VC Dimension 為 N

• $H$ 可以 shatter 最多 N 個資料點
• 但不是任意 N 個資料點都能被 $H$ 給 shatter
• 當 N 夠大, $d_{VC}$ 也夠大時, 成長函數會比 N 的 VC dimension 次方來得小
• VC dimension 是 finite 的 Hypothesis set 才是好的 $H$

VC Dimension of Perceptrons

證明 PLA 在資料維度為 d 時, VC Dimension 是 d+1

• 證明 $d_{VC} \leq d+1$, 只要找到一種d+1筆的資料是可以被 PLA 給 shatter 的即可

• 證明 $d_{VC} \geq d+1$, 需要證明對於任何 d+2 筆的資料, PLA 都不能夠 shatter

  本段證明看不懂

總之 PLA 的 VC Dimension 就是 d+1 ㄏㄏ

Physical Intuition of VC Dimension

• 和 M 一樣, VC Dimension 不論太大或太小都不好, 因此要選擇一個好的 VC Dimension

Interpreting VC Dimension

假設壞事情($E_{in}$ 和 $E_{out}$ 差很多) 發生的機率為 $\delta = 4(2N)^{d_{VC}}exp(-\frac{1}{8}\epsilon^2N)$, 則此時 generalization error $|E_{in}(g)-E_{out}(g)|\leq \epsilon = \sqrt {\frac{8}{N}ln(\frac{4(2N)^{d_{VC}}}{\delta})}$, 等同於我們有 $1-\delta$ 的信心水準使得 $E_{out}$ 會落在 $[E_{in}-\epsilon, E_{in}+\epsilon]$ 內

• 我們現在知道 $E_{out} \leq E_{in} + \sqrt {\frac{8}{N}ln(\frac{4(2N)^{d_{VC}}}{\delta})}$
• 這裡的 $\sqrt {\frac{8}{N}ln(\frac{4(2N)^{d_{VC}}}{\delta})}$ 也就是我們付出的penalty, 而這個penalty會隨著 model的強大(VC Dimension的提高)而變得更大

• VC Dimension 可以說是 model 的 complexity