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