决策树也能做语言生成，还能推理，潜力惊人。
On the Power of Decision Trees in Auto-Regressive Language Modeling
- 用链式思维让决策树模拟自动机与图灵机
- 小规模实验中生成文本质量媲美小型Transformer
- 适合想探索非Transformer架构的研究者
自回归决策树（ARDTs）最初用于时间序列数据，尚未被用于语言建模。本文从理论和实践两方面探索其在该新场景中的应用。理论上，我们证明了ARDTs可通过‘链式思维’计算复杂函数，如模拟自动机、图灵机和稀疏电路，并给出了其规模、深度和计算效率的边界。实证上，我们在简单语言生成任务中训练了ARDTs，结果表明其能生成连贯且语法正确的文本，性能可与更小的Transformer模型相当。此外，我们还展示了将ARDTs应用于Transformer表征之上，可解决复杂推理任务。本研究揭示了ARDTs独特的计算能力，旨在拓展语言模型架构的多样性。
原文摘要 · Abstract (English)
Originally proposed for handling time series data, Auto-regressive Decision Trees (ARDTs) have not yet been explored for language modeling. This paper delves into both the theoretical and practical applications of ARDTs in this new context. We theoretically demonstrate that ARDTs can compute complex functions, such as simulating automata, Turing machines, and sparse circuits, by leveraging "chain-of-thought" computations. Our analysis provides bounds on the size, depth, and computational efficiency of ARDTs, highlighting their surprising computational power. Empirically, we train ARDTs on simple language generation tasks, showing that they can learn to generate coherent and grammatically correct text on par with a smaller Transformer model. Additionally, we show that ARDTs can be used on top of transformer representations to solve complex reasoning tasks. This research reveals the unique computational abilities of ARDTs, aiming to broaden the architectural diversity in language model development.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。