1. 没有免费午餐定理

没有免费午餐(No Free Lunch,NFL)定理表明没有一个学习算法可以在任何领域总是产生最准确的学习器。不管采用何种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。

平常所说的一个学习算法比另一个算法更“优越”，效果更好，只是针对特定的问题、特定的先验信息、数据的分布、训练样本的数目、代价或奖励函数等。

2. 归纳偏置

归纳偏置(inductive bias)是指任何一个有效的机器学习算法必有其“偏好”，否则算法无法处理对于假设空间中看似在训练集上“等效”(如在数据集上具有相同的分类准确率)的假设，从而无法产生确定的学习结果。

3. 奥卡姆剃刀

奥卡姆剃刀（Occam’s Razor）是自然学科研究中最基本的原则之一。

原理：“如无必要，勿增实体”（Entities must not be multiplied unnecessarily）
应用于机器学习：能够拟合数据的模型中最简单的是最好的。

奥卡姆剃刀提供了一种引导机器学习算法克服归纳偏置的一般性原则。衡量模型的“简单”程度这个问题本身并不简单。一种参考是模型复杂度低，即对于一个模型具有更少的假设空间，对于一个假设具有更少的参数量。

4. 采样偏差

在训练机器学习模型时，会从训练集中直接划分或采样出一个验证集，通过验证集调整超参数，并通过验证精度选择最优子模型。

采样偏差（sampling bias）是指采样获得的验证集本身跟测试集差别比较大，即两者的数据分布存在偏差；则在验证集上表现较好的模型在测试集上不一定表现也好，从而导致模型学习的结果也会产生偏差。

在实践中应尽可能保持训练环境和测试环境接近，而训练集和测试集的数据分布通常是不匹配的，因此需要合理地调整验证集的采样策略，使得验证集和测试集的分布更一致一些。

⚪ 基于对抗学习和重要性采样的验证集划分策略

按照对抗学习的思想训练一个二分类判别器$D(x)$，用于区分训练集(标签为$0$)和测试集(标签为$1$)：

\[- \Bbb{E}_{x \text{~} P_{train}(x)}[\log (1-D(x))] - \Bbb{E}_{x \text{~} P_{test}(x)}[\log D(x)]\]

为防止过拟合，即判别器彻底地把训练集和测试集分开，通常判别器选择比较简单的模型，如逻辑回归。根据对抗学习理论，上式的最优解是：

\[D(x) = \frac{P_{test}(x)}{P_{train}(x)+P_{test}(x)}\]

模型评估是在测试集上进行的。对于给定目标$f(x)$，计算：

\[\Bbb{E}_{x \text{~} P_{test}(x)}[f(x)] = \int P_{test}(x) f(x)dx\]

根据重要性采样，在测试集上的采样评估可以通过在训练集上实现：

\[\begin{aligned} & \int P_{test}(x) f(x)dx = \int P_{train}(x)\frac{P_{test}(x)}{P_{train}(x)} f(x)dx \\& = \Bbb{E}_{x \text{~} P_{train}(x)}[\frac{P_{test}(x)}{P_{train}(x)} f(x)] = \Bbb{E}_{x \text{~} P_{train}(x)}[\frac{D(x)}{1-D(x)} f(x)] \end{aligned}\]

记权重$w(x)=\frac{D(x)}{1-D(x)}$用于衡量样本跟测试集的相似程度，则上式表示从训练集中采样，为跟测试集相近的样本赋予更高的权重。至此可以构造两种验证集划分策略：

按照随机打乱的方式划分训练集和验证集，并为每个样本设置权重$w(x)=\frac{D(x)}{1-D(x)}$；
计算训练集所有样本$\{x_1,...,x_N\}$的权重$\{w_1,...,w_N\}$，并将权重归一化为概率$p_i=\frac{w_i}{\sum_j w_j}$；按照概率$\{p_1,...,p_N\}$从训练集中有放回地独立重复采样一个验证集。

5. 数据窥探

要防止数据窥探（data snooping），即测试数据不能以任何形式泄漏到训练过程中。

在实际应用中很难做到完全不窥探数据。比如某个研究领域使用某基准benchmarks，前人已发表论文中提到的方法在解决这个问题时，已经间接泄露了一些数据信息；当你在前人的基础上开发出新的模型，实际上已经应用了泄漏的数据，增加了过拟合的风险。

一种常用的防止数据窥探的方法是不人为的引入先验知识。比如解决某一问题时，先不观察具体的数据集，而是先提出一些可能的解决方法和应用技巧，再将其应用到数据上；而不是通过数据来选择模型。

6. 维度灾难

维度灾难（the curse of dimensionality）指出，数据在高维空间中的分布具有稀疏性，从而产生有悖于低维空间（如三维空间）常识的现象。

例1. 考虑$k$维空间中边长为$1$的超立方体内接超球体，超球体半径为$\frac{1}{2}$，其体积（测度）为$\text{const} \cdot (\frac{1}{2})^k $，当$k→∞$时，超球体体积为$0$，即高维空间中边长为$1$的超立方体内的数据集中分布在立方体角落。
例2. 考虑$k$维空间中半径为$r$和$r+ε$的同心超球体，其中$ε$是一个很小的数。两个超球体的体积分别为$\text{const} \cdot (r)^k $和$\text{const} \cdot (r+ε)^k $，其体积之比为$\frac{(r)^k}{(r+ε)^k}=\frac{1}{(1+\frac{ε}{r})^k}$，当$k→∞$时体积之比趋近于$0$。即高维空间中的超球体内数据集中分布在表面上。