Self-Attention Networks Can Process Bounded Hierarchical Languages
Self-Attention Networks Can Process Bounded Hierarchical Languages
复制标题
DOI：
10.18653/v1/2021.acl-long.292
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Shunyu Yao;Binghui Peng;C. Papadimitriou;Karthik Narasimhan
中科院分区：
文献类型：
--
作者：
Shunyu Yao;Binghui Peng;C. Papadimitriou;Karthik Narasimhan
尽管自注意力网络在自然语言处理（NLP）中表现出色，但最近被证明在处理具有层次结构的形式语言（如由\(k\)种类型的良好嵌套括号组成的Dyck - \(k\)语言）时存在局限性。这表明，对于形式语言来说能力过弱的模型却能很好地近似自然语言，或者说层次结构和递归在自然语言中的作用可能是有限的。我们通过证明自注意力网络能够处理Dyck - (\(k\), \(D\))（即Dyck - \(k\)中深度受\(D\)限制的子集，它可以说更好地捕捉了自然语言的有限层次结构）来对这一暗示进行限定。具体而言，我们构建了一个具有\(D + 1\)层且每层每个标记的内存大小为\(O(\log k)\)的硬注意力网络来识别Dyck - (\(k\), \(D\))，以及一个具有两层且内存大小为\(O(\log k)\)的软注意力网络来生成Dyck - (\(k\), \(D\))。实验表明，在Dyck - (\(k\), \(D\))上训练的自注意力网络能够以近乎完美的准确率泛化到更长的输入，并且也验证了自注意力网络相对于循环网络在理论内存上的优势。
Despite their impressive performance in NLP, self-attention networks were recently proved to be limited for processing formal languages with hierarchical structure, such as Dyck-k, the language consisting of well-nested parentheses of k types. This suggested that natural language can be approximated well with models that are too weak for formal languages, or that the role of hierarchy and recursion in natural language might be limited. We qualify this implication by proving that self-attention networks can process Dyck-(k, D), the subset of Dyck-k with depth bounded by D, which arguably better captures the bounded hierarchical structure of natural language. Specifically, we construct a hard-attention network with D+1 layers and O(log k) memory size (per token per layer) that recognizes Dyck-(k, D), and a soft-attention network with two layers and O(log k) memory size that generates Dyck-(k, D). Experiments show that self-attention networks trained on Dyck-(k, D) generalize to longer inputs with near-perfect accuracy, and also verify the theoretical memory advantage of self-attention networks over recurrent networks.