美文网首页
7-VC dimension

7-VC dimension

作者: Klaas | 来源:发表于2018-03-11 10:07 被阅读11次
    • 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

          本文链接:https://www.haomeiwen.com/subject/pedbfftx.html