为什么引入vc维？
为了估计out of sample error，必须定义模型得复杂度。 目前知道得复杂度度量方法：
模型参数个数。。。
naive，\(sin(\alpha x)\)虽然只有一个参数，但是明显比分类器\(I(\alpha x1 + \beta x2>0)\)复杂度高
trace
\[\begin{eqnarray*}
\text{若} \hat{y} = Sy，
\text{那么复杂度是} tr(S)
\end{eqnarray*}\]
实际上，这种复杂度定义应用范围有限，我们需要更general得复杂度定义方式
定义
某一类模型\(f\{x,\alpha\}\)所能shatter得点得数量（假设点得label是任意得）
例子
二维回归不能shatter4个点，所以，vc dimension是3
作用
给out of sample error限定了bound，尽管很loss [Cherkassky & Mulier (2007, pages 116-118)]
\[\begin{eqnarray*}
\text{对于二分类：} Err_\tau \leqslant \overline{err} + \frac{\varepsilon}{2}(1 + \sqrt{1 + \frac{4\cdot\overline{err}}{\varepsilon}}) \\
\text{对于回归：} Err_\tau \leqslant \frac{\overline{err}}{(1 - c\sqrt{\varepsilon})_{+}} \\
\text{其中,} \varepsilon = a_1\frac{h[\log(a_2N/h) + 1] - \log{(\eta/4)}}{N} \\
0 < a_1 \leqslant 4, 0 < a_2 \leqslant 2
\end{eqnarray*}\]
缺点
有些模型，vc dimension根本不知道