A Caltech Library Service

Learning Differentiable Programs with Admissible Neural Heuristics

Shah, Ameesh and Zhan, Eric and Sun, Jennifer J. and Verma, Abhinav and Yue, Yisong and Chaudhuri, Swarat (2020) Learning Differentiable Programs with Admissible Neural Heuristics. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Sun, Jennifer J.0000-0002-0906-6589
Verma, Abhinav0000-0002-9820-8285
Yue, Yisong0000-0001-9127-1989
Record Number:CaltechAUTHORS:20201110-085241409
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:106585
Deposited By: Tony Diaz
Deposited On:10 Nov 2020 17:32
Last Modified:10 Nov 2020 17:32

Repository Staff Only: item control page