机器学习-没有免费的午餐（NFL）

置顶 | 发表于 2025-12-18 更新于 2025-12-19 分类于机器学习阅读次数：
本文字数： 650 阅读时长 ≈ 2 分钟

没有免费的午餐定理告诉我们，任何事都要放到具体的环境中取讨论，脱离了实际去讨论问题是没有意义的。实践是检验一切真理的标准。

假设样本空间和假设空间都是离散的。令代表算法经过训练样本产生假设的概率，在令表示我们希望学习到的真实目标函数。
的训练集外误差为：

符号	含义
	期望总误差（Expected Total Error），衡量分类器在未见样本上的平均错误率
	某个特定的学习算法或学习策略（如决策树、SVM 等）
	训练集（已观测数据）
	真实标签函数（ground truth），即是输入的真实类别
	整个输入空间（所有可能的输入样本集合）
	未见样本集，即不在训练集中的输入点（测试/泛化样本）
	一个假设（hypothsis），即由学习算法生成的一个分类器（如某个决策规则）
	输入的先验概率分布（即出现的概率）
	指示函数（Indicator Function）：当时取值为 1（分类错误）；否则为 0（正确）
	在给定训练集和学习算法下，产生假设的概率 → 表示该学习算法输出的可能性

对于二分类问题，且真实目标函数可以是任何函数,函数空间为。对所有可能的按照均匀分布对误差求和

即总误差与学习算法无关，也就是说对于任意两个算法都有

这就是“没有免费的午餐”定理。这个定理基于均匀分布，然而显式中的问题并不总是均匀分布的。这提示我们脱离了实际问题的理论是毫无意义的，任何高谈阔论都要以实践为基础。