终极算法 第三章 符号学派:休谟的归纳问题

终极算法 第三章 摘要

理性主义者认为,感官会欺骗人,而逻辑推理是通往知识的唯一可靠的道路。经验主义者认为所有推理都是不可靠的,知识必须来源于观察及实验。评论员、律师、数学家是理性主义者,记者、医生、科学家是经验主义者。《女作家与谋杀案》是关于犯罪的电视剧,属于理性主义,《犯罪现场调查》则属于经验主义。在计算机科学领域,理论家和知识工程师属于 理性主义者,黑客和计算机学习者属于经验主义者

大卫·休谟是最伟大的经验主义者,以及有史以来最伟大、以英语为母语的哲学家。诸如亚当·斯密、查尔斯·达尔文之类的思想家都深受其影响。你也可以说他是符号学派的守护神。休谟借用了洛克开创的经验主义思想,并提出一个问题,这个问题在所有领域的知识中就像一把达摩克利斯之剑,从最琐碎的领域到最先进的领域,都是一个时刻存在的问题:在概括我们见过的东西以及没见过的东西时,怎样才能做到合理?从某种意义上说,每种学习算法都在尝试回答这个问题。

自休谟提出归纳问题,哲学家就已经对此进行辩论,但还没有人能给出一个满意的答案。伯特兰·罗素喜欢用“归纳主义者火鸡”这个故事来阐述这个问题。故事的主人公是一只火鸡,它来到农场的第一个早晨,主人在早上9点喂它们,但作为实实在在的归纳法优越论者,它不想过早下结论:主人每天都9点喂它们。首先它在不同情况下观察了很多天,收集了许多观察数据。主人连续多天都是9点喂它们,最终它得出结论,认为主人每天早上9点喂火鸡,那么主人一直会在早上9点给它喂食。接下来是平安夜那天的早晨,主人没有喂它,因为它被宰了。如果我们只是假设未来和昨天一样,那么会怎样呢?这当然是一个有风险的假设。另外,没有这样的假设,所有知识将不复存在,生活也是如此。虽然有很多不确定性,但我们还是宁可活下来。这属于机器学习问题:将某结果推广到我们没有见过的事件中。

天下没有免费的午餐 定理

休谟提出爆炸性问题之后的250年,大卫·沃尔珀特(David Wolpert)赋予了这个问题优雅的数学形式。沃尔珀特原来是一名物理学家,后来成为机器学习者。他的研究结果被人们称为“天下没有免费的午餐”定理,规定“怎样才算是好的学习算法”。这个规定要求很低:没有哪个学习算法可以比得上随意猜测。而且如果真的是那样,为什么这个世界——从垃圾邮件过滤(随时都在进行)到 自动驾驶汽车——到处都是非常成功的学习算法呢?

同时,“天下没有免费的午餐”这个实际的结论表明,不靠知识进行学习,这样的事不存在。只有数字也不够。从零开始只会让你一无所获。机器学习就像知识泵,我们可以用它来 从数据中提取大量的知识,但首先我们得先对泵进行预设。

数学家认为机器学习这个问题是一个不适定问题(ill–posed problem):这个问题没有唯一解。下面是一个简单的不适定问题:哪两个数相加的得数是1000?假设这两个数都是正 数,答案就有500种……1和999,2和998等等。解决不适定问题的唯一办法就是引入附加假 设。如果我告诉你,第二个数是第一个数的三倍,那么答案就是250和750。

对知识泵进行预设

在《自然哲学的数学原理》一书及三大运动定律中,牛顿阐述了推理的四条法则。虽然 这些法则没有那些物理定律那么著名,但可以说很重要。其中第三条是关键法则,我们可以 这样表述:

我们见过的所有真实的东西,在宇宙中也是真实的。

可以毫不夸张地说,这句听起来无伤大雅的话就是牛顿革命以及现代科学的核心。牛顿法则是机器学习的第一个不成文规则。我们归纳自己能力范围内、应用最广泛的规 则,只有在数据的迫使下,才缩小规则的应用范围。乍一看,这看起来可能过于自信甚至近 乎荒谬,但这种做法已经为科学服务了300余年。当然也可以想象出一个变化无常的宇宙,在那里牛顿法则不起作用,但那并不是我们的宇宙。

首先做有条件的假设,如果这样无法解释数据,再放松假设的条件,这就是典型的机器学习。这个过程通常由算法自行进行,不需要你的帮助。首先,算法会尝试所有单一因素, 然后尝试所有两个因素的组合,之后就是所有三个因素的组合等。但现在我们遇到一个问题:合取概念太多,没有足够的时间对其逐个尝试。

如何征服世界

夏德·米哈尔斯基(Ryszard Michalski),他是波兰的一位计算机科学家。米哈尔斯基的故乡——卡尔鲁兹之前曾属于波兰、俄罗斯、德国以及乌 克兰,这让米哈尔斯基比多数人更能理解合取概念。1970年移民美国之后,他和汤姆·米切 尔、杰米·卡博内尔一起创立了机器学习的符号学派。他个性傲慢,如果你在一场机器学习 会议中做报告,那么很有可能他会举手指出你只是重新发现了他之前的旧观点。

在无知与幻觉之间

规则集的力量是一把双刃剑。从正面看,你知道自己总能找到和数据完美匹配的规则。 但你还没来得及开始觉得走运,就意识到自己很有可能会找到一个毫无意义的规则。记住“天下没有免费的午餐”:没有知识,你就无法进行学习。假设某概念能通过规则集来定 义,相当于什么也没有假设。

每当算法在数据中找到现实世界中不存在的模型时,我们说 它与数据过于拟合。过拟合问题是机器学习中的中心问题。在所有主题中,关于过拟合问题的论文最多。每个强大的学习算法,无论是符号学算法、联结学算法,或者其他别的学习算法,都不得不担忧幻觉模式这个问题。避免幻觉模式唯一安全的方法,就是严格限制算法学 习的内容,例如要求学习内容是一个简短的合取概念。很遗憾,这种做法就像把孩子和洗澡 水一起倒掉一样,会让学习算法无法看到多数真实的模型,这些模型在数据中是可见的。因此,好的学习算法永远在无知与幻觉的夹缝中行走。

学习算法特别容易过拟合,因为它们拥有从数据中发现模型、近乎无限制的能力。人类发现一个模型所用的时间,计算机可以找到数百万个。在机器学习中,计算机最大的优势(处理大量数据以及不知疲倦不断重复同样步骤的能力)也是它的劣质所在。如果你做的研 究够多,然后能有所发现,也很不错《圣经密码》(1998年的畅销书)声称如果你以固定间距跳过某些字母,然后把点中的字母拼起来,就会发现《圣经》对未来的预言。遗憾的是,保证你能从任何足够长的文本中找到“预言”,有很多方法。怀疑论者会说,他们在《白 鲸记》和最高法院的裁决中找到了预言,除此之外,还提到罗斯威尔,以及《圣经·创世 纪》中的不明飞行物。约翰·冯·诺依曼(计算机科学的奠基之父之一)曾说过一句众所周知的话:“用4个参数,我能拟合一头大象;用5个参数,我可以让它的鼻子扭动起来。”当今我们通常会学习拥有数百万参数的模型,这些参数足以让世界上的每头大象都扭动鼻子。甚至 曾有人说过,数据挖掘意味着“折磨数据,直到数据妥协”。

当算法需要做的事情和输入的数据一样呈指数级增长时,计算机科学家就将这个现象称为组合爆炸。

你能信任的准确度

你可以利用自己拥有的数据,将其分成一个训练集和一个测试集,然后前者交给学习算法,把后者隐藏起来不让学习算法发现,用来验证其准确度。留存数据的准确度就是机器学习中的“黄金标准”。你可以写一篇 关于你发明的伟大的新型学习算法的文章,但如果你的算法的留存数据不如之前的算法的留存数据准确,那么这篇文章也没有什么出版价值。

对于机器学习来说,对不可见数据的测试是必不可少的,因为这是判断学习算法是否过拟合的唯一方法。

你可以估算一种学习算法的偏差和方差,方法就是在掌握训练集的随机变量之后,对算 法的预测进行对比。如果算法一直出错,那么问题就出在偏差上,而你需要一个更为灵活的 学习算法(或者只和原来的不一样即可)。如果出现的错误无模式可循,问题就出在方差上,而你要么尝试一种不那么灵活的学习算法,要么获取更多的数据。大多数学习算法都有 一个“把手”,通过旋转“把手”,你可以调节这些算法的灵活度。

归纳是逆向的演绎

问题的关键在于认识到,归纳仅仅是逆向演绎,就和减法是加法的逆运算,或者积分是 微分的逆运算一样。这个观点由威廉姆·斯坦利·杰文斯于19世纪末首次提出。史蒂夫·马格尔 顿和雷·邦坦(一个英国—澳大利亚研究组)在此基础上于1988年设计出第一个实用算法。

掌握治愈癌症的方法

逆向演绎是在生物学中发现新知识的重要方法,这也是治愈癌症要迈出的 第一步。根据中心法则的观点,在活细胞中进行的任何活动都最终由细胞的基因控制,通过发起蛋白质的合成来完成。一个细胞就像一台微型计算机,而DNA就是计算机运行的程序:改变DNA,皮肤细胞就会变成神经元细胞,或者小鼠细胞会变成人类细胞。在计算机的程序 中,所有的故障都是由程序员引起的。但在细胞中,故障可自行产生,比如当辐射或者细胞复制误差将某基因变成另外一个基因时,当基因偶然被复制两次时……很多时候,变异会导致细胞悄无声息地死去,但有时候细胞开始生长,然后不可控制地分裂,这样癌细胞就产生了。

20问游戏

逆向演绎的另外一个局限性就在于,它涉及很密集的计算,因此很难扩展到海量数据集中。因为这些原因,符号学家选择的算法是决策树归纳。

你要么是共和党人,要么是民主党人,要么是独立人士。你无法选择其中的两种或三种,或者一个都不选。拥有这个属性的概念组被称为类集,而预测类集的算法称为分类器。单个概念隐含两类定义:概念本身及其反面(例如,垃圾邮件和非垃圾邮 件)。分类器是机器学习最为普遍的方式。

决策树可应用在许多不同的领域。在机器学习领域,决策树源于心理学方面的知识。厄尔·亨特及其同事于20世纪60年代利用了决策树,目的是为了模拟人类如何掌握新的概念。另外,亨特其中的一个研究生罗斯·昆兰后来尝试把决策树用于象棋中。他最初的目的是为了从棋盘占位预测王车大战骑士的后果。据调查,决策树已经由一开始这些微不足道的用途,发展成为机器学习算法中应用最为广泛的方法。要知道原因并不困难:决策树易于理解,可以快速掌握,而且通常无须太多调整就可以做到准确无误。昆兰是符号学派中最卓越的研究者。作为一个沉稳、务实的澳大利亚人,因为对决策树年复一年不断地改进,并写了 和决策树有关、逻辑清晰的论文,使决策树成为分类活动中的“黄金标准”。

符号学派

符号学派的核心理念就是,所有和智力相关的工作都可以归结为对符号的操纵。数学家在解方程时,会移动符号,然后根据预先定义的规则,用其他符号来代替这些符号。逻辑学 家进行推论时也是同样的道理。符号学机器学习者和许多其他计算机科学家、心理学家、哲学家一样,都相信符号操纵的力量。

符号主义机器学习是人工智能知识工程学派的一个分支。20世纪70年代,所谓的基于知识的系统取得卓越成绩,而到了80年代,它们迅速传播,后来却消失了。它们消失的主要原因是人人逃避的知识习得瓶颈:从专家身上提取知识,然后将其编码成为规则,这样做难度太大、太费力、易出故障,会引起很多问题。让计算机自行学习,比如通过查看过往患者症状及其相应疗效的数据库,就可以进行疾病诊断,比无数次地找医生要容易很多。

注:摘自原书中文版(百度云下载PDF) 第三章