NFL公式推导
【什么是NFL】
按照周志华老师说的
通过公式的推导,我们发现总误差竟然与学习算法无关,对于任意两个学习算法,
无论哪个算法更加”聪明“或者更加”笨拙",它们的期望性能竟然相同。
这就是”没有免费的午餐“定理(No Free Lunch Theorem,简称NFL定理)
【NFL推导】
为简单起见,假设样本空间X和假设空间H都是离散的.令P(h|X,ζa) 代表算法ζa基于训练数据X产生假设h的概率,再令f代表我们希望学习的真实目标函数。ζa的“训练集外误差”,即ζa在训练集之外的所有样本上的误差为
【相关解释】
:ζa在训练集之外的所有样本的误差
:假设函数h在训练集之外的所有样本上预测的错误率
:ζa基于训练数据X产生假设h的概率
对所有的f按均匀分布对误差求和:
1.0
![20200729171334214.png][]1.1
![20200729171404421.png][] 1.2
![20200729171426265.png][] 1.3
![20200729171501209.png][] 1.4
【相关解释】
步骤1.0到步骤1.1:我们是对f按均匀分布求和,在外面添加一个求和符号,然后我们这里可以整理下,将求和公式下面的符号与公式里面的符号相同的放在一起,然后就可以化简成1.1所示的形式。
接下来就是从1.1到1.2:
那么就可以得到如下所示的结果:
然后我们在整理下就可以得到1.3到1.4:为什么这里会是1呢
因为我们加上求和公式就是相当于求ζa基于训练数据X产生假设h的概率的和,就相当于我们求一个事件发生的全部概率之和是不是为1呢,显然为1.
最后我们整理下公式就得到如下所示:
【参考资料】
1.NFL定理及前提
2.绪论
还没有评论,来说两句吧...