ICLR 2018 | 彩云科技提出结合组合子抽象的神经编程器-解释器，提升通用性和可学习性

选自OpenReview

作者：Da Xiao、Jo-Yu Liao、Xingyuan Yuan

机器之心编译

参与：李舒阳、刘晓坤

近日，ICLR 2018 接收论文公布，国内人工智能公司彩云科技的一篇论文被此大会接收。在此论文中，作者们通过引入组合子抽象的方法，可以建立一种新的架构 CNPI，使得核心控制器需要解释的程序显著减少且程序复杂度显著降低，从而克服神经编程器-解释器（NPI）在通用性和可学习性存在局限性的问题。

论文：IMPROVING THE UNIVERSALITY AND LEARNABILITY OF NEURAL PROGRAMMER-INTERPRETERS WITH COMBINATOR ABSTRACTION

论文地址：https://openreview.net/pdf?id=rJlMAAeC-

摘要：为了克服神经编程器-解释器（NPI）在通用性和可学习性方面的局限，本文提出在神经编程中引入组合子抽象（combinator abstraction）方法，并为此提出了 NPI 的一种新架构——组合神经编程器-解释器（CNPI）。有了组合子抽象，CNPI 的核心控制器需要解释的程序显著减少且程序复杂度显著降低，同时在核心控制器与其他组件的协同作用下，CNPI 仍然可以表示和解释任意复杂度的程序。本文提出用四个组合子来表征最常见的四种编程模式。由于组合子数量有限，形式简单，并且减少了核心控制器的解释工作量，我们可以构造出一个 CNPI，使之适用于所有可「组合子化」（即可用组合子描述）的程序，这样足以解决大多数算法任务。此外，通过恰当地设计课程，可能直接用策略梯度增强学习来训练 CNPI，无需提供程序执行轨迹。

1 引言

教机器学程序是个有挑战的任务。研究者提出了很多模型，例如神经图灵机（Graves et al., 2014）、可微分神经计算机（Graves et al., 2016）、神经 GPU（Kaiser & Sutskever, 2015）、神经编程器（Neelakantan et al., 2015）、神经随机存取机（Kurach et al., 2015），还有神经编程器-解释器（Reed & de Freitas, 2016）。这些模型通常含有可微分存取的存储组件。大多数模型以程序输入-输出对作为训练数据，训练后的神经网络可以成为特定的目标程序，模仿一种特定的图灵机。

这些模型中的一个特例是神经编程器-解释器（NPI）（Reed & de Freitas, 2016）及其支持递归的扩展形式（Cai et al., 2017，在该论文中被称为 RNPI）。NPI 包含三个组件：一个核心控制器，通常由递归神经网络（RNN）实现；一个程序存储器，用于存储已学得程序的嵌入向量；还有多个特定域编码器，让单个 NPI 在多种环境中均可运行。核心控制器不学习任何特定的程序，而是学习解释任何一个用向量表示的程序，即模仿一个通用图灵机。核心控制器（即解释器）与已学得程序的存储器（即编程器）相结合，使 NPI 能够通过合子程序来学习新的程序，其架构更灵活也更具可组合性。然而，NPI 在理论和实际应用方面依然存在一些局限。

NPI 模型之所以可能适用于多任务学习、迁移学习和终身学习，是因为研究者假设 NPI 理论上具有通用性，即能够表达和解释任何程序。由于 NPI 仅靠核心控制器来解释程序，通用性意味着一个固定的核能够解释潜在的大量程序。想要持续地学习新程序并复用已学得的程序，一个普适且固定的核至关重要，因为一旦核的权重改变，学习了新程序就可能没法解释学过的旧程序了。尽管最早提出 NPI 的论文（Reed & de Freitas, 2016）实验显示单个共享的核可以解释 21 个程序，涵盖五种任务，并且训练过的固定核 NPI 还可以学习一个简单的新程序 MAX，但尚不清楚普适的 NPI 是否存在、究竟能够多普适。具体而言，考虑到所有可能的程序是个无限集，能够被一个固定核解释的程序子集并没有被显式定义。就算存在普适的 NPI，用 Cai et al. (2017) 论文中提出的验证方法也很难保证其通用性，因为需要验证无穷个程序。

实际应用时，Reed & de Freitas (2016) 的 NPI 模型需要强监督训练，也就是以程序的示例执行轨迹为训练数据。获取这种形式的训练数据，其成本往往高于获取程序输入-输出示例。相比之下，弱监督训练才是充分发挥 NPI 潜力的理想选择。

为了克服 NPI 的上述局限，本文提出将组合子抽象方法引入 NPI 模型，并为此设计了必要的组件和机制来增强原有的 NPI 架构。新架构被称为组合神经编程器-解释器（CNPI）。组合子，即高阶函数，是函数式编程中一种重要的抽象技巧，本文借用组合子的概念来表示不同程序共有的一些编程模式。

2 组合子抽象概述

2.1 综述 NPI 及其局限

本节将概述 Reed & de Freitas (2016) 和 Cai et al. (2017) 论文中的 NPI 架构，分析架构的局限，这也是本文提出组合子抽象的动机。NPI 模型包含三个具有学习能力的组件：一个与任务无关的核心控制器、一个程序存储器，以及让 NPI 适用于多种环境的多个特定域编码器。核心控制器是一个长短期记忆（LSTM）网络（Hochreiter & Schmidhuber, 1997），作为各个程序之间的路由。在每个时间步上，核心控制器可以选择以特定的参数调用其他程序，也可以终止调用当前程序。当程序返回后，控制权将返给主调程序，即主调程序的 LSTM 隐藏单元和程序嵌入向量弹出程序调用栈，从中断处继续执行主调函数。

NPI 的推理过程如下（详见论文 Reed & de Freitas (2016) 第 3.1 节和算法 1）。在时间步 t 上，编码器 f_enc 接收环境观测量 e_t 和参数 a_t，输出状态 s_t。核心 LSTM 网络 f_lstm 接收状态 s_t、程序嵌入向量 p_t∈ R^P 和上一个隐状态 h_t-1，从而更新自身的隐状态 h_t。根据最顶层 LSTM 的隐状态，多个解码器可产生如下输出：返回概率 r_t、下一个程序的键嵌入向量 k_t+1，以及下一个程序的参数 a_t+1。通过对比键嵌入向量 k_t+1 与键存储器 M_key 中的每一行，可得到下一个程序的 ID。于是，从存储了 N 个程序的程序存储器 M_prog 中可以获取下一个程序的嵌入向量：

以上描述的 NPI 架构有两个局限。第一，由上式可知，程序存储器中保存着已学得的全部 N 个程序，在每个时间步上，核心控制器都要从这 N 个程序里选择一个调用。随着数量 N 增大到成百上千，让单个核心控制器正确解释程序会变得越来越困难。更难的是，核心控制器在学习新程序的同时，还不能忘记已学得的旧程序。第二，不同名称、不同功能的程序往往有一些共同的潜在编程模式。以 Reed & de Freitas (2016) 和 Cai et al. (2017) 论文中的两个程序为例（见图 1）：ADD1 程序执行多位数十进制加法，BSTEP 程序执行冒泡排序中的一次冒泡。这里采用 Cai et al. (2017) 论文中的递归形式。两个程序的循环模式非常相似，然而核心控制器需要分别学习这两个程序，无法利用他们共有的模式来提高学习效率。于是，以普适为目标的核心控制器需要学习无穷个程序。由于存在以上两个局限，我们认为即使可以构造普适的 NPI，挑战也非常大。

图 1：传统 NPI 与引入组合子抽象的 CNPI

2.2 本文的组合子抽象方法

为了克服 NPI 的局限，本文提出在 NPI 架构中引入组合子抽象。函数式编程中，作为有力的抽象手段，组合子是一种特殊高阶函数，可以增强编程语言的表达力。本文将组合子概念引入到神经编程中，使之成为提升 NPI 通用性的关键角色。

组合子定义为一个「程序模板」，形参作为要填的空，可以是要调用的子程序。用另一个称为应用子（applier）的程序来包裹组合子，即可表示实际的程序。当执行组合子的时候，应用子调用组合子，将实参传递给组合子。组合子的实参可以是一组实际的程序，也可以是包裹结构的程序（即应用子），这样就能反复组合，构造出越来越复杂的程序了。与原始 NPI 相似的是，核心控制器对组合子的解释取决于一个轻量级的特定域编码器的输出。这个编码器我们称为探测子（detector），也由应用子动态地提供。图 1 为引入组合子抽象的 NPI 新架构。

在 CNPI 架构中，组合子是唯一需要被核心控制器解释的程序类型。由于限定了组合子只能调用传递给它的参数（程序），在每个时间步上可调用程序的选择范围就从不断增加的 N 个缩减到常数 K 个，K 是组合子可调用参数的最大数量（本文模型中 ≤ 9）。同时，与无限个潜在程序相比，有用的组合子数量有限而且通常很少。本文构造的组合子集合仅包含四个，用于表征最常见的四种编程模式。我们将证明，一个相当小的核与其他组件协同作用，就足以构造出普适的 CNPI。

3 CNPI 模型

3.1 组合子和组合程序

本文提出用四个组合子来表征算法任务中最常见的四种编程模式：顺序模式、条件模式、线性递归和树形递归（即多重递归）。四个组合子的伪代码见图 2。

图 2：组合子集合的伪代码

图 3：BSTEP（气泡排序）写成组合程序的示例。其中 NOP 是特殊的的元动作（ACT），不进行任何操作。

3.2 CNPI 架构及算法

表 1：CNPI 与 NPI、RNPI 的定性比较

5 实验

5.1 监督学习结果

图 5：可调用参数的数量 K=4 时，对应组合子集合包含 57 个组合子。用三种模型分别学习整个集合，模型 LSTM 单元数与预测精度的关系。

表 3：单个固定核学习新程序/组合子并记忆旧程序/组合子的准确率。用新程序/组合子训练，RNPI 和 CNPI 取得的最高准确率分别为 100% 和 97.7%。

5.2 增强学习的课程

表 4：用增强学习训练 CNPI 执行排序任务的课程设计。要学习的程序（包括探测子）显示为加粗蓝色字。为辅助学习排序任务，课程中增加了几个动作（ACT）：OUT_x 是将指针 x 处的元素写入 P3 指向的位置，并让 P3 所指位置向前移动一步；CLEAR_x 是将指针 x 处的元素置为 -1；OUTCLEAR_x 是将指针 x 处的元素输出，然后置为 -1。这里的排序任务并非在原位操作，而是将每个回合找到的最大元素写入 P3 指向的另一个数组中。

5.3 增强学习结果

表 5：采用不同的采样方法及课程时，增强学习训练 CNPI 核的成功率。

表 6：增强学习训练 CNPI、RNPI 模型，完成简单版任务和最终版任务的成功率。

表 7：采用两类探测子、有无瞬态条件时，学习组合子 linrec（线性递归）的成功率比较。

6 结论

通过在函数式编程中结合组合子抽象，本文提出的 CNPI 首次解决了 NPI 提升通用性和可学习性的问题。分析和实验结果表明 CNPI 对于所有「可组合子化」的程序都是通用的，并且无论用强监督还是弱监督都可以训练。研究者认为这个方法足够通用，除了解决算法任务之外，还存在潜在的应用。其中一个可能的应用场景是用强化学习训练智能体以服从指令和进行泛化（例如, Oh et al. (2017), Andreas et al. (2017), Denil et al. (2017)）。自然语言中包含了「高阶」词，例如「然后」、「两次」等，这些词在语言表达中很重要，但普通的序列到序列模型（Lake & Baroni, 2017）可能很难理解其意义。通过将这类词表示成组合子，并将智能体结合类似 CNPI 的组件，就有可能构造出性能更强的智能体，不仅可以根据简明的指令做出更复杂、更结构化的行为，而且由于抽象程度的提升，泛化性能也会提升。此类探索将在未来的研究中进行。

本文为机器之心编译，转载请联系本公众号获得授权。