没有免费午餐定理No Free Lunch Theorem | 您所在的位置:网站首页 › 天下没有免费的午餐翻译 › 没有免费午餐定理No Free Lunch Theorem |
不得不说,网上博客千千万,在技术方面,我承认这些博客的重要性。然而,只要和机器学习理论挂钩,似乎都讲得不清不楚,大家都是各自地抄,抄书籍,抄论文,抄别人的博客或者直接翻译,或者讲故事一样描述,几乎没什么太深入的理解,给人的感觉是“哎?似乎是这样,我好像有一点懂了”,然后就没了,其实看这样的博客简直就是在浪费时间,凡是不能一次性地搞懂一点内容,都是扯犊子。总之,看了网上的关于机器学习博客的文章,我感觉很不理解,很困惑,很迷茫。所以我就推导了一遍周志华书籍《机器学习》没有免费午餐定理(No Free Lunch Theorem)的一个简单证明过程。 一、讲故事一样的描述讲故事虽然并不严格,然而它还是有必要用这样的思维去描述这个定理。其用途是给别人普及,同时也方便自己记忆。 那么,如何像讲故事一样地描述没有免费午餐定理呢?最直观的,我们吃午饭都是要付钱的,哪怕有人请客,那请你吃饭的人也帮你付了钱。但这个似乎跟机器学习并没有半吊子关系。 在机器学习领域里面,有一个雷打不动的定理,即没有免费午餐定理。它被描述为:没有一个学习算法可以在所有情况下总是产生最准确的模型。也就是说,不管采用何种学习算法,至少存在一个模型,比随机猜测算法得到的模型要差。这个定理的最重要意义是,在脱离实际意义情况下,空泛地谈论哪种算法好毫无意义,要谈论算法优劣必须针对具体学习问题。所以,我们在比较学习算法的时候,需要针对具体的学习问题。针对这个问题,学习算法a可能更好;而针对那个问题,学习算法b可能更好。 周志华在他的机器学习书籍里面说到,实际上在很多时候,我们只关注自己正在试图去解决的问题并它找到一个方案,而至于这个方案在其他问题上是否为好方案并不关心。例如,为了快速从A地到达B地,如果我们正考虑的A地是南京鼓楼,B地是南京新街口,那么骑自行车是一个很好的方案;如果A地是南京鼓楼,B地是北京故宫,那么骑自行车显然是一个极其糟糕的方案,但我们对此并不关心。 总之一句话,谈论算法的相对好坏,要针对具体的学习问题。而当你的算法在某个问题取得较好的性能时,那得注意了,请你说说你为这这么好的性能付出了什么代价? 二、相对严格的描述及其证明这个定理之所以雷打不动,是因为它是经过严格的数学证明的。下面就顺着周志华机器学习书籍里面的内容,推导一遍其证明过程。 首先,我们来看看原文,如下。 看着这些公式,确实头都大了。不过不用怕,这充其量也就是高中数学的知识。求和公式、条件概率、均匀分布,这些不都很熟悉吗?我们高中就学过。只要我们把它展开,你就明白为什么会是这样的计算过程了。 先从公式(1.1)开始理解吧。 先看左边, 机器学习算法 所以, 再看右边。有两个求和符号,第一个求和符号是遍历机器学习算法 现在再来看看公式(1.2)的计算过程。在开始之前,先说一下目标函数 所以,要求得机器学习算法 那么,现在可以正式地推导这个过程了。具体如下 看了一长串的计算过程之后,来个直观的例子,那是最舒服的。具体如下: 给定 给定训练集 对于机器学习算法 而机器学习算法 利用得出结论之前的公式(即公式(1.2)包含了三个求和符号的式子)计算,得到 同理, 对于机器学习算法 而机器学习算法 利用得出结论之前的公式(即公式(1.2)包含了三个求和符号的式子)计算,得到 经过计算发现,两个学习算法的训练集外误差竟是一样的。 也许有人要站出来问了,你两个算法的假设空间太特殊了,万一这个例子是巧合呢? 那好,现在令 好,现在令机器学习算法 此时,这两个机器学习算法对应的指示函数表分别为 它们所对应的训练集外误差分别为 这时发现它们的计算结果依然是4(通过数指示函数表中“1”的个数,然后乘以 1.(强推)浙大2021-机器学习_哔哩哔哩_bilibili 2.浙江大学-研究生机器学习课程-_哔哩哔哩_bilibili 3.参考资料第2条 五、结束语码字之余,难免疏漏,欢迎点评指出改正。同时,码字不易,不喜勿喷,文明交流。毕竟是个人理解,所以写的东西很有可能有所疏漏,但是希望大家能够文明交流。爱与尊重。 花费两天找了一些资料理解这个没有免费午餐定理,再花费一天时间把我所理解的内容全部写在博客之上。确实,在理解和作笔记的过程,都是相当艰苦的。不过有了一定的理解之后,确实让人恍然大悟,感觉收获良多。一大堆写得很复杂的公式难以让人理解,实际上是由于它的跳跃性真的太大了。如果能够缩短这个跳跃间距,那么学习便不成问题了。可惜的是,论文没有那么多的篇幅给你一步一步地计算。 参考资料1.周志华,机器学习 2.Ho, Yu-Chi, and David L. Pepyne. "Simple explanation of the no-free-lunch theorem and its implications." Journal of optimization theory and applications 115.3 (2002): 549-570. |
CopyRight 2018-2019 实验室设备网 版权所有 |