Learning From Data Lecture 6 一般化的理论

segment 1 证明成长函数mH(N)是多项式

核心思想:

  • 如果要证明成长函数是mH(N)多项式,只需要证明成长函数mH(N)小于一个多项式。

关键的数量:

  • B(N,k),在转折点为k时,对于N个数据点的最大二分法数量。

回顾转折点k的定义:

  • 如果包含k个数据点的数据集均不能被假说集合H“打碎”,则称k是假说集合H的转折点。

在B(N,k)的定义中,假说集合被限定为二分法。

对二分法结果的矩阵而言,B(N,k)的值意味着:

  • 在N列的矩阵中,任意选择k列,要这k列中均不包含所有(2k)种可能的模式。B(N,k)是满足该条件的矩阵的行数。

例如,k=2,N=3,考虑下面二分法是否满足 B(N,k)的定义?

X1 X2 x3
+1 +1 +1
-1 -1 -1
+1 -1 +1
-1 +1 +1
-1 -1 +1

上述二分法是不符合 B(N,k)定义的,因为第1和第2个数据这2个数据点的及和被二分法打碎了(+1+1,-1-1,+1-1,-1+1均包含了2k = 22=4种模式)。

通过枚举法可知k=2,N=3时,二分法的最大可能性为4:

例如:

X1 X2 x3
+1 +1 +1
-1 +1 +1
+1 -1 +1
+1 +1 -1

接下来讨论一般情况,对于N个数据点,所有满足B(N,k)的二分法数量的上限是多少。

考虑一个满足B(N,K)的二分法矩阵,每一列分别对应一个数据点Xi。

考虑可以如何将矩阵进一步细分。

bnk-matrix

矩阵的第一部分称为S1,共有2α行。

S1中的每一列中的X1至XN-1的可能组合都出现正好2次,一次是伴随着XN=+1,一次是伴随着XN=-1。

根据XN=+1还是-1将其分为2个子部分S1+和S1-,两个子部分的行数相等均为α

矩阵的第2部分称为S2,共有β行。

其中每一列的X1至XN-1的可能情况都是与第一部分中X1至XN-1的情况互斥。

得出 B(N,k) = 2α+β

举一个例子N=4,k=3:

QQ截图20131218110408

有B(4,3) = 11

我们尝试通过递归的方法获得B(N,k)的上限。

首先尝试发现B(N,k)与B(N-1,k)之间的关系,由B(N,k)的二分法矩阵出发,尝试分析一下B(N-1,k)的二分法矩阵:

bn-1k-matrix

因为S1+和S1-这两个部分原先只有XN项不同,因此只可保留其一,而S2这部分的X1至XN-1均与S1中的情况互斥。

这样便构成了一个比B(N,k)小一些的矩阵。

在原先的B(N,k)矩阵中,任选k列,均不可能包含所有(2k)种模式。

因此可以知道,这个小矩阵中任选k列,也不可能会有包含所有(2k)种模式的情况。

因此知道:B(N-1,k) >=α+β

以上面B(4,3)为例,这样操作的结果是获得如下二分法矩阵:

QQ截图20131218110549

则知道B(3,3)>=3+4=7

如果尝试对B(3,3)进行枚举,结果可以发现B(3,3)确实为7,与这样构建的结果相同。

接下来观察原本B(N,k)二分法矩阵中的S1部分:

bnk-matrix3

因为S1+和S1-的前XN-1列完全是相同的,只随意选取其一来分析。

尝试说明这个被选出的部分的转折点为k-1。

原因是:对于S1+任意一行,S1-中均有一模一样的一行。

XN项的特殊性在于包含了其所有可能的情况,在加上XN项的情况下S1部分的突破点为k,在去掉XN后剩余的部分突破点应该为k-1。

即 α <= B(N-1,k-1)。

仍以之前B(4,3)的为例,抽取出来的S1+的前三列为:

QQ截图20131218110455

通过枚举亦可知B(3,2) = 4。

综合上面的结论B(N-1,k) >=α+β,α <= B(N-1,k-1),B(N,k) = 2α+β得到:

  • B(N,k)>=B(N-1,k)+B(N-1,k-1)

因此可以以此公式,在通过枚举法获得前几个情况的结果后,通过递归地f方式求出B(N,k)的上限表格:

  • 注意到B(N,1)的含义是,在N列的矩阵中任意取一列,该列中不能既有+1又有-1,其结果显而易见只能是1
  • 注意到B(1,k)的含义是,在1列的矩阵中任意取k列,该k列中不能包含所有可能的模式,因为实际上只有1列,因此B(1,k)=2

此后可用递归方法填满整张表格。

growth function matrix

这个表格实际上告诉我们B(N,k)的公式为:

theory

可以用归纳法证明:

proof

最后将此B(N,k)作为成长函数mH(N)的上限,这个值是多项式,因为最大项为NK-1,而N是训练集的数据数量,为常数。

gro fun

三个例子:

3 examples

  • 正射线假说集合的转折点为2,其成长函数上限为N+1
  • 正区间假说集合的转折点为3,其成长函数上限为1/2×N2+1/2×N+1
  • 2维感知器假说集合的转折点为4,其成长函数上限为1/6×N3+5/6×N+1

不论任何情况,我们都只需要知道假说集合的转折点这一个量,即可知道成长函数的多项式上限是多少。

segment 2 证明成长函数mH(N)可用于替代假说集中假说数量M

我们希望用上限为多项式形式的成长函数mH(N)来替代原本的假说集合中所有假说的数量M。

即从认为所有的假说均为互斥的,考虑最糟糕的情况:

1

到考虑到假说之间的互相包含关系,采取成长函数这个有限的上限:

2

尝试以图像的方式说明这样做的好处:

pictorial proof

假设上图中的黑框代表数据集的空间,黑框内的任意一个点都代表一个数据,黑框包含了所有可能的数据。

我们所使用的数据集是由某未知概率分布P从此数据集空间所生成的,整个黑框代表概率1,其中每一个点都有一定地概率被选进我们所看到的数据集。

  • 针对一个特定的假说h,我们将其运用到每一个数据(即黑框内的每一个点),如果发现|Ein(h)-Eout(h)|> ε则将这个代表这个数据的点着色,如(a)所示。
  • 采用联合上限就相当于,认为所有的h均互斥,因此对假说集合H中的所有h都进行上述操作,则获得(b)中情况。
  • 采用成长函数作为上限,考虑进h之间的互相包含关系,对假说集合H中的所有h都进行同样操作,获得(c)中情况,这个上限又称为VC上限。

关键的一个问题在于,成长函数能够在多大程度上捕捉假说之间的互相包容关系。

考虑容器-弹珠模型:

Eout_thumb.png

如果我们有很多容器(h),用一个概率分布取一个样本进行检验,则其中出现|Ein(h)-Eout(h)|> ε情况的概率随容器数量上升而上升。

Eout(h)是无限的,无法知道的,因此尝试将其替换掉。

方法是:与其只取一个样本,用同样的概率分布再取一个样本进行检验,E'in(h)和Ein(h)之间是微弱地相关的(Ein(h)和E'in(h)针对的是不同的两个样本)。

如果|Ein(h)-Eout(h)|> ε则很有可能|Ein(h)-E'in(h)|> ε。

原先的问题:容器越多,其中出现|Ein(h)-Eout(h)|> ε情况的概率就越高。

如果只考虑这些Ein(h),随着抽取的样本越多,出现|Ein(h)-E'in(h)|> ε情况的概率也就越高。

即:越来越多假说带来的问题,与反复抽样带来的问题实际上是一样的。

反复抽样的问题就是上面以图片形式加以说明的。

针对数据量N的样本检验Ein(h)-Eout(h)就相当于,针对数据量为2N的样本检验两个不同假说Ein(h)-E'in(h)。

因此我们用成长函数对M进行替换并不能获得:

2_thumb.png

而是:

VC in

这个式子被称为VC不等式(The Vapnik-Chervonenkis Inequality)

补充林老师课里详细一些的证明过程:

Ein,E'in和Eout之间关系如下图所示:

prob

因此有:

prof1

prof2

prof3

prof4

课程地址:

http://work.caltech.edu/telecourse.html

 

3 thoughts on “Learning From Data Lecture 6 一般化的理论

  1. whose心

    “矩阵的第2部分称为S2,共有β行。其中每一列的X1至XN-1的可能情况都是与第一部分中X1至XN-1的情况互斥。”
    互斥是什么概念?怎么得到S2的?

    Reply
    1. 小小人_V Post author

      我的理解是:“互斥”意味着,互相独立、不重复,可以看我举得B(4,3)的例子。
      S2不是通过怎样的规则或者计算“得到”的,而是对于一个已有的二分法矩阵,可以将其中的行数人为地分为S1和S2两个部分。

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *