Attention, specifically scaled dot-product attention, has proven effective
for natural language, but it does not have a mechanism for handling
hierarchical patterns of arbitrary nesting depth, which limits its ability to
recognize certain syntactic structures. To address this shortcoming, we propose
stack attention: an attention operator that incorporates stacks, inspired by
their theoretical connections to context-free languages (CFLs). We show that
stack attention is analogous to standard attention, but with a latent model of
syntax that requires no syntactic supervision. We propose two variants: one
related to deterministic pushdown automata (PDAs) and one based on
nondeterministic PDAs, which allows transformers to recognize arbitrary CFLs.
We show that transformers with stack attention are very effective at learning
CFLs that standard transformers struggle on, achieving strong results on a CFL
with theoretically maximal parsing difficulty. We also show that stack
attention is more effective at natural language modeling under a constrained
parameter budget, and we include results on machine translation.

我们提出了堆栈注意力：一种集成堆栈的注意力操作符，其灵感来源于堆栈与上下文无关语言（CFLs）的理论联系，以解决标准注意力无法识别某些句法结构的局限性。我们提出了两种变种：一种与确定性下推自动机（PDAs）相关，一种基于非确定性 PDAs，使得 transformers 能够识别任意 CFLs。我们证明，具有堆栈注意力的 transformers 在学习 CFLs 方面非常有效，能够在理论上具有最大的解析困难的 CFL 上取得强大的结果。我们还证明，堆栈注意力在受约束参数预算下在自然语言建模中更加有效，并包括机器翻译方面的结果。

层叠注意力：提高 Transformer 模型对层次模式建模的能力

Stack Attention: Improving the Ability of Transformers to Model  Hierarchical Patterns

Traditional recurrent neural networks (RNNs) have a fixed, finite number of
memory cells. In theory (assuming bounded range and precision), this limits
their formal language recognition power to regular languages, and in practice,
RNNs have been shown to be unable to learn many context-free languages (CFLs).
In order to expand the class of languages RNNs recognize, prior work has
augmented RNNs with a nondeterministic stack data structure, putting them on
par with pushdown automata and increasing their language recognition power to
CFLs. Nondeterminism is needed for recognizing all CFLs (not just deterministic
CFLs), but in this paper, we show that nondeterminism and the neural controller
interact to produce two more unexpected abilities. First, the nondeterministic
stack RNN can recognize not only CFLs, but also many non-context-free
languages. Second, it can recognize languages with much larger alphabet sizes
than one might expect given the size of its stack alphabet. Finally, to
increase the information capacity in the stack and allow it to solve more
complicated tasks with large alphabet sizes, we propose a new version of the
nondeterministic stack that simulates stacks of vectors rather than discrete
symbols. We demonstrate perplexity improvements with this new model on the Penn
Treebank language modeling benchmark.

通过给循环神经网络增加非确定性堆栈数据结构，可以扩展循环神经网络的语言识别能力，识别上下文无关语言和更多的非上下文无关语言，同时提高信息容量，这可以通过模拟向量堆栈来实现。

非确定性堆栈循环神经网络的惊人计算能力

The Surprising Computational Power of Nondeterministic Stack RNNs

We present a simple encoding for unlabeled noncrossing graphs and show how
its latent counterpart helps us to represent several families of directed and
undirected graphs used in syntactic and semantic parsing of natural language as
context-free languages. The families are separated purely on the basis of
forbidden patterns in latent encoding, eliminating the need to differentiate
the families of non-crossing graphs in inference algorithms: one algorithm
works for all when the search space can be controlled in parser input.

该研究提出了一种用于未标记的无交叉图编码的简单方法，并展示了通过其潜在的对应物，如何代表在自然语言的句法和语义分析中使用的几个有向和无向图族作为上下文无关语言。这些族基于潜在编码中的禁止模式而分离，因此在推理算法中不需要区分非交叉图族，当可以在解析器输入中控制搜索空间时，一个算法适用于所有族。