机器学习基石-Theory of Generalization

Theory of Generalization

Lecture5我们主要目的是证明hypothesis set是无限的情形下的Hoeffding的成立问题,我们最终通过一系列定义和推导得到成长函数和break point间的猜想,本节课我们主要解决这个问题的证明。

回顾

Restriction of Break Point

首先我们回到已经研究过的四类成长函数及其相关的break point:

下面我们研究下成长函数的影响因素,我们考虑break point K=2的情形(K=2,意味着N中任意两个点都被不能被shattered,shatter的意思是对N个点,能够分解为2^N种dichotomies)。

很明显,当N=1时,mH(N)=2,;当N=2时,由break point为2可知,任意两点都不能被shattered,mH(N)最大值只能是3;当N=3时,简单绘图分析可得其mH(N)=4,即最多只有4种dichotomies。

于是我们可以总结影响成长函数大小的因素主要有两个:取样的样本集大小N和break point K的大小。

那么,给定N和K,我们的思路是证明mH(N)的最大值的上界是多项式形式的,进而达到证明机器学习可行的目的。

Bounding Function: Basic Cases

我们引入一个新的函数B(N,K),定义是在break point为K时,成长函数mH(N)可能的最大值,即为mH(N)的上界,于是我们接下来的目标是证明这个函数是多项式形式的。

然后我们试着填一下上面这张表,当k=1时,我们容易得出B(N,1)恒为1;当N

Bounding Function: Inductive Cases

下面我们来看看N>K的情形,我们以计算B(4,3)为例来推导完成表的下半部分。

我们首先写出B(4,3)对应的所有的dichotomy共11种情形,然后我们将这11钟情形做一个分类,分成orange(x1,x2,x3存在一致的情况)和purple(x1,x2,x3均不一致的情况)。

在dichotomy中我们去掉x4,去重后得到的维数为α(orange)和β(purple)。根据定义,B(4,3)是不允许任意三点被shatter的,所以α+β

另一方面,由于orange中x4是成对存在的,所以可以推出α是不允许两个点被shatter的,所有有α

于是我们可以得到B(4,3)的上界,进而得出一般形式的B(N,k)的上界公式,于是我们可以完成表格的下半部分。

根据递推公式,我们发现B(N,K)的上界函数满足多项式分布poly(N),他的最高次幂为K-1次,于是我们完成了整个证明过程。

A Pictorial Proof

我们通过前述的结论推导出相应的Hoeffding公式,公式的证明比较复杂,本节内容不予展示,有兴趣的可以查阅相关资料查看。

本节课我们主要证明了成长函数满足多项式分布poly(N)这件事,我们研究了break point的性质,然后引入了成长函数上界函数的概念,通过通过证明后者满足poly(N)来达到目的,最终完成整个机器学习可行性的证明。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180410G1KC4Q00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励