台湾大学林轩田机器学习基石课程学习笔记6 -- Theory of Generalization

上一节课,我们主要探讨了当M的数值大小对机器学习的影响。如果M很大,那么就不能保证机器学习有很好的泛化能力,所以问题转换为验证M有限,即最好是按照多项式成长。然后通过引入了成长函数m_H(N)和dichotomy以及break point的概念,提出2D perceptrons的成长函数m_H(N)是多项式级别的猜想。这就是本节课将要深入探讨和证明的内容。

一、Restriction of Break Point

我们先回顾一下上节课的内容,四种成长函数与break point的关系:

下面引入一个例子,如果k=2,那么当N取不同值的时候,计算其成长函数m_H(N)是多少。很明显,当N=1时,m_H(N)=2,;当N=2时,由break point为2可知,任意两点都不能被shattered(shatter的意思是对N个点,能够分解为2^N种dichotomies);m_H(N)最大值只能是3;当N=3时,简单绘图分析可得其m_H(N)=4,即最多只有4种dichotomies。

所以,我们发现当N>k时,break point限制了m_H(N)值的大小,也就是说影响成长函数m_H(N)的因素主要有两个:

  • 抽样数据集N
  • break point k(这个变量确定了假设的类型)

那么,如果给定N和k,能够证明其m_H(N)的最大值的上界是多项式的,则根据霍夫丁不等式,就能用m_H(N)代替M,得到机器学习是可行的。所以,证明m_H(N)的上界是poly(N),是我们的目标。

二、Bounding Function: Basic Cases

现在,我们引入一个新的函数:bounding function,B(N,k)。Bound Function指的是当break point为k的时候,成长函数m_H(N)可能的最大值。也就是说B(N,k)m_H(N)的上界,对应m_H(N)最多有多少种dichotomy。那么,我们新的目标就是证明: B(N,k)\leq poly(N)

这里值得一提的是,B(N,k)的引入不考虑是1D postive intrervals问题还是2D perceptrons问题,而只关心成长函数的上界是多少,从而简化了问题的复杂度。

求解B(N,k)的过程十分巧妙:

  • 当k=1时,B(N,1)恒为1。
  • 当N < k时,根据break point的定义,很容易得到B(N,k)=2^N
  • 当N = k时,此时N是第一次出现不能被shatter的值,所以最多只能有2^N-1个dichotomies,则B(N,k)=2^N-1

到此,bounding function的表格已经填了一半了,对于最常见的N>k的情况比较复杂,推导过程下一小节再详细介绍。

三、Bounding Function: Inductive Cases

N > k的情况较为复杂,下面给出推导过程:

以B(4,3)为例,首先想着能否构建B(4,3)与B(3,x)之间的关系。

首先,把B(4,3)所有情况写下来,共有11组。也就是说再加一种dichotomy,任意三点都能被shattered,11是极限。

对这11种dichotomy分组,目前分成两组,分别是orange和purple,orange的特点是,x1,x2和x3是一致的,x4不同并成对,例如1和5,2和8等,purple则是单一的,x1,x2,x3都不同,如6,7,9三组。

将Orange去掉x4后去重得到4个不同的vector并成为α,相应的purple为β。那么B(4,3) = 2\alpha + \beta,这个是直接转化。紧接着,由定义,B(4,3)是不能允许任意三点shatter的,所以由α和β构成的所有三点组合也不能shatter(alpha经过去重),即\alpha + \beta\leq B(3,3)

另一方面,由于α中x4是成对存在的,且α是不能被任意三点shatter的,则能推导出α是不能被任意两点shatter的。这是因为,如果α不能被任意两点shatter,而x4又是成对存在的,那么x1、x2、x3、x4组成的α必然能被三个点shatter。这就违背了条件的设定。这个地方的推导非常巧妙,也解释了为什么会这样分组。此处得到的结论是\\alpha \leq B(3,2)

由此得出B(4,3)与B(3,x)的关系为:

最后,推导出一般公式为:

根据推导公式,下表给出B(N,K)

根据递推公式,推导出B(N,K)满足下列不等式:

上述不等式的右边是最高阶为k-1的N多项式,也就是说成长函数m_H(N)的上界B(N,K)的上界满足多项式分布poly(N),这就是我们想要得到的结果。

得到了m_H(N)的上界B(N,K)的上界满足多项式分布poly(N)后,我们回过头来看看之前介绍的几种类型它们的m_H(N)与break point的关系:

我们得到的结论是,对于2D perceptrons,break point为k=4m_H(N)的上界是N^{k-1}。推广一下,也就是说,如果能找到一个模型的break point,且是有限大的,那么就能推断出其成长函数m_H(N)有界。

四、A Pictorial Proof

我们已经知道了成长函数的上界是poly(N)的,下一步,如果能将m_H(N)代替M,代入到Hoffding不等式中,就能得到E_{out}\approx E_{in}的结论:

实际上并不是简单的替换就可以了,正确的表达式为:

该推导的证明比较复杂,我们可以简单概括为三个步骤来证明:

这部分内容,我也只能听个大概内容,对具体的证明过程有兴趣的童鞋可以自行研究一下,研究的结果记得告诉一下我哦。

最终,我们通过引入成长函数m_H,得到了一个新的不等式,称为Vapnik-Chervonenkis(VC) bound:

对于2D perceptrons,它的break point是4,那么成长函数m_H(N)=O(N^3)。所以,我们可以说2D perceptrons是可以进行机器学习的,只要找到hypothesis能让E_{in}\approx0,就能保证E_{in}\approx E_{out}

五、总结

本节课我们主要介绍了只要存在break point,那么其成长函数m_H(N)就满足poly(N)。推导过程是先引入m_H(N)的上界B(N,k),B(N,k)的上界是N的k-1阶多项式,从而得到m_H(N)的上界就是N的k-1阶多项式。然后,我们通过简单的三步证明,将m_H(N)代入了Hoffding不等式中,推导出了Vapnik-Chervonenkis(VC) bound,最终证明了只要break point存在,那么机器学习就是可行的。

注明:

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

【从零开始学统计】2.可决系数真的决定一切么?

【从零开始学统计】可决系数真的决定一切么? 前几天逛知乎的时候看到一个帖子,学计量的和学统计的在争论关于anova里的可决系数的问题。突然萌生了一个念头,想听听...

1746
来自专栏大数据挖掘DT机器学习

百度电影推荐系统比赛——初步推荐算法实践

前一阵子参加了百度的电影推荐系统创新比赛。http://openresearch.baidu.com/activitycontent.jhtml?channel...

4856
来自专栏机器学习算法与Python学习

机器学习(26)之K-Means实战与调优详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 在K-Means聚类算法原理(...

4486
来自专栏智能算法

机器学习算法常用指标总结

来自:Poll的笔记 链接:http://www.cnblogs.com/maybe2030/p/5375175.html(点击尾部阅读原文前往) 阅读目录 ...

3266
来自专栏机器学习之旅

理论:FM理论解析及应用FM的产生背景one-hot过程什么叫做组合问题组合特征后的表达形式方程定义完成了,下面就要开始数学定义下面让我们来解这个式子引申一个FFM概念代码实现

我其实没有做过很多ctr预估的事情,但是我在工作中常常遇到CRM流失预估、订单预估这些依赖于特征工程的事情,其中就涉及到特征的组合问题。

603
来自专栏达观数据

技术干货 | 达观数据智能问答技术研究

在AlphaGo大胜李世石、柯洁之后,人工智能越来越火,智能问答也是其中必不可少的一环。智能问答一般用于解决企业客服、智能资讯等应用场景,实现的方式多种多样,包...

34811
来自专栏绿巨人专栏

机器学习实战 - 读书笔记(14) - 利用SVD简化数据

2939
来自专栏机器之心

NAACL | 评价端到端生成式聊天系统,哈工大提出新型数据集 LSDSCC

得益于深度学习的发展,端到端的生成式聊天系统在模型层面的研究工作在近两到三年中取得了长足的进步 [1-5]。与之相比,对于生成结果的合理评价方法的探索则极为滞后...

1093
来自专栏达观数据

技术干货 | 细说YouTube推荐系统的变迁

作者简介 郝俊禹:达观数据高级工程师,曾获美国大学生数学建模竞赛二等奖,目前参与达观数据推荐系统研发,负责酷6,wifi万能钥匙和视频看看等项目。 ---- ?...

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

机器学习系列:(四)从线性回归到逻辑回归

从线性回归到逻辑回归 在第2章,线性回归里面,我们介绍了一元线性回归,多元线性回归和多项式回归。这些模型都是广义线性回归模型的具体形式,广义线性回归是一种灵活的...

3816

扫码关注云+社区