按年被提到
20212022 · 3 次2026
大模型与语言模型›序列模型与注意力机制·arXiv:2111.00600 · cs.CL

Minimum Description Length Recurrent Neural Networks

最小描述长度循环神经网络
Nur Lan, Michal Geyer, Emmanuel Chemla, Roni Katzir · 2021

以最小描述长度为目标训练的小型 RNN 能精确掌握形式语言

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2022-04-03 · 最近 2024-05-19
3不同的人
4活跃月份
5讨论串
12被引(OpenAlex)

论文训练神经网络优化最小描述长度(MDL)得分,在网络复杂度与任务准确率之间取得平衡。这样得到的网络能掌握需要记忆的任务并超越上下文无关语言,例如 aⁿbⁿ、aⁿbⁿcⁿ、aⁿb²ⁿ、aⁿbᵐcⁿ⁺ᵐ,还能做加法,且常常达到 100% 准确率。网络很小、内部结构透明,作者因此给出形式化证明,说明其完美准确率对任意输入序列都成立。

HN 为什么提它

评论者引用它作为近期工作:优化 MDL(Kolmogorov 复杂度)能得到可证明 100% 准确的二进制加法网络,或用于说明用进化方法压缩状态数的思路。

方法难度 4 / 5约 40 分钟经得起时间
读之前最好知道
1循环神经网络(RNN)
2最小描述长度(MDL)与 Kolmogorov 复杂度
3形式语言与上下文无关文法
4形式化证明基础

学习路径

读这篇之前,按顺序读书架上的 5 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

这条路径先看神经网络学习算法和形式语言的早期工作,再看栈增强网络和自动机提取,用来理解最小描述长度如何让小 RNN 精确学会 a^n b^n 之类的语言。

  1. 1
    Learning to Execute学习执行 · 2014

    让 LSTM 学习执行程序和加法,展示了神经网络学习算法的难点。

    读加法任务和课程学习的做法。

  2. 2
    Neural Turing Machines神经图灵机 · 2014

    用外部记忆增强网络学习算法,是目标论文要处理的记忆任务的背景。

    读复制任务以及可微记忆的读写机制。

  3. 3
    Inferring Algorithmic Patterns with Stack-Augmented Recurrent Nets用栈增强的循环网络推断算法模式 · 2015

    给 RNN 加栈来学习计数和 a^n b^n 一类的模式,与目标论文的任务相同。

    读可微栈的结构,以及在计数语言上的实验。

  4. 4

    从 RNN 中提取自动机,是检验网络内部是否学到规则的方法。

    读查询和反例的学习算法。

  5. 5

    同样关注小而结构简单的网络,不靠大量权重训练。

    读网络结构本身带来的归纳偏置;与 MDL 目标思路对比。

  6. 6
    Minimum Description Length Recurrent Neural Networks最小描述长度循环神经网络 · 2021 · 就是这篇

    目标论文:以最小描述长度为目标训练小型 RNN。

    读MDL 目标函数、学到的形式语言和对精度的形式化证明。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用puttycat · 2022-06

“This work referenced also in the OP paper uses recurrent neural nets and a genetic algorithm to evolve the minimal number of states needed:”

指出原论文引用的工作用 RNN 和遗传算法演化出最少状态数
Differentiable Finite State Machines原评论 ↗
引用puttycat · 2023-01

“Recent work on NNs where applying Kolmogorov complexity optimization leads to a network that solves binary addition with a carry-over counter and 100% provable accuracy”

指出应用 Kolmogorov 复杂度优化的网络能做二进制加法,且准确率可证明为 100%
Reverse Engineering a Neural Network's Clever Solution to Binary Addition原评论 ↗
被提交为 story · 3 次