没有免费午餐定理是一组数学结果的统称,探讨普遍有效的算法所面临的局限,尤其涉及数学优化和机器学习。其核心结论带有前提条件:如果按照某种指定的对称权重,对一个限制足够少的问题集合上的性能取平均,那么算法在某些问题上的优势就会被其在其他问题上的劣势抵消。这些定理并不意味着所有算法在实际任务中的表现都一样。它们表明,算法能否取得更好的性能,取决于其假设与所遇问题的结构是否契合。
背景与发展
“没有免费午餐”这句话表达的是:获得优势就必须付出某种代价。在这些定理中,这种“代价”通常是关于问题类别的信息或假设,例如哪些函数是合理的、哪些模式在已观测数据之外仍然成立,或者搜索空间中的哪些区域更值得探索。
戴维·H. 沃尔珀特(David H. Wolpert)在1996年发表的研究中提出了监督学习的没有免费午餐结果。沃尔珀特与威廉·G. 麦克雷迪(William G. Macready)在1997年的论文《优化的没有免费午餐定理》(No Free Lunch Theorems for Optimization)中,给出了影响深远的优化领域结果。相关结果在假设、平均方式和性能定义上各不相同,因此,这个名称并非指一条无需附加条件便可适用的单一定理。
学习领域的结果关注的是:当目标关系不受限制时,已有观测能够让我们对未见情形作出什么判断。优化领域的结果关注的是:对未知目标函数的求值,能够揭示其在尚未考察位置上的哪些信息。两者都依赖同一个原则:如果没有任何限制将已观测值与未观测值联系起来,那么已经取得的成功未必能预示未来的成功。
有限优化定理
问题设定
一种标准表述考虑以下条件:
- 有限且非空的搜索空间 ,其中 。
- 有限且非空的可能目标值集合 。
- 所有函数 构成的集合 。
- 一个在 中查询点的算法,每次依据先前查询过的点及其观测值来选择下一个点。
- 固定的求值次数预算 ,且任何点都不会被查询超过一次。
目标函数按照 上的均匀分布选取。在这一分布下,每个点的值都从 中独立、均匀地选取。
对于算法 ,令
表示它观测到的目标值序列。算法对 的选择可以依赖于先前的观测。
对于任意两个不重复访问的确定性算法 和 ,以及任意序列 ,都有
因此,在对所有目标函数进行均匀平均时,所有这类算法观测到的值序列都具有相同的分布。
性能相等
假设性能由观测值的某个实值函数 来衡量。例如,可以用 次求值后找到的最优值,或是否达到指定的数值阈值来衡量。那么
这表示在上述问题分布下平均性能相等,而不是在每一个函数上的性能都相等。完整序列的分布相等,比单个期望值相等更强:它说明,仅由该序列决定的任何性能统计量都相等。
如果随机算法的内部随机性独立于目标函数,并且每一次实际产生的查询序列都满足不重复访问的条件,那么随机算法也适用。对其随机选择取平均,即可得到同样的等式。
定理为何成立
当算法观测到 个不同的输入—输出对后, 中恰好还剩下
个函数与这些观测一致。无论一个尚未查询的点是如何选出的,它取每个可能值的概率仍然相同。
因此,自适应选择无法利用有关未查询值的信息,因为假定的分布中,这些值与已有观测之间不存在任何关联。在这种平均方式下,复杂精巧的搜索规则与预先确定的查询顺序所得到的值序列具有相同的分布。
这一论证并不是说自适应方法通常没有用。它说的是:当模型使所有未观测值都独立于已观测值时,自适应方法就没有可以利用的信息。
学习的没有免费午餐结果
在监督学习中,算法利用训练数据,为观测样本之外的情形作出预测。核心问题是:样本是否提供了关于这些未见情形的信息。
考虑一个有限输入空间 和二元标签集合 。固定一组已观测输入 及其标签,并在所有与这些观测一致的目标函数 上赋予均匀分布。
对于任意未见过的输入 ,都有
因此,任何仅依据已观测样本作出预测的规则,在该输入上的期望误分类概率都是 。如果有 个等可能标签,那么在零一损失函数下,期望误差为 。
这是有限情形下学习的一个基本没有免费午餐结果。其他表述则通过对目标函数、样本或分布取平均来比较学习过程。它们的结论取决于究竟固定哪些量,以及对哪些量取平均。
归纳偏置
当观测能够约束未见输入上合理的输出行为时,学习便成为可能。使这种外推成为可能的假设称为归纳偏置。
这类假设包括:
- 相近的输入往往具有相似的输出。
- 目标函数可以用线性关系很好地近似。
- 图像中不同位置具有共同的相关结构。
- 相比任意其他模型,较简单或较平滑的模型更为合理。
这些假设可以体现在模型类别、先验分布或正则化惩罚项中。例如,线性回归将考虑范围限制为某种特定的函数形式,而平滑性假设则限制输出的变化速度。
没有免费午餐结果并不能确定哪种偏置才合适。它们解释了为什么必须对各种可能性施加某些限制或赋予非均匀权重,才能为超出已有观测的预测提供依据。
受限问题类别与置换对称性
对所有函数进行均匀平均,是标准优化定理成立的充分条件,但并不是这种相等关系成立的唯一情形。
一个重要的推广涉及对搜索空间的置换封闭的函数类。如果对于任意 和任意置换 ,都有
那么函数类 就具有这一性质。
对这样的函数类进行均匀平均时,不重复访问搜索所对应的没有免费午餐等式仍然成立。任意重新标记搜索位置都不会改变该函数类,因此,基于位置的结构无法系统性地使某个算法占优。
更一般地,如果函数上的某个概率分布在搜索空间的任意置换下都保持不变,那么它就具有相应的对称性。这种分布不一定是在所有函数上的均匀分布。
许多有用的问题类别并不具有这种对称性。将不同位置上的值进行置换,可能会破坏连续性、局部性、几何关系或凸性。这些恰恰是专门算法所利用的性质。
不过,没有免费午餐定理的某项假设不成立,并不意味着就能据此找出更优的算法。这仅仅意味着,该定理所保证的特定相等关系不再受到保证。
实际意义
优化方法利用结构
梯度下降和牛顿法等方法利用局部导数信息。它们的收敛性结果依赖于平滑性、曲率条件和合适的初始化等假设。
同样,凸优化中的理论保证依赖于一个受限的问题类别,其中局部性质与全局性质相互关联。这些保证与没有免费午餐定理并不矛盾:这些限制排除了标准等式所涵盖的任意函数。
在离散优化中,某种表示方式可能揭示有用的邻域关系或分解结构。当这些关系与目标值存在关联时,搜索方法便能从中受益;但这种关联属于额外的问题结构,而不是不受限制的搜索本身所带来的结果。
模型选择与评估
必须结合任务分布、数据生成过程和性能准则来评估学习算法的表现。交叉验证在对现有数据与未来情形之间的关系作出假设的基础上,估计预测性能。它并不能证明算法优于其他算法的结论适用于每一种可能的目标函数或未来分布。
同样,基准测试结果描述的是算法在所测试的任务集合和测试规程下的表现,未必能推广到任意不同的任务。没有免费午餐结果澄清了这种局限,但并不意味着基准比较毫无意义:如果基准中的任务能够代表预期应用,它就可以提供有用的信息。
先验信息改变比较结果
在贝叶斯推断中,非均匀先验赋予某些假设比其他假设更大的权重。此时,各算法的期望性能可能不同,因为用于取平均的分布不再对所有目标关系一视同仁。
同样的原则也适用于贝叶斯方法之外。受限的假设类、几何表示或关于数据依赖关系的假设,都会改变所考察的问题族。算法的优势需要结合这些选择来评价。
局限与常见误解
“所有算法都一样好。”
定理只在其指定的平均分布和允许条件下确立相等关系。在单个问题和具有结构的问题族上,算法之间可能存在巨大差异。
“没有算法能胜过随机搜索。”
在适当的问题类别上,算法经常优于不利用问题信息的搜索。在标准的有限情形表述中,不放回的均匀随机搜索与其他不重复访问算法在所有函数上的平均性能相同;但这并不意味着它在每一种实际分布下都同样有效。
“均匀平均不需要任何假设。”
这是一项实质性的建模选择。在所有有限函数上采用均匀分布,会使未观测值独立于已观测值,并消除实际算法旨在利用的关系。
“有限情形的结果自动适用于连续定义域。”
对于任意无限定义域,并不存在与“从所有函数中均匀选取”直接对应的做法。连续定义域上的结果需要各自的函数空间、概率测度,以及信息和性能的定义。
“重复访问某些点从来都无关紧要。”
不重复访问条件对标准优化等式十分重要。对确定性函数进行重复求值,可能消耗查询次数预算,却不能揭示新的数值。而在有噪声的情形下,重复测量可能提供有关不确定性的信息;那属于另一种模型。
“没有免费午餐定理否定了通用方法的可能性。”
一种方法可以在范围广泛的相关任务中发挥作用,而不必在所有数学上可能的问题中都最优。广泛适用与这组任务具有共同结构并不矛盾。
“该定理给出了计算复杂度的下界。”
标准结果讨论的是在问题实例上取平均后的信息与性能,而不是直接给出运行时间的界限。即使算法的目标值统计特征相同,它们在内存使用、计算开销或实现成本上仍可能不同。