NFL公式推导

朴灿烈づ我的快乐病毒、 2023-03-02 13:21 87阅读 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
  2. ![20200729171404421.png][] 1.2
  3. ![20200729171426265.png][] 1.3
  4. ![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 条评论,87人围观)

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

相关阅读

    相关 CNN公式推导

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

    相关 BP算法与公式推导

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

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

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

    相关 JMP地址公式推导

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