Abstract
Plenty of existing work has analyzed the abilities of the transformer architecture by describing its representational capacity with formal models of computation. However, the focus so far has been on analyzing the architecture in terms of language \emph{acceptance}. We contend that this is an ill-suited problem in the study of \emph{language models} (LMs), which are definitionally \emph{probability distributions} over strings. In this paper, we focus on the relationship between transformer LMs and $n$-gram LMs, a simple and historically relevant class of language models. We show that transformer LMs using the hard or sparse attention mechanisms can exactly represent any $n$-gram LM, giving us a concrete lower bound on their probabilistic representational capacity. This provides a first step towards understanding the mechanisms that transformer LMs can use to represent probability distributions over strings.
Abstract (translated)
大量现有工作通过用计算模型描述Transformer架构的表示能力来分析Transformer架构的能力。然而，目前的研究主要集中在分析语言接受性方面。我们认为，这对语言模型的研究来说是一个不适合的问题，因为它们定义为字符串上的概率分布。在本文中，我们将关注Transformer LMs和$n$-gram LMs之间的关系，这是语言模型中一个简单且具有历史相关性的类。我们证明了，使用硬或稀疏注意机制的Transformer LMs可以准确地表示任何$n$-gram LM，这为我们提供了关于它们概率表示能力的一个具体下界。这为理解Transformer LMs如何表示字符串上的概率分布提供了一个初步步骤。
URL
https://arxiv.org/abs/2404.14994
