彩云ICLR 2018顶会论文带你进入“组合式神经编程”的世界

大家好，年前彩云科技就爆出重磅消息，肖达、廖若雨和袁行远的论文《Improving the Universality and Learnability of Neural Programmer-Interpreters with Combinator Abstraction》被国际顶级学术会议ICLR2018接受。小编苦苦研读了一个春节假期终于搞明白这篇论文原来是将神经网络的泛化能力与经典AI的组合、推理能力结合到了一起，可以用于解决自然语言处理领域的一系列问题，并有望在攻克图灵测试的道路上迈进一步。于是，小编赶紧从肖老师那里淘来了关于论文构思的第一手材料，以及肖达老师亲自撰写的科普解读，以及对他的独家专访，今天一并奉献给大家。

前言

什么是神经编程

神经编程（Neural Programming，简称NP），顾名思义，就是利用神经网络来写程序。我们都知道，神经网络擅长的是模式识别和预测，并不擅长写程序这样的逻辑性很强的任务。所以，由此可知这个任务的难度非同小可。我们需要将神经网络的泛化能力优势与传统AI的逻辑推理能力巧妙地结合起来才能实现我们的预期。但是，一旦我们造出靠谱的神经编程机器，它就有可能兼具形象思维和高级的逻辑推理能力，这有助于我们解决自然语言处理中的一系列高难度任务，如阅读理解、机器翻译、人机对话等，甚至有可能突破图灵测试难题。

什么是组合子

组合子（combinator），也就是函数的函数。我们都写过计算机程序，函数或者子过程可以封装一部分功能。那么函数的函数就是将函数的指针作为参数传给另一个函数实现的。例如，y=x^2是一个函数，求导Derivative就是一个函数的函数，我们将y=x^2这个函数的指针传递给Derivative，就可以得到这个函数的导数2x了。将这种组合子作为我们操作的基本单元，就可以实现功能强大的计算。

关于ICLR

ICLR，全称为「International Conference on Learning Representations」（国际学习表征会议），2013 年才由Yoshua Bengio和Yann LeCun牵头创办。这个一年一度的会议虽然今年才办到第五届，但已经被学术研究者们广泛认可，被认为「深度学习的顶级会议」。ICLR 不同于其它国际会议，它推行了 Open Review 评审制度，论文质量普遍很高，录用率仅30%多，被称为深度学习界的无冕之王。

论文介绍

“组合式神经编程解释器”简介

为什么神经编程近年来会成为学界研究的一个热点呢？其实研究神经编程的最大意义并不是真的搞出个AI programmer代替人类程序员。我们知道，现在的深度神经网络在视觉识别、语音识别等低级感知任务上的已经超过人类，但在逻辑推理、规划、搜索、语言理解等需要“高级认知”能力的任务上的表现却远没有令人满意。而我们所能想到的最全面和集中的体现这种高级认知能力的活动，可能非编程莫属了。程序设计不仅仅是我们熟悉的写一段代码解决一个算法题（例如排序），其实很多困难AI问题归根结底都要用程序求解。所以，让神经网络学习构造和解释执行程序来解决问题，是提升其高级认知能力的可行手段。从更技术的层面说，高级认知能力的一个核心，是抽象和组合能力。我们想让机器具有抽象思考和举一反三的泛化能力，就要把合适的抽象机制引入模型中。这些抽象机制哪里来呢？计算机科学的先辈们已经给我们准备好了一个大宝藏，就是程序设计语言的各种抽象机制及其在编译器/解释器中的实现方式。这里的程序设计语言不仅限于大家熟悉的命令式编程语言（如C/C++，Java），还包括函数式编程语言（如Lisp、Haskell）和声明式编程语言（如Prolog）。

言归正传，下面介绍我们的这篇论文。

戏说版

时空轮转，一个叫Agent的同学，来到了一个需要不断打怪升级的陌生世界。纯小白的他要从头开始学习各种战斗技能。好在A同学有学霸潜质，善于学习和思考，有悟性。身无分文的A同学，唯一的初始装备是一个空的技能卡槽。卡槽背面写着简单的行动规则：每get到一个新技能，就把写有技能名称和描述（例如，一技能：[举盾、前冲、砍一剑]）的技能卡放到技能卡槽里，以备需要时取出施展。每次行动前，先根据当前情况，从卡槽里取出一张技能卡。每做完一个动作，就根据血量、技能恢复进度等自身状态，周围的敌我情况和当时手里拿的技能卡，决定下一个动作，并更新自身状态。下一个动作做完后，再根据新的周围情况和状态，重复这个过程，直到把当前技能打完。怎么get新技能呢？有两种方式：足够幸运的话，会遇到一个老师手把手一个动作一个动作的教各个技能，否则，就只能直接上战场，在要么成功杀敌要么不幸阵亡的不断锤炼中学习成长（好在可以无限复活）。

A同学一开始的学习进度很慢，学到的也都是些基础技能，练了很久还在青铜级徘徊，经常被虐，只能打打小怪。直到有一天，他猛然醒悟：原来一个技能里的下一个动作，除了砍一剑这种具体动作，还可以是一个已经学到的技能！如果是后者，就把已学技能的卡片从卡槽里取出，用同样的套路开始打，打完后再返回之前的技能接着打，perfect。这样，A同学就能把技能组合起来变成威力倍增的组合技，技能卡槽里多了像[一技能、二技能、大招]这种新开发的组合技连招后，功力突飞猛进，大杀四方，很快升级为黄金英雄。

然而A同学并未就此满足，为了避免单一英雄被克制，他开始尝试变身成各种英雄，学习他们的技能和打法。随着要掌握的普通技能和组合技能越来越多，技能卡槽越插越满，A同学对学习新的组合技渐感力不从心，也经常狗熊掰苞米似的学了新的忘了旧的。升级进入瓶颈期。直到有一天，也许是他的不断努力探索得到了上天的眷顾，A同学再次顿悟：看似五花八门的各种组合技，如果忽略被组合的具体技能，组合的方法本身不也是一种技能吗？！而且组合技虽多，其背后的组合方法好像就只有那么几种！顿悟后，A同学学习效率大增，例如，从英雄甲的“一二大”三连和英雄乙的“二三大”三连总结出“三连”这个“元技能”后，他瞬间学会了其他英雄的各种三连。仅仅掌握了几种元技能后，A同学就轻松精熟了各路英雄的打法，终于成为无敌寂寞的王者。

术语对照表：动作 = primitive action，技能 = policy / program /procedure，组合技 = compound procedure，技能名称 = program key，技能描述 = program embedding，技能卡槽 = program memory，自身状态 = hidden state，周围情况 = environment input，手把手教 = supervised learning，战斗中学习 = reinforcement learning，青铜英雄 = plain RL agent，黄金英雄 = hierarchical RL agent / NPI，王者英雄 = CNPI，元技能 = combinator

正经版

本文工作的基础是神经编程解释器（NPI，Neural Programming Interpretor，即A同学的第一次顿悟），相比之前的神经编程模型，NPI的最大亮点是有个program memory来存储已经学到的子过程，解释执行程序时可以调用program memory中的子过程，因此NPI可以在已学到子过程的基础上学习新程序，而不必从头学起，从而使得用一个核心控制器（core controller）持续不断的学习从简单到复杂的程序成为可能。实际上，NPI引入了程序设计中一种非常基本和常用的抽象和组合机制——定义子过程并用子过程的嵌套调用实现复杂功能，即过程抽象。

但NPI也存在一些重要缺陷。首先，由于NPI依赖一个单独的核心控制器去学习解释执行所有的程序，随着program memory中学到的子过程越来越多，学习新程序的难度也越来越大。其次，很多程序虽然表面不同，但其实有相似或相同的结构（见下图右半部分十进制加法和冒泡排序程序），而NPI把它们都当成完全不同的程序花同样的力气去学，没有利用它们的相似性提高学习效率。这些问题导致NPI虽然目标是模拟通用图灵机，但无论在理论上还是实验中都无法达到真正的universal——即能够正确解释执行任何程序；并且只能以有监督的方式训练，用程序执行的trace作为训练样本（即手把手教）。

造成这些问题的根本原因是，NPI虽然利用过程抽象对程序进行分解降低了每个子过程的复杂度，但由于抽象层次不够高，分解得并不彻底。

为了解决NPI的这些问题，我们在这篇论文提出组合式NPI（CNPI，Combinatory Neural Programmer-Interpreter即A同学的第二次顿悟），引入程序设计中另一个非常重要的抽象机制，即函数式编程中的高阶函数，也叫组合子（combinator）。顾名思义，高阶函数就是函数的函数，一般是通过把函数作为参数传给另一个函数实现的。CNPI中的组合子（combinator）是种特殊的有参过程，它只能调用作为参数传给它的子过程，组合子的作用就是把这些子过程组合成一个新的过程。特别要注意的是：因为子过程是通过参数传给组合子的，所以每个组合子实现的用形参表示的子过程的组合方式和被组合的实际子过程（实参）无关。换句话说，组合子表达的是一个抽象的关于“如何组合”的概念，就像“三连”元技能一样。

和普通过程不同，由于组合子的高度抽象性和由此带来的可复用性，它们的数量并不需要很多。这篇论文的讨论限定在算法任务。那么我们要问，到底需要几个组合子，才能搞定所有的算法任务呢？论文提出：四个就够了。这四个组合子分别表达四种最普遍的程序结构，它们是：

seq（顺序，表达顺序执行）、

cond（条件，表达if-then-else等分支结构）、

linrec（线性递归，表达for循环、while循环等循环结构）

treerec（树递归），表达多次递归调用，例如在快速排序和图的深度优先遍历中。

前三个组合子的伪代码见下图。树递归组合子treerec比较复杂，这里就不介绍了。

除了子过程参数，组合子还会接收一个检测子（detector）参数。如果说子过程是主动技能，那检测子可以看成被动技能。它们并不会被显式调用执行动作，而是持续的提取环境中的某种信息，提供给组合子用于条件判定（例如分支条件或循环的终止条件）。检测子是NPI中encoder的精简版。注意组合子linrec和treerec递归调用自身（self），以实现某种循环结构。

仅有这四个组合子还不够，因为单靠它们无法构成完整的程序，也就只能把原始动作做一次最浅层组合。我们还要引入另一种特殊过程——应用子（applier）。应用子调用一个组合子并给它提供参数，把有参的组合子封装成跟无参的原始动作一样的东西。应用子就像粘结剂把多个组合子连接起来构成完整程序，允许把组合出的子过程再做组合，通过任意多层的组合实现任意复杂的程序。于是一个程序的完整执行过程可能是这样子：应用子A调用组合子b，组合子b又调用应用子C，应用子c又调用组合子D，……直到应用子X或组合子y调用原始动作Z。这个组合子和应用子的循环调用是个非常基本的计算结构，实际上，它正是函数式编程语言解释器的核心eval-apply循环。《计算机程序的构造和解释》（即传说中的神书SICP）第4章对此作了很好的讲解。下图给出了冒泡排序的一趟冒泡过程的子过程BSTEP的正常版本和组合式版本以及执行trace。

我们把这样构造出的程序，叫组合式程序（combinatory program）。可是这种构造方法有什么特别的好处呢？这也是理解为什么CNPI能universal，即本论文主旨的关键。我们回头再来看一下构成组合式程序的四种特殊的基本子过程：

1）组合子：总个数固定（本文中为4），且每个组合子能调用的子过程的个数有限（=组合子参数的个数，本文中也为4）；

2）应用子：总个数无限制，执行一次调用即返回，没有任何分支循环等控制结构，相当于一个只有一行的宏定义；

3）检测子：每个检测子可以单独训练一个神经网络来实现，存储在detector memory中；

4）原始动作：解释执行由每个具体领域提供，不需要学习。

一方面，我们看到，四种子过程都是高度受限的，所以它们的解释执行很容易被学习。而且由于应用子和检测子这两种子过程的特殊性，CNPI的架构可以保证即使不断学习新的子过程添加到program memory，后添加的子过程也不会对已有子过程的正确解释执行造成干扰（见论文第4节定理1）。另一方面，通过这四种极其简单的子过程的相互调用，却可以表达任意复杂的程序（实际上我们认为组合式程序是图灵完备的，但论文中没有证明，只给出把普通程序转化为组合式程序的一个一般算法，见附录B的算法2）。正是这两点保证了CNPI是universal的。

至此我们已经搞出一种可以被分解得非常彻底的组合式程序，可离大功告成还差重要一步：要让NPI通过训练能正确解释执行它，为此我们还要对NPI架构和解释执行过程做了几个重要扩展，以让新的CNPI架构和这种新程序“兼容”：

1）增加了detector memory来保存检测子，它和program memory一样也是一个key-value存储结构。

2）增加了个parser专门用来解释执行应用子。

3）为了能给组合子传递参数，应用子调用组合子时，要构造一个帧结构（frame），并在里面填好组合子需要的子过程参数和检测子参数的key。帧可以看成是一个动态创建的局部program memory，为每个组合子的调用提供一个执行环境。解释执行子过程时，由原来每步用输出的key直接到program memory里找下一步调用子过程的向量，变成每步先从当前帧里找到下一步调用子过程的key，再拿这个key到program memory里找程序向量。这种间接寻址使每步决定下一步调用子过程的搜索范围由program memory里存储的所有子过程（个数可以不断增长）缩减为一个帧里的固定4个子过程参数，大大降低了组合子的学习难度。

论文的训练方法、分析和实验等部分不再详细介绍，只列出几个重要结果：

在给定特定领域的已训练好的检测子的条件下，通过学习应用子添加到program memory，CNPI可以正确解释执行所有的组合式程序，即CNPI对于组合式程序的全集是universal的。

为解决给定任务，训练和验证模型正确性所需的样本数，CNPI都比NPI少一个量级，因为组合子只需训练和验证一次，就可以在所有任务中复用。

在有监督学习中，NPI有比较明显的遗忘效应，而CNPI不会遗忘。

用基于梯度策略的强化学习（战斗中学习）可以训练CNPI，但需要设计合适的教程（curriculum），先通过完成辅助任务学习组合子，再学特定任务的应用子。因为组合子是元技能，先学会它们可以大大加速具体技能的学习。

结语和展望

CNPI的原理就介绍到这里。你可能会问，搞了一堆这么复杂的东西除了浪费脑细胞还有什么实际用途呢？确实，离实际应用尚有距离或者说缺乏杀手级应用，可以说是目前几乎所有神经编程工作（包括本论文）的一个通病。而我们认为CNPI的最大价值，正在于它的思想和基本框架有应用到算法编程以外领域的潜力（戏说里的例子也多少体现出这点）。其实自然语言可以看成一种程序，而所谓自然语言理解，就是人脑对这种程序的解释执行。当我们分析自然语言程序时，会发现它之所以有极强的表达能力，使你在读完这篇文字后能理解CNPI这么复杂的东西，正是因为也包含函数抽象、高阶函数等抽象和组合机制。这里不再详述，感兴趣的同学可以去看Montague语法等自然语言语义学研究的相关书籍和论文。CNPI的特性使它有可能发展成自然语言解释器的内核，进而构建能更好的理解和执行人类语言和指令的且能终身学习的agent。当然，本论文的工作只是我们在通用人工智能的探索之路上迈出的一小步，就像A同学一样，前方还有更多的未知在等待着我们。

完整版

北京海淀区学院路甲5号768创业园C座04号。

作者介绍

肖达博士毕业于清华大学计算机科学与技术系，现为北京邮电大学网络空间安全学院讲师，彩云科技首席科学家，集智俱乐部核心成员，集智科学家。目前研究兴趣包括深度学习、人工智能、认知科学。曾在集智俱乐部发起并主持“脑与deep learning读书会”、“高级认知deep learning读书会”等线下活动。

采访肖达老师

Q：请问您是什么时候开始创业的，为什么想到做彩云天气？

A：2010年左右，我的研究兴趣从云安全转到人工智能，一开始的目标很“宏大”，试图用神经生物学、统计物理等理论方法弄清人脑认知的基本原理，揭开智能的本质。2012年底在集智俱乐部的读书会了解到行远的用雷达图做短临降雨预报的想法，觉得很酷就加入一起做了，当时对天气是纯小白，在过程中工作重心逐渐转到更加具体的深度学习研究及其在天气上的应用。发现与理论研究相比，这种扎进一个完全陌生的领域，以解决实际问题为出发点，死磕并最终搞定，用技术创新给数以百万的用户提供更好的服务，是一种全新的体验，很有成就感。几年做下来，公司依赖技术优势逐渐发展壮大，自己的提升也非常大。

Q：你的论文研究的方向是神经编程，您是如何想起来做这个方面的研究？这个研究以后会不会用于商业用途？

A：在彩云做产品相关的算法研发的同时，我一直在思考怎样给擅长基于模式匹配的感知的深度神经网络加入人的高阶认知，即抽象思维能力，以实现更像人类的通用智能。我认为神经编程是达到这个目标的一条有前景的路，所以一直在关注这个方向，尤其是2016年NPI的工作出来后。但NPI有一些在我看来很严重的缺陷，2017年我接触到函数式编程和解释器领域，发现可以借鉴一些思想和方法解决NPI的问题，就写了这篇CNPI的论文。这篇论文只是个开头，神经编程真正的价值不在编程而在其他领域，例如我们目前正在做的将CNPI框架应用于自然语言理解，这是块难啃的硬骨头，但最终会落地为产品带来商业价值。

Q：很多学者在面临商业和科研的时候都觉得很矛盾，无法权衡，您是如何考虑应对商业压力和科研兴趣？

A：就公司理念来说，我认为商业压力和科研兴趣并没有本质矛盾。我们会追求商业利益，但根本目的是两个：一是做好的产品用技术服务大众，践行人工智能让生活更美好；二是通过产品和商业上的成绩获得更多的社会资源投入，支持我们在通用人工智能上持续的科学研究。后者是我们创立彩云的初心，也是一直没变的终极目标。当然，从实操角度讲，作为一个创业公司，平衡商业与科研是个挑战，尤其在我们科研的方向和公司主营业务关系并不紧密的情况下。但通过我们的不断尝试我认为并不是不可能。如果放弃“跑偏”的科学探索，“专心”做一个纯粹追求商业价值最大化的公司，也许“成功”的概率更大。但为了有机会成为我们自己心目中真正理想的公司，我们还是要不忘初心。