简单自学机器学习理论—— 泛化界限 (Part II )

  1. 云栖社区>
  2. 博客>
  3. 正文

简单自学机器学习理论—— 泛化界限 (Part II )

uncle_ll 2017-07-12 17:02:10 浏览885
展开阅读全文

首发地址:https://yq.aliyun.com/articles/67168

本文由北邮@爱可可-爱生活 老师推荐,阿里云云栖社区组织翻译。

以下为译文

机器学习理论 part II- 泛化界限(第I部分内容点;第III部分内容点

上节总结到最小化经验风险不是学习问题的解决方案,并且判断学习问题可解的条件是求:

0ff10c454d6605d4126217e115e23459a503f936

在本节中将深度调查研究该概率,看其是否可以真的很小。

独立同分布

为了使理论分析向前发展,作出一些假设以简化遇到的情况,并能使用从假设得到的理论推理出实际情况。

我们对学习问题作出的合理假设是训练样本的采样是独立同分布的,这意味着所有的样本是相同的分布,并且每个样本之间相互独立。

大数法则

如果重复一个实验很多次,这些实验的平均值将会非常接近总体分布的真实均值,这被称作大数规则,若重复次数是有限次m,则被称作弱大数法则,形式如下:

 b286e2eca71646b2bac531072d7f5be7335f48e7

将其用在泛化概率上,对于单假设h

 dbf0adadd5f5b6175b73c271c17cdb760bd8d516

hoeffding不等式

集中不等式提供了关于大数法则是如何变化的更多信息,其中一个不等式是Heoffding不等式:

 42685c288958cd9da1ed4c245257cdeb33cc8388

将其应用到泛化概率上,假设错误限定在0和1之间,则对于假设h有

 5b080bee7970a7ddf85510e9b79fe7bcc0ab285d

这意味着训练与泛化误差之间的差大于a89b186098930306e0e130bed92ad35e8cb46989的概率是随着数据集的大小成指数衰减。

泛化界限:第一次尝试

为了针对整个假设空间都有泛化差距大于a89b186098930306e0e130bed92ad35e8cb46989,表示如下:

 3101ebe47f90635cfd07900db972e701a04eed8a

使用布尔不等式,可以得到

 b286e2eca71646b2bac531072d7f5be7335f48e7

使用Heoffding不等式分析,能够准确知道概率界限,以下式结束:

 11d416f85007c68da736f6473fc14ee497538a3a

置信度1-δ

 0c5116f0f55acd56d230f620ead87cf038f263bd

使用基本代数知识,用δ表示a89b186098930306e0e130bed92ad35e8cb46989得到:

 de6e15cdf48bd757975fcde620d7a127cee57bd9

上式就是第一次泛化界限,该式表明泛化错误是受到训练误差加上以假设空间大小和数据集大小的函数的限定。

检验独立性假设

首先需要问自己是否每一个可能的假设都需要考虑?答案是简单的,由于学习算法需要搜索整个假设空间以得到最优的解决方案,尽管这个答案是正确的,我们需要更正式化的答案:

泛化不等式的公式化揭示了主要的原因,需要处理现存的上确界,上确界保证了存在最大泛化差距大于a89b186098930306e0e130bed92ad35e8cb46989的可能性。如果忽略某个单假设,则可能会错过最大泛化差距并失去这一优势,这不是我们能够承担的,因此需要确保学习算法永远不会落在一个有最大泛化差距大于a89b186098930306e0e130bed92ad35e8cb46989的假设上。

 9215d6bfc83de54d707eef9a765a2f3e7994a857

从上图可以看出是二分类问题,很明显彩色线产生的是相同的分类,它们有着相同的经验风险。如果只对经验风险感兴趣,但是需要考虑样本外的风险,表示如下:

 303715cfbe90a0b62a44e3a1e2bc6a2eeeda8cff

为了确保上确界要求,需要考虑所有可能的假设。现在可以问自己,每一个有大泛化差距的假设事件可能是互相独立的吗?如果上图红线假设有大的泛化差距大于a89b186098930306e0e130bed92ad35e8cb46989,那么可以肯定的是在该区域的每个假设也都会有。

 f4621d86222be6d44f3110851c2bb53aef25a361

这对我们的数学分析是没有帮助的,由于区域之间看起来取决于样本点的分布,因此没有方法在数学上精确获取这些依赖性,于是这些统一的界限和独立假设看起来像是我们能够做的最佳近似,但它高估了概率并使得这些界限非常接近,性能不好。

对称引理

假设训练集是独立同分布,但不是只考虑数据集S的部分,假设有另外的数据集S,大小为m,将其称作ghost数据集。使用ghost数据集可以证明:

0d60e8ae4bf0ea7b561d1f3494661405087f676e1

该式意味着最大泛化差距大于a89b186098930306e0e130bed92ad35e8cb46989的概率几乎是SS之间的经验风险差概率大于ac8e24def07aea1dff51281bb1c0fe2266ad9e33的两倍,这被称作对称引理。

生长函数

如果我们有许多假设有着相同的经验风险,可以放心地选择其中一个作为整个群的代表,将其称作有效假设并抛弃其它的假设。

假设在668e04560c0b7d692ed8f8f35bc607e552e3d628中的假设的独立性与之前在H的假设一样,使用一致限可以得到:

e978fe7848c7415656956591482b06273db25cb12

定义不同S数据集的标签值的最大数作为生长函数,对于二元分类情况,可以看到:

 9278255968ffaf623f23b9d4da6aad7f7e7085b3

但由于是指数形式,随着m的增大而快速增长,这会导致不等式变坏的几率变得更快。

VC

如果一个假设空间确实能够在数据点集上产生概率标签,我们可以说该假设空间打碎了该数据点集。但任何假设空间能打碎任何尺寸的数据集吗?下图展示的是2D的线性分类器有多少种方法标记3点(左边)和4点(右边)。

 406119eae69c54dcef051c5d883617bec9fc2f9d

事实上,没有2D线性分类分类器可以打散任何4点的数据集,因为总是会有两个标签不能被线性分类器生成,如下图所示:

 a5c77e657f05291da6f1270a3dcf0312c7d07ba3

从图中的判定边界,清晰知道没有线性分类器能产生这样的标签,因为没有线性分类器能够以这样的方式划分空间,这一事实能够用来获得更好的限定,这使用Sauer引理:

如果假设空间H不能打算任何大小超过k的数据集,那么有

 11d67971aea187fd70fa0d7fd33bdc0f19b7155e

K是空间H能够打碎的最大数量点,也被称作Vapnik-Chervonenkis-dimension或者VC维数

生长函数的界限是通过sauer引理提供的,确实是比之前的指数形式好很多,运用代数运算,能够证明:

 fcfbe2c2133114f71f63c7fe75107657bab43bc7

这样我们能够针对生长函数使用VC维数作为其替身,56f81ea4b64130140d4172bec4896e594a459b1b将会是复杂度或者假设空间丰富度的测量。

VC泛化界限

通过结合公式1与公式2可以得到Vapnik-Chervonenkis理论,形式如下:

 de5506ee465861881908b537cde97b29f492f4dc

重新将其表述作为泛化误差上的界限,得到VC泛化界限:

 900144c98112780e116862ec1c47b6b664824256

或者使用56f81ea4b64130140d4172bec4896e594a459b1b表示生长函数上的界限得到:

 2d77fe7e44b8b3e869cb9deff6b70b06ed2048be

该式清晰并间接表示了学习问题是否可解,并针对无限假设空间,对其泛化误差有着有限的界限。

基于分布的界限

事实上,56f81ea4b64130140d4172bec4896e594a459b1b是带有值的自由分布:通过不利用结构和数据样本的分布,该界限会趋向于松弛。对于数据点是线性分开的,包含半径为R,两个非常接近点之间的边缘ρ,可以证明得到针对假设分类器有:

 b2a639d3bf81412c01a2b621d475777507ce0aa8

这就是支持向量机(SVM)背后的理论依据。

一个不等式去管理所有的它们

上面的所有分析是针对二元分类问题,然而VC的概念上的框架一般也适用于多分类与回归问题。根据相关研究人员的工作,不管这些工作产生的界限是多么的精确,总会有如下的形式:

 621ccc127fde6f4d573d142f75d9a2ac9914da80

其中C是假设空间复杂度、数据集大小以及置信度δ的函数,这个不等式基本说明泛化误差能够分解为两部分:经验训练误差和学习模型的复杂度。该不等式的形式对于任何学习问题、不管多么准确界限而言都是适用的。

参考文献:

  Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012.

        Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.

        Abu-Mostafa, Y. S., Magdon-Ismail, M., & Lin, H. (2012). Learning from data: a short course.

 文章原标题《Machine Learning Theory - Part II》,作者:Mostafa Samir,译者:海棠 

 文章为简译,更为详细的内容,请查看原文

翻译者: 海棠 

Wechat:269970760 

Email:duanzhch@tju.edu.cn

微信公众号:AI科技时讯

157f33dddfc596ede3681e0a2a0e7068dc288cc1

网友评论

登录后评论
0/500
评论
uncle_ll
+ 关注