NFL公式推导

朴灿烈づ我的快乐病毒、 2023-03-02 13:21 88阅读 0赞

【什么是NFL】

按照周志华老师说的

  1. 通过公式的推导，我们发现总误差竟然与学习算法无关，对于任意两个学习算法，
  2. 无论哪个算法更加”聪明“或者更加”笨拙"，它们的期望性能竟然相同。
  3. 这就是”没有免费的午餐“定理（No Free Lunch Theorem,简称NFL定理)

【NFL推导】

为简单起见，假设样本空间X和假设空间H都是离散的.令P(h|X,ζa) 代表算法ζa基于训练数据X产生假设h的概率,再令f代表我们希望学习的真实目标函数。ζa的“训练集外误差”，即ζa在训练集之外的所有样本上的误差为

20200729170504400.png

【相关解释】

20200729170757815.png：ζa在训练集之外的所有样本的误差

20200729170948842.png：假设函数h在训练集之外的所有样本上预测的错误率

20200729171038410.png：ζa基于训练数据X产生假设h的概率

对所有的f按均匀分布对误差求和：

2020072917064075.png1.0

  1.                              ![20200729171334214.png][]1.1
  3.                                 ![20200729171404421.png][]                            1.2
  5.                               ![20200729171426265.png][]                            1.3
  7.                            ![20200729171501209.png][]                               1.4

【相关解释】

步骤1.0到步骤1.1：我们是对f按均匀分布求和，在外面添加一个求和符号，然后我们这里可以整理下，将求和公式下面的符号与公式里面的符号相同的放在一起，然后就可以化简成1.1所示的形式。

20200729171334214.png

接下来就是从1.1到1.2：

20200729172048402.png

那么就可以得到如下所示的结果：

20200729172147235.png

然后我们在整理下就可以得到1.3到1.4：为什么这里会是1呢

20200729172308469.png

因为我们加上求和公式就是相当于求ζa基于训练数据X产生假设h的概率的和，就相当于我们求一个事件发生的全部概率之和是不是为1呢，显然为1.

最后我们整理下公式就得到如下所示：

20200729172600430.png

【参考资料】

1.NFL定理及前提

2.绪论

发表评论

表情：
评论列表 （有 0 条评论，88人围观）

还没有评论，来说两句吧...

相关阅读

    相关 CNN公式推导

    CNN公式推导 1 前言 在看此blog之前，请确保已经看懂我的前两篇blog【深度学习笔记1(卷积神经网络)】和【BP算法与公式推导】。并且已经看过文献\[1\]

    男娘i男娘i/ 0 赞/ 465 阅读

    相关 BP算法与公式推导

    BP(backpropgationalgorithm )：后向传导算法，顾名思义就是从神经网络的输出(顶层)到输入(底层)进行求解。那么求解什么呢，求解的就是神经网络中的参数的

    傷城~傷城~/ 0 赞/ 76 阅读

    相关 ***汉诺塔公式推导

    问题背景：有A，B和C三根柱子，开始时n个大小互异的圆盘从小到大叠放在A柱上，现要将所有圆盘从A移到C，在移动过程中始终保持小盘在大盘之上。求移动盘子次数的最小值。 变量设

    川长思鸟来川长思鸟来/ 0 赞/ 425 阅读

    相关 JMP地址公式推导

    ![20130618101300359][] 以上有个问题：为什么同样的汇编指令JMP 12345678却对应不同的机器码呢？ 首先，机器码E9表明这是一个近跳转（Near

    青旅半醒青旅半醒/ 0 赞/ 546 阅读