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计算公式

排序损失$\mathcal{l}_{rank}$被定义为

$$ \begin{aligned} \mathcal{l}{rank} = \frac{1}{m^+m^-}\sum{x^+\in D^+}\sum_{x^-\in D^-}\left(\mathbb{I}(f(x^+)<f(x^-)) + \frac{1}{2}\mathbb{I}(f(x^+)=f(x^-))\right) \end{aligned} $$

对于一个ROC图，我们有如下关系： $$ \text{AUC}=1-\mathcal{l}_{rank} $$

（代入理想模型和随机模型，发现是对的。。）