程序编写程序：泛用人工智能领域的一颗明珠

　　2017年2月，微软研究院与剑桥大学宣布他们合作开发了一种新的算法，名为DeepCoder——现在看来可能跟算法的名称有关，因为Coder也是程序员的昵称，有读者以为机器程序员来了，传出了“DeepCoder能够从网络论坛和开源社区中复制代码并加以组合来生成新的程序”的说法。

　　如同作者在论文所说，这是一种能根据问题输入输出自动编写解题程序的算法：目前业界使用的编程语言对于机器算法来说还是太难掌握了，DeepCoder使用的编程语言是一种原创的、极其精简的语言，其中只有整数数据类型，内置了基本的四则运算以及一些基本函数，例如排序，或者对数组中的元素依次执行某种操作等等。此外，DeepCoder完成的程序生成是一种叫做Inductive Program Synthesis（IPS，归纳式程序合成）的特例；在这种程序生成方法中，机器通过观察输入输出的样例组合来生成一个“与当前样例数据行为一致”的程序。

　　不过，尽管原理是如此简单，DeepCoder还是展现了惊人的解题能力：它使用一种非常简单的DSL语言，这种语言允许机器将小的语句和程序块逐个拼接成更大的部分（类似于微软的LINQ语言），这样一来，机器在程序生成的每一步中，只需要考虑下一行执行一个什么操作而不用考虑括号如何匹配、如何安排分支代码这样的问题，也不用自带游标卡尺，大大简化了机器的思考过程。

　　此外，在DeepCoder出现以前的做法（是的，解题机早已存在），更多采用“枚举”的方法依次验证所有程序，就是由“所有程序”组成一个“程序空间”，解题机在这个空间里执行搜索任务，这样做的一个问题在于，枚举执行大量的重复操作，生成无数毫无道理的程序。

　　“……前三行和第四行的前四个字都是表达生命对宏伟的惊叹，最后一个字是诗眼，它是诗人在领略了之浩渺后，对生命在无限时空中的渺小发出的一声无奈的叹息。”——刘慈欣《诗云》

　　与此形成对比，DeepCoder并不逐一枚举，而是使用神经网络来辅助搜索过程。在此算法的框架中，神经网络担当了两个任务：一是观察输入输出之间的关系，例如输入是否全是负数，输出是否从小到大有序等等，将其转换成机器理解的一组特征。这一做法受到了前人工作的，之前的做法是用手工编写方式列举这些规则，而DeepCoder则使用神经网络将这一过程自动化。二是在通过观察了解数据的特征之后，以特征为输入，通过一个神经网络来预测程序中可能有哪些语句。这个预测过程产生的分布会改变搜索程序选择不同语句的优先级，从而避免生成重复而无意义的程序，使得解题效率大大提高。

　　目前来看，包括DeepCoder在内的现有程序生成算法还不能处理较为复杂的问题。但从另一方面看，既然机器已经能够完成简单的编程任务，那么我们就可以利用它来辅助程序员的工作，或者帮助普通计算机用户来自动化一些工作流程。

　　DeepCoder解题过程示意图：每行代表一个程序，每列代表一种语句。红色越深代表其神经网络给出的预测值越高；绿色代表最终搜索得出的正确结果。

　　实现程序自动编写程序是通用人工智能领域学者们一个共同的梦想，也是我们机器学习组的一个研究方向。与其他AI研究领域类似，在这一领域的探索工作中，存在两种不同的思，分别是符号派（Symbolic Method）和连接派（Connectionism）。

　　符号派秉承了古典AI的风格，其思是将所有程序定义在一个空间内并通过搜索方法来寻找一个合适的程序。其中又包含不同的分支，例如DeepCoder所使用的IPS（归纳式）生成方法，以及基于Constraints（条件）的求解方法等。符号型程序生成也和机器自动证明（ATP）、编程语言理论（PLT）、静态程序分析（SPA）等领域有着深刻的联系：如果我们能顺着程序语言的语法语义规则进行论证，最终达成问题中需求的逻辑，那么我们也就完成了一个严格正确的程序的生成；反过来，给定一个手工编写的程序，如果我们通过搜索在程序空间中找到了它，那么机器能给出大量程序中隐含的逻辑，为程序员提供另一种看待问题的视角。因此，这类方法能和编程语言一起演化，相互促进。

　　在基于条件的求解方法中，算法不仅从上考察输入和输出的特征和其中（可能）蕴含的规律，还能根据问题定义中的符号式条件，对程序空间进行更精确的探索。

　　举例：如果我们用一个可满足模理论求解器（SMT）来玩扫雷游戏，我们可以预先将游戏规则告诉机器，它就能精确地根据当前地图提供的信息进行推导并避免生成触雷的指令。

　　在这一类问题族谱的另一端，当我们放松条件，不要求输出完全和样例匹配但要尽量接近，就将问题成了符号型回归问题。一个符号型回归算法执行的是回归任务，它尝试给出一个模型来逼近样例。与其他回归算法不同，符号型回归算法中并没有一个确定的模板公式（例如线性回归的模板是以权重参数给出输入的线性组合）。这类算法与IPS相似，通过搜索方法来寻找最适合当前数据的公式和参数值。Nutonian公司的Eureqa系统即是这类方法的典型代表；据作者称，它能在仅观察钟摆运动数据的情况下自行推导出牛顿定律。

　　当前这类方法仍然面临的挑战在于，在问题及语言复杂的情况下，其计算量或将不可承受；此外，归纳式的求解方法也不能完全抓住问题的本质，其关键在于问题中给出的输入输出能否完整覆盖问题本质所包含的逻辑，以及从同质输入输出中排除歧义，这往往非常困难。

　　二是连接派。随着神经网络的复兴，连接派学者开始使用神经网络来挑战编程任务。与符号型方法的枚举不同，在神经网络型的系统中，算法更多地将程序空间看成一个连续的空间，将程序看作一个由大量参数以及一套可微分的固定规则组成的系统。这样一来，搜索过程无需进行枚举，而是转为在连续空间里面采用可微分优化方法（例如梯度下降）来逼近一个合适的解。由于程序中可能蕴含状态（也就是说，多次调用同一个函数可以得到不同结果），很多连接派的算法都会在网络结构中对内部和外部存储机构进行重点加强。

　　比如，Google发表的神经元图灵机（Neural Turing Machines ，NTM）和后续工作差分神经元计算机（Differentiable Neural Computer，DNC）给出了一个模仿真实计算机架构，利用神经网络学习与预判对外部存储器执行动作序列的方案。神经元符号机（Neural Symbolic Machines）对自然语言进行编码，再根据其特征预测生成一种可组合的函数式编程语句，从而实现访问外部数据，在知识图谱中进行遍历。在神经元编程/解释器中，作者提出将外部状态广泛化，使该算法不仅可以建模存储，也可以建模真实世界中的状态（例如机械臂的，摄像头接收的图像等）。算法通过对外部状态的观察，优选一个预先习得的程序来执行，而程序本身又对外部世界造成影响。此外，学界提出了多种对长短时记忆网络（LSTM）的改进方法，使其不仅拥有状态式的短时记忆，也能够结构化的数据进行存取：例如Facebook AI研究院学者提出，可以在LSTM中增加一个栈，入栈出栈的功能由位移式的连接和对操作指令的预测机构实现。这类方法面临的挑战在于过度依赖概率性的决策；由于缺少验证机制，甚至不能得到一个“合适”的结果；其次，完全基于神经网络的方法都试图一次性得到答案，也就是说即使能验证出错误，也没有一个明确的方案指导如何撤销错误并重试。

　　令人感到乐观的是，近几年来上述两派观点开始融合，实现了前所未有的效率提升：神经网络使算法具有了一定的直觉，能够根据当前的程序和数据猜测下一条语句，而搜索方提供了试错的机会，如果神经网络犯了错误，搜索框架能凭借记忆撤销错误的代码而转向别的方向思考。可以预见，随着这一结合打开新的思，有利于将人工智能推向越来越广的应用场景。漫漫其修远兮，我们离机器像人一样思考还有相当的距离。但是我们相信，人的智慧是无穷的。随着计算机科学、认知科学、生命科学等众多学科在此汇聚一堂，学者们在愈加深入地理解机器的同时，也会更多地了解我们自己，人机并进，勇攀科学的高峰。

　　如果你也对这个题目感兴趣，欢迎访问我们微软亚洲研究院机器学习组网页：

　　李亚韬现任微软亚洲研究院副研究员，在机器学习组从事分布式计算、图数据库、查询语言和人工智能方面的研究，研究兴趣包括分布式计算平台、知识图谱存储与查询方案，程序语言设计以及符号式机器学习等，是微软图引擎(Graph Engine)的主要设计者与开发者之一。

　　微软亚洲研究院机器学习组一直致力于推动机器学习理论、算法和应用的学术前沿。我们的研究课题涉及机器学习和人工智能研究的各个方面，目前的研究重点为深度学习、增强学习、分布式机器学习和符号学习。在过去的十几年间，我们在国际会议和学术期刊上发表了大量高质量论文，并把先进的机器学习技术应用到微软很多产品中解决实际问题。我们向开源社区贡献的微软分布式机器学习工具包 (DMTK) 和微软图引擎 (Graph Engine) 受到了开发社区的广泛关注。

　　机器学习组现招聘实习生，工作内容涉及深度学习、增强学习，分布式机器学习和符号学习等领域的研究及应用。具体工作内容根据个人兴趣和能力确定。要求热爱科研，对机器学习和人工智能研究充满兴趣；有较强的编程能力；有良好的沟通和团队协作能力；半年以上实习期。

　　感兴趣的同学可以下载并填写申请表（申请表链接： 点击阅读原文即可查看）并将其与完整的中英文简历（PDF/Word/Txt/Html形式）一同发送至：ml-

　　感谢你关注“微软研究院AI头条”，我们期待你的留言和，共建交流平台。来稿请寄：。