Differentiable Synthesis of Program Architectures

Guofeng Cui, He ZhuNeurIPS 2021 · OpenReview

TL;DR

Researchers have developed dPads, a new method for program synthesis that swaps slow, discrete search for efficient gradient descent. By relaxing a program's "grammar" into a continuous space, they can "train" the program's structure and parameters simultaneously, discovering highly interpretable models for complex sequence classification tasks much faster than previous state-of-the-art methods.

What Problem Does This Paper Address?

Deep learning is powerful but often acts as a "black box." Program synthesis offers an alternative: instead of a massive neural network, we "grow" a small, human-readable program in a Domain-Specific Language (DSL) to solve a task. These programs are interpretable, modular, and can be easily audited.

The catch? Finding the right "architecture" for a program is a nightmare. Because programs are made of discrete building blocks (like if-then-else, map, or add), the number of possible combinations explodes exponentially as programs get longer. Previous methods tried to solve this by enumerating possibilities or using smart "guessing" (heuristics) with algorithms like A* search. However, these are still fundamentally limited by the discrete, combinatorial nature of the search space, making them slow and often unable to find the best programs for complex data.

Methods

The authors introduce dPads (domain-specific Program architecture differentiable synthesis), which borrows an idea from Neural Architecture Search (NAS) called continuous relaxation.

  1. Program Derivation Graphs: They represent all possible programs as paths through a graph. Nodes are "partial" programs with missing pieces, and edges are the grammar rules used to fill those pieces.
  2. Continuous Relaxation: Instead of picking one rule at a time, they use a softmax over all possible rules. This allows them to assign "weights" to different paths. Now, the "best" program structure can be found using gradient descent—the same math used to train neural networks.
  3. Node Sharing: To prevent the graph from becoming too massive, they allow different partial programs to share the same "child" nodes if they use the same grammar rules. This significantly compresses the search space.
  4. Iterative Graph Unfolding: They don't build the whole graph at once. They start with a shallow graph, use neural networks to "fill in" the missing parts temporarily, train to see which paths look promising, prune the bad ones (Top-N preservation), and then expand the promising paths deeper.
Iterative graph unfolding process in dPads
  1. Heuristic Search: Once the graph is optimized, they use a search algorithm guided by the learned weights to extract the final, discrete program.

Datasets

The authors evaluated dPads on four challenging sequence classification benchmarks:

  • Crim13-sniff: Detecting social behaviors (sniffing) between pairs of mice.
  • Fly-vs-fly: Classifying 7 different interaction behaviors between fruit flies.
  • Basketball: Predicting which player has the ball or if a pass is occurring based on player trajectories.
  • Skeletics 152: Classifying 10 different human pose actions from video skeleton data.

Key Insights and Ideas

  • Differentiable is Faster: By turning program synthesis into an optimization problem rather than a search problem, dPads avoids the "combinatorial explosion" that plagues discrete search.
  • The Power of Node Sharing: Without node sharing, the search space for programs is too rich for standard differentiable methods. Sharing nodes based on function types and arities makes the problem tractable.
  • Neural Heuristics: Using neural networks to approximate "missing" code during the search process allows the algorithm to evaluate the potential of a partial program before it's fully built.
  • Interpretability vs. Performance: The synthesized programs are remarkably simple—often just a few lines of code—yet they achieve performance nearly as good as complex, opaque Recurrent Neural Networks (RNNs).

Key Results

  • Higher Accuracy: dPads consistently achieved higher $F_1$ scores than the previous state-of-the-art (NEAR). For example, on the Fly-vs-fly dataset, dPads reached an $F_1$ of 0.887 compared to NEAR's 0.828.
  • Massive Speedups: On the Basketball dataset, dPads found the optimal program 70% faster than A*-based search (174 minutes vs. 553 minutes).
Performance comparison of dPads against baselines
  • Human-Readable Code: The paper showcases programs that use intuitive logic, proving that the method doesn't sacrifice clarity for performance.

Limitations and Future Work

  • Gradient Bias: Like many differentiable search methods, there is a risk of the algorithm "overfitting" to certain paths that provide quick gradient descent but lead to sub-optimal final programs. The authors use a search phase at the end to mitigate this.
  • DSL Dependency: The success of the method depends on having a well-designed Domain-Specific Language (DSL) and a library of differentiable primitives.
  • Future Directions: The authors suggest applying formal program reasoning to these synthesized models to further enhance their security, fairness, and trustworthiness. They also aim to expand the method beyond classification to tasks like cryptographic circuit synthesis.

Summary updated

Abstract

Differentiable programs have recently attracted much interest due to their interpretability, compositionality, and their efficiency to leverage differentiable training. However, synthesizing differentiable programs requires optimizing over a combinatorial, rapidly exploded space of program architectures. Despite the development of effective pruning heuristics, previous works essentially enumerate the discrete search space of program architectures, which is inefficient. We propose to encode program architecture search as learning the probability distribution over all possible program derivations induced by a context-free grammar. This allows the search algorithm to efficiently prune away unlikely program derivations to synthesize optimal program architectures. To this end, an efficient gradient-descent based method is developed to conduct program architecture search in a continuous relaxation of the discrete space of grammar rules. Experiment results on four sequence classification tasks demonstrate that our program synthesizer excels in discovering program architectures that lead to differentiable programs with higher F1 scores, while being more efficient than state-of-the-art program synthesis methods.
BibTeX
@inproceedings{cui2021differentiable,
  author = {Guofeng Cui and He Zhu},
  title = {{Differentiable Synthesis of Program Architectures}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=ivXd1iOKx9M},
}
Figure