vc-dimension

Processing math: 80%

为什么引入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根本不知道

vc-dimension

deng.zhou

2016/12/17

为什么引入vc维？

模型参数个数。。。

trace

定义

例子

作用

缺点