“If you are interested in learning more about the limits of gradient descent, you should look into the TerpreT problem [1].”
TerpreT: A Probabilistic Programming Language for Program Induction
用领域专用语言比较各种归纳程序合成的推断算法
论文研究归纳程序合成的机器学习表述:给定输入输出样例,合成能产生对应输出的源代码。核心贡献是 TerpreT,一种类似概率编程语言的 DSL,把程序表示与解释器模型的规范同推断算法分离,使得从同一份规范出发可自动用梯度下降、LP 松弛、离散可满足性求解和 Sketch 四种后端做推断。实验的关键发现是:约束求解器优于基于梯度下降和 LP 的方案。
评论者用它说明梯度下降并不是程序归纳与程序搜索的万能方法,提供了一个梯度下降吃力的具体问题的例子。
学习路径
读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出这条路径先建立「可微外部记忆与可微程序解释器」这一类神经程序归纳模型的认识,再读 TerpreT 如何用统一的 DSL 把它们和传统约束求解放在一起比较。
- 1
神经图灵机是 TerpreT 所比较的神经程序归纳路线的起点:用可微记忆学习简单算法。
读读控制器加读写头的结构,以及基于内容和基于位置的寻址;复制、排序等任务的结果可略读。
- 2
把栈、队列等结构做成可微记忆,是神经程序归纳里另一类归纳偏置。
读抓可微栈 / 队列的连续化操作思路,以及它如何让网络更容易泛化到更长的序列。
- 3
NPI 用程序嵌入和核心网络学习调用子程序,是神经程序合成的代表之一。
读抓核心网络、程序记忆和环境编码三部分如何协作;关注它需要强监督(执行轨迹)这一点。
- 4
∂4 用可微 Forth 解释器配合程序草图,只需输入输出样例,与 TerpreT 研究的问题设定最接近。
读抓程序草图加可微解释器的思路:哪些部分写死、哪些空位由梯度下降填;对比 TerpreT 中的同类设定。
- 5TerpreT: A Probabilistic Programming Language for Program Induction
目标论文:用统一的 DSL 描述程序合成问题,并比较梯度下降、线性规划、SMT 等多种后端。
读先看 TerpreT 语言怎样描述程序与解释器,再看不同推断后端的对比实验;重点是为什么梯度方法在许多问题上不如传统求解器。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“See also this paper for a comparison of programming by example using gradient descent versus more standard alternatives:”
“If you're interested in these kinds of things, many years ago we created TerpreT (TerpreT and [LINK]) to look into generic program synthesis problems”
“gradient descent may not always be the best approach to such problems (e.g., TerpreT).”
- TerpreT: A Probabilistic Programming Language for Program Induction by MSR ↗bunelr · 2016-08-17 · 2 分