终极算法 第九章 解开迷惑

终极算法 第九章 摘要

我们迈向终极算法的第一步会简单得令人意外。事实证明,要将许多不同的学习算法结 合成一个并不难,利用的就是元学习。网飞公司、沃森、Kinect以及其他无数公司都会利用它,而它在机器学习算法的箭袋中也是最有力量的一支。它还是接下来要进入的深层次统一的垫脚石。

万里挑一

最聪明的元学习算法之一就是推进,由两位学习领域的理论家约阿夫·弗罗因德和罗伯·夏皮尔创造。推进算法不是通过结合不同的学习算法,而是将相同的分类器不断应用到数据 中,利用每个新的模型来纠正前面模型的错误。它通过将权值分布给训练实例的方式来完成这件事。每个被误分类的权值,在每轮学习过后都会增长,使得后面的几轮会更向它集中。 推进算法的名字源于这样的想法:该过程可以推进只比随机猜测好一点的分类器,但如果持续如此,就会接近完美。

元学习非常成功,但它却不是深入组合模型的方法。另外,它也昂贵、苛刻,因为会做 很多轮学习,而且组合模型可能会很难懂(“我认为你有前列腺癌,因为决策树、遗传算 法、朴素贝叶斯算法都这么判断,虽然多层感知器和支持向量机反对”)。此外,所有的组 合模型确实只是一个巨大而凌乱的模型。难道我们不能找到完成同样任务的单一学习算法吗?当然可以。

终极算法之城

我们的统一学习算法也许通过延伸寓言可以得到最好的介绍。如果机器学习是一块大陆,被分成5个区域,那么终极算法就是首都城市,矗立在5个区域会合的特殊地带。如果从远处接近它,你会看到这个城市由3个同心圆组成,每个圆被一堵墙围着。外围的圆,也是最宽的圆是“优化城”。这里的每个房间就是一种算法,而且它们有不同的形状和面积。有些房子在建设中,当地人忙着围着它团团转;有些房子非常崭新;有些房子则看起来老旧荒废。山的更高处是“评价城堡”,命令不断从它的大厦和宫殿向下面的算法发出。最重要的是,在天空的映衬下,“代表法之塔”矗然而立,这里住着城市的统治者。他们的城市有不可改变的法律,不仅规定在城市范围内,而且规定了在整个大陆什么能做、什么不能做。在中央,最高的塔尖飘扬着终极算法的旗帜,颜色是红和黑,上面的五角星围着我们无法理解的文字。

马尔科夫逻辑网络

利用MLN作为表示方法,利用后验概率作为评估函数,利用与梯度下降结合的基因搜索作为优化器。如果我们愿意,可以轻易地利用其他准确度测量方法来代替后验概率,或者利用爬山法来代替遗传搜索。我们上升到一座高峰,现在我们可以享受风景了。但是,我不会那么轻率地将这个学习算法称作终极算法。一方面,布丁的味道好不好,吃了才知道,而且虽然过去10年这种算法(或者它的变化版本)已经成功应用于许多领域,但还是有许多领域没有应用到它,因此还不清楚它的一般用途。另一方面,它还有一些重要的问题没有解决。

从休谟到你的家用机器人

符号学家结合运算中不同碎片的知识,这和数学家结合公理来证明定理是一个道理。这 和神经网络和其他有固定结构的模型迥然不同。炼金术利用逻辑来完成这件事,正如符号学 派所做的那样,却是一个迂回曲折的过程。为了证明逻辑中的定理,你需要发现产生该定理 的公理应用的唯一顺序。因为炼金术从可能性的角度谈到其实它要做得更多:找到公式的多 重序列,引出定理或者它的否定面,然后对它们进行权衡,以计算出定理真实的概率。这样 它能推理的不仅与数学共性有关,还可以推理在一则新闻报道中的“总统”指的是不是“巴拉 克·奥巴马”,或者一封邮件该在哪个文件夹之下。符号学派的主算法——逆向演绎,假定新 的逻辑规则,用于作为数据与预期结论之间的步骤。炼金术通过爬山法来介绍新的规则,以 原始规则作为开始,与原始规则和数据相结合,构建使结果概率更大的规则。

关联学派模型的灵感来源于大脑,S形曲线的网络与神经元相对应,它们之间的加权关 联对应的是突触。利用炼金术,如果两个变量在某个公式中一起出现,那么它们就被联结在 一起,考虑到近邻,一个变量的概率就是一条S形曲线(我不会解释为什么,这是我们在前 面部分看到的主算法的直接结果)。联结学派的主算法是反向传播,他们利用它来弄清楚哪 个神经元负责哪些误差,并根据它们的权值来进行调整。反向传播是梯度下降的一种形式, 炼金术用它来优化马尔科夫逻辑网络权值。

进化学派利用遗传算法来模仿自然选择。遗传算法包含假设的“人口”,在每一代中,适 应能力最强的会进行交叉和变异,以生产下一代。炼金术以加权公式的形式来维持假设 的“人口”,在每一步中以不同的方法对它们进行改变,然后把那些最能提高数据(或者一些 其他的评分函数)后验概率的变量留下。如果人口是一个单一假设,这就简化为爬山法了。 当前炼金术的开源实施并不包含交叉,但这就是一个简单的加法。进化学派的主算法是遗传 编程,应用交叉和突变于计算机程序上,以子集树的形式表示出来。子集树可以用一组逻辑 规则来表示,Prolog编程语言就是这么做的。在Prolog中,每个规则与一个子集对应,而它 前面的规则是它称呼的子集。因此我们可以将带有交叉的炼金术当作利用Prolog相似编程语 言的遗传编程,这样会有一个额外的优势——规则可以是概率性的。

贝叶斯学派相信模拟不确定性是学习的关键,并利用形式表示方法如贝叶斯网络和马尔 科夫网络来工作。正如我们已经看到的那样,马尔科夫网络是MLN的特殊类型。贝叶斯网络 利用MLN主算法也可以轻易表示出来,一个特征对应一个变量及其起源的每个可能状态,而 相应条件概率的算法则作为它的权值(然后归一化常数Z 就便利地简化为1,意味着我们可 以忽略它)。贝叶斯的主算法是贝叶斯定理,执行的方法是利用概率推理算法,比如置信传 播和MCMC。正如你已经注意到的那样,贝叶斯定理是主算法的特例,包含P =P (A ∣B ),Z =P (B),而特征和权值对应P (A )和P (B ∣A )。炼金术系统包含置信传播和 MCMC用于推理,推广至处理加权逻辑公式。将概率推理用于对逻辑提供的证明路线上,炼 金术为支持或者反对结局来权衡证据,并输出结局的可能概率。这与符号学派利用的“单纯 功能”逻辑相反,该逻辑不是全有就是全无,因此当给定矛盾证据时,该逻辑就会崩溃。

类推学派的学习方法是假设有已知相似属性的实体,也会有相似的未知属性:拥有相似 症状的病人也会有相似的诊断,过去喜欢买某类书的读者可能未来还会买同样的书,等等。 MLN可以代表具有像“拥有相同品位的读者会买相同的书”公式的实体之间的相似性。爱丽丝 和鲍勃买到的相同的书越多,他们越可能有相同的品位;(将相同的公式应用于相反方向 中)如果鲍勃买一本书,爱丽丝也买这本书的概率就比较大。他们的相似性由他们有相同品 位的概率来表示。为了使这一方法真正起作用,对于相同规则的不同实例,我们可以有不同 的权值:如果爱丽丝和鲍勃都买了某本罕见的书,这包含的信息量也许会比他们购买畅销书 的信息量大,因此应该有更高的权值。在这种情况下,相似度由我们计算的属性是离散的 (买或者不买),但我们也可以在连续属性之间表示相似度,就像两座城市之间的距离一 样,方法就是让MLN把这些相似性当作特点。如果评估函数是一个边际风格评分函数,而不 是后验概率,结果就是支持向量机的概括版,也就是类推学派的主算法。我们的主学习算法 面临的更大挑战是复制结构地图,这是类比更强大的类型,可以从这个域(比如太阳系)推 断到另外一个域(原子)。我们可以通过学习公式来做到这一点,这些公式不会指代源域中 的任何特定关系。例如,“抽烟的人的朋友也抽烟”讲的是友谊和抽烟,但“相关的实体有相 似的属性”适用于任何关系和属性。我们可以通过概括“朋友的朋友也抽烟,专家的同事也是 专家”来掌握它,还有在社交网络中其他这样的模式,然后将其应用到诸如网页之类的地 方,包含像“有趣的网页会链接到有趣的网页”这样的实例,或者应用于分子生物学中,包含 像“与蛋白质调控互动的蛋白质也会调控基因”这样的实例。我的小组的研究人员和其他人已 经完成所有这些事,接着还会做更多。

目前炼金术最大的应用在于从网络中学习语义网络(或者谷歌所谓的知识图谱)。一个 语义网络就是一组概念(就像行星与恒星)以及这些概念中的关系(行星环绕恒星)。炼金 术会通过从网页中提取的事实(例如,地球绕着太阳转)来掌握100万个以上这样的模式。 它会独自发现诸如行星之类的概念。我们之前使用过的版本,比我在此已经描述过的基本版 要先进,但基本思想是一样的。各式各样的研究已经利用炼金术或者他们自己的MLN执行工具来解决自然语言处理、计算机视觉、动作识别、社会网络分析、分子生物学及其他许多领 域中的问题。

尽管成功了,炼金术还是有一些明显的不足之处:它还没有真正扩展到大数据,而一些在机器学习领域没有博士学位的人会发现它很难使用。

行星尺度机器学习

在计算机科学中,如果一个问题没能得到有效解决,它就没有真的得到解决。如果你不 能在可用时间和记忆内完成一件事,那么知道这件事怎么做并没有多大用处,因为在你处理 MLN时,这些时间和记忆会消耗得很快。通常我们利用数百万的变量和数十亿的特征来对 MLN进行学习,但这并不像表面看起来的那么大规模,因为变量的数量会随着MLN中实体 的数量迅速增长——如果你有一个包含1000人的社交网络,你就已经拥有100万对可能的朋 友,以及10亿个“朋友的朋友是朋友”公式的实例。

炼金术中的推理是逻辑与概率推理的结合。前者通过证明定理来完成,后者则通过置信 传播、MCMC以及我们在第六章中见过的其他方法来完成。我们将两者结合至概率定理证明 中,统一推理算法可以计算任意逻辑公式的概率,是当前炼金术系统的关键部分。但在计算 法方面,它需要的很多。如果你的大脑利用概率定理证明,那么一只老虎会在你没来得及想 明白如何逃离时就把你吃掉,这就是马尔科夫逻辑一般性的高昂代价。你的大脑在真实世界 中已经进化,必须对额外的猜想进行编码,这样有利于它进行有效推理。在过去几年中,我 们已经开始弄清楚它们可能是什么,并将其编码入炼金术。

,解释学习算法的宣言本身需要大量的技能。虽然如 此,如果转错手柄,学习算法可能会涌出一系列胡言乱语,或者在反抗中保持沉默。不幸的 是,就这一点而言,炼金术并不比多数算法好。把你知道的用逻辑的形式写下来、输入数 据、按下按钮才是好玩的部分。当炼金术返回准确而有效的MLN时,你会去酒吧庆祝;当它 不返回时——很多时候会出现的状况——战争就开始了。问题存在于知识、学习、推理中 吗?一方面,因为学习和概率推理,简单的MLN可以做复杂程序能做的事。另一方面,当它 不起作用时,调试起来就困难很多。解决办法就是让它更加交互,有能力进行反省,并解释 它的推理。这就会让我们向终极算法更加靠近一步。

医生马上来看你

治愈癌症的方法是一种能够输入癌症基因组,并输出杀死癌细胞药物的程序。我们现在 可以想象,这样的程序(就叫它“CanceRx”)会长什么样。尽管外表上看起来简单,CanceRx 是编出的程序中规模最大也是最复杂的程序,的确太大了,所以它只能在机器学习的辅助下 建立。它的基础是一个关于活细胞如何运转的详细模型,人体内的每种细胞都会有一个子类 别,还有关于细胞如何互动、支配一切的模型。该模型以MLN或者与其相似的形式,将分子 生物学的知识与来自DNA测序仪、微阵列,以及其他许多来源的大量数据结合起来。有些数 据通过手动进行编程,但大部分是从生物医学文献中提取出来的。模型会不断进化,并将新 实验的结果、数据来源、患者病历合并起来。最后,它就掌握每种类型人体细胞中的每条路 线、调节机制、化学反应,这就是人体分子生物学的总和。

现在人们已经在努力建造最终会成为CanceRx的东西。在系统生物学的新领域中的研究 员会模拟整个代谢网络,而非个体基因和蛋白质。位于斯坦福的一个团队已经构建了整个细 胞的模型。全球基因组学与健康联盟推动数据在研究员和肿瘤学家之间的分享,着眼于大规 模分析。癌症联盟会(Cancer Commons.org)收集癌症模型,让病人集中他们的病历,然后 从相似例子中学习。基础医学(Foundation Medicine)查明病人肿瘤细胞中的变异,然后开 出最合适的药物。10年前,人们不知道癌症是否可以或者如何被治愈,现在我们就能看到如 何做到这一点。路还很长,但我们已经找到路了。

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