We study the problem of learning differentiable functions expressed as programs in a domain-specific language. Such programmatic models can offer benefits such as composability and interpretability; however, learning them requires optimizing over a combinatorial space of program "architectures". We frame this optimization problem as a search in a weighted graph whose paths encode top-down derivations of program syntax. Our key innovation is to view various classes of neural networks as continuous relaxations over the space of programs, which can then be used to complete any partial program. This relaxed program is differentiable and can be trained end-to-end, and the resulting training loss is an approximately admissible heuristic that can guide the combinatorial search. We instantiate our approach on top of the A-star algorithm and an iteratively deepened branch-and-bound search, and use these algorithms to learn programmatic classifiers in three sequence classification tasks. Our experiments show that the algorithms outperform state-of-the-art methods for program learning, and that they discover programmatic classifiers that yield natural interpretations and achieve competitive accuracy.
翻译:我们研究的是学习不同功能的问题,这些不同功能表现为特定领域的语言中的程序。这样的程序模型可以带来一些好处,例如可变性和可解释性;然而,学习它们需要优化于“建筑”程序的组合空间。我们把这个优化问题设置为一个加权图,其路径编码了程序语法的自上而下衍生。我们的关键创新是将各种神经网络的种类视为程序空间的连续放松,然后可以用来完成任何部分程序。这个宽松的程序是不同的,可以经过培训,最终可以接受,因此产生的培训损失是一种可被接受的超常,可以指导组合式搜索。我们在A星算法的顶端即刻使用我们的方法,并反复深化分支和范围搜索,用这些算法来学习三个序列分类任务的方案分类师。我们的实验表明,算法超越了程序学习的现代方法,它们发现了产生自然解释并实现竞争性准确性的方案分类师。