-
VC dimension就是假设空间能打散的最多的点, 也就是刚好比break point小1.
definition -
因此, growth function也被VC dimension联结起来了, 如下。 那么VC inequality同时考虑了VC, data size N。
growth -
examples from before.
example -
VC dimension是与learning algorithm, input distribution, target function独立的。
relationship -
VC dimension 的含义: 一是模型的自由度。 在Positive rays, 能打散的点是1, break point是2, 模型刚好有一个参数a, d_vc刚好等于参数个数。在Positive intervals中, 能打散的点是2, break point是3,模型刚好有2个参数, d_vc刚好等于参数个数。 但是参数并不一定以为着自由度, 如第三个slide, 输出再变成下一个的输入, 模型的自由度仍然不变, 在多层神经网络中也是类似的情况, 层数的堆叠并不以为着自由度变大了。
explain1
explain2
explain3 -
二是隐含着训练这样一个模型所需要的数据。我们希望epsilon和delta都很小。下面的公式是delta的简化版本,N^d是保留最高阶的项。横坐标是N, 不同的线表示不同的d, 纵坐标是做了log变化的, actual我们希望的是这个函数值越小越好, 也就是需要N比较大。 可以看出随着d变大, N也需要增大来满足这种需求, 一个rule of thumb是取N ≥ 10 d。
data
N -
generation bound. 重新整理之后, 得到在概率≥ 1- delta的情况下, Eout与Ein在一个小区间内。再简化之后得到了Eout 小于等于 Ein + \delta, 称为generation bound。通常来说, 如果hypothesis set更大的话, 那么Ein肯定会更小, 但是\delta会更大, 这其中存在trade-off, 实际中,我们还采用了regularization的technique来惩罚Ein, 让模型的hypothesis set不要太大。
rearange
bound
网友评论