『终极算法』摘抄笔记-符号学派

『终极算法』摘抄笔记-符号学派

理性主义和经验主义

理性主义者认为,感官会欺骗人,而逻辑推理是通往知识的唯一可靠的道路。经验主义者认为所有推理都是不可靠的,知识必须来源于观察及实验。理性主义者喜欢在迈出第一步前,就提前规划好一切。经验主义者喜欢尝试新事物,然后看看结果会怎样。

柏拉图是早期的理性主义者,而亚里士多德是早期的经验主义者。关于这个问题的辩论,真正开始于启蒙运动时期,每方有三位伟大的思想家:笛卡儿、斯宾诺莎、莱布尼茨是理性主义的代表,洛克、贝克莱、休谟则是经验主义的代表。

休谟提出过一个非常爆炸性的问题:在概括我们见过的东西以及没见过的东西时,怎样才能做到合理?从某种意义上说,每种学习算法都在尝试回答这个问题。在这个问题提出250年之后,大卫沃尔伯特提出了“没有免费的午餐”定理,规定了怎样才是最好的学习算法,最直白的答案就是没有那个学习算法可以比得上随意猜测

没有免费的午餐理论(No free lunch theorem, NFL) 没有算法能完美地解决所有问题。当所有问题出现的机会相同,或所有问题同等重要时,不管算法A有多好,泛化能力多强,算法A有多笨拙,这两个算法的期望值是相同的,换言之,这两个算法的性能可能差不多,甚至,一个最优算法可能和一个胡乱猜想的算法性能相似。

数学家认为机器学习这个问题是一个不适定问题(ill–posed problem):这个问题没有唯一解。下面是一个简单的不适定问题:哪两个数相加的得数是1000?假设这两个数都是正数,答案就有500种……1和999,2和998等等。解决不适定问题的唯一办法就是引入附加假设。如果要求第二个数是第一个数的三倍,那么答案就是250和750。因此,在机器学习的问题中引入预设观念是必不可少的,没有观念就无法进行学习。事实上,预设观念对于人类认识社会也是必要的。

适定问题(well-posed problem): 适定问题是指定解满足下面三个要求的问题:解是存在的;解是唯一的;解连续依赖于定解条件,即解是稳定的。这三个要求中,只要有一个不满足,则称之为不适定问题。

预设的重要性

Four Rules of Scientific Reasoning from Principia Mathematica

  • We are to admit no more causes of natural things than such as are both true and
    sufficient to explain their appearances.
  • Therefore to the same natural effects we must, as far as possible, assign the same
    causes.
  • The qualities of bodies, which admit neither intensification nor remission of
    degrees, and which are found to belong to all bodies within the reach of our
    experiments, are to be esteemed the universal qualities of all bodies whatsoever.
  • In experimental philosophy we are to look upon propositions inferred by general
    induction from phenomena as accurately or very nearly true, not withstanding
    any contrary hypothesis that may be imagined, till such time as other phenomena
    occur, by which they may either be made more accurate, or liable to exceptions

牛顿法则

  • 规则1:没有什么比既真实又足以解释其现象者更能说明自然事物的原因。
  • 规则2:对于相同的自然现象,我们必须尽可能地找到相同的原因。
  • 规则3:事物的属性,如果其程度不能增加或减少,且在我们的实验所及范围之内为所有物体所有,则应视其为所有事物的普遍属性。
  • 规则4:在实验哲学中,我们认为由现象所总体归纳出的命题是准确的或是基本正确的,而不管任何反面假设,直到出现了其他可以使之更精确,或是可以推翻这些命题之时。

牛顿法则的第四条(我们见过的所有东西在宇宙中也是真实的)是机器学习的第一个不成文规则。我们归纳自己能力范围内、应用最广泛的规则,只有在数据的迫使下,才缩小规则的应用范围。

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

以在线约会匹配为例,另一种思路是,暂且假设每个配对都合适,然后排除所有不含有某品质的搭配,对每种品质重复同样的做法,然后选择那个排除了最多不当搭配和最少适当搭配的选项。

现在你的定义看起来就像“只有他开朗,这对才合适”。现在反过来试着把其他品质加进去,然后选择那个排除了剩下最多的不当搭配和剩下最少的适当搭配的选项。现在的定义可能是“只有他和她都开朗,这对才合适”。然后试着往那两个特点里加入第三个品质,以此类推。一旦排除了所有不合适的搭配,你就成功了:就有了这个概念的定义,这个概念排除了所有的正面例子和所有的负面例子。例如,“每对中的两个人都开朗,这对才合适,他爱狗,而她不爱猫”。现在你可以丢掉所有数据,然后只把这个定义留下,因为这个定义概括了所有和你的目标相关的东西。这个算法保证能在合理的时间内完成运算,而这也是我们在本书中见过的第一个真实的学习算法。

过拟合的问题

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

其实在现实生活中,过拟合的问题无处不再。例如白人小孩看到拉美裔的小孩会脱口而出女佣。学习算法因为拥有从数据中发现模型近乎无限制的能力,因此非常容易过拟合。

约翰·冯·诺依曼曾说过:“用4个参数,我能拟合一头大象;用5个参数,我可以让它的鼻子扭动起来。”当今我们通常会学习拥有数百万参数的模型,这些参数足以让世界上的每头大象都扭动鼻子。甚至曾有人说过,数据挖掘意味着“折磨数据,直到数据妥协”。

组合爆炸的组合爆炸

假设的数量会随着属性的增多而呈指数级增长。在机器学习中,一个概念可能实例的数量,是其属性数量的指数函数:如果属性是布尔值,每种新的属性可能会是实例数量的两倍,方法就是引用之前的每个实例,然后为了那个新属性,对该实例以“是”或“非”来进行扩展。反过来,可能概念的数量是可能实例数量的指数函数:既然每个概念都把实例分成正面或者负面,加入一个实例,可能的概念就会翻倍。因此,概念的数量就是属性数量的指数函数的一个指数函数!换句话说,机器学习就是组合爆炸的组合爆炸。

学习就是你拥有的数据的数量和你所做假设数量之间的较量。更多的数据会呈指数级地减少能够成立的假设数量,但如果一开始就做很多假设,最后你可能还会留下一些无法成立的假设。

信任的准确度

在机器学习中,我们可以利用自己拥有的数据,将其分成一个训练集和一个测试集,然后前者交给学习算法,把后者隐藏起来不让学习算法发现,用来验证其准确度。留存数据的准确度就是机器学习中的“黄金标准”。对不可见数据的测试是判断学习算法是否过拟合的唯一方法。

避免过拟合的方法就是运用统计显著性检验来确保我们看到的模型真实可靠。例如,拥有300个正面例子、100个反面例子的规则,和拥有3个正面例子、1个负面例子的规则一样,它们训练数据的准确率都达到75%,但第一个规则几乎可以肯定比抛硬币好用,而第二个则不然,因为抛4次硬币,可以很容易得出3次正面朝上。在构建规则时,如果某一时刻无法找到能提高该规则准确度的条件,那么我们只能停下,即便它还包括一些负面例子。这样做会降低规则的训练集准确度,也可能让它变成一个更能准确概括的规则。

显著性检验是决定一项研究结果是否值得出版的“黄金标准”,为了降低假阳性的可能,我们一方面可以否定低显著性的假设进而对剩下的假设做进一步的数据检测。另一种方法则是选择更加简单的假设,比如稍微降低规则的准确度,来缩短规则的长度。

对较简单假设的偏好就是众人皆知的奥卡姆剃刀原理(Ocam’s razor),但在机器学习背景下,这有点误导性。“如无必要,勿增实体”,因为剃刀常常会被替换,仅意味着挑选能够拟合数据的最简原理。奥卡姆可能对这样的想法感到迷惑,也就是我们会偏向那些不那么能完整解释论据的理论,因为这个理论的概括性更好。简单的理论更受欢迎,因为它们对于我们来说,花费的认知成本更低;对于我们的算法来说,花费的计算成本更低,这不是因为我们想让这些理论更准确。

当准确度不尽如人意时,我们需要分析原因。在机器学习中,即分析“偏差”和“方差”。某座钟如果总是慢一个小时,那么它的偏差会很高,但方差会很低。但如果这座钟走得时快时慢,最后平均下来准点了,那么它的方差会很高,但偏差会很低。

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

归纳是逆向的演绎

对于每个事实,我们构建这样的规则,让我们由第一个事实推出第二个事实,然后通过牛顿定律将其推广。当同一条通用规则一次又一次被归纳出来时,我们有信心说那条规则说的是真的。

逆向演绎的一个局限性就在于,它涉及很密集的计算,因此很难扩展到海量数据集中。因为这些原因,符号学家选择的算法是决策树归纳。决策树可以当作此类问题的答案:如果有多个概念的规则对应一个实例,那怎么办?那么我们怎么知道实例对应哪个概念呢?

答案是让规则自己选择。决策树通常会保证,每个实例会准确对应一条规则。也就是说,在一次及以上的属性测试中,如果每对规则存在区别,这样的规则集将被组织成一棵决策树。对于决策树而言,你无法选择其中的两种或三种,或者一个都不选。拥有这个属性的概念组被称为类集,而预测类集的算法称为分类器。单个概念隐含两类定义:概念本身及其反面(例如,垃圾邮件和非垃圾邮件)。分类器是机器学习最为普遍的方式。

针对如何选择决策树最佳属性的问题,可以考虑信息论中熵的概念。一组对象的熵,就是用来衡量混乱度的单位。如果150人的组里面有50个共和党人、50个民主党人、50个独立人士,那么这个组的政治熵会达到最大。另一方面,如果这个组全部是共和党人,那么熵就变成零(这就是党派联合的目的)。所以为了学习一棵好的决策树的优点,我们在每个节点选择这样的属性:在其所有分支中,产生的熵在平均值上属性最低,取决于每个分支上有多少例子。

符号学派

因为其起源和指导原则,符号学派和其他学派相比和人工智能的其他方面关系更为密切。如果计算机科学是一块大陆,符号主义机器学习和知识工程学会有很长的交界线。知识通过两个方向进行交易——手动输入的知识,供学习算法使用;还有归纳得出的知识,用来加入知识库中,但最终理性主义者和经验主义者的断层线会刚好落在这条界线上,想越过这条界线则不容易。

符号主义是通往终极算法的最短路程。它不要求我们弄明白进化论和大脑的工作原理,而且也避免了贝叶斯主义的数学复杂性。规则集合决策树易于理解,所以我们知道学习算法要做什么。这样它可以轻易算出自己做对或做错什么,找出故障,得出准确结果。


本文作者:思考问题的熊

版权声明:本博客所有文章除特别声明外,均采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 (CC BY-NC-ND 4.0) 进行许可。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×