arXiv:2006.08084 · 中英对照阅读
Neural Execution Engines: Learning to Execute Subroutines
中文速览
神经网络能模仿排序、最短路径等算法,却常常一遇到更长的输入或训练时没见过的数字就出错,问题在于它既难以准确判断该看哪里,也难以表示大范围数值。作者提出神经执行引擎(Neural Execution Engine),让模型在输出计算结果的同时预测接下来该关注哪个位置,并用这个指针动态更新注意力范围;数字则用二进制表示,让模型从加法、乘法等任务中学出有结构的数值表示。实验显示,这种方法在远长于训练数据的输入上也能近乎完美地完成多种算法子步骤,而且二进制表示能较好地补全训练中没出现过的数字。它说明,给模型明确的“下一步看哪里”机制并选对数字表示,有望让神经网络从记住样例走向真正学会可迁移的算法。
摘要
A significant effort has been made to train neural networks that replicate algorithmic reasoning, but they often fail to learn the abstract concepts underlying these algorithms. This is evidenced by their inability to generalize to data distributions that are outside of their restricted training sets, namely larger inputs and unseen data. We study these generalization issues at the level of numerical subroutines that comprise common algorithms like sorting, shortest paths, and minimum spanning trees. First, we observe that transformer-based sequence-to-sequence models can learn subroutines like sorting a list of numbers, but their performance rapidly degrades as the length of lists grows beyond those found in the training set. We demonstrate that this is due to attention weights that lose fidelity with longer sequences, particularly when the input numbers are numerically similar. To address the issue, we propose a learned conditional masking mechanism, which enables the model to strongly generalize far outside of its training range with near-perfect accuracy on a variety of algorithms. Second, to generalize to unseen data, we show that encoding numbers with a binary representation leads to embeddings with rich structure once trained on downstream tasks like addition or multiplication. This allows the embedding to handle missing data by faithfully interpolating numbers not seen during training.
术语表
- algorithmic reasoning
- 算法推理
- strong generalization
- 强泛化
- numerical subroutine
- 数值子程序
- subroutine imitation
- 子程序模仿
- sequence-to-sequence model
- 序列到序列模型
- transformer
- Transformer
- self-attention
- 自注意力
- attention weight
- 注意力权重
- attention entropy
- 注意力熵
- self-attention mask
- 自注意力掩码
- conditional masking mechanism
- 条件掩码机制
- Neural Execution Engine (NEE)
- Neural Execution Engine(NEE,神经执行引擎)
- pointer
- 指针
- pointer manipulation
- 指针操作
- binary representation
- 二进制表示
- binary embedding
- 二进制嵌入
- interpolation
- 插值
- selection sort
- 选择排序
- merge sort
- 归并排序
- Dijkstra's algorithm
- Dijkstra 算法
- shortest paths
- 最短路径
- Prim's algorithm
- Prim 算法
- minimum spanning tree
- 最小生成树
- comparison subroutine
- 比较子程序
- arithmetic subroutine
- 算术子程序
- addition
- 加法
- multiplication
- 乘法
- Graph Attention Networks
- 图注意力网络