机器学习基石上 (Machine Learning Foundations)—Mathematical Foundations
Hsuan-Tien Lin, 林轩田，副教授 (Associate Professor)，资讯工程学系 (Computer Science and Information Engineering)

The VC Dimension

Recap

Definition of VC Dimension

VC Dimension

the formal name of maximum non-break point

the Four VC Dimensions

VC Dimension and Learning

• finite dVC⟹g$d_{VC}⟹g$ can generalize Eout(g)≈Ein(g)$E_{out}(g)\approx E_{in}(g)$
• regardless of learning algorithm A$\mathcal{A}$、input distribution P$P$、target function f$f$

VC Dimension of Perceptrons

2D PLA Revisited

d-D perceptrons: dVC=d+1 ?$d_{VC}=d+1?$

dVC≥d+1$d_{VC}\ge d+1$

- There are some d+1$d+1$ inputs we can shatter.
- 每一行代表一个点
- 灰色部分（第一列）视作第 0 维，是常数，代表 threshhold
- X$\mathbf{X}$ 可逆
- 任意的 Y$\mathbf{Y}$ 都可以表示出来

dVC≤d+1$d_{VC}\le d+1$

• We cannot shatter any set of d+2$d+2$ inputs.
• linear dependence restricts dichotomy
• 任意一个可以 shatter 的 d+1$d+1$ 向量组再加一维
• Xd+2${\mathbf{X}}_{d+2}$ 能被前 d+1$d+1$ 个向量线性表出

Physical Intuition of VC Dimension

Degrees of Freedom 自由度

• dVC≈freeparameters$d_{VC}\approx freeparameters$

Penalty for Model Complexity

• with a high probability, Eout≤Ein+Ω(N,H,δ)$E_{out}\le E_{in}+\mathrm{\Omega }(N,\mathcal{H},\delta )$

• The VC Message
  

Sample Complexity

• theory: N≈10000 dVC$N\approx 10000d_{VC}$

• practical: N≈10 dVC$N\approx 10d_{VC}$ often enough!

• Looseness of VC Bound