-
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
7-VC dimension
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Lec 7：The VC Dimension tips：符号含义主要参照lec 1，部分需要参照其他lec 上一节...
- 前几节课着重介绍了机器能够学习的条件并做了详细的推导和解释。机器能够学习必须满足两个条件： 1、假设空间H的Siz...
- 转化代码 需要注意 在使用中,我们注意如果是NSDictionary 中包含 NSArray的话,只需要把最终的 ...
