Aha.
正在载入中英对照阅读…

arXiv:2006.08084 · 中英对照阅读

Neural Execution Engines: Learning to Execute Subroutines

Yujun Yan、Kevin Swersky、Danai Koutra、Parthasarathy Ranganathan、Milad Hashemi

中文速览

神经网络能模仿排序、最短路径等算法,却常常一遇到更长的输入或训练时没见过的数字就出错,问题在于它既难以准确判断该看哪里,也难以表示大范围数值。作者提出神经执行引擎(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
图注意力网络