NFL定理#
No Free Lunch Theorem：天下没有免费的午餐
我们计算一个学习算法La的“训练集外误差”，有
Eote(La∣X,f)=h∑x∈X−X∑P(x)I(h(x)=f(x))P(h∣X,La)如果对于所有真实目标函数f求和，则有
f∑Eote(La∣X,f)=f∑h∑x∈X−X∑P(x)I(h(x)=f(x))P(h∣X,La)=x∈X−X∑P(x)h∑P(h∣X,La)f∑I(h(x)=f(x))=x∈X−X∑P(x)h∑P(h∣X,La)212∣X∣=212∣X∣x∈X−X∑P(x)h∑P(h∣X,La)=212∣X∣x∈X−X∑P(x)我们可以看到，总误差与学习算法无关，也就是说，对于任意两个学习算法La，Lb，无论看上去La多复杂，多聪明，在期望的意义下，他们的性能是相同的。（也就是说，随便瞎猜和复杂推导一样，不学了 (*｀皿´*)ﾉ ）
尝试证明AUC计算公式#
排序损失lrank被定义为
lrank=m+m−1x+∈D+∑x−∈D−∑(I(f(x+)<f(x−))+21I(f(x+)=f(x−)))对于一个ROC图，我们有如下关系：
AUC=1−lrank（代入理想模型和随机模型，发现是对的。。）
