VC Dimension,成长函数 (growth function)

机器学习笔记-VC Dimension, Part II

笔记整理自台大林轩田老师的开放课程-机器学习基石,笔记中所有图片来自于课堂讲义。

  上一篇用成长函数$m_{\mathcal{H}}(N)$来衡量Hypotheses Set $\mathcal{H}$中有效的方程的数量(Effective Number of Hypotheses),以取代Hoeffding’s Inequality中的大$M$,并用一种间接的方式 —- break point,来寻找$m_{\mathcal{H}}(N)$的上界,从而避免了直接研究$\mathcal{H}$的成长函数的困难。

机器学习笔记-VC Dimension, Part I

笔记整理自台大林轩田老师的开放课程-机器学习基石,笔记中所有图片来自于课堂讲义。

  上一篇讲到,learning的时候如果遇上bad sample,如果遇上bad sample我们就无法保证$E_{in}$和$E_{out}$很接近。我们用了一个不等式来衡量遇上bad sample的概率:

$$\mathbb{P}_\mathcal{D}[BAD\ D]\leq 2Mexp(-2\epsilon ^2N)$$