NFL定理
No Free Lunch Theorem:天下没有免费的午餐
我们计算一个学习算法\(\mathcal{L}_a\)的“训练集外误差”,有 \[
\begin{aligned}
E_{ote}(\mathcal{L}_a|X,f)=\sum_{h}\sum_{x\in\mathcal{X}-X}P(x)\mathbb{I}(h(x)\ne
f(x))P(h|X,\mathcal{L}_a)
\end{aligned}
\]
如果对于所有真实目标函数\(f\)求和,则有 \[
\begin{aligned}
\sum_f E_{ote}(\mathcal{L}_a|X,f)&=\sum_f\sum_h\sum_{x\in
\mathcal{X}-X}P(x)\mathbb{I}(h(x)\ne f(x))P(h|X,\mathcal{L}_a)\\
&=\sum_{x\in\mathcal{X}-X}P(x)\sum_hP(h|X,\mathcal{L}_a)\sum_f\mathbb{I}(h(x)\ne
f(x))\\
&=\sum_{x\in
\mathcal{X}-X}P(x)\sum_hP(h|X,\mathcal{L}_a)\frac{1}{2}2^{|\mathcal{X}|}\\
&=\frac{1}{2}2^{|\mathcal{X}|}\sum_{x\in
\mathcal{X}-X}P(x)\sum_hP(h|X,\mathcal{L}_a)\\
&=\frac{1}{2}2^{|\mathcal{X}|}\sum_{x\in \mathcal{X}-X}P(x)\\
\end{aligned}
\]
我们可以看到,总误差与学习算法无关,也就是说,对于任意两个学习算法\(\mathcal{L}_a\),\(\mathcal{L}_b\),无论看上去\(\mathcal{L}_a\)多复杂,多聪明,在期望的意义下,他们的性能是相同的。(也就是说,随便瞎猜和复杂推导一样,不学了
(*`皿´*)ノ )
尝试证明AUC计算公式