在机器学习中,有一些非常有名的理论或定理,对理解机器学习的内在特性非常有帮助。

PCA学习理论

当使用机器学习算法来解决某个问题时,通常靠经验或者多次实验来得到合适的模型,训练样本数量和相关的参数。但是经验判断成本较高,且不太可靠,因此希望有一套理论能够分析问题,计算模型能力,为算法提供理论保证。这就是计算学习理论(Computational Learning Theory),其中最基础的就是近似正确学习理论(Probably Approximately Coorrect,PCA)。

机器学习中一个很重要的问题就是期望错误与经验错误之间的误差,称为泛化误差(Generalization Error),用来衡量一个机器学习模型能否很好的泛化到未知数据。

根据大数定理,当训练的数据集D接近于无穷大时,泛化错误趋向于0,即经验风险趋向于期望风险。由于我们并不知道真实的数据分布,因此从有限的数据样本学习到一个期望错误为0的模型是很难的,因此需要降低对模型的期望,只要求学习到的模型能够以一定的概率学习到一个近似正确的假设,这就是PCA学习理论。

PCA学习理论包含了两部分:近似正确和可能。

没有免费午餐定理

没有免费午餐定理(No Free Lunch Theorem,NFL)是由Wolpert和Macerday在最优化理论中提出的,NFL证明:对于基于迭代的最优化算法不会存在某种算法对所有问题(有限的搜索空间内)都有效。如果一个算法对某些问题有效,那么他一定在另一些问题上比纯随机搜索算法更差。也就是说,不能脱离具体问题来讨论算法的优劣,任何算法都有优劣性,必须要“具体问题具体分析”。

丑小鸭定理

丑小鸭定理(Ugly Duckling Theorem)是1969年由渡边慧提出的[Watan-able, 1969]。“丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大”。这个定理初看好像不符合常识,但是仔细思考后是非常有道理的。因为世界上不存在相似性的客观标准,一切相似性的标准都是主观的。如果以体型大小的角度来看,丑小鸭和白天鹅的区别大于两只白天鹅的区别;但是如果以基因的角度来看,丑小鸭与它父母的差别要小于他父母和其他白天鹅之间的差别。

奥卡姆剃刀

奥卡姆剃刀(Occam’s Razor)是由14世界逻辑学家William of Occam提出的一个解决问题的法则:“如无必要,勿增实体”。

奥卡姆剃刀的思想和机器学习上正则化思想十分相似:简答的模型泛化能力更好。如果有两个性能相近的模型,我们更倾向于选择简单的模型。因此在机器学习准则上,我们经常会引入参数正则化(比如L2正则)来限制模型能力,避免过拟合。

这里需要区分下L1正则和L2正则的区别,如果需要小编回答,可在评论区留言!

奥卡姆剃刀的一种形式化是最小描述长度(Minimum Description Length, MDL)原则,即对一个数据集D,最好的模型f属于F是会使得数据集的压缩效果最好,即编码长度最小。

最小描述长度也可以通过贝叶斯学习的观点来解释,模型 f 在数据集 D 上的对数后验概率为:

其中 -log p(f)和-log p(D|f)可以分别看作是模型f的编码长度和在该模型下数据集D的编码长度,也就是说我们不但要使得模型f可以编码数据集D,也要使模型f尽可能的简单。

归纳偏置

在机器学习中,很多算法会对学习的问题做一些假设,这些假设就称为归纳偏置(Inductive Bias)。比如在最近邻分类器中,我们会假设在特征空间内,一个小的局部区域中的大部分样本都属于同一类。在朴素贝叶斯分类器中,我们会假设每个特征的条件概率是相互独立的。

归纳偏置在贝叶斯学习中也成为先验(priors)。

大数定理

假设X1,X2,….是独立同分布的随机变量,记他们的均值为 $\mu$,方差为:$\sigma ^2$,则对于任意的正数$\varepsilon$,有

我们通常对数据进行抽样估计利用的则是大数定理思想。

中心极限定理

中心极限定理是研究独立随机变量和的极限分布为正态分布的命题。经过科学家长期的观察和总结,发现服从正态分布的随机现象往往是由独立(或弱相依)的随机变量产生的。

这类随机现象往往可视为独立随机变量之和

在什么条件下渐进于正态分布的问题。为使问题规范化,数学家们将问题归结为讨论规范和

有渐进分布N(0,1)的条件,并称有此结论的随机序列{x_n}服从中心极限定理。即:

独立同分布的中心极限定理和德莫佛-拉普拉斯中心极限定理参考:


【搜索与推荐Wiki】专注于搜索和推荐系统,尝试使用算法去更好的服务于用户,包括但不局限于机器学习,深度学习,强化学习,自然语言理解,知识图谱,还不定时分享技术,资料,思考等文章!