“This work referenced also in the OP paper uses recurrent neural nets and a genetic algorithm to evolve the minimal number of states needed:”
按年被提到
20212022 · 3 次2026
Minimum Description Length Recurrent Neural Networks
最小描述长度循环神经网络
Nur Lan, Michal Geyer, Emmanuel Chemla, Roni Katzir · 2021
以最小描述长度为目标训练的小型 RNN 能精确掌握形式语言
被提及 · 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
- 2
- 3
给 RNN 加栈来学习计数和 a^n b^n 一类的模式,与目标论文的任务相同。
读可微栈的结构,以及在计数语言上的实验。
- 4
从 RNN 中提取自动机,是检验网络内部是否学到规则的方法。
读查询和反例的学习算法。
- 5
- 6Minimum Description Length Recurrent Neural Networks
目标论文:以最小描述长度为目标训练小型 RNN。
读MDL 目标函数、学到的形式语言和对精度的形式化证明。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及引用puttycat · 2022-06
指出原论文引用的工作用 RNN 和遗传算法演化出最少状态数
引用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%
被提交为 story · 3 次
- Minimum Description Length Recurrent Neural Networks ↗botencat · 2022-04-03 · 2 分
- Minimum Description Length Recurrent Neural Networks ↗schmidt87 · 2022-06-10 · 1 分
- Minimum Description Length Recurrent Neural Networks (2022) ↗puttycat · 2024-05-19 · 1 分