台湾大学林轩田机器学习基石课程学习笔记7 -- The VC Dimension

前几节课着重介绍了机器能够学习的条件并做了详细的推导和解释。机器能够学习必须满足两个条件:

  • 假设空间H的Size M是有限的,即当N足够大的时候,那么对于假设空间中任意一个假设g,E_{out}\approx E_{in}
  • 利用算法A从假设空间H中,挑选一个g,使E_{in}(g)\approx0,则E_{out}\approx0

这两个条件,正好对应着test和trian两个过程。train的目的是使损失期望E_{in}(g)\approx0;test的目的是使将算法用到新的样本时的损失期望也尽可能小,即E_{out}\approx0

正因为如此,上次课引入了break point,并推导出只要break point存在,则M有上界,一定存在E_{out}\approx E_{in}

本次笔记主要介绍VC Dimension的概念。同时也是总结VC Dimension与E_{in}(g)\approx0,E_{out}\approx0,Model Complexity Penalty(下面会讲到)的关系。

一、Definition of VC Dimension

首先,我们知道如果一个假设空间H有break point k,那么它的成长函数是有界的,它的上界称为Bound function。根据数学归纳法,Bound function也是有界的,且上界为N^{k-1}。从下面的表格可以看出,N(k-1)B(N,k)松弛很多。

则根据上一节课的推导,VC bound就可以转换为:

这样,不等式只与k和N相关了,一般情况下样本N足够大,所以我们只考虑k值。有如下结论:

  • 若假设空间H有break point k,且N足够大,则根据VC bound理论,算法有良好的泛化能力
  • 在假设空间中选择一个矩g,使E_{in}\approx0,则其在全集数据中的错误率会较低

下面介绍一个新的名词:VC Dimension。VC Dimension就是某假设集H能够shatter的最多inputs的个数,即最大完全正确的分类能力。(注意,只要存在一种分布的inputs能够正确分类也满足)。

shatter的英文意思是“粉碎”,也就是说对于inputs的所有情况都能列举出来。例如对N个输入,如果能够将2^N种情况都列出来,则称该N个输入能够被假设集H shatter。

根据之前break point的定义:假设集不能被shatter任何分布类型的inputs的最少个数。则VC Dimension等于break point的个数减一。

现在,我们回顾一下之前介绍的四种例子,它们对应的VC Dimension是多少:

d_{vc}代替k,那么VC bound的问题也就转换为与d_{vc}和N相关了。同时,如果一个假设集H的d_{vc}确定了,则就能满足机器能够学习的第一个条件E_{out}\approx E_{in},与算法、样本数据分布和目标函数都没有关系。

二、VC Dimension of Perceptrons

回顾一下我们之前介绍的2D下的PLA算法,已知Perceptrons的k=4,即d_{vc}=3。根据VC Bound理论,当N足够大的时候,E_{out}(g)\approx E_{in}(g)。如果找到一个g,使E_{in}(g)\approx 0,那么就能证明PLA是可以学习的。

这是在2D情况下,那如果是多维的Perceptron,它对应的d_{vc}又等于多少呢?

已知在1D Perceptron,d_{vc}=2,在2D Perceptrons,d_{vc}=3,那么我们有如下假设:d_{vc}=d+1,其中d为维数。

要证明的话,只需分两步证明:

  • d_{vc}\geq d+1
  • d_{vc}\leq d+1

首先证明第一个不等式:d_{vc}\geq d+1

在d维里,我们只要找到某一类的d+1个inputs可以被shatter的话,那么必然得到d_{vc}\geq d+1。所以,我们有意构造一个d维的矩阵X能够被shatter就行。Xd维的,有d+1个inputs,每个inputs加上第零个维度的常数项1,得到X的矩阵:

矩阵中,每一行代表一个inputs,每个inputs是d+1维的,共有d+1个inputs。这里构造的XX很明显是可逆的。shatter的本质是假设空间H对X的所有情况的判断都是对的,即总能找到权重W,满足X\ast W=yW=X^{-1}\ast y。由于这里我们构造的矩阵X的逆矩阵存在,那么d维的所有inputs都能被shatter,也就证明了第一个不等式。

然后证明第二个不等式:d_{vc}\leq d+1

d维里,如果对于任何的d+2个inputs,一定不能被shatter,则不等式成立。我们构造一个任意的矩阵X,其包含d+2个inputs,该矩阵有d+1列,d+2行。这d+2个向量的某一列一定可以被另外d+1个向量线性表示,例如对于向量X_{d+2},可表示为:

X_{d+2}=a_1\ast X_1+a_2\ast X_2+\cdots+a_{d+1}\ast X_{d+1}

其中,假设a1>0,a2,⋯,ad+1<0

那么如果X_1是正类,X_2,\cdots,X_{d+1}均为负类,则存在W,得到如下表达式: X_{d+2}\ast W=a_1\ast X_1\ast W+a_2\ast X_2\ast W+⋯\cdots+a_{d+1}\ast X_{d+1}\ast W>0

因为其中蓝色项大于0,代表正类;红色项小于0,代表负类。所有对于这种情况,X_d+2一定是正类,无法得到负类的情况。也就是说,d+2个inputs无法被shatter。证明完毕!

综上证明可得d_{vc}=d+1

三、Physical Intuition VC Dimension

上节公式中W又名features,即自由度。自由度是可以任意调节的,如同上图中的旋钮一样,可以调节。VC Dimension代表了假设空间的分类能力,即反映了H的自由度,产生dichotomy的数量,也就等于features的个数,但也不是绝对的。

例如,对2D Perceptrons,线性分类,d_{vc}=3,则W=\{w_0,w_1,w_2\},也就是说只要3个features就可以进行学习,自由度为3。

介绍到这,我们发现M与d_{vc}是成正比的,从而得到如下结论:

四、Interpreting VC Dimension

下面,我们将更深入地探讨VC Dimension的意义。首先,把VC Bound重新写到这里:

根据之前的泛化不等式,如果|E_{in}-E_{out}|>\epsilon,即出现bad坏的情况的概率最大不超过δ。那么反过来,对于good好的情况发生的概率最小为1-\delta,则对上述不等式进行重新推导:

ϵ表现了假设空间H的泛化能力,ϵ越小,泛化能力越大。

至此,已经推导出泛化误差E_{out}的边界,因为我们更关心其上界(E_{out}可能的最大值),即:

上述不等式的右边第二项称为模型复杂度,其模型复杂度与样本数量N、假设空间H(d_{vc})、ϵ有关。E_{out}E_{in}共同决定。下面绘出E_{out}、model complexity、E_{in}d_{vc}变化的关系:

通过该图可以得出如下结论:

  • d_{vc}越大,E_{in}越小,Ω越大(复杂)
  • d_{vc}越小,E_{in}越大,Ω越小(简单)
  • 随着d_{vc}增大,E_{out}会先减小再增大

所以,为了得到最小的E_{out},不能一味地增大d_{vc}以减小E_{in},因为E_{in}太小的时候,模型复杂度会增加,造成E_{out}变大。也就是说,选择合适的d_{vc},选择的features个数要合适。

下面介绍一个概念:样本复杂度(Sample Complexity)。如果选定d_{vc},样本数据D选择多少合适呢?通过下面一个例子可以帮助我们理解:

通过计算得到N=29300,刚好满足δ=0.1的条件。N大约是d_{vc}的10000倍。这个数值太大了,实际中往往不需要这么多的样本数量,大概只需要d_{vc}的10倍就够了。N的理论值之所以这么大是因为VC Bound 过于宽松了,我们得到的是一个比实际大得多的上界。

值得一提的是,VC Bound是比较宽松的,而如何收紧它却不是那么容易,这也是机器学习的一大难题。但是,令人欣慰的一点是,VC Bound基本上对所有模型的宽松程度是基本一致的,所以,不同模型之间还是可以横向比较。从而,VC Bound宽松对机器学习的可行性还是没有太大影响。

五、总结

本节课主要介绍了VC Dimension的概念就是最大的non-break point。然后,我们得到了Perceptrons在d维度下的VC Dimension是d+1。接着,我们在物理意义上,将d_{vc}与自由度联系起来。最终得出结论d_{vc}不能过大也不能过小。选取合适的值,才能让E_{out}足够小,使假设空间H具有良好的泛化能力。

注明:

文章中所有的图片均来自台湾大学林轩田《机器学习基石》课程

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

小白学数据:教你用Python实现简单监督学习算法

1714
来自专栏AI研习社

如何使用高大上的方法调参数

本文主要介绍作者与 Elad Hazan, Adam Klivans 合作的最新论文: Hyperparameter Optimization: A Spec...

3509
来自专栏专知

【干货】动手实践:理解和优化GAN(附代码)

【导读】本文是机器学习研究员Mirantha Jayathilaka撰写的一篇技术博文,主要讲解了生成对抗网络(GAN)。本文分别从理论和代码实践两方面来介绍G...

3095
来自专栏机器之心

从决策树到随机森林:树型算法的原理与实现

选自Github.io 作者:Sadanand Singh 机器之心编译 基于树(Tree based)的学习算法在数据科学竞赛中是相当常见的。这些算法给预测模...

3966
来自专栏游戏杂谈

旋转矩阵(Rotation Matrix)的推导及其应用

矩阵如何进行计算呢?之前的文章中有简介一种方法,把行旋转一下,然后与右侧对应相乘。在谷歌图片搜索旋转矩阵时,看到这张动图,觉得表述的很清晰了。

484
来自专栏深度学习自然语言处理

深度学习数学基础一--最小二乘法

之前总是先上手一些比较高级的神经网络算法,CNN,RNN等。可是总觉得有些知识原理总是羁绊着我进一步理解。这才意识到基础的重要性。所以,就一点一点的从基础数学最...

3099
来自专栏智能算法

集成学习算法----Adaboost

1. Adaboost 算法思想 AdaBoost 是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器,即弱分类器,然后把这些弱分类器集合起来,构...

3288
来自专栏PPV课数据科学社区

【学习】十张图解释机器学习的基本概念

在解释机器学习的基本概念的时候,我发现自己总是回到有限的几幅图中。以下是我认为最有启发性的条目列表。 ? 1. Test and train...

2585
来自专栏机器学习原理

机器学习(16)——EM算法示例

算法思想:含有隐变量的极大似然估计 我们经常会从样本观察数据中,找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。 但是在一些情况下,我们得到...

3278
来自专栏人工智能头条

只知道GAN你就OUT了——VAE背后的哲学思想及数学原理

1403

扫码关注云+社区