Differentiable Synthesis of Program Architectures
Authors: Guofeng Cui
He Zhu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Program Synthesis
Differentiable Architecture Search

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.

Differentiable Synthesis of Program Architectures
Guofeng Cui Department of Computer Science Rutgers University gc6690cs rutgers.
He Zhu
Department Computer Science Rutgers University hz375dcs rut7eesss.uttgrrs.. edu
Abstract
Differentiable programs have recently attracted much interest due to their inter- pretability, compositionality. and their efficiency to leverage differentiable training. However, synthesizing differentiable programs requires optimizing torial, 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 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 developed to conduct program architecture search in continuous relax- ation 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 Fi scores, while being more efficient than state-of-the-art program synthesis methods.
combina-
Introduction
Program synthesis has recently emerged an effective approach address tasks in several fields where deep learning is applied traditionally. A synthesized program in domain-specific language (DSL) provides a powerful abstraction for summarizing discovered knowledge from data and offers greater interpretability and transferability across tasks than a deep neural network model, while achieving competitive task performance 41..
differentiable program encourages interpretability by using structured symbolic primitives to compose set of differentiable modules with trainable parameters in its architecture. These parameters can be efficiently learned with respect to a differentiable loss function over the program's 's outputs. However, synthesizing reasonable program architecture remains challenging because the architecture search space is discrete and combinatorial. Various enumeration strategies have been developed to explore the program architecture space, including greedy enumeration 2 evolutionary search [5]. and Monte Carlo sampling [6]. To prioritize highly likely top-down search directions in the combinatorial architecture space, NEAR [ uses neural networks to approximate missing expressions in partial program whose Fi score serves as an admissible heuristic to effective graph search algorithms such A [ However, since the discrete program architecture search space is intractably large, enumeration based search strategies are inefficient in general.
We propose encode program architecture search learning the probability distribution over all possible program architecture derivations induced by a context-free DSL grammar. This problem bears similarities with searching the structure of graphical models [9] and neural architecture search. Specifically, to support differentiable search, DARTS 10 uses a composition of softmaxes over all possible candidate operations between fixed set of neural network nodes to relax the discrete search space of neural architectures. However, applying this method to program synthesis is challenging
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

because the program architecture search space is much richer 77]. Firstly, different sets of operations take different input and output types and may only be available at different points of program. Secondly, there is no fixed bound on the number of expressions in a program architecture.
To address the aforementioned challenges, we learn the probability distribution of program archi- tectures in a continuous relaxation of the search space of DSL grammar rules, We conduct program architecture search in a program derivation graph, which nodes encode architectures with missing expressions, and paths encode top-down program derivations. For each partial architecture f on a graph node, we relax the categorical choice of production rules for expanding a missing expression in f to a softmax over all possible production rules with trainable weights. A program derivation graph essentially expresses all possible program derivations under context-free grammar up to a certain depth bound (on the height of program abstract syntax trees), which can be iteratively increased during search to balance accuracy and architecture complexity. We encode program derivation graph itself as differentiable program whose output is weighted by the outputs of all the programs involved. We seek to optimize program architecture weights with respect to an accuracy loss function defined over the encoded program's 's output. The learned weights allow our synthesis algorithm to efficiently prune away search directions to unlikely program derivations to discover optimal programs. Compared with cuumeration-basel synthesis strategies, differentiable program synthesis in the relaxed architecture space is easier and more efficient with gradient- based optimization.
One major challenge of differentiable program architecture synthesis is that program derivation graph involves an exponential number of programs and huge set of trainable variables including architecture weights and program parameters. To curb the large program derivation search space, we introduce node sharing in program derivation graphs and iterative graph unfolding. Node sharing allows two partial architectures to share the same child nodes if the missing expressions in the two architectures can be expanded using the same grammar rules. Iterative graph unfolding allows the synthesis algorithm to construct program derivation graph on the fly focusing higher-quality program derivations than all the rest. These optimization strategies significantly reduce the program architecture search space, scaling differentiable program synthesis to real-world classification tasks. We evaluate our synthesis algorithm in the context of learning classifiers in sequence classification applications. We demonstrate that our algorithm substantially outperforms state-of-the art methods for differentiable program synthesis, and can learn programmatic classifiers that are highly interpretable and are comparable to neural network models in terms of accuracy and Fi-scores.
As a summary, this paper makes three contributions. Firstly, we encode program synthesis as learning the probability distribution of program architectures in a continuous relaxation of the discrete space defined by programming language grammar rules, enabling differentiable program architecture search. Secondly, we instantiate differentiable program architecture synthesis with effective optimization strategies including node sharing and iterative graph unfolding, scaling it to real-world classification tasks. Lastly, present tfate-of-the-art the-art results in learning programmatic classifiers for four sequence classification applications.
2 Problem Formulation
A program in domain-specifie language (DSL) is pair (a, 6), where is discrete program architecture and 9 is a vector of real-valued parameters of the program. Given a specification over the intended input-output behavior of an unknown program, program synthesis aims to discover the program's 's architecture a and optimize the program parameters 0.
In this paper, we focus on learning programmatic classifiers for sequence classification tasks We note that the proposed synthesis technique is applicable to learning any differentiable programs.
Program Architecture Synthesis. A program architecture a is typically synthesized based on a context-free grammar [12]. Such grammar consists of a set of production rules a + {o,); over terminal symbols Σ and nonterminal symbols Y where aę E Y and o, E EUY. As an example, consider the context-free free grammar of DSL for sequence classification depicted in the standard Backus-Naut form 13] in Fig. [ adapted from 77] A terminal in this grammar is a symbol that can appear in a program's 's code, e.g. x and the map function symbol, while a nonterminal stands for a missing expression (or subexpression), e.g. 02 and a3. Any program in the DSL operates over a real vector or a sequence of real vector x. may use constants e, arithmetic operations Add and Multiply, and an If-Then-Elss Else branching construct ITE. To avoid discontinuities for
2

---

= Add a1 02 Multiply on 02 ITE 01 02 03 (s,0(2) map (fun at 21.01) ) æ
mapprefix (fun 01.01) fold (fun x1.01 c SlideWindowArg (fun 21-01)
Figure 1: Context-free DSL Grammar for Sequence Classification (adapted from
Add
Mui
Depth
Add: øj"
1045 0.2 0.35
W
Add
IT.
Depth 1
4 03
2. a.
2.
3
Depth
Figure 2: Program Derivation Graph of the grammar in Fig.
differentiabilityy interpret it in terms of smooth approximation: [ITE(a] 0,02, (z) o ([a]](=)) [x2](x) + (1 [[[,](<)) [[>](()) where a is the sigmoid function. A program may invoke customized library of differentiable, parameterized functions. In context, these functions are in the shape F (z)) that extract a vector consisting of a predefined subset S of the dimensions of input and pass the extracted vector through linear function with trainable parameters 0. A program may also use a set of higher-order combinators to recurse over sequences including the standard map and fold combinators. The higher-order combinators takes input an anonymous function fun zz)(r) that evaluates an expression e(x) over the input x. For sequence the mapprefix higher-order combinator returns a sequence f [x[11 : 1]), f= [ 2l)...... ... [x]] n]). where æ11 i] is the i-th prefix of x. The SlideWindow function computes the average of
sequence over a moving window of frames.
We define the complexity of a program architecture a. Let each grammar rule have non-negative real-valued cost c(r). The structural cost c(a) is the sum of the costs of the multi-set of rules used to create a. Intuitively, program architectures with lower structural cost are more interpretable. In the context of this paper, program synthesis aims learn simple program (in terms of structure cost) that satisfies some specifications over program input-output behaviors. In this paper, we set c(r) = for any production rule r.
Program Synthesis Specifications. {ie) taken input and expect classify i into certain category oμ. Each é is sequence of observations. Each observation captures features extracted at a frame as a 1-dimensional real-valued vector. We aim to synthesize program P(; a, 0) as a classifier with high accuracy and low architecture cost. Our program synthesis goal is formalized as follows:
sequence classification task, a set feature sequences
arg min Ei 0,a
0), ow)] c(a)
where D(ig, 0x) is an unknown distribution over input sequences iz and labels og. The first term of Equation (1) defines some prediction error loss & of program P(-) for classification task over P's predicted labels and the ground truth labels. The second term enforces program synthesis to learn an architecturally simple programmatic classifier.
3 Differentiable Program Architecture Synthesis
We formulate program architecture derivation form of top-down graph traversal. Given the context-free grammar G a DSL, an architecture derivation starts with the initial nonterminal (i.e. the empty architecture), then applies the production rules in G to produce series of partial architectures which consist in expressions made from one or more nonterminals and zero or more terminals, and terminates when complete architecture that does not include any nonterminals is derived.

---

Formally, program architecture synthesis with respect to a context-free grammar G is performed over directed acyclic program derivation graph G = {V, E} where V and E indicate graph nodes and edges. Fig. _ depicts a program derivation graph for the sequence classification grammar in Fig. I node u E V is set of partial or complete program architectures permissible by G. An edge (u, u') E E exists if one can obtain the architectures in u' by expanding nonterminal of an architecture in u following some production rules of G. For simplicity, Fig. 2 only shows three partial or complete architectures in any node of the program derivation graph. In the graph node at depth 0.0 to the Add, ITE and Map functions (each with missing 1, expand the initial nonterminal a1
expressions) using the grammar rules in Fig. | Notice that the edge direction in a program derivation graph indicates search order. However, program dataflow through each edge (2, u') is in the opposite direction. The output of u' is calculated first and then passed as input to u.
The main challenge of program architecture synthesis is that the search space embedded in program derivation graph is discrete and combinatorial. Enumeration- based synthesis strategies are inefficient in general because of the intractable search space. Instead, we aim to learn the probability distribution of program architectures within a program derivation graph in a continuous relaxation of the search space. Specifically, to expand a nonterminal of partial program architecture, we relax the categorical choice of production rules a context-free grammar into a softmax over all possible production rules with trainable weights. For example, in Fig. if we expand the initial nonterminal a1 to partial architecture Add 01 (k2g on node 1, we have several choices to further expand the architecture's 1.0 weighted by the probability matrix (obtained after softmax) drawn in Fig. 0: on node 2. Our main idea
1,0
first nonterminal 0x
Based on w, the synthesizer will choose to expand a to Add 2.0 2.0 to learn architecture weights is to encode a program derivation graph itself as a differentiable program Tw. whose output is weighted by the outputs of all programs included in Tu.0. where represents architecture weights and A includes program parameters of all the mixed programs in the graph. The parameters w and 0 can be jointly optimized with respect to a differentiable loss function l over program outputs via bi-level optimization. Similar to DARTS [10, we train @ and w on a parameter training dataset Dg and an architecture validation dataset D. respectively until convergence:
g' = 8 - V Ve D,, (TT (ix),
w' = w V V.llEigoo D_ e (Tw,,r (ix),ox)
However, a program derivation graph includes an exponential number of programs. Therefore, it involves a huge set of trainable variables including program architecture weights and unknown program parameters 6. To curb the large program derivation search space, we introduce node sharing (Sec. 3.1
and iterative graph unfolding (Sec. 3.2)
3.1 Node Sharing
Intuitively, node sharing in a program derivation graph allows two partial architectures to share the same child nodes if the nonterminals in the two architectures can be expanded using the same grammar production rules. Fig.
B depicts the compressed program derivation graph for the sequence
1.0 classification grammar in Fig. I At depth 1, three partial architectures Add a,10 ag ITE a >
0 ag 0' 1,1 and Map (fun 21 .1-00 2) are expanded from the initial nonterminal a Because only one of the three partial architectures would be used derive the final synthesized program, we allow the nonterminals a2
1.0 the second parameter of Add, and ar the second parameters of ITE, to
share the same child node 3, weighted by the probability matrix w drawn in Fig. Importantly, node sharing takes function arities and types into account. The matrix w has probability for the Map partial architecture because unlike Add and ITE it does not contain a second parameter.
Formally, in a program derivation graph, let K2 be the number of program architectures on node u. Denote fü (a a a )) as the k-th (partial) architecture on u where Ty(f(t is the number
of nonterminals contained in f and a. is the i-th nonterminal of ft. For the grammar of Fig.
essentially each f is a function application with missing argument expressions a; u.A 1 S < ((2). and n n(( is the arity of the function. Assume that w' is the i-th child of from left to right in the program derivation graph. The weight w. of the edge e = (u, u') is of the shape IR K_*K, where the matrix rows refer to the partial architectures on u and the matrix columns refer to architectures on w'. We have we [[k k')] proportional to the probability of expanding the i-th nonterminal of f to fi

---

Stort
Depth
Addi
IT6:
0.5
0.17
0.33
A4
0
W
Add
Depth
Depth
Figure 3: Node Sharing Program Derivation Graphs.
(obtained after softmax), e.g. the matrix drawn in Fig. + To make the architecture search space continuous, relax the categorical choice of expanding particular nonterminal o; over all possible grammar production rules for og in the program derivation graph:
u.k to softmax
exp( We [[k k(I)
[a (0""(())) Σ
K E exp( (.,kk ()) LfW (a)
W'
a' m( )(r)) 1(x))
where u' the i-th child and e = (u,
Complexity. Let be the depth a program derivation graph, Kmax be the number productions rules, and Mmea be the maximum number of nonterminals in any rules of context-free grammar. With node sharing, we reduce the space complexity the program derivation graph from [[K Amaz) [ I)+ to [[Mmax]++] In program synthesis task, K is typically much larger than Mmazz Without compression, the program derivation graph of a grammar with large Kmaz even hardly fits GPU memory.
3.2 Iterative Graph Unfolding
Node sharing significantly restricts the width of program derivation graph. However, a derivation graph still grows exponentially with its depth, which limits the scalability of differentiable architecture search. To address this problem, we propose an on-the-fly approach that unfolds program derivation graphs iteratively and prunes away unlikely candidate architectures at the end of each iteration based on their weights. Fig. depicts the iterative procedure of derivation graph unfolding.
At the initial iteration, the program derivation graph is shallow as it only contains architectures to u.k on any node of the depth-bounded graph, our algorithm substitutes neural networks for the nonterminals a. approximate the missing expressions. These networks are sype-consistent. For example, recurrent neural network is used to replace missing expression whose inputs are supposed to be sequences. For program derivation graph as such, unknown program parameters come from both parameterized functions like I and the neural modules. The goal is to optimize the architecture weights and the unknown program parameters using Equation 2 The qualitics candidate partial architectures each graph node ranked based on the learned architecture weights.
depth dy. We set d, in Fig. 4 For any partial program architecture ft (a u.k ..... a m(ft))
In the next iteration, on each graph node, our synthesis algorithm retains top-N program architectures as children for each partial architecture on the node's 's parent, which are defined to be those assigned with higher weights on the node's incoming edge in the previous iteration. We set N 2 in the example of Fig. 4 After top-N preservation on each node, our synthesis algorithm increases the depth of the program derivation graph by expanding the nonterminals (that were replaced with neural modules in the previous iteration) d, depths deeper. Suitable neural networks are leveraged to substitute any new nonterminals at depth 2d, Our algorithm again jointly optimizes architecture weights and unknown program parameters and performs top-N preservation each node based on
5

---

B JALB
1
61
100
Singros
1
2
O +
c 00+
1000
F0o
100
+
Figure 4: Differentiable program architecture synthesis with iterative graph unfolding.
learned architecture weights, as depicted in Fig. Such a process iterates until the unfolded program derivation graph contains nonterminals or the maximum search depth is reached. Our differentiable program architecture synthesis method is outlined in (the first while loop of) Algorithm
3.3 Searching Optimal Programs
Once we have an optimized program derivation graph G, due the top-N preservation strategy, each node retains small number of partial architectures. From G. we could greedily obtain discrete program ar- chitecture top-down by replacing each graph node containing mixed partial architectures with the likely partial architecture based on learned architec- ture weights. However, the performance estimation ranked by architecture weights in program deriva- tion graph can be inaccurate due to the co-adaption among architectures via node sharing. Recent work also discovers that relaxed architecture search meth- ods tend to overfit to certain functions that lead to more rapid gradient descent than others 17 and thus produce unsatisfying performance.
Algorithm 1: Program Archit Synthesis
Input :Grammar G. Graph expansion
depth dg. Top-N parameter
Output :Synthesized Program P G contains only the initial nonterminal; while G contains nonterminals do Extend G depth d, deeper w.r.t. G:
Optimize and 0 in G w.rt. Eq. 2
Top-N preservation in G's nodes;
Q :
while Q 0 do
== arg min f()::
Q = Q \ {q};
To overcome this potential disadvantage of difffrrnn tiable architecture search, our algorithm introduces a search procedure as depicted in Fig. The core idea is that while one super program derivation graph may not be able to model the entire search space accu- rately, multiple sub program derivation graphs can be used effectively address the limitation by having each sub graph modeling one part of the search space.
if q is well-ryped program then return
the top-left most node in g with more than one architecture choice; for each partial archit. f& on do q' == g glu/ [[] Compute g( (.) h(d'), s(1');
Q = QUQQU(H
In the search, Algorithm| [ maintains a queue Q of program derivation graphs sorted by their quality that initialized [G]. Our algorithm measures the quality of program by both its task performance and structure cost. The algorithm dequeues one graph q from Q and extracts the top-most and left-most node u of q that still contains more than one partial architecture for search, As u co-adapts multiple architectures, we separate the entire search u.k space into disjoint partitions by picking each available architecture f (a u.k ...., m((g) from the
compound node and assign a sub program derivation graph to model each partition. The algorithm computes quality score s for each option of retaining only fl on u. denoted as q(u/ [
s(qlu/ f(]) = g(glu/ft) + h(qlu//f)) f21)
The g(glu/ [ function measures the structure cost of expanding the initial nonterminal up to (Sec. 2. and h[qlu/ [f]] is e-Admissible heuristic estimate of the cost-to-go from node [88
h(glu/ (2]) 1 F. [u/ [K], Deat) where w", 0" arg min D (Tt..ooo-i((TTTell////l
w,0
where T encodes the program derivation graph g itself via Equation 3 as differentiable program whose output is weighted by the output of all complete programs included g. and are the sets of architecture weights and unknown program parameters in the subgraph rooted at in qlu/ f2). The

---

function fine- tunes these trainable variables using the training dataset D to provide informed feedback on the contribution program quality of the choice of only retaining f on node u, measured by the program's $ Fi score. In practice, to avoid overfitting, we use a separate validation dataset Daa to obtain the Fi score. After computing the quality score 8, we add g(u/jk] back to the queue Q sorted based on s-scores. The search algorithm completes when the derivation graph with the least s-score from Q is a well-typed program, i.c. each graph node contains only one valid architecture choice. Our architecture selection algorithm is optimal given the admissible heuristic function / the returned program optimally balances program accuracy and structure complexity among all the programs contained in G. The proof is given in Appendix A
4
Experiments
We have implemented Algorithm I in tool named dPads (domain speeiiiic Program architecture differentiable synthesis) [19] and evaluated it on four sequence classification datasets.
4.1 Datasets for Evaluation
We partition dataset to training, validation, and test datasets. dPads uses the training dataset to optimize the architecture weights and program parameters in a program derivation graph. When searching a final program from a converged program derivation graph, we use the validation dataset to obtain the program's 's Fi score to guide the search. We use the test dataset to obtain the final accuracy and Pi score of a program. Additionally, in training we construct two separate datasets by randomly selecting 60% of training dataset as Do to optimize program parameters 0 and using the remaining 40% as Dw to train architecture weights w via Equation 2
Crim13 Dataset. The dataset collects social behaviors of a pair of mice. We cut every 100 frames as a trajectory. Each trajectory frame is annotated with an action by behavior experts 220 For each frame, a 19-dimensional feature vector is extracted including the positions and velocities of the two mice. The goal is to synthesize a program to classify each trajectory to action smiff or no sniff. In total we have 12404, 3077, and 2953 trajectories in the training set, validation set, and test set respectively.
Fly-vs-fly Dataset. We use the Boy-meets-boy, Aggression and Courtship datasets collected in the fly-ss-fly enviromment for monitoring two fruit flies interacting with each other (21). Each trajectory frame is a 53-dimensional feature vector including fly position, velocity, wing movement, etc. We subsample the dataset similar to 77. which results in 5341 train trajectories, 629 validation trajectories. and 1050 test trajectories. We aim to synthesize program to classify each trajectory as one of 7 actions displaying aggressive, threatening, and nonthreatening behaviors.
Basketball Dataset. The dataset tracks the movement of a basketball, 5 defensive players and offensive players [2 Each trajectory has 25 frames with each frame 22- 22-dimensional feature vector of ball and player position information. We aim to learn a program that can predict which offensive player handles the ball whether the ball is being passed. In total we have 18000, 2801, and 2693 trajectories in the training set, validation set, and test set respectively.
Skeletics 152 Dataset. The dataset 233 contains 152 human pose actions as well related YouTube Videos subsampled from Kinetics-700 [24]. For each video frame, 25 3-D skeleton points are collected, resulting in a 75-dimensional feature vector per frame. We extract 100 frames from each trajectory to reduce noise. Finally, the training set contains 8721 trajectories, the validation set contains 2184 trajectories, and the test set contains 892 trajectories. We aim to learn program to classify a pose trajectory as one 10 actions.
As discussed in Sec. 2 the DSL for each dataset is equipped with a customized library of differentiable and parameterized functions Fs,o We define these functions in Appendix B In this paper, we focus on sequence classification benchmarks. However, dPads is a general program synthesis algorithm and is not limited to sequence classification. Appendix [C.6] we evaluate dPads on cryptographic circuit synthesis to demonstrate the generalizability of dPads.
4.2 Experiment Setup
To train architecture weights w and unknown program parameters in a differentiable program architecture derivation graph, use the Adam optimizer (25). In Algorithm [ we set N = 2
7

---

Table 1: Experiment results on the performance of dPads compared with NEAR 77. All results are
reported as the average of runs on five random seeds. Costs of time are set in minutes.
Crim13-sniff
Fly-vs-fly
Bbal--ballhandler
SK152-10 actions
Fi
Acc.
Time
Acc.
Time
Acc.
Time
Fi Acc.
Time
RNN
.481
.851
.964
.964
.980
.980
.444
.428
A' N'-NEAR
.286
.200
164.92
.888
.64
243.82
.400
.934
553.01
.312 .313 210.23
IDS-BB-NEAR
.323
.834
463.36
.822
.750
465.57
.793
.768 513.33
.314
.317
848.44
dPads
.488
.812
147.87
.887
.833
348.25
.945
.939
174.68
.337
.337 162.70
0.55
0.50
0.4
0:34
0.45
Ft Soore
Ft Score
0.32
F1
JEADAR d'eds
A-NDAA
0.2
0.75
sPace
0.80
200
<00
620
200
500
400
500
200
600
500
600 500 1000
Time (min)
Time (min)
Time (min)
Time (min)
(a] Crim13-sniff
(b) Fly-vs-fly
(c) Bball-balihandier
(d) SK152-10 actions
Figure 5: Experiment results the Crim13, Fly-vs-fly, Basketball and SK152 datasets over five random seeds. x axis refers to costs of time recorded minutes and y axis refers to Fj scores.
for top-N preservation and set graph expansion depth d, to 2. For evaluation, we compare dPads with the sute-of-the-aie art program learning algorithms A -EAR and IDS-BB-NEAR 77]. We only report a comparison with NEAR because NEAR significantly outperforms other program learning methods based on top-down enumeration, Monte-Carlo sampling, Monte-Carlo tree search, and genetic algorithms 77. All experiments were performed on Intel 2.3-GHz Xeon CPU with 16 cores, equipped with NVIDIA Quadro RTX 6000 GPU. More experiment settings including learning rates and training epochs are given in Appendix C.I and C,2
4.3 Experiment Results
For fair comparison with NEAR [7]. for any of the four datasets, all tools search over the same DSL. We use random seeds 0, 1000, 2000, 3000, 4000 and report average F1 scores, accuracy rates and execution times for both methods. We also report the results achieved using highly expressive RNN baseline which provides a task performance upper bound on F1 -coress and accuracy.
Table I shows the experiment results. On both the Crim13 and SK152 datasets, dPads outperforms A --EAR and IDS-BB-NEAR achieving higher F, scores and using much less time consumption. dPads also achieves competitive accuracy with NEAR Crim13, On the Basketball dataset, although dPads achieves a bit higher Fi score, the architectures synthesized by dPads and A **-NEAR are exactly the same. However, dPads takes 70% less time get the result. While A -NEAAR completes the search faster than dPads on Fly-vs-fly, the program architecture synthesized by dPads leads to program with much better Fi score and higher accuracy. More quantitative analyses of the experiment results are given in Appendix C.3
We visualize the results of dPads and NEAR in terms of Fi scores (y axis) and running times (z axis) on the random seeds Fig. 5 where red triangles refer to the results of dPads, and black plus marks and rectangles refer to the results of A -N-R and IDS-BB-NEAT NEAR in achieving higher F1 scores with less computation and is closer to the RNN bascline.
dPads consistently outperforms
Although the RNN baseline provides better performance, dPads learns programs that are more interpretable. Fig. depicts the best programs synthesized by dPads on Crim and SK152 (among all the 5 random seeds). The program for Crim13 13 has simple architecture and achieves high F1 score 0.475 (only 0.006 less than the RNN result). invokes two Fs.0 library functions: PositionAAfine and DistanceAffiie. This program is highly human-readable: it evaluates the likelihood of "sniff" by applying a position bias and if the distance between two mice is small they are doing "sniff". The programmatic classifier for SK 152 achieves an Fi score 0.35 which is close to the RNN baseline. It uses the arm and leg positions of a 3-D skeleton to complete a human-action classification. We show more examples about the interpretability of programs learned by dPads in Appendix C.5
8

---

s slide
Map (
Multiply (LegsAffines, (a)).
Multiply(
LegsAffines, (xt))
PositionAffines, (x:)),
Multiply (ArmsAffineg, (xt)
DistanceAffinees (2x)))
ArmsAffineg, (x)))) x
Figure 6: Synthesized Programs for Crim13-snin (left) and SK152-10 actions (right).
Table 2: Ablation study on the importance of node sharing and iterative graph unfolding as two optimization strategies in dPads. All results reported as the average of runs on five random seeds. Costs of time are set in minutes. OOM represents an out-of-memory error.
Crim13-sniff
Fly-vs-fly
Bball-bal
SK152-10 actions
Variants of dPads
Fi Acc. Time
Fi Acc. Time
Fi Acc.
Time
Fj Acc. Time
dPads w/o Node Sharing
.453 .800 334.93
1440
> 1440
.321 .322 252.81
dPads w/o Graph Unfolding
.449 .818 280.67
0OM
848 .832
348.09
.348
.346 273.95
dPads in full
.458 .812 147.87
.887 .853 348.25
.945 .939
174.68
.337 .337 162.70
4.4 Ablation Studies
We introduce two more baselines to study the importance of node sharing and iterative graph unfolding. The first baseline does not use node sharing to reduce the size of a program derivation graph but still performs iterative graph unfolding. The second baseline directly expands a program derivation graph to the maximum depth but still applies node sharing. We report the comparison results over 5 random runs in Table 2 Without the two optimizations, limited by the size of GPU memory, dPads may either time-out or encounter -ft-oo- error when searching programs that need deep structures to ensure high accuracy. This is because the size of program derivation graph grows exponentially large with the height of program abstract syntax trees and the number of DSL production rules. Moreover, while being more complete, training without these two optimizations does not necessarily produce better results even when there is not OOM or timeout. For example, on Basketball, dPads achieves .945 F1 score. dPads without iterative graph unfolding only obtains .848 Fj score. We suspect this because the program derivation graph without top-N preservation and iterative unfolding is more difficult train it contains significantly more parameters.
We further investigate the effect of the top-N preservation strategy in program architecture synthesis (Sec. 3.2) and its impact searching optimal programs (Sec. 3.3) We set N to 2, respectively and study how dPads responds to these changes. Table 3 summarizes the average results of F1 scores, accuracy rates, time costs, and the standard deviations of these results. When N 1. dPads extracts final programs greedily from optimized program derivation graphs without conducting further search. There is a significant decrease in time consumption compared with N 2. However, dPads in this condition achieves less Fj scores and the results have higher variances, which suggests that architecture weights learned using only differentiable synthesis overfit sub-optimal programs. dPads gets similar Fi scores when setting N = 3 compared to N = 2 but consumes more time. It optimal program from the converged program derivation graph, since N = 3 incurs a much larger search space. This result confirms that scaling discrete program search to large architecture search spaces is challenging. dPads addresses this fundamental limitation by leveraging differentiable search of program architectures to significantly prune away unlikely search directions. Therefore. suffices to set N in our experiments to balance search optimality and efficiency. Additional ablation study results are given in Appendix C.4 The limitations of dPads are discussed in Appendix [..
even times-out on the Basketball dataset while searching
5 Related Work
Program Synthesis. Tasks in program synthesis aim to search for programs in DSL to satisfy specification over program inputs and outputs. There also a growing literature on applying deep learning methods to guide the search over program architectures 6 34 There exist efforts
that extend this line of research to program synthesis from noisy data 1 approaches either require a detailed hand-written program template simply enumerate the discrete
4. These

---

Table 3: Ablation study on the value of N for the Jop-N preservation strategy used in dPads. All results are reported as the average of runs on five random seeds. Costs of time are set to minutes.
N
dPads
Fi
Acc.
Time
Std.
Std. Acc.
.272
.627
50.85
.111
.218
Crim13-sniff
2
.458
.812
147.87
.014
.008
3
.450
.811
441.12
.025
.008
.769
.716
95.36
.052
.062
Fly-vs-fly
2
.887
.853
348.25
.010
.006
3
.866
.818
620.48
.017
.039
.808
.785
41.14
.042
.045
Bhall-balhandler
2
.945 3
.939
174.68
.004
004
1440
.310
.310
40.34
.020
.024
SK152-10 actions
2
.337
.337
162.70
.017
.017
3 .336
.338
609.14
.011
.010
space of program architectures permitted by DSL. Additionally, most of these literature methods build models that trained using corpora of synthesis problems and solutions, which are not available in our setting. The most closest work to our technique includes (38) ( that enumerate the space of program architectures prioritizing search directions with feedback from machine learning models. Specifically, Lee et al. corpus) to guide A search over discrete program syntax trees and NEAR 7 uses neural networks to approximate missing expressions in a partial program whose F1 score serves as an admissible heuristic guide an A search again over discrete program syntax trees. As opposed these efforts, our method more efficiently conducts program synthesis in a continuous relaxation of the discrete space of language grammar rules and only searches the optimal program space after differentiable architecture synthesis for addressing its gradient bias problem [14..
38 uses a probabilistic model (trained from a synthesis problem
much reduced search
Differentiable Architecture Search. Neural architecture search has attracted much interest promising approach to automate deep learning tasks 39 42 Particularly, our program architecture synthesis algorithm inspired by DARTS [10]. This method uses composition of softmaxes over all possible candidate operations between a fixed set of neural network nodes to relax the neural architecture search space. Various methods further improve neural architecture search efficiency and accuracy [14 43 44]. Applying this line of algorithms to program synthesis is challenging because the space of program architectures much richer. Different operations take different number and types of inputs/outputs and may only be available at different points of program. There is also no fixed bound on the number of program expressions. By relaxing the discrete search space of language grammar rules with node sharing and iterative unfolding of program derivation graphs, our method addresses the aforementioned challenges. To the best of our knowledge, this the first approach that applies differentiable architecture search to program synthesis.
6 Conclusions
This paper presents a novel differentiable approach program synthesis. With gradient descent, our method learns the probability distribution of program architectures induced by the context-free grammar a DSL continuous relaxation of the discrete space of language grammar rules. This allows the synthesis algorithm to efficiently prune away unlikely program derivations to discover optimal program architectures. We have instantiated differentiable program architecture synthesis with effective optimization strategies including node sharing and iterative graph unfolding, scaling it to real-world sequence classification tasks. Experiment results demonstrate that our algorithm substantially outperforms bate-of-the-are program learning approaches.
Programmatic models high-level DSLs are a powerful abstraction for summarizing discovered knowledge from data in a through structured symbolic primitives in a DSL and open opportunities for programmers to influence the semantic meaning of learned programs. However, the programming biases in a DSL may also leave opportunities to attack on the security and fairness of a learned model. One direction for future work is to apply formal program reasoning enhance the trustworthiness of programmatic models.
way. Programmatic models incorporate inductive bias
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their comments and suggestions. This work was supported by NSF Award #CCF-2124155 and the DARPA Symbiotic Design for Cyber Physical Systems program.
References
[1] Abhinav Verma. Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Pro- grammatically interpretable reinforcement learning. In International Conference on Machine Learning. pages (045-5054, PMLR, 2018,
[2] Abhinav Verma, Hoang Minh Le, Yisong Yue, and Swarat Chaudhuri. Imitation Imitation-projected programmatic reinforcement learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 14, 2019, Vancouver, BC, Canada, pages 15726-15733 2019.
[3] Alexander L. Gaunt, Mare Brockschmidt, Nate Kushman, and Daniel Tarlow. Differentiable programs with neural libraries. In Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th International Conference on Machine Learning, JCML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1213 1222.. PMLR, 2017.
[4] Alexander L. Gaunt, Mare Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. Terpret: probabilistic programming language for program induction. CoRR, (bbs/1608.04488, 2016.
[5] Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. HOUDINI: lifelong learning as program synthesis. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 8701-8712 2018.
[6] Kevin Ellis, Maxwell I. Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando SolaraLezama. Write, execute, assess: Program synthesis with REPL. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' D'Alché-Bucc Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 14, 2019, Vancouver, BC, Canada, pages 9165 9174, 2019.
[7] Ameesh Shah, Eric Zhan, Jennifer J. Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. Learning differentiable programs with admissible neural heuristics. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Floriaa Balcan, and Hsuan-Tiee Tien Lin, editors, Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[8] Judea Pearl. Hearistics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co., Inc., USA. 1984, ISBN 0201055945.
[9] Jing Xiang and Scyoung Kim. A lasso for learning sparse bayesian network structure for continuous variables. In Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevoda, United States, pages 2418-2426, 2013.
[10] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[11] Thomas G. Dietterich. Machine learning for sequential data: A review. In Terry Caelli, Adnan Amin, Robert P. W. Duin, Mohamed S. Kamel, and Dick de Ridder, editors, Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshops SSPR 2002 and SPR 2002, Windsor, Ontorio, Canada, August 6-9, 2002, Proceedings, volume 2396 Lecture Notes in Computer Science, pages 15-30. Springer, 2002. doi: 10. 10111177--50-77665990
[12] John E. Hoperoft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to automata theory, languages, and computation, 3rd Edition. Pearson international edition. Addison-Wesley. 2007. ISBN 978-0-321-476177
[13] Glynn Winskel. The formal semantics of programming languages an introduction. Foundation of computing series. MIT Press, 1993. ISBN 978-0-262-22166-5.

---

[14] Xin Chen, Lingxi Xie. Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV). October 2019.
[15] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan aanMMchhael Frahm, editors, Computer Vision ECCV 2020 16th European Conference. Glasgow, UK, August 23-28, 2020, Proceedings, Part XVI, volume 12361 of Lecture Notes in Computer Science, pages 544-560. Springer, 2020. doi: 00.10077978-3-000-55555
[16] Yiyang Zhao, Linnan Wang, Yuandong Tian, Rodrigo Fonseca, and Tian Guo. Few-shot neural architecture search. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 12707-12718. PMLR, 2021.
[17] Ruochen Wang. Minhao Cheng, Xiangning Chen, Xiaocheng Tang. and Cho-Jui Hsich. Rethinking architecture selection in differentiable NAS. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[18] Larry Harris. The heuristic search under conditions of error. Artif. Intell., 5(3):217-234, 1974, doi:
10. 10.1016/004437222 370007797774911149
[19] Guofeng Cui and He Zhu.
dPads 2021. [Online; accessed 26- 26-Oct-2021).
Source Code.
https://githut com/
RU- Aueooattteeeeesooteee
Group/dPads
[20] Xavier Burgos-Artizze Piotr Dollár, Dayu Lin, David Anderson, and Pietro Perona. Social behavior recognition in continuous video. 2012 IEFE Conference on Computer Vision and Pattern Recognition, pages 1322-1329. IEEE, 2012.
[21] Eyrun Eyjolfsdotti,, Steve Branson, Xavier P.Burgos-Artizuu, Eric D. Hoopfer, Jonathan Schor, David J. Anderson, and Pietro Perona. Fly fly dataset, 2021. URL htttp:://data. http://tataaaaacccc..c...c
1893
[22] Yisong Yue, Patrick Lucey, Peter Carr, Alina Bialkowski, and lain Matthews. Learning fine- fine-graing grained spatial models for dynamic sports play prediction. In 2014 IEEE international conference on data mining, pages 670 019.6679.00 IEEE, 2014.
[23] Pranay Gupta, Anirudh Thatipelli, Aditya Aggarwal, Shubh Maheshwari, Neel Trivedi, Sourav Das, and Ravi Kiran Sarvadevabhatla. Quo vadis, skeleton action recognition ?, 2020.
[24] Joao Carreira, Eric Noland, Chloe Hillier, and Andrew Zisserman. A short note on the kinetics-700 human action dataset. arXiv preprint 1XXv::1077006977 2019.
[25] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:I412.660 2014.
[26] Maxwell I. Nye, Luke B. Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach. California, PMLR, 2019.
USA, volume 97 of Proceedings of Machine Learning Research, pages
[27] Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepeoder: Learning to write programs. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[28] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pages 990-998. PMLR, 2017.
[29] Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[30] Vijayaraghavan Murali, Letao Qi. Swarat Chaudhuri, and Chris Jermaine. Neural sketch learning for conditional program generation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
12

---

[31] Rudy Bunel, Malthew J. Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging graminar and reinforcement learning for neural program synthesis. In 6th International Conference on Learning Representations. ICLR 2018, Vancouver, BC, Canada, April May 3. 2018, Conference Track Proceedings. OpenReview.net, 2018.
[32] Amit Zohar and Lior Wolf. Automatic program synthesis long programs with learned garbage collector. In Samy Bengio, Hamna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Dasa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 2098-2101 2107, 2018.
[33] Xinyun Chen, Chang Liu, and Dawn Song. Exccution-guided neural program synthesis. In 7th Inter- national Conference on Learning Representations, ICLR 2019, New Orleans, IA,, USA, May 6-9, 2019. OpenReview.net, 2019.
[34] Yaroslav Ganin, Tejas Kulkarni, Igor Babuschkin, S. M. Ali Eslami, and Oriol Vinyals. Synthesizing programs for images using reinforced adversarial learning. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüsson Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1652 1661. PMLR, 2018
[35] Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Desa-Bianchi, and Roman Garnelt, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 6062-6077 2018
[36] Kevin Ellis, Armando Lezama, and Joshua B. Tenenbaum. Unsupervised learning by program synthesis. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lcc, Masashi Sugiyama, and Roman Gareett, editors, Advances in Neural Information Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, December 12, 2015, Montreal, Quebec, Canada, pages 973-981, 2015.
[37] Brenden Lake, Ruslan Salakhutdinov, and Joshua Tenenbaum. Human- level concept learning through prohahilistic program induction. Science, 350: 1332-1338, 12 2015. doi: 10.1 00500000.
[38] Woosuk Lee, Kihong Heo, Rajecv Alur, and Mayur Naik. Accelerating search-based program synthesis using learned probabilistic models. Jeffrey Foster and Dan Grossman, editors, Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018, pages 436-449. ACM, 2018. doi: 10.1 1451119266666631922410
[39] Barret Zoph and Quoc Lc. Neural architecture scarch with reinforcement learning. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[40] Barret Zoph, Vijay Vasudevan, Jomathon Shlens, and Quoc V Le. Learning transfcrable architectures for scalahle image recognition. In Proceedings of the IEFE conference computer vision and pattern recognition, pages 8697-8710 10, 2018.
[41] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European conference on computer vision (ECCV), pages 19-34, 2018
[42] Esteban Real, Alok Aggarwal. Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. In The Thirty-Thic Third AAAÍ Conference on Artificial Intelligence, AAAI 2019, The Thirty- First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pages 4780 4789. AAAI Press, 2019. doi: 10. 10.1609/aaii.ooo v33001 0333001.3311777 330144880.
[43] Yufan Jiang. Chi Hu, Tong Xiao, Chunliang Zhang, and Jingbo Zhu. Improved differentiable architecture search for language modeling and named entity recognition. In Proceedings the 2019 Conference on Empirical Methods Natural Language Processing and the 9th International Joint Conference on Natural Language Processing DEMNLP-IJCNLL P,, pages 3576-3581 2019.
[44] Chenxi Liu, Liang-Chiee Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L. Yuille, and Li Fei-Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. Proceedings of the JEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
13


Reviews:
[{"review_id": "pQCyLGE7Oj0", "reviewer": "Reviewer_AjTJ", "summary": "This paper introduces dPads, an approach to learning interpretable programs to perform sequence classification tasks, as an alternative to using RNNs which are less interpretable and possibly less robust. The programs are generated using a context-free grammar (adapted from prior work) of differentiable operations applied to sequences. The ultimate objective is to find a program that obtains high classification accuracy on a dataset, while having low architectural cost. This is done by using a continuous relaxation of the discrete choices in the grammar, using a softmax over all possible grammar production rules instead of a categorical choice, with learnable weights. Further optimizations include “node sharing” (where two nodes in the program derivation graph are shared if they represent the same nonterminal and thus can be expanded the same way) and “iterative graph unfolding” which is somewhat like a beam search over the program derivation process, narrowing down the earlier choices using a guess for their quality, resulting in less combinatorial explosion (higher efficiency) at the cost of a fully complete search. As a final step, an A* search is used to choose a single complete program with high accuracy and low cost. Experiments on 4 sequence classification datasets show that dPads performs better than prior work NEAR, but worse than plain RNNs (which are not interpretable programs).", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Positives**\n* dPads performs better than prior work NEAR\n* The diagrams are quite helpful for understanding the approach\n* The iterative graph unfolding idea is quite interesting. Even though it’s similar to a beam search, I haven’t seen such an idea presented for a tree-shaped program derivation before.\n\n**Negatives**\n* The prose is a bit dense which makes it hard to follow some parts (but the diagrams are quite helpful)\n* The work is quite similar to NEAR, with the similarities and differences not adequately explained, which can make many parts of dPads appear more novel than they are\n* There is not enough experimental analysis about the impact of the differences between dPads and NEAR\n\n---\n\nOverall the approach in this paper makes sense. It did take me multiple passes through the paper to actually understand the approach, so perhaps the writing could be made more clear, maybe with a higher emphasis on conveying the broader intuitions before diving into details. I found that the diagrams were quite helpful in understanding the approach.\n\nMy main concern is that the paper is not clear enough on how dPads differs from NEAR. The two works use very similar DSLs (by design), both view program search as a graph search problem where the graph nodes are partially expanded programs and edges represent grammar production rules, both use A* with admissible heuristics to perform the search within this graph, and both use neural networks to approximate missing (unexpanded) expressions. It appears that dPads implements some engineering optimizations to make the search process faster, but it is not clear whether NEAR uses similar optimizations (since NEAR is faster than dPads on one dataset), what the impact of these optimizations are, nor how novel they are (when viewed at a high level, sharing nodes when nodes represent the same thing is a common technique, and iterative graph unfolding is similar to beam search). Given how similar dPads and NEAR are, I think the paper should have space dedicated to explaining how NEAR works, what its drawbacks are in more detail (maybe with examples), and then demonstrating how dPads’ modifications help address those drawbacks.\n\nAs it is, I feel that this paper is a bit misleading because the high similarity to NEAR is swept under the rug, and would only be noticed by a reader already familiar with NEAR. Thus, in my opinion, the paper needs a significant change to present the approach in a way that adequately explains its relationship (similarities and differences and _why_) to prior work. Doing so would also strengthen the paper's significance, if readers can come away with stronger intuitive understandings of why certain approaches are better than others.\n\n**Questions**\n* 105: where to do the costs $c(r)$ come from?\n* 289: “all tools search over the same DSL” - have you extended NEAR to use the extra DSL elements, or limited dPads to use NEAR’s DSL?\n* 307: Why is the F1 score of 0.475 different from the value in Table 1, 0.458? Is it because Figure 6 contains the best program over 5 runs, and the other runs produce programs with much lower F1 score? What are those other programs?\n* Table 2: Is there a copy/paste error here? The F1, Acc, and Time columns are exactly the same between Crim13 and Sk152.\n* What are the main differences between dPads and NEAR? Intuitively speaking, why are dPads’ approach better than NEAR’s approach? I understand the argument of being more efficient in an enormous search space, but why is NEAR faster than dPads on Fly-vs-fly, and similar in speed on Crim13 and Sk152? From the timing results, I infer that NEAR must have other kinds of optimizations, and a deeper dive into the pros and cons of each approach is needed.\n* Each dataset has a training, validation, and test set. Furthermore, the training set is split into $D_{val}$ and $D_{train}$ (line 279), so now we have 4 splits. Where is each split used?\n\n**Minor suggestions**\n* 21: achieves -> achieving\n* 32: inefficient in natural -> inefficient in nature? Or just inefficient\n* 138: still not sure what “inefficient in natural” means\n* 223: depcited -> depicted\n* I would give an example task in the introduction or problem formulation to help clarify what is meant by “sequence classification,” which I initially interpreted to mean classification of text. This also helps the reader think about the correct datatypes when reading about the approach\n* I would make a connection between iterative graph unfolding and beam search -- when I realized the similarities, the iterative graph unfolding step suddenly made much more sense.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One point that should be mentioned is that, IIUC, dPads requires more time and resources (i.e., higher carbon footprint) to produce a program, compared to simpler approaches like plain RNNs.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "b5t3WrG7wud", "reviewer": "Reviewer_3c6i", "summary": "This paper considers the task of synthesizing differentiable programs for sequence classification tasks. It introduces a novel method, dPads, that first constructs a program derivation graph representing a subset of the highest probability possible architectures under a CFG, and subsequently uses an A*-like search to find a program in the graph that balances minimizing complexity with maximizing accuracy. Central to the derivation graph construction method are the ideas of (1) iterative training of architecture weights and neural approximations of subexpressions, (2) node sharing, and (3) iterative graph unfolding. The method is evaluated on four sequence classification tasks, where it is found to have better performance than the program synthesis baselines considered, and worse performance than an RNN baseline, with the key advantage over the RNN being the interpretability of the resultant programs from dPads.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Program synthesis is an important area because it yields results that are more interpretable, manipulable, and potentially generalize more robustly than neural models. So, it is promising that this method produces results beginning to approach those obtained by an RNN on sequence classification tasks. Still, the results are far enough behind the RNN's to make the accuracy / interpretability trade-off significant.\n\nThe approach builds upon the ideas of NEAR [1] and Euphony [2]. It uses a similar strategy to NEAR of (1) using neural models to approximate unexpanded subexpressions and (2) using an A*-like search for the optimal program. The contributions of this paper over those of [1] and [2] come from the methods of making the search space smaller. Performing iterative graph unfolding retaining only the top-N programs per node, combined with node sharing, allows for this. The other core aspect of this paper's method is it constructs a continuous relaxation of the otherwise discrete search space, iteratively training the architecture weight selection parameters and the neural subexpression parameters; this is most similar to the approach of the DARTS line of work [3], with which I acknowledge limited familiarity.\n\nTo demonstrate the value of this reduced search space, the experiments compare against two methods from [1], making the claim that other methods perform even worse and need not be compared against in the paper. Overall, the evaluation is done well, on four datasets with sequence classification tasks. These tasks are quite similar to one another in number of examples, frames, and number of features, and also share the similarity that they all come from visual recordings over time, despite the approach being more general than this one modality. It is interesting to note that the variance in run time can be quite high. Consider providing an explanation of this observation.\n\nConsider also making the description of T clearer. Line 240 states the intention of T, but making it precise or explicitly stating its type or outputs would improve clarity. Other than this, the paper is written precisely. The appendix provides adequate details to understand the experiments fully.\n\nConsider also including empirical information about the reduction in search space provided by node sharing and top-N retention. While the run times are informative, quantifying the search space reduction would be more useful for understanding the source of the relative performance of dPads and baselines more precisely.\n\nFrom the results in Appendix A, it is interesting that performance already begins to drop off when N=3. The increase in time is understandable, but the drop in f1 score and accuracy is surprising. Do you have an explanation for this? Much of Appendix B already appears in the paper and is duplicated precisely; this is not necessary.\n\n---\n\n[1] Learning Differentiable Programs with Admissible Neural Heuristics https://arxiv.org/abs/2007.12101\n\n[2] Accelerating Search-Based Program Synthesis using Learned Probabilistic Models https://www.seas.upenn.edu/~mhnaik/papers/pldi18b.pdf\n\n[3] DARTS: Differentiable Architecture Search https://arxiv.org/abs/1806.09055\n\n---\n\nLine 21: s/achieves/achieving\n\nLine 204: \"noterminals\" should be \"nonterminals\".\n\nLine 223: \"depcited\" should be \"depicted\"\n\nLine 234: $q[u/f^u_k]$ denotes the graph with $u$ modified, not the $f$-score; reword to make this clear.\n\nLine 535: s/shows/show\n\nLine 553: I'm not familiar with the term \"sortness\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors acknowledge the main technical limitation of the work, the relative performance compared with RNN methods. The authors also mention in Section 6 that there is potential for attacks on security and fairness on models derived via the paper's method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "_sPRT_pii38", "reviewer": "Reviewer_Rykf", "summary": "A method for synthesising programs using gradient descent is presented, alternating between optimisation of operator parameters (constants) and of the program structure (nested expressions). The submission focuses on reducing the complexity of the search for correct structures, using the idea of sharing different nodes in the search tree (i.e., allow them to appear in different contexts) as well as initially approximating subexpressions by neural networks and only starting to learn to represent them by programs when the subtree appears to be a promising candidate.\nExperiments on four small datasets show that the method compares favourably to a baseline in synthesizing programs that explain observed behaviour.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality\n---\nI'm not an expert in this area, and hence cannot comment much on this dimension. However, the idea of re-using parts of the synthesized programs in several places was already present in the TerpreT work of Gaunt et al, which considered a number of formalisms (e.g., assembly programs) in which operand choices were shared in a similar way as in the proposed \"Node Sharing\" method in this submission.\n\nQuality\n---\nThe only claims in the paper are related to the effectiveness of the proposed method. Claims regarding the overall method seem well-supported by the experiments (but again, not an expert and hence no idea if these datasets/baselines are appropriate), but the individual contribution of the different methods remain unclear:\n1. The experiments do not break out the effect of the node sharing technique at all. For example, what would happen if every potential function would have its own child nodes? Clearly, the runtime would explode, but would the quality of the generated programs improve as well? You could even imagine faster convergence, as the number of constraints on each parameter is reduced.\n2. The effect of the iterative search tree deepening technique is not studied in detail. In particular, I'm not sure if N=3 means that all children are always preserved (that somewhat depends on how the $c$ parameter of fold is treated); and many other pruning approaches (e.g., considering the top N candidates across the entire search tree, rather than per node) are not considered at all.\n\nClarity\n---\nI found the paper very hard to follow, in particular because some core concepts are not illustrated in a helpful way. For example, it would have been helpful to explain the meaning of $w$ - I first thought this is simply the probability distribution over potential choices in a node; however this seems to be wrong when considering Fig. 3 and Eq. (3), and instead it turns out that this is conditional on where it is used. Providing a full example would have made following the text much easier.\n\nThere are a number of imprecisions (or maybe missed opportunities):\n* l162-l165: What about the first parameter of ITE and Add? Are these not shared (because this wouldn't be well-typed), or is there some special-casing happening here? More generally, are types used at all to direct the search?\n* how are variables picked by the system? does the grammar contain a fixed pool of variables, or is this somehow special-cased?\n* Sect. 3.3: the choice of the name $f$ to compute a cost in Alg. 1 is extremely unfortunate, as it has no relationship to the $f_u^k$ also appearing here.\n\nSignificance\n---\nThe present submission does not seem to be a breakthrough in applicability of neural program search to complex problems. The idea of iterative deepening of the search is interesting, though somewhat underexplored in this submission, and just aims to bound the base of the exponential blowup of the search method. \n\n\nMinor details\n---\n- Fig. 1: I found this DSL extremely strange (without knowing the datasets), as it mixes non-standard, apparently task-focused primitives such as mapprefix and SlideWindowAvg into a basic functional language. It would be helpful to comment on the choice of functions in the text.\n- l105: \"sum of the multiset of rules\" -> \"sum of the costs of the rules in the multiset of rules\" (or something slightly less ungainly, but correct)\n- l135: \"are inefficient in natural\" -> \"... in general\"\n- l204: \"noterminals\"\n- l223: \"depcited\"\n- Fig. 6: left half of table for \"Sk152-10 actions\" is a copy of the Crim13-sniff results\n\nUpdate after Author Response\n---\nGiven the additional example on a different DSL, I'm happy to believe that this submission is more significant as it is applicable to a wider range of examples; hence I'm upgrading my original rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the checklist, the authors claim that they discussed the limitations of their work, but I could find no such discussion in the paper. No negative societal impact is apparent.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "EPOx32qwAC", "reviewer": "Reviewer_twpr", "summary": "This work proposes a method for differentiable synthesis of program architectures. A program derivation graph is encoded as a differentiable program whose output is a weighted output of all the programs in the graph. The method learns a probability distribution over all possible program derivations induced by a context-free grammar. The grammar rule selection weights and the program parameters are co-optimized iteratively with respect to a loss function over program outputs. The approach is evaluated on four sequence classification tasks. The discovered architectures have better F1 scores as compared to the state-of-the-art program synthesis methods (A*-NEAR and IDS-BB-NEAR).\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**\n\nThe idea of differentiable network architecture search by relaxing the search space to be continuous has already been explored in DART. However, applying this technique to architecture search is not straightforward; the space of program architectures in this setting is huge. This work introduces two techniques, \"node sharing\" and \"iterative unfolding\" to address the challenges associated with program synthesis of differentiable programs. If the expansion of nonterminals in two programs are expanded with the same grammar production rule then the resulting subterms can be clubbed together in one node. This converts the program expansion tree into a graph reducing the search space to a great extent.\nThe Iterative Graph Unfolding approach unfolds the program derivation graph iteratively and prunes away unlikely candidates architectures at the end of each iteration. As the rule selection probabilities and program parameters are co-optimized, iterative graph unfolding ensures that only relevant nodes are kept in the program derivation tree. In my view, these two techniques are the main contributions of this work.\n\n**Significance**\n\nProgram Architecture Search is a challenging problem due to the exponential search space. The enumeration-based strategies just do scale to the real world tasks. Differentiable synthesis is an important research direction for effective search. The two techniques introduced in the papers, \"node sharing\" and \"iterative graph unfolding\" enables the use of differentiable search methods for synthesizing programmatic models from a context free grammar.\n\n**Quality**\n\n* The problem formulation and the method presentation is technically sound. The iterative parameter update rules are presented clearly.\n* The proposed method has been implemented as a tool called dPads. dPads is evaluated on four sequence classification tasks. The proposed method outperforms the state-of-the-art program synthesis methods on the F1 score metric and time.\n* I think the evaluation is a bit inadequate. Although the datasets are from diverse domains, I would have liked some variety in the tasks. Currently all the tasks are sequence classification tasks. (Maybe include regression and other data types in addition to sequences). Some comparison with the enumerative approaches would have emphasized the benefit of the proposed approach.\n* Naive application of DART like differentiable search does not work in the program synthesis domain. Including the results on dPads without using node sharing and/or iterative folding would bolster the paper's claim.\n* The authors might consider reporting ROC-AUC to report the results across thresholds (if the dataset is not imbalanced.)\n\n**Clarity**\n* The paper is well written and easy to follow. I would have liked some light introduction to the Program Derivation Graph before diving into the notation heavy exposition. You may think of presenting a simple program derivation tree and the corresponding graph with collapsed nodes.\n* I do not get the sentence on line 200. Is it that each node has at most N subterms?  However, there are 3 subterms in node 4 in Figure 4 (step 5).\n* Minor: Line 85 uses $\\sigma$ for grammar vocabulary. Immediately after that $\\sigma$ is used for sigmoid function.\n* Minor: Figure 5. Swap figures b and c to keep the same sequence as in Table 1.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "* The paper doesn’t spend much time discussing the limitations or possible pain points. This is, in one way, a byproduct of the inadequate evaluations. The proposed approach is only compared with NEAR. I believe more diverse tasks of varying complexity will reveal the strong and weak points of the method.\n* The paper already acknowledges that the results achieved with dPads do not match the RNN baseline result. This may be due to limitations in expressivity imposed by the DSL. I would like the authors to comment on this.\n\nThere does not seem to be any potential negative societal impact of this work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciated the novel idea presented in the paper to use gradient-based search in a continuous relaxation of context-free grammar rules for synthesis of program architectures. The additional experiments with comparison to enumerative approaches and ablation experiments, as well as more information about empirical savings in search space and relationship with NEAR were also greatly appreciated. There was still a concern about improving the writing and presentation in the paper, which hopefully the authors can improve in the final version taking feedback from the detailed reviews. It would also be great to incorporate the new experiments and discussions from the responses in the final version.
Decision: Accept (Poster)