用信息论方法揭示Transformer如何在上下文中学习变阶马尔可夫链
An Information-Theoretic Approach to Understanding Transformers' In-Context Learning of Variable-Order Markov Chains
- 基于信息论的贝叶斯框架，将变阶马尔可夫链学习建模为最优压缩问题
- 两层及以上Transformer才能有效学习，层数越多性能越优，单层则失败
- 提出可精确实现CTW算法的多层结构，解释为何双层模型表现良好
我们研究Transformer在上下文中学习变阶马尔可夫链（VOMCs）的能力，关注随着上下文示例数量增加时的有限样本精度。与固定阶马尔可夫链（FOMCs）相比，学习VOMCs更具挑战性，因其需额外进行结构学习。该问题天然适合贝叶斯建模，其中信息论领域提出的上下文树加权（CTW）算法提供了最优解。实验发现，单层Transformer无法在上下文中学习VOMCs，而两层及以上结构可成功实现，层数增加带来小幅但显著的性能提升。与此前针对FOMCs的研究不同，仅依赖注意力机制的网络不足以处理VOMCs。为此，我们给出了显式构造：一个含$D+2$层的Transformer可精确实现最大阶数为$D$的VOMC的CTW；另有一个简化的两层结构，通过部分信息近似融合，解释了双层模型为何能有效工作。
原文摘要 · Abstract (English)
We study transformers' in-context learning of variable-length Markov chains (VOMCs), focusing on the finite-sample accuracy as the number of in-context examples increases. Compared to fixed-order Markov chains (FOMCs), learning VOMCs is substantially more challenging due to the additional structural learning component. The problem is naturally suited to a Bayesian formulation, where the context-tree weighting (CTW) algorithm, originally developed in the information theory community for universal data compression, provides an optimal solution. Empirically, we find that single-layer transformers fail to learn VOMCs in context, whereas transformers with two or more layers can succeed, with additional layers yielding modest but noticeable improvements. In contrast to prior results on FOMCs, attention-only networks appear insufficient for VOMCs. To explain these findings, we provide explicit transformer constructions: one with $D+2$ layers that can exactly implement CTW for VOMCs of maximum order $D$, and a simplified two-layer construction that uses partial information for approximate blending, shedding light on why two-layer transformers can perform well.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。