2.8.1 PAC(可能近似正确 Probably Approximately Correct)

  • 降低对学习算法的期望，只要求学习算法可以以一定的概率学习到一个近似正确的假设，即PAC学习
  • 一个PAC 可学习（PAC-Learnable）的算法是指该学习算法能够在多项式时间内从合理数量的训练数据中学习到一个近似正确的𝑓(𝒙)．
  • 要达到相同的泛化能力，越复杂的模型需要的样本数量越多．为了提高模型的泛化能力，通常需要正则化（Regularization）来限制模
    型复杂度。

2.8.2 没有免费午餐定理理（No Free Lunch Theorem，NFL）

  • ．没有免费午餐定理证明：对于基于迭代的最优化算法，不存在某种算法对所有问题（有限的搜索空间内）都有效．如果一个算法
    对某些问题有效，那么它一定在另外一些问题上比纯随机搜索算法更差．也就是说，不能脱离具体问题来谈论算法的优劣，任何算法都有局限性．必须要“具体问题具体分析”。

2.8.3 奥卡姆剃刀原理（Occam’s Razor）

  • 简单的模型泛化能力更好．如果有两个性能相近的模型，我们应该选择更简单的模型．因此，在机器学习的学习准则上，我们经常
    会引入参数正则化来限制模型能力，避免过拟合.

2.8.4 丑小鸭定理（Ugly Duckling Theorem）

  • “丑小鸭与白天鹅之间的区别和两只白天鹅之间的区别一样大”．
  • 因为世界上不存在相似性的客观标准，一切相似性的标准都是主观的．如果从体型大小或外貌的角度来看，丑小鸭和白天鹅的区别大于两只白天鹅的区别；但是如果从基因的角度来看，丑小鸭与它父母的差别要小于它父母和其他白天鹅之间的差别．

2.8.5 归纳偏置（Inductive Bias）

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