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

2017 年 9 月 6 日 机器学习研究会

台大机器学习课程学习笔记7

The VC Dimension


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


机器能够学习必须满足两个条件:

  • 假设空间H的Size M是有限的,即当N足够大的时候,那么对于假设空间中任意一个假设g,

  • 利用算法A从假设空间H中,挑选一个g,使


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


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

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


1
  Definition of VC Dimension



首先,我们知道如果一个假设空间H有break point k,那么它的成长函数是有界的,它的上界称为Bound function。

根据数学归纳法,Bound function也是有界的,且上界为。从下面的表格可以看出,N(k−1)比B(N,k)松弛很多。

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

下面介绍一个新的名词:VC Dimension。

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

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

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

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

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




2
   VC Dimension of Perceptrons



回顾一下我们之前介绍的2D下的PLA算法,已知Perceptrons的k=4,即=3。


根据VC Bound理论,当N足够大的时候,如果找到一个g,使,那么就能证明PLA是可以学习的。


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


已知在1D Perceptron,=2,在2D Perceptrons,=3,那么我们有如下假设:=d+1,其中d为维数。要证明的话,只需分两步证明:

首先证明第一个不等式:d+1。


在d维里,我们只要找到某一类的d+1个inputs可以被shatter的话,那么必然得到d+1。


所以,我们有意构造一个d维的矩阵X能够被shatter就行。X是d维的,有d+1个inputs,每个inputs加上第零个维度的常数项1,得到X的矩阵:

矩阵中,每一行代表一个inputs,每个inputs是d+1维的,共有d+1个inputs。这里构造的X很明显是可逆的。


shatter的本质是假设空间H对X的所有情况的判断都是对的,即总能找到权重W,满足XW=y。由于这里我们构造的矩阵X的逆矩阵存在,那么d维的所有inputs都能被shatter,也就证明了第一个不等式。

然后证明第二个不等式:


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


转自:机器学习算法与自然语言处理

登录查看更多
0

相关内容

专知会员服务
115+阅读 · 2019年12月24日
【干货】​深度学习中的线性代数
专知
21+阅读 · 2018年3月30日
课程笔记|吴恩达Coursera机器学习 Week1 笔记-机器学习基础
机器学习研究会
4+阅读 · 2017年10月18日
BAT机器学习面试1000题系列(第51~55题)
七月在线实验室
10+阅读 · 2017年10月8日
BAT机器学习面试1000题系列(第46~50题)
七月在线实验室
7+阅读 · 2017年10月7日
机器学习(13)之最大熵模型详解
机器学习算法与Python学习
7+阅读 · 2017年8月24日
Arxiv
4+阅读 · 2018年9月6日
Arxiv
11+阅读 · 2018年4月25日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
3+阅读 · 2018年1月31日
Arxiv
6+阅读 · 2017年12月2日
VIP会员
相关VIP内容
专知会员服务
115+阅读 · 2019年12月24日
相关论文
Arxiv
4+阅读 · 2018年9月6日
Arxiv
11+阅读 · 2018年4月25日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
3+阅读 · 2018年1月31日
Arxiv
6+阅读 · 2017年12月2日
Top
微信扫码咨询专知VIP会员