Deep learning has led to encouraging successes in many challenging tasks. However, a deep neural model lacks interpretability due to the difficulty of identifying how the model's control logic relates to its network structure. Differentiable programs have recently attracted much interest due to their interpretability, compositionality, and efficiency to leverage differentiable training. However, synthesizing differentiable programs requires optimizing over a combinatorial, non-differentiable, and rapidly exploded space of program structures. Even with good heuristics, program synthesis by enumerating discrete program structures does not scale in general. We propose to encode program structure search as learning the probability distribution of high-quality structures induced by a context-free grammar. In a continuous relaxation of the search space defined by the grammar rules, our algorithm learns the discrete structure of a differentiable program using efficient gradient methods. Experiment results over application domains including classification, reinforcement learning, and recommendation systems demonstrate that our algorithm excels in discovering optimal differentiable programs that are highly interpretable.

Speaker: He Zhu https://herowanzhu.github.io/