1.1 基本概念

每个西瓜都可以在这个空间中找到自己的坐标位置 - 每个点对应一个特征向量 (feature vector)。

学得模型的过程：这个过程通过执行某个学习算法来完成。学习过程就是为了找出或逼近真相。模型可看作学习算法在给定数据和参数空间上的实例化。

机器学习的目标是使学得的模型能很好地适用于"新样本" - 泛化 (generalization) 能力。

尽管训练集通常只是整个样本空间中一个很小的采样集，我们仍希望它能很好地反映出样本空间的特性，否则就很难期望在训练集上学得的模型能在整个样本空间上都工作得很好。

假设样本空间中全体样本服从一个"分布"(distribution)，每个样本都可以独立地从这个分布中采样获得，即"独立同分布"(independent and identically distributed，i.i.d.)

通过学习得到的模型对应了假设空间中的一个假设。应该采用哪一个模型(或假设)？

1.2 归纳偏好

机器学习算法在学习过程中对某种类型的假设的偏好，称为"归纳偏好"(inductivebias)

任何一个有效的机器学习算法必有其归纳偏好

- 1.否则，如果没有偏好，模型时而告诉我们它是好的、时而告诉我们它是不好的，这样的学习结果显然没有意义。

- 2.学习算法必须有其偏好，才能产出它认为"正确"的模型。

- 3.算法的归纳偏好是否与问题本身匹配，大多数时候直接决定了算法能否取得好的性能。

NFL定理是让我们清楚地认识到，脱离具体问题，空泛地谈论"什么学习算法更好"毫无意义，要比较算法的相对优劣，必须针对具体的实际问题。在某些问题上表现好的学习算法，在另一些问题上却可能不尽如人意。

1.3 NP问题

然而必须认识到，过拟合是无法彻底避免的，我们所能做的只是"缓解"​，或者说减小其风险。

- P与NP是计算机科学理论的核心概念

P问题 (Polynomial Time) 指可以在多项式时间内由确定性图灵机求解的问题：计算机科学中"实际可解"。

NP问题 (Nondeterministic Polynomial Time) 指可以在多项式时间内由非确定性图灵机验证解的正确性：若存在解，则验证解的正确性很容易，但找到解本身极难。

机器学习中的模型训练 (使经验误差最小化) 通常被视为NP难问题 (寻找全局最优解比验证最优解困难很多)。

若找到一种学习算法能彻底避免过拟合，意味着此算法能在多项式时间内找到经验误差最小化的最优解，即能找到泛化能力最优的模型。但现实中普遍坚信这是NP问题(很难找到最优解)，过拟合无法被彻底消除，只能通过正则化、交叉验证等方法缓解风险。

这一理论揭示了机器学习的根本矛盾：理想的最优解(零过拟合)与计算最优解的复杂性之间的冲突与挑战 - 任何学习算法都必须在"理想的最优解"和其自身的"泛化能力"之间权衡。