Guiding Program Synthesis by Learning to Generate Examples
Authors: Larissa Laich
Pavol Bielik
Martin Vechev
Venue:  (2020)
Keywords: program synthesis
programming by examples

Abstract: A key challenge of existing program synthesizers is ensuring that the synthesized program generalizes well. This can be difficult to achieve as the specification provided by the end user is often limited, containing as few as one or two input-output examples. In this paper we address this challenge via an iterative approach that finds ambiguities in the provided specification and learns to resolve these by generating additional input-output examples. The main insight is to reduce the problem of selecting which program generalizes well to the simpler task of deciding which output is correct. As a result, to train our probabilistic models, we can take advantage of the large amounts of data in the form of program outputs, which are often much easier to obtain than the corresponding ground-truth programs.

Published as a conference paper at ICLR 2020
GUIDING PROGRAM SYNTHESIS BY LEARNING TO GENERATE EXAMPLES
Larissa Laich, Pavol Bielik, Martin Vechev Department of Computer Science ETH Zurich, Switzerland 1la ch@ethz.ch, {pavol ppavol.bielik, martin.vechev)@inn ch
ABSTRACT
A key challenge of existing program synthesizers ensuring that the synthesized program generalizes well. This can be difficult to achieve as the specification provided by the end user is often limited, containing few as one or two input- output examples. In this paper we address this challenge via an iterative approach that finds ambiguities in the provided specification and learns to resolve these by generating additional input-ouiput examples. The main insight is to reduce the problem of selecting which program generalizes well to the simpler task of decid- ing which output is correct. As a result, to train probabilistic models, take advantage of the large amounts of data in the form of program outputs, which are often much easier to obtain than the corresponding ground-trut trrnth programs.
INTRODUCTION
Over the years, program synthesis has been applied to a wide variety of different tasks including string, number date transformations (Gulwani] 2011 (Singh & Gulwani] 2012: 2016; Ellis al.
2019 Menon et al. 2013 Ellis & Gulwani 2017). layout and graphic program generation (Bielik)
al.
2018 Hempel& & Chugh 2016) Ellis et al. 2019 2018), data extraction (Barowy et 2014
Le & Gulwani 2014 Lyer et al. 2019). superoptimization (Phothilimthana et al. 2016 Schkufza (016)), code repair (Singh et al. 20133 Nguyen et al., 2013;
D'Anto'n Antoni al.] 2016 language
modelling (Bielik et al.) 2017), synthesis of data processing programs (Polosukhin & Skidanov) 2018 Nye et al., 2019) or semantic parsing Shin et al. (2019a). To capture user intent in an easy and intuitive way, many program synthesizers let its users provide set of input-output examples I which the synthesized program should satisfy.
Generalization challenge A natural expectation of the end user in this setting is that the synthe- sized program works well even when severely limited (e.g.. to one or two examples). Because of this small number of examples and the big search space of possible programs, there are often millions of programs consistent with I. However, only a small number of them generalizes well to unseen examples which makes the synthesis problem difficult.
Existing methods Several approaches have provided ways to address the above challenge, in- cluding using an external model that learns to rank candidate programs returned by the synthesizer, modifying the search procedure by learning to guide the synthesizer such that it returns more likely programs directly, or neural program induction methods that replace the synthesizer with neural network to generate outputs directly using a latent program representation. However, regardless of what other features these approaches use, such as conditioning on program traces (Shin al. 2018 Ellis & Gulwani 2017 Chen et al. 2019) or pre-training on the input data (Singh) 2016). they are limited by the fact that their models are conditioned on the initial, limited user specification.
This work We present a new approach for program synthesis from examples which addresses the above challenge. The key idea to resolve ambiguity by iteratively strengthening the initial specification I with new examples. To achieve this, we start by using existing synthesizer to find a candidate program P1 that satisfies all examples in I. Instead of returning Pt, we use it to find a distinguishing input x² that leads to ambiguities, i.c., other programs pt that satisfy I but produce different outputs pı (x*) * (x)). To resolve this ambiguity, we first generate a set of candidate outputs for x" then neural model (which we train beforehand) that acts oracle and selects

---

Published as a conference paper at ICLR 2020
Input Specification Z
Extend the Input Specification {(341dp (P4 Pro).
Selected Output
n
18
Synthesized Program Outputs
141 (P4
p((21)
p((x')
Symbolic Search E C.v(a,, M,) EZ p(ms)
Neural Oracle
P1
arg fly" 1x*)
(Po)
arg max f( .0'"""
(Ds)
orland
P2
max f(v 1 .0 E
(D$)
Statistical Search arg max 2 q(p ())
Pn
Candidate Outputs
V = (px(="))
dp (Nexus
3-1dp (P4 Pro)
Existing Android Layout Synthesizer InferUI
Figure 1: An overview of our approach which introduces a refinement loop around black-box synthesizer that incrementally extends the input specification I {(T1 ((z1,,1)}, which in this case contains a single example, with additional input-output examples until all ambiguities are resolved.
the most likely output, and finally, add x" and its predicted output to the input specification I. The whole process is then repeated. These steps similar those used in Oracle Guided Inductive Synthesis (Jha et al. 2010) with two main differences: (i) we automate the entire process by learning the oracle from data instead of using human oracle, and (ii) as do not use human oracle to produce correct output, we need to ensure that the set of candidate outputs contains the correct one.
Augmenting an existing Android layout synthesizer state-of-the-art synthesizer, called InferUI (Bielik et al., (0088). that creates an Android layout program which represents the implementation of a user interface. Given an application design con- sisting of set of views (e.g., buttons, images, text fields, etc.) and their location the device screen, InferUI synthesizes a layout program that when rendered, places the views at that same location. Concretely, each input-output example (æt, y) consists of device screen I and set of n views E R"x4, all which are represented using their coordinates in a two dimensional euclidean space. As an example, the input specification I shown in Figure contains a single ex- ample with absolute view positions for a Nexus 4 device and the InferUI synthesizer easily finds multiple programs that satisfy it (dashed box). To apply our method and resolve the ambiguity, we find a distinguishing input z², in this case a narrower P4 Pro device, on which some of the candidate programs produce different outputs. Then, instead of asking the user to manually produce the cor- rect output, we generate additional candidate outputs (to ensure that the correct one is included) and our learned neural oracle automatically selects one of these outputs (the one it believes is correct) and adds it to the input specification I. In this case, the oracle selects output pa (x*) as both buttons are correctly resized and the distance between them was reduced to match the smaller device width. In contrast, Pı (z*) contains overlapping buttons while in (x, only the left button was resized.
this work we apply our approach to a
Automatically obtaining real-world datasets An important advantage of our approach is that reduce the problem of selecting which program generalizes well to the simpler task of deciding which output is correct. This is especially useful for domains, such as the Android layout synthesis, for which the output correctness depends mostly on properties of the output and not the program used to generate it. As a result, obtaining a suitable training dataset can be easier as we do not require the hard obtain ground-trut -ruth programs, for which currently no large real-world datasets exist (Shin et al.] 2019b). In fact, it is possible to train the oracle using unsupervised learning only, with a dataset consisting of correct input-output examples Dy. For example, in layout synthesis an autoencoder can be trained over a large number of views and their positions extracted from running real-world applications. However, instead of training such an unsupervised model, in our work we use Dr to automatically construct supervised dataset Ds by labelling the samples in Dy positive and generating a set of negative samples by adding suitable noise to the samples in Dy. Finally, we also obtain the dataset Ds+ that additionally includes the input specification I. In the domain of Android layouts, although it is more difficult, such a dataset can also be collected automatically by running the same application on devices with different screen sizes.
2

---

Published as a conference paper at ICLR 2020
Our contributions We present new approach to address the ambiguity in the existing Android layout program synthesizer InferUI by iteratively extending the user provided specification with new input-output examples. The key component of our method is learned neural oracle used to generate new examples trained with datasets that do not require human annotations or ground-truth programs. To improve generalization, InferUI already contains probabilistic model that scores programs q(p Z) as well as handcrafied robustness properties, achieving 35% generalization accu- racy on dataset of Google Play Store applications. In contrast, our method significantly improves the accuracy to 71% while using a dataset containing only correct and incorrect program outputs. We make our implementation and datasets available online at:
2 RELATED WORK
In this section we discuss the work most closely related to ours.
Guiding program synthesis To improve scalability and generalization of program synthesizers several techniques have been proposed that guide the synthesizer towards good programs. The most widely used approach is to implement statistical search procedure which explores candidate programs based on some type of learned probabilistic model - log-linear models (Menon et al.] [0133] Long & Rinard 2016). hicrarchical Bayesian prior (Liang et al., 2010), probabilistic higher order grammar (Lee et al. 2018) or neural network (Balog et al.) [0117] Sun et al., 2018). Kalyan et al.
(2018) also takes advantage of probabilistic models but instead of implementing a custom search procedure, they use the learned model to guide an existing symbolic search engine. In addition to approaches that search for a good program directly (conditioned on the input specification), a number of works guide the search by first selecting a high-level sketch of the program and then filling in the
holes using symbolic (Ellis et al. 2018 Murali et al. [017]] Nye et al. 2019), enumerative or neural search (Bosnjak et al. [017 Gaunt al. 2016). A similar idea is also used by (Shin et al. 2018),, but instead of generating program sketch the authors first infer exccution traces (or condition on partial traces obtained the program is being generated (Chen et al. 2019)), which are then used to guide the synthesis of the actual program.
In comparison to prior work, a key aspect of our approach is guide the synthesis by generating additional input-output examples that resolve the ambiguities in the input specification. Guiding the synthesizer in this way has several advantages - (i) it interpretable and the user can inspect the generated examples, (ii) it can be used to extend any existing synthesizer by introducing refinement loop around it, (iti) the learned model is independent of the actual synthesizer (and its domain specific language) and instead is focused only on learning the relation between likely and unlikely onput-output examples, and (iv) often it is easier to obtain a dataset containing program outputs instead of a dataset consisting of the actual programs. Further, our approach is complementary to prior works as it treats the synthesizer as a black-box that can generate candidate programs. We also note that several prior works explore the design of sophisticated neural architectures that encode onput-output examples (Sun et al.) [0188] Devlin et al., Parisotto et al. (017)) and incorporating some of their ideas might lead to further improvements to models presented in Section
Learning to rank To choose among all programs that satisfy the input specification, existing pro-
gram synthesizers select the syntactically shortest program (Liang et al. 2010; Polozov & Gulwani
2015
Raychev et al., 2016). the semantically closest program to a reference program (D' Antoni 2016) or program based on a learned scoring function (Liang et al., 2010 Mandelin al.,
al.
2005
Singh & Gulwani 2015 Ellis & Gulwani] 2017 Singh 2016). Although the scoring function usually extracts features only from the synthesized program, some approaches also take advantage of additional information - Ellii & Gulwani (2017) trains a log-linear model using a set of handcrafted features defined over program traces and program outputs while (Sing (2016) leverages unlabelled data by learning common substring expressions shared across the input data.
Similar to prior work, our work explores various representations over which the model is learned. Because we applied our work to domain where outputs can be represented as images (rather than strings or numbers). to achieve good performance we explore different types of models (i.e., convo- lutional neural networks). Further, we do not assume that the synthesizer can efficiently enumerate
3

---

Published as a conference paper at ICLR 2020
all programs that satisfy the input specification as in Ellis & Gulwani (0117) synthesizers, applying a ranking of the returned candidates will often fail since the correct program is simply not included in the set of synthesized programs. Therefore, the neural oracle is defined over program outputs instead of actual programs. This reduces the search space for the synthesizer as well as the complexity of the machine learning models.
Singh (201)). For such
Neural program induction Devlin et al. (2017) and Parisotto et al. (2017). as well as related line of work on neural machines (Graves et al. 2016; Reed de Freitas 2016; Bošnjak et al. 2017 Chen et al.] 2018), explore the design of end-to-end neural approaches that generate the program output for a new input without the need for an explicit search. In this case the goal of the neural network is not find the correct program explicitly, but rather generate the most likely output for a given input based on the input specification. These approaches can be integrated in our work as one technique for generating set of candidate outputs for given distinguishing input instead of obtaining them using a symbolic synthesizer. However, the model requirements in our work are much weaker is enough if the correct output is among the top n most likely candidates rather than requiring 100% precision for all possible inputs as in program induction.
3 LEARNING TO GENERATE NEW INPUT-OUTPUT EXAMPLES
Let I= ((2 w)] denote the input specification consisting of user provided input-output exam- ples. Further, assume we are given an existing synthesizer which can find a program p satisfying all examples in I, i.e., 3p E L, (,;, yi) E I. p(x;) = V/. where p(x;) is the output obtained by running program p on input H; and L is a hypothesis space of valid programs. To reduce clutter, we use the notation p - I to denote that p satisfies all examples in I. We extend the synthesizer such that a program p not only satisfies all examples in Z but also generalizes to unseen examples as follows:
1. Generate a candidate program pı }= I that satisfies the input specification I.
2. Find distinguishing input x", a set of programs p that satisfy the input specifica- tion I but produce different outputs when evaluated on x=, and define candidate outputs as y= {pi (x"), P2(""), . Pro (x*) "): }. If no distinguishing input x" exists, return program P1-
3. Query an oracle to determine the correct output v" E y for the input
4. Extend the input specification with the distinguishing input and its corresponding output
I I {(x", ,y²)} and continue with the first step.
Finding a distinguishing input To find the distinguishing input xx we take advantage of existing symbolic synthesizers by asking the synthesizer to solve Ax Ex', P2 E p2 IApp # pi (x*), where X' denotes set of valid inputs. The result is both a distinguishing input x" as well as a program P2 that produces a different output than P1. Programs p1 and p2 form the initial sequence of candidate outputs y= [p2 (x") P2(22)) ]] which is extended until the oracle is confident enough that contains the correct output (described later in this section).
To make our approach applicable any existing synthesizer, including those that can not solve the above satisfiability query directly (e.g., statistical synthesizers), we note that the following sampling approach can also be applied: first, use the synthesizer to generate the top n most likely programs,
then randomly sample valid input x= not in the input specification, and finally check if that input leads to ambiguities by computing the output of all candidate programs.
Finding candidate outputs To extend y with additional candidate outputs once the distinguishing input x* is found, three techniques can be applied: (i) querying the synthesizer for another program with a different output: 3p E L. p -= IAV EAAyeep((""" A yts (ii) sampling program induction model P(y x², I) and using the synthesizer to check whether each sampled output is valid, or (iii) simply sampling more candidate programs, running them on x² and keeping the unique outputs. It is pos- sible to use the second approach as we are only interested in the set of different outputs, rather than the actual programs. The advantage of (i) is that it is simple to implement for symbolic synthesizers and is guaranteed to find different outputs if they exist. In contrast, (ii) has the potential to be faster as it avoids calling the synthesizer and works for both statistical and symbolic synthesizers. Finally, (ūi) is least effective, but it does not require pretraining and can be applied to any synthesizer.
4

---

Published as a conference paper at ICLR 2020
Neural oracle The key component of our approach is neural oracle which selects the cor- rect program output from a set of candidate outputs y. Formally, the neural oracle is defined as arg may fo( x², v²"""," I), where f is a function with learnable parameters 0 (in our case a neural network) that returns the probability of the output y² being correct given the in- put x² and the input specification I. We train the parameters 0 using supervised dataset Ds+ = {(V, It, Vi, Ii) U (XX,,,, Iy. Vj 1n which, for a given distinguishing input x* and input specification I. contains both the correct (v) as well as the incorrect (X) outputs. Because might difficult obtain such a dataset in practice, we also define simpler model fo(v x²,"") that is trained using supervised dataset Ds = {(, Tz, ) U { 2z, } which does not include the input specification. In the extreme case, where the dataset contains only the correct input- output examples Du { } we define the oracle as foly x Even though the dataset does not contain any labels, we can still train f in an unsupervised manner. This can be achieved for example by splitting the output into smaller parts y: = y ..f (such splitting a word into characters) and training f as an unsupervised language model. Alternatively, we could also train an autoencoder that first compresses the output into lower dimensional representation, with the loss corresponding to how well it can be reconstructed. To achieve good performance, the architecture used to represent f is tailored to the synthesis domain at hand, as discussed in the next section.
Dynamically controlling the number of generated candidate outputs Since generating a large number of candidate outputs is time consuming, we allow our models to dynamically control the number of sampled candidates for each distinguishing input x=. That is, instead of generating all candidate outputs y first and only then querying the neural oracle to select the most likely one, we query the oracle after each generated candidate output and let the model decide whether more candidates should be generated. Concretely, we define a threshold hyperparameter t E R which is used to return the first candidate output y" for which the probability of the output being correct is above this threshold. Then, only if there are no candidate outputs with probability higher that t, we return arg max of all the candidates. Note for t= 1 this formulation is equivalent returning the arg max of all the candidates while for t = 0, it corresponds to always returning the first candidate, regardless of its probability of being correct. We show the effect of different threshold values as well as the number of generated candidate outputs in Section 5
4 INSTANTIATION OF OUR APPROACH TO ANDROID LAYOUT SYNTHESIS
In this section we describe how to apply our approach to the existing Android layout program syn- thesizer InferUI (Bielik et al. 2018 Here, the input x E R. defines the absolute positions of the top left and bottom right coordinates of a given device screen while the output y E RRax4 consists of views and their absolute positions.
Finding a distinguishing input and candidate outputs Because InferUI uses symbolic search, finding a distinguishing input and candidate outputs is encoded as a logical query solved by the syn- thesizer as described in Section 3] However, instead of synthesizing the layout program containing correct outputs of all the views once (as done in InferUI), we run the synthesizer n times, each time predicting the correct output for only a single view (starting from the largest view) which is then added as additional onput-output example (we provide concrete example in Appendix C.4). This is necessary since there are exponentially many combinations of the view positions when consider- ing all the views at once and the InferUI synthesizer not powerful enough include the correct one in the set of candidate outputs (e.g.. for samples with more than 10 views in less than 4%). The advantage of allowing the position of only a single view to change, while fixing the position of all prior views, is that the correct candidate output is much easier to include. The disadvantage is that the neural oracle only has access to partial information (consisting of the prior view positions) and therefore performs a sequence of greedy predictions rather than optimizing all view positions jointly.
Neural oracle Because the input æ has the same dimensions as each view, we encode it as an addi- tional view in all our network architectures. In Figure 2 we show three different neural architectures that implement the oracle function f. each of which uses a different way to encode the oututt example into hidden representation followed by a fully-connected ReLU layer and a softmax that computes the probability that the output is correct. In the following, we describe the architecture of all the models. The formal feature definitions are included in Appendix A
5

---

Published as a conference paper at ICLR 2020
(CKN) Rendered Wireframe
(RNN) Per View Encoding
(2, v)
CNN
L.TMM
LSTM
L.STM
1
(MLP) Handcrafted Features
(a, v)
Encoder
aligned
2
centered
3
1
(x, v)
ReLU
V1
2/2
Vn
intersect
where y = [V15 -015-.-50 Un.
Illustration of three different models used to implement the neural oracle CNN, RNN and MLP. All models include a fully-connected ReLU layer and a softmax layer (not shown in the image) which computes the probability that the output y is correct. Note, that the features in the MLP model are shown unnormalized, that is, centered = denotes that three views are centered.
Figure 2:
In (CNN), the output converted to an image (each view drawn as a rectangle with a 1px black border on white background) and used as an input to convolutional neural network (CNN) with 3 convolutional layers with 5x5 filters of size 64, 32 and 16 and max pooling with kernel size 2 and stride 2. To support outputs computed for different screen sizes, the image dimensions are slightly larger than the largest device size. We regularize the network during training by positioning the outputs with random offset such that they still fully inside the image, instead of placing them in the center. This is possible as the image used as input to the CNN is larger than the device size. We provide visualization of this regularization in Appendix C.2
In (MLP), the output is transformed to a normalized feature vector and then fed into a feedforward neural network with 3 hidden layers of size 512 with ReLU activations. To encode the properties of a candidate output we use high-level handcrafted features adapted from InferUI such as the num- ber of view intersections whether the views are aligned or centered. By instantiating the features for both horizontal and vertical orientation we obtain a vector of size 30, denoted as PmuP (x", y yy",, which used as input the neural network. For the model f(V x*, x²,y" ,I) the network input is a concatenation of output features (as before) (x (x",""), features of each sample in the input specification [PHLP (ar, (2.))) and their difference (=", y²" ) SHLP (x. ())(Z.)) This differ- ence captures how the views have been resized or moved between the devices with different screen dimensions. This allows the model to distinguish between outputs that are all likely when considered in isolation but not when also compared to examples in I (as illustrated in Appendix C.3
In (RNN), we use the fact that each output consists of set of views y² = [oi;... Un)] by using an en- coder to first compute hidden representation of each view. These then combined with LSTM to compute the representation of the whole output. To encode a view 2s we extract pairwise feature vectors with all other views (including the input) Paax (U,, x", v²) = [6(u,, (flleyff=="uye combine them using LSTM. Here, Φ I x I + R" is function that extracts n real valued features from a pair of views. For each pair of views. we apply 11 simple transformations of the view coordinates, capturing their distance (4 vertical, 4 horizontal), the size difference (in width and height) and the ratio of the aspect ratios. For the model f(v a:",, x²,y") we additionally use 17 high- level features computed for each view that are adapted from InferUI. When using f(/ x=", """"""" I), these additional high-level features are not required and instead we only use the 11 simple transfor- mations combined in the same way as for the MLP model. That is, by concatenating PaXx (vi, x", ,y",, [P (v,, x, y) () and their difference [Prmm (V;, x=' u²) Pram (v,, x. (.) (x.))
and
To train our models we obtained three datasets Dv. Ds and Dÿ., each containing an increasing amount of information the expense of being harder to collect.
Datasets
The unsupervised Du = {(.,, y4) W is the simplest dataset and contains only positive oututt samples obtained by sampling z 22, 000 unique screenshots (including the associated metadata of all the absolute view positions) of Google Play Store applications taken from the Rico dataset (Dekal et al. 2017). Since the screenshots always consist of multiple layout programs combined together,

---

Published as a conference paper at ICLR 2020
Table Generalization accuracy of the existing InferUI synthesizer.
InferUI
P - I
arg max q(P) I) probabilistic model
arg ma g(p I)
Bielik et al. 2018
baseline
probabilistie & robustness model
Accuracy
15.5%
24.7%
35.2%
approximate the individual programs by sorting the views in decreasing order of their size and taking a prefix of random length (of up to 30 views). For all of the datasets, we deduplicate the views that have the same coordinates and filter out views with negative width or height.
The supervised Ds {(V, Fi, y:) (axa))DD U { UU ((, 24 y: + (g))) (as.a))) contains both correct and incorrect input-output examples. In our work this dataset is produced synthetically from Dy by extending it with incorrect samples. Concretely, the positive samples correspond to those in the dataset Dy and for each positive sample we generate up to 15 negative samples by applying transformation Eg to the correct output. The transformations considered in our work are sampled from the common mistakes the synthesizer can make resizing view, shifting a view horizontally, shifting a view vertically or any combination of the above.
The supervised dataset is Ds+ {(V ... Vi. I,)) ((( By: I,) where each I, contains the same application rendered on multiple devices. We downloaded the same applications as used in the Rico dataset from the Google Play Store and executed them on three Android emulators with different device sizes. The number of valid samples is Rs 600 since not all applications could be downloaded, executed or produced the same set of views (or screen content) when executed on three different devices. The negative examples are generated by running the synthesizer with the input specification I containing single sample and selecting up to 16 outputs that inconsistent with the ground -tuth output for the other devices.
EVALUATION
We evaluate our approach by applying it to an existing Android layout synthesizer called InferUI (Bielik et al. 2018) as described in Section 4 InferUI is symbolic synthesizer which encodes the synthesis problem as a set of logical constraints that are solved using the state-of-the-ar SMT solver Z3 (De Moura & Bjørner 2008). To improve generalization, InferUI already im- plements two techniques a probabilistic model that selects the most likely program among those that satisfy the input specification, and set of handcrafted robustness constraints d(p) that prevent synthesizing layouts which violate good design practices. We show that even if we disable these two optimizations and instead guide the synthesizer purely by extending the input specification with additional input-output examples, we can still achieve an accuracy increase from 35% to 71%.
In all our experiments, we evaluate our models and InferUI on a test subset of the Ds+ dataset which contains 85 Google Play Store applications, each of which contains the ground truth of the absolute view positions on three different screen dimensions - 1400x2520, 1440x2566 and 1400x We use one screen dimension as the input specification Z, the second as the distin- guishing input and the third one only to compute the generalization accuracy. The generalization accuracy of a synthesized program p - I is defined as the percentage of views which the program p renders at the correct position.
InferUI Baseline To establish a baseline, we run InferUI in three modes as shown in Table I The baseline mode returns the first program that satisfies the input specification, denoted as psp - T. and achieves only 15.5% generalization accuracy. In the second mode the synthesizer returns the most likely program according to a probabilistic model q(p Σ) which leads to an improved ac- curacy of 24.7%. The third mode additionally defines a set of robustness properties <(p) that the synthesized program needs to satisfy, which together with the probabilistic model achieve 35.2% accuracy. The generalization accuracy of all InferUI models is relatively low we using a challenging dataset where each sample contains on average 12 views. Note however, that this is expected since increasing the number of views leads to exponentially larger hypothesis space.
7

---

Published as a conference paper at ICLR 2020
Table 2: Generalization accuracy of different models used neural oracle in our approach.
Accuracy
Training Dataset
Model
MLP
CNN
RNN
RNN CNN
Ds Ds+
f(V x=" yy)
14.3%
14.2%
23.8%
32.1%
S( xx II)
20.7%
33.2%
63.4%
71.0%
Table 3: Effect of the threshold t and the maximum number of generated candidate outputs ly/ on the accuracy and the average number of generated candidate outputs per view (shown brackets).
t 0.9
1
Model
ly
y S
y S 16
|g/| 16
J(V x", II)
RNN CNN
40.8% (2.8)
68.3% (4.7)
71.3% (6.0)
71.0% (14.7)
Further, to establish an upper bound on how effective a candidate ranking approach can be, we query the synthesizer for up to 100 different candidate programs (each producing a unique output) and check how often the correct program is included. While for small samples (with up to 4 views) the correct program almost always included, for samples with 6 views it is among the synthesized candidates in only 30% of the cases and for samples with more than 10 views in less than 4%. Sampling more outputs will help only slightly as increasing the number of views would require generating exponentially more candidates.
Our Work We apply our approach the InferUI synthesizer by iteratively generating additional input-output examples that strengthen the input specification. The specification initially contains absolute positions of all the views for one device and we extend the specification by adding one view at time (rendered on different device) as described in Section 4 In the experiments presented here we focus on evaluating the overall improvement of the enfe synthesizer extended with our approach. We provide additional experiments that evaluate the effectiveness of the neural oracle as well as an ablation study in Appendix B
Generalization Accuracy The results of our approach instantiated with various neural oracle mod- els are shown in T The best model trained on the dataset Ds has almost the same accuracy as InferUI with all its optimizations enabled. This means that it is possible to replace existing opti- mizations and handcrafted robustness constraints by training on an easy to obtain dataset consisting of correct outputs and their perturbations. More importantly, when training the harder to obtain dataset Ds+, the generalization accuracy more than doubles 71% since the model can also condi- tion the input specification I. However, the results also show that the design of the model using the neural oracle important for achieving good results. In particular, both MLP models achieve poor accuracy since the high level handcrafted features adapted from the InferUI synthesizer are not expressive enough to distinguish between correct and incorrect outputs. The CNN models achieve better accuracy but limited for the opposite reason, they try learn all the relevant features from the raw pixels which is challenging as many features require pixel level accuracy across large dis- tances (e.g., whether two views in the opposite parts of the screen are aligned or centered). The RNN model performs the best, especially when also having access to the input specification. Even though it also processes low level information, such as distance or size difference between the views, it uses more structured representation that first computes individual view representations that are combined to capture the whole output.
Number of Candidate Outputs We show the effect of different threshold values & used by the neural oracle to dynamically control whether to search for more candidate outputs as well as the maximum number of candidate outputs in Table 3 We can that using the threshold both slightly improves the accuracy (+0.3%) but more importantly, significantly reduces the average number of generated candidate outputs from 14.7 6.0 using the same number of maximum generated outputs [y] 16.
8

---

Published as a conference paper at ICLR 2020
Incorporating User Feedback Even though our approach significantly improves over the InferUI synthesizer, it does not achieve perfect generalization accuracy. This is because for many synthesiz- ers the perfect generalization is usually not achievable the correct program and its outputs depends on a user preference, which is only expressed as severely underspecified set of input-output exam- ples. For example, for given input specification there are often multiple good layout programs that do not violate any design guidelines and which one is chosen depends on a particular user. To achieve 100% in practice, we perform an experiment where the user can inspect the input-output examples generated by our approach and correct them if needed. Then, we simply count how many corrections were required. The applications best model, no user corrections are required in 30% of the cases and in 27%, 15%, 12%, 5% of the cases the user needs to provide 2, or corrections, respectively. In contrast, InferUI with all optimizations enabled requires on average twice as many user corrections and achieves perfect generalization (i.e., zero user corrections) in only 3.5% of the cases.
our dataset have on average 12 views and for our
6 CONCLUSION
In this work we present a new approach to improve the generalization accuracy of existing program synthesizers. The main components of our method are: (i) an existing program synthesizer, (ii) a refinement loop around that synthesizer, which uses neural oracle to iteratively extend the input specification with new onput-output examples, and (iii) a neural oracle trained using an easy to obtain dataset consisting of program outputs. To show the practical usefulness of our approach apply it to an existing Android layout synthesizer called InferUI (Biclik et al.) 2018)) and improve its generalization accuracy by 2x, from 35% to 71,, when evaluated challenging dataset of real-world Google Play Store applications.
REFERENCES
Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In 5th International Conference on Learning Represen- fations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Daniel W. Barowy, Sumit Gulwani, Ted Hart, and Ben Zorn. Flashrelate: Extracting relational data from semi-structured spreadsheets using examples. In PLDI '15 Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation. Microsoft Research Technical Report, April 2014. Distinguished Artifact Award.
Pavol Bielik, Veselin Raychev, and Martin Vechev. Program synthesis for character level language modeling. In 5rd International Conference on Learning Representations, ICLR 2017 2017.
Pavol Bielik, Mare Fischer, and Martin Vechev. Robust relational layout synthesis from examples for android. Proc. ACM Program. Lang., 2(000PLLA):15::1115:222 October 2018. ISSN 2475- 1421. doi: 10. 10.1 145/32222666
Matko Bosnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 547-556. PMLR, 2017.
Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 547-556. PMLR, 06-11 Aug 2017.
Xinyun Chen, Chang Liu, and Dawn Song. Towards synthesizing complex programs from input- output examples. In International Conference on Learning Representations, 2018.
Xinyun Chen, Chang Liu, and Dawn Song. Execution- guided neural program synthesis. In Interna- fional Conference on Learning Representations, 2019.

---

Published as a conference paper at ICLR 2020
Loris D' D'Antoni, Roopsha Samanta, and Rishabh Singh. Qlose: Program repair with quantiative objectives. In 27th International Conference on Computer Aided Verification (CAV 2016), July 2016.
Leonardo De Moura and Nikolaj Björner. Z3: An efficient smt solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems,
08, pp. 337-340. Springer- Verlag,
2008. ISBN 3-540-78799-2, 978-3-540-78799--..
Biplab Deka, Zifeng Huang, Chad Franzen, Joshua Hibschman, Daniel Afergan, Yang Li, Jeffrey Nichols, and Ranjitha Kumar. Rico: A mobile app dataset for building data-driven design applica- tions. In Proceedings of the 30th Annual Symposium User Interface Software and Technology, UIST 17, 2017.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 990-998, PMLR, 2017.
Kevin Ellis and Sumit Gulwani. Learning learn programs from examples: Going beyond pro- gram structure. In Proceedings of the Twenty-Sxxth International Join! Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017. pp. 1638-1645, 2017. doi: 2224963/jcai22211/2277
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graph- ics programs from hand-drawn images. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Gameett (eds.), Advances in Neural Information Processing Systems 31, pp.
Curran Associates, Inc., 2018
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama Write, execute, assess: Program synthesis with a repl. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Buun Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Curran Associates, Inc., 2019.
Systems 32, pp. 9165-9174
Alexander L. Gaunt, Mare Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. Terpret: A probabilistic programming language for program induction. CoRR, abs/1 600.4688. 2016.
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agmieszka Grabska- Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho. John Agapiou, Adrià Puigdomênech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626); 471-476, October 2016.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Thomas Ball and Mooly Sagiv (eds.). Proceedings of the 38th ACM SIGPLAN-SIGACT Sympo- sium on Principles of Programming Languages, POPL 2011, Austin, TX. USA, January 26-28, 2011, pp. 317-330. ACM, 2011. doi: 10. 10.1145/1926385.192222 1926443...
Brian Hempel and Ravi Chugh. Semi-automated svg programming via direct manipulation. In Proceedings of the 29th Annual Symposium on User Interface Software and Technology, UIST doi: 10.1 1114//229451..294444
'16. pp. 379- 779-390. ACM, 2016. ISBN 17781-45503-489-
Arun Iyer, Manohar Jonnalagedda, Suresh Parthasarathy, Arjun Radhakrishna, and Sriram K. Raja- mani Synthesis and machine learning for heterogencous extraction. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI 2019, pp. 301-315. Association for Computing Machinery, 2019. ISBN 9781450367127.
Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. sracle-guided, component-bart based program synthesis. In Proceedings of the 32Nd ACM/IEEE International Conference on Software Engineering- Volume 1, ICSE '10, pp. 215-224. ACM, 2010. ISBN 978-1-60558-719-6 doi: 10. 10.1145 1011141//6679..01 101.99918899999888833.
10

---

Published as a conference paper at ICLR 2020
Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateck Jain, and Sumit Gul- wani. Neural-guided deductive search for real-time program synthesis from examples. In 6th In- ternational Conference on Learning Representations, ICLR 2018, Vancouver. BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018.
Vu Le and Sumit Gulwani. Flashextract: a framework for data extraction by examples. In Michael F. P. O' B'oylle and Keshav Pingali (eds.), ACM SIGPLAN Conference Programming Language Design and Implementation. PLDI 14, Edinburgh, United Kingdom June 09 11, 2014, pp- $42-553 ACM, 2014. doi: 10. 10.1145/2592291255993
Woosuk Lee, Kihong Heo, Rajeev Alur, and Mayur Naik. Accelerating search-based based program syn- thesis using learned probabilistic models. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDII 2018, pp. 436-449. ACM, 2018.
ISBN 978- 1--------55-5----- doi: 10. 00.11453192366631194410
Percy Liang, Michael I. Jordan, and Dan Klein. Learning programs: A hierarchical bayesian ap- proach. In Johannes Fürnkranz and Thorsten Joachims (eds.). Proceedings of the 27th Interna- fional Conference on Machine Learning (ICMI-10), June 21-24, 2010, Haija, Israel, pp. 639- 646. Omnipress, 2010.
Fan Long and Martin Rinard, Automatic patch generation by learning correct code. In Pro- ceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Program- ming Languages, POPL '16, pp. 298-312, ACM, 2016. ISBN
doi:
00.1145/23371122836111
David Mandelin, Lin Xu, Rastislav Bodík, and Doug Kimelman. Jungloid mining: Helping to navigate the api jungle. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '05. pp. 48-61. ACM, 2005. ISBN 1-59593-056-6. doi: (144///05510000650000
Aditya Krishna Menon, Omer Tamuz, Sumit Gulwani, Butler Lampson, and Adam Tauman Kalai. A machine learning framework for programming by example. In Proceedings of the 30th Inter- national Conference International Conference on Machine Learning Volume 28, ICML' pp. 1-187-1-195. 1...--99...MRR..or.... 2013.
Vijayaraghavan Murali, Swarat Chaudhuri, and Chris Jermaine. Bayesian sketch learning for pro- gram synthesis. CoRR, abs/1 10177003..500 00668, 2017.
Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. Semfix: Pro- gram repair via semantic analysis. In Proceedings of the 2013 International Conference on Soft- ware Engineering, ICSE '13 pp. 772-781. IEEE Press, 2013. ISBN 978-1-4673-3376-3.
Maxwell I. Nye, Luke Hewitt, Joshua B. Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 4861-4870, 2019.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bodik, and Dinakar Dhurjati. Scaling up superoptimization. In Proceedings of the Twenty-Fe First International Conference on Architec- tural Support for Programming Languages and Operating Systems, ASPLOS '16, pp. 297-310. ACM, 2016. ISBN 978- 450044400--4-40 doi: 10. 00.11457272236.2872388
Illia Polosukhin and Alexander Skidanov. Neural program search: Solving data processing tasks http://wwwwwww..eeoooeeeee fer/foomm?id
from description and examples, 2018. URL
BIKJJf-RR
Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthesis. In OOPSLA 2015 Proceedings of the 2015 ACM SIGPLAN International Conference on Object- Oriented Programming, Systems, Languages, and Applications, pp. 107-126, October 2015.
11

---

Published as a conference paper at ICLR 2020
Veselin Raychev, Pavol Bielik, Martin T. Vechev, and Andreas Krause. Learning programs from noisy data. In Rastislav Bodik and Rupak Majumdar (eds.), Proceedings of the 43rd Anmual ACM SIGPLAN-SIGARE Symposium Principles of Programming Languages. POPL 2016, St. Petersburg, FI,, USA, January 20 22, 2016, pp. 761-774, ACM, 2016. doi: 10.1 14//2344/87611 2837671.
Scott Reed and Nando de Freitas. Neural programmer--mierpreenn International Conference on Learning Representations (ICLR), 2016.
Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic program optimization. Commun. ACM, 59(2): 14-122, 2016. doi: 10.1 151/2867077
Eui Chul Shin, Miltiadis Allamanis, Marc Brockschmidt, and Alex Polozov. Program synthesis and semantic parsing with learned code idioms. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 10824-10834. Curran Associates, Inc., 2019a.
Richard Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- DasacBianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8917-8926. Curran Associates, Inc., 2018.
Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic datasets for neural program synthesis. In 7th International Conference on Learn- ing Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019b.
Rishabh Singh. Blinkfill: Semi-supervised programming by example for syntactic string transfor- mations. PVLDB, 910):816 1128866--7,,.1 2016. doi: 10.14778/9977771.977888
Rishabh Singh and Sumit Gulwani. Synthesizing number transformations from input-output exam- ples. P. Madhusudan and Sanjit A. Seshia (eds.), Computer Aided Verification, pp. 634-651.
Springer Berlin Heidelberg, 2012. ISBN 978-3-642--31244-7
Rishabh Singh and Sumit Gulwani. Predicting correct program in programming by example. In Daniel Kroening and Corina S. Păsăreanu (eds.), Computer Aided Verification, pp. 314-414. Springer International Publishing, 2015. ISBN 978-3-319-21690-4.
Rishabh Singh and Sumit Gulwani. Transforming spreadsheet data types using examples. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Pro- gramming Languages, POPL. '16, pp. 343-356. ACM, 2016. ISBN 978- 18-1--3003-344-2. doi:
10.11457837614.2336666
Rishabh Singh, Sumit Gulwani, and Armando Solar-Lezama. Automated feedback generation for introductory programming assignments. In Proceedings of the 34th ACM SIGPLAN Conference Programminng Language Design and Implementation, PLDI 13. pp. 15-26. ACM, 2013. ISBN 978-1-4503-20144 doi: 10. 1411449919562246219999
Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4799.4799.. PMLR, 10-15 Jul 2018.
12

---

Published as a conference paper at ICLR 2020
APPENDIX
We provide three appendices. Appendix A contains an in-depth description the feature transfor- mations for the MLP and RNN models. Appendix contains an additional ablation experiment as well as results from the oracle evaluation. Appendix Ceadiixxporrooe provides visualizations of positive and nega- tive candidate outputs, the CNN regularization well outputs from the end-to-end synthesis.
A FEATURE DEFINITIONS
In this section we describe in detail the feature transformations used in Section 4 As mentioned in Section Teach view consists of the coordinates: æı (#teft), Yt (stop), Ty (Eright), yb (yhottom). We use U.W for the width, v.h for the height and v.r for the aspect ratio (w.w/v.h /u.h)) of view v.
A.I MLP
In Table we define the feature types that lead vector of size used in the MLP model. All the features are normalized (divided) by the factor in the normalization column.
Table 4: Feature definitions for the MLP
Size
Name
Description
Normalization
Number of off-screen views
[V]
Number of views with spe- cific aspect ratio
Instantiated for the ratios 1, [3/4, 4/3] and [9/16, 9/16]
[V]
Number of view intersections
Pairwise comparison if two views intersect (without counting fully contained views.)
[v
Number of views which have the same dimension
The same dimension is defined as: V1.2 = 22.0 A 01.h 22.h
|V|2
1 vertical + horizontal
Number of view alignments
Pairwise comparison if two views align (e.g. for verti- cal alignment: = 22.31 V ei .t = U2,3r Vuj 02.01 V .r, U2.2,
[V/
vertical + horizontal
Number of views with a spe- cific margin to another view
Instantiated for the margins O, 16, 28, 32, 40, 48, 60, 64 and 96.
|V/
1 vertical horizontal
Number of centered views
Pairwise comparison if view is centered within an- other view.
|V/2
vertical + horizontal
Number of centered views be- tween two different views
Comparison if one view is centered between other views.
[V|
A.2 RNN
We formally define the 11 transformations used as the pairwise view feature vector Φ; R 4 R in the RNN model. These features capture properties like the view's 's distance to the other view or the size difference. The feature vectors extracted for each pair of views combined to fixed length representation by passing them through the LSTM, in the decreasing order of view size. Figure all the properties are listed and visualized.
13

---

Published as a conference paper at ICLR 2020
View 2
View
View 2
View
Distance
Size difference
Ratio
Name
Description
Formula
Distance
Horizontal distance from one view an- other view
du (U1 U2) (1,, U2)
U ..] 02 .
= U1 02 Zr
(11 U2)
U1 ..y 02 1
d (1r, U2)
= U1.E, 22
Vertical distance from one view to another view
di 02)
U1- U2-1/
des U2)
= UI -J/t V2-9/
du (u U2)
U1- U/- Ut
dos(U1 (U1, 02)
= U1 -bb U2-Yb
Size difference
Size difference of two views
8u (V1, U2)
= U1 21- - -2-10
sh(U1 02)
Uj U2
Ratio
Relation the aspect ratio
r(U1, 02)
= 01.r/02.7
Figure 3: Definition of the pairwise view feature vector Φ: TRA R.. R used in the RNN model (bottom) and their visualization (top).
To guide the model for f (V xx", yy", we defined 17 more abstract features, adapted from InferUl which defined using the simple transformations shown in Figure Concretely, define the following 17 features:
For alignments (8 features: 4 horizontal, 4 vertical); Compare if view 81 is aligned with 02, such that one of the 4 distance functions is O, e.g. du (11 02) =
For centering (2 features: 1 horizontal, vertical): Compare if view is centered in such that dul U1, (2) = (11, 12).
For overlaps (4 features: 2 horizontal, 2 vertical): Check if the V1 and U2 can possibly intersect, i.c. have overlapping x x-coordinates in the horizontal case: U1 2 02.21 and
U1-04 S U2
For the same size (2 features): Compare if the height width difference of vn and v2 is equal to 0, such that (11, 02) = 0 and Sμ (V1, v2) = 0.
For the same ratio (1 feature): Compare the ratio v1 and Ug 's aspect ratios 1, such that r(v1, U2) 1.
14

---

Published as a conference paper at ICLR 2020
Table 5: Accuracy of different models (used as neural oracle) evaluated on the test dataset of s++ For the pairwise accuracy we count correct if the score of the positive sample is smaller than the score of the negative sample. square brackets, we report the model performance if we additionally consider equal scores of the positive and the negative sample as correct (in case it differs).
Pairwise Accuracy
Training Dataset
Model
MLP
CNN
RNN
RNN CNN
Ds
J(V xx ,y"
84.4 [91.6]%
80.0%
78.5 [80.0]%
83.5%
Dst
S(V xx ,""""I
90.5 [97.6]%
84.3%
95.6%
96.8% %
Accuracy One vs. Many
Ds
f(V |x",8")
44.5 [73.0]%
36.7%
36.3 [38.3]%
55.8%
Ds+
f(V x² II)
54.6 [87.3]%
51.2%
80.6 (81.0]%
85.9%
B EXPERIMENTS
In this appendix, we evaluate the oracle performance and include an ablation study of our models.
B. ORACLE EVALUATION
We evaluate the oracle's performance (shown in Table 5 using two metries: The pairwise accuracy and one vs. many accuracy. The pairwise accuracy is the binary ranking problem - for each pair consisting of positive and negative candidate, it is considered to be correct, if the score of the positive example is higher than of the negative example (the pair was ranked correctly). To capture if the network can't 't distinguish between the samples, we also report second value in square brackets in which we count as correct if the score of the positive example is higher or equal to the score of the negative example. In addition, we measure the one vs. many accuracy, in which the oracle is correct if the score of the correct candidate was higher than the scores of all incorrect candidates (since selecting the correct candidate out of many candidates represents what we are interested in during the end-to-end synthesis experiment).
Usually, models with a higher pairwise accuracy also have a higher one vs. many accuracy since more pairs are ranked correctly. The one vs. many accuracy might be lower than expected if the mistakes of the pairwise accuracy spread over a wide number of different samples (instead of having many mistakes in small set of samples).
In general, the results of the one vs. many accuracy correlate with the results of the end-to-end synthesis. For example, RNN+CNN and RNN trained on Ds+ achieve the highest scores in both of the experiments. One exception is the MLP model trained on Ds+ dataset which performs worse on the end-to-end synthesis experiment the MLP often makes mistakes when predicting the early views which then affect the positioning of the subsequent views. For the same reason, the accuracies of the oracle experiment higher than the accuracy we observe in the synthesis experiment. Another interesting insight is that the MLP often scores the positive and the negative examples the same since there is a large difference in the pairwise accuracy depending on if we count the same score as correct or not. This shows that the MLP's feature functions are not expressive enough.
though the oracle performs better. A reason for this is that
in general
B.2 ABLATION STUDY
To investigate which high-level properties are learned by our models, we generate an ablation dataset from the test dataset of Ds+. The results of the study are collected in and Table 7
Recall from Section 4 that Puu y) computes a vector of size 30 with the handcrafted functions which are described in detail in Appendix A.] For each pair of positive (x* ypos) and negative examples (x* yneg) and their corresponding sample the input specification (x, 8) we compute the difference of their handcrafted feature functions d [Paa (x", -ppos) sPLL (Ir, y)lcr,)ezz
15

---

Published as a conference paper at ICLR 2020
Table 6: Ablation study based on different subsets the Ds- test dataset check which general properties the model has learned. The f(v ,," models are trained on Ds+
Pairwise Accuracy
Dataset
MLP
CNN
RNN
RNN + CNN
samples
Test
90.5 [97.6]
84.3
95.6
96.8
all
Aspect ratio 1.0
96.9
63.5
92.7
99.0
96
Horiz. centering-view
100.0
89.0
96.6
98.2
5262
Horiz. centering-views
99.7
89.0
96.5
98.0
6360
Vert. centering-viens
98.5
83.1
97.4
96.8
852
Vert. centering-viee
98.2
89.3
97.1
97.7
6710
Inside screen
100.0
98.0
98.8
99.0
3292
Intersections
99.5
93.3
97.3
98.2
2792
Horizontal alignment
99.6
85.5
95.7
96.9
1658
Vertical alignment
99.7
95.0
98.0
98.6
3804
Horizontal margins
98.5
91.1
97.2
98.2
5642
Vertical margins
97.1
88.0
97.6
98.0
4547
Specific aspect ratio
100.0
61.1
100.0
100.0
18
Same dimensions
100.0
85.8
97.0
96.6
471
[PNLP (x=", (neg) (m, v)x.z.)).. We add pair the ablation dataset for the violated property d o 0, that is, if the property on the positive sample is different from the negative sample. For example, if the number of view intersections of the positive sample and input specification are the same, but different for the negative sample, we add this pair of positive and negative samples to the inersectionn-ablatiin dataset.
The MLP models perform very well on all the ablation properties. The reason is that MLP's features are the handcrafted features which are designed to capture the properties in the ablation dataset. The MLP's performance the whole test dataset is worse, which indicates that some properties in the dataset are not captured by the handcrafted features.
The CNN fails at preserving the aspect ratios due the pooling and the downsampling operations. Alignments and intersection properties can be learned with local filters detecting overlapping views. Off-screen views can be detected by checking the downsampled representation after the convolu- tional layers. On these three properties, the CNN performs best. The RNN performs better on the ablation dataset than the CNN since it processes the exact numeric values of the view coordinates.
The overall performance on the ablation dataset better than the one on the whole test dataset for all models, indicating that there are some features not expressed in the handcrafted functions. Furthermore, the results of the ablation study should be considered carefully: the ablation study shows tendencies, but features could be correlated or have common hidden features.
16

---

Published as a conference paper at ICLR 2020
Table 7: Ablation study based on different subsets the ss- test dataset check which general properties the model has learned. The f(v ,,,,")
vV) models are trained on Dg.
Pairwise Accuracy
Dataset
MLP
CNN
RNN
RNN + CNN
samples
Test
84.4 [91.6]
80.0
78.5 [80.0]
83.5
all
Aspect ratio 1.0
85.4
54.2
65.6
70.8
Horiz. centering-view
97.5
86.7
88.0
89.5
5262
Horiz. centering-views
96.3
86.6
87.8
89.4
6360
Vert. centering-vien
91.4
76.0
85.9
78.6
852
Vert. centering- -iiwws
93.0
86.6
84.9
89.6
6710
Inside screen
100.0
97.7
96.2
99.5
3292
Intersections
97.0
90.6
93.3
96.7
2792
Horizontal alignment
91.0
83.1
87.7
88.1
1658
Vertical alignment
96.4
90.7
85.6
97.3
3804
Horizontal margins
92.6
89.3
89.1
91.1
5642
Vertical margins
91.4
83.1
83.0
88.0
4547
Specific aspect ratio
100.0
100.0
61.1
44.4
18
Same dimensions
95.3
86.4
94.9
90.2
471
C
VISUALIZATION
In this section, we provide visualizations of two concepts introduced Section the rendered output candidates and how the CNN input is shifted for regularization. Further, we visualize the steps of the end-to-end synthesis and render outputs of synthesized programs.
C.1 POSITIVE AND NEGATIVE OUTPUT CANDIDATES
Figure Suirershore shows four different rendered output candidates. The correct candidate is on the left and the three incorrect ones are on right. The candidates differ their 6th view which is moved around and overlaps in all of the three incorrect candidates. The three negative examples are generated by the synthesizer as described Section (for dataset Ds+) or applying perturbations sampled from the synthesizer mistakes (for dataset Ds).
Correct
Incorrect
Incorrect
Incorrect
Figure 4: One positive example (left) and negative examples (right).
17

---

Published as a conference paper at ICLR 2020
C.2 CNN REGULARIZATION
Figure 3 visualizes visualiess how the robustness the CNN increased by placing the input randomly within the input image described in Section
Figure 5: Illustration three possible shifts (denoted by different colors) of the CNN input used
during training.
C.3 ADVANTAGE HAVING THE ADDITIONAL INPUT SPECIFICATION THE Ds+ DATASET
Figure 6 visualizes the absolute view positions in the input specification on the left and the four candidates (differing the red view) on the distinguishing device x² on the right. Looking at four candidates, the first candidate is incorrect, since the red view is not centered. The third candidate not the correct one either, since the red view intersects with the view below. It is hard to decide between the second and fourth candidate since the red view is centered in both cases. When taking the input specification into consideration, the second candidate is the correct one, since there is no space between the red view and the view below candidate (unlike in second candidate and the input specification).
Output Candidates
Inpul specification
Candidate Not centered
Candidate
Candidate 3
Caudidate
Intersects
Figure 6: The input specification provides an important indication that candidate 2 the correct one (unlike candidate 4).
18

---

Published as a conference paper at ICLR 2020
C.4 END-TO-ENT SYNTHESIS PROCEDURE
In Figure we present an example of the end-to-end synthesis described in Section and Section 4 The input of the synthesizer is the top left of the F consists of input specification I with a single input-output pair (x, y). The synthesis loop starts by the synthesizer generating a can- didate program p1 }= I (not shown) and checking whether ambiguities exists. To do this, it finds a distinguishing input x², in our example a smaller device x' = [0. 0, 1400, 2520] and set of pro- grams P2.....P2. Pn that satisfy the input specification but produce different outputs when evaluated on x². Three possible candidate outputs P1 (x"). pr(=="))ss<") are visualized in Figure (column Iteration 1). Note that as described Section [ the synthesis proceeds by synthesizing the views iteratively therefore, the first iteration contains only the first view uy The oracle (in this example the CNN+RNN model trained on Ds+) selects the second candidate (the oracle prediction is indicated by the dashed rectangle) since its score is the largest with 0.88. The position of U1 the device x² is added to the specification and the iterative synthesis proceeds by selecting the correct output for the second view. In the second iteration we perform the same steps, except now synthesize different candidate outputs for the second view 1/2 on the device x², given that the position of the first view V1 is fixed from the previous iteration. The same process repeated until the absolute positions of all the views are predicted for the distinguishing input x². The new input specification, shown at the bottom in Figure 7 contains the absolute view positions for both the original input as well as the distinguishing input x=". After that, the whole process repeats by querying for another distinguishing device and extending the input specification even further.
Note that in our evaluation we restrict the distinguishing input to be among those device sizes for which we trained model. Since our datasets consist of three different screen sizes the choice is small and all the experiments in Section 5 are evaluated with single distinguishing input x². However, we could generate more than three dimensions for the training dataset and use them to train additional models. This was however not needed as three different devices are typically enough to resolve majority of ambiguities (as long as the oracle does not make mistakes).
C.4.1 LIMITATIONS OF THE MLP FEATURES
Figure g visualizes eight candidate outputs in the first synthesis iteration for the same application as in Figure 7 The MIP oracle assigns score of 0 to all the output candidates in which view is off-screen. However, the handcrafted features are not expressive enough to distinguish between the candidate outputs in the bottom row which all have a score of 0.76. In general, the MLP performs bad in selecting the first views (earlier iterations) since there are only few views from which properties e.g. margins can be extracted. On the bottom right, the synthesis result is compared to the correct output. Since the first view was not selected correctly in the synthesis, all the subsequent inner views also slightly off in comparison the correct output.
C.5 EXAMPLES OF SYNTHESIS OUTPUTS
Figure 9 visualizes the rendered output of the synthesizer for the distinguishing device x². The correct output is on the left while the synthesis output of the different oracles is on the right. At first glance, the outputs of the MLP look visually appealing since the handcrafted features contain properties like intersections or off-sereen and the model learns to avoid them. However, it is often not expressive enough, since the view sizes positions often different to the correct output. This happens in particular if there are only few views which is why the second view is often misplaced which leads to consecutive errors. This also explains the bad performance in the synthesis experi- ment in Table [ in comparison to the oracle experiment in Table 5S] The CNN outputs look much worse and often contain views which are misaligned or not centered. The RNN performs quite well one the first and third application but fails on the second application. The RNN+CNN predicts the correct output for the first application but fails on five views (out of 22) in the second and on seven (out of 17) views in the third application.
19

---

Published as a conference paper at ICLR 2020
I= (x57)
Distinguishing input
[0.0, 144,,
x [0,0,4400,2520]
[0,520,1440,1944]
| 1864]
y
[144,856, 1296, 1544]
(x, y) rendered
1144,1608,12900 1196,,199,11000 1800|
1294,,64
Iteration
Iteration
Iteration 5
Candidate Outputs
Vig
Candidate
Candidate
Candidate
V1
Incorrect
Incorrect
Incorrect
Score: 0.03
Score: 0.01
Score: 0.1
vr||40,500,1400,,
va: [0, 184,,,440,,
vs|[144,644,1296,755
Vv
Candidate 2
Candidate
Candidate 2
Correct
Incorrect
Correct
V1
Score:
Score:
Score:
1=10050001400.19911
va: 100,5,0013600188000
v=|[14,,64,11566,750
Vis
Candidate
Candidate
Candidate
V1
Incorrect
Correct
Incorrect.
Score: 0.01
Score: 0.90
Score: 0.001
1400,4900,4000,1900
88,500 180,,88.1120. 1320.184444411
vol 2214,666,1126,..
Update
== [u(x", (0.500,1400,1922) I, -I, u (x" (300580, I..I, I u (14,,555,,,,,,,,,5,,,
[0.0,1440,2500)
10.0,1400,2520)
Trme (x.y) U (x*, yx*
10.520,1440,1944
|0,500,1400 1400,1924]
13,6600,1360,188,
|80,580, 1320,
1444,56,1199,1544
1444,836,1266,133
1144,1608,1296,1 12010.00..960000)
1146,7088.2666.188)
1144,664 144,666,,1296,779
144,64441256,756)
Figure 7: The synthesis procedure step-by-step.
20

---

Published as a conference paper at ICLR 2020
VI
Vi
:| 19244) vI 10,480,144001994 |I 40,520,1400.1944
1000,0001444,,1990
(0000400,1140) 1944,1904]
Incorrect
Incorrect
Incorrect
Incorrect.
Incorrect.
Score: 0.0
Score: 0.0
Score: 0.0
Score: 0.0
Score: 0.0
VI
1004450,1400.1904 Incorrect
100.,00,400.19244
(0,,00,,14001100000 1900
Syuthesized with MLP
Correct Output
Correct
Incorrect
Score: 0.76
Score: 0.76
Score: 0.76
Figure 8: Eight output candidates in the first synthesis iteration. The oracle for the synthesizer was an MI.P trained on Dst-
21

---

Published as a conference paper at ICLR 2020
Correct Output
MLP
CNN
RNN
CNN+RNN
Correct Output
MLP
CNN
RNN
CNN+RNN
Correct Output
CNN
RNN
Figure 9: Rendered outputs on device Iº of the synthesizer for different oracles which were trained on Ds+.
22


Reviews:
[{"review_id": "Skgbh4Untr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "= Summary\nA method for a refinement loop for program synthesizers operating on input/ouput specifications is presented. The core idea is to generate several candidate solutions, execute them on several inputs, and then use a learned component to judge which of the resulting input/output pairs are most likely to be correct. This avoids having to judge the correctness of the generated programs and instead focuses on the easier task of judging the correctness of outputs. An implementation of the idea in a tool for synthesizing programs generating UIs is evaluated, showing impressive improvements over the baseline.\n\n= Strong/Weak Points\n+ The idea is surprisingly simple and applies to an important problem in program synthesis.\n+ The experiments show that the method works very well in UI-generation domain\n- The paper repeatedly claims general applicability to program synthesizers, but is only evaluated in the specific domain of UI-generating programs. I have substantial doubts that the approach would work as well in the domains of, e.g., string manipulation, Karel, or data structure transformations. My doubts are based on the fact that there are easily generalizable rules for UIs (no overlaps, symmetry, ...), whereas other domains are less easily described. This creates a substantial gap between paper claims and empirical results.\n- The writting is somewhat sloppy (see below), which makes it sometimes hard to understand. Names such as \"views\" are used without explanation, and it's not explained how a device is an input to a program (yes, I get what this means, but it makes in unnecessarily hard to follow the paper)\n\n= Recommendation\nI would ask the authors to rewrite their paper to make less general claims, but believe that the general idea of judging the correctness of a program (or policy) by evaluating it on different inputs is a powerful concept that would be of substantial value to the wider ICLR audience. Improving the readability of the paper would make me improve my rating to a full accept.\n\n= Minor Comments\n* page 1, par \"Generalization challenge\": The second sentence here is 4 lines long and very hard to follow. Please rephrase.\n* page 2, par 2: \"no large real-word datasets exists\" -> exist\n* page 2, par 3: \"even when both optimizations of InferUI are disabled\": at this point, the reader doesn't know about any optimizations of InferUI.\n* page 4, par 1: \"i.e., $\\exists p \\in \\mathcal{L}$\" - $\\mathcal{L}$ is undefined here (will be defined later on the page)\n* page 4, par 2: \"Generate a candidate program $p_1 \\models \\mathcal{I}$\" - in step 2, there are suddenly also $p_2 \\ldots p_n$, which are never explicitly generated. Either adapt this step, or explicitly generate them in step 2 based on the distinguishing input\n* page 7 par 2: \"We use one screen dimension as the input specification $\\mathcal{I}$, the second as the distinguishing input\" - this confused me, as the paper discussed discovering the distinguishing input (page 4, paragraph \"Finding a distinguishing input\"), whereas it sounds here like that input is manually selected.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SJlNo_lk5B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\nThis paper aims to improve the generalization of program synthesis, ensuring that the synthesized programs not only work on observed input/output (I/O) examples but also generalize well to assessment examples (i.e. model the real intent of the end-user). To this end, the paper proposes a framework that iteratively alternates between producing programs with an existing program synthesizer and augmenting examples to disambiguate possible programs with a neural oracle that learns to select correct outputs. Several architectures and the design of input of the neural oracle have been investigated. The experiments on Andriod layout program synthesis with an InferUI synthesizer show that the proposed framework can improve the generalization of synthesized programs. However, I find it is difficult to evaluate the effectiveness without sufficient qualitative results and the intermediate outputs (e.g. a distinguishing input and candidate outputs) of the proposed framework (see details below).\n\nSignificance: are the results significant? 4/5\nNovelty: are the problems or approaches novel? 4/5\nEvaluation: are claims well-supported by theoretical analysis or experimental results? 3/5\nClarity: is the paper well-organized and clearly written? 4/5\n\n[Strengths]\n\n*motivation*\n- The motivation for improving the generalization of program synthesis by augmenting examples is convincing.\n\n*novelty*\n- The idea of utilizing a neural network to select correct outputs to augment examples for disambiguating the possible programs is intuitive and convincing. This paper presents an effective way to implement this idea.\n\n*technical contribution*\n- The paper investigates a set of network architectures and ways to specify the network input for learning the neural oracle. The RNN+CNN model that leverages both rendered views and features seems effective.\n\n*clarity*\n- The overall writing is clear. The authors utilize figures well to illustrate the ideas. Figure 1 clearly shows the proposed framework.\n\n*experimental results*\n- The presentations of the results are clear. The results demonstrate that the proposed framework can improve generalization accuracy.\n\n*reproducibility*\n- Given the clear description in the main paper and the details provided in the appendix, I believe reproducing the results is possible if the dataset is available. \n\n[Weaknesses]\n\n*related work*\nThe descriptions of the related work are not comprehensive. Some neural program synthesis works explore a variety of mechanisms to encode examples and fuse their features, which are not mentioned in the paper. [Devlin et al. in ICML 2017] investigates different attention mechanisms to sequentially encode a set of I/O examples and performs pooling to merge them. [Sun et al. in ICML 2018] proposes a doubly encoding method to capture more details of examples and merge the features using a relation network. I believe it would be interesting to see if these methods could further improve the performance of the neural oracle.\n\n*experiment setup*\n- The experiments are not sufficient. While the claims look promising, the proposed method is only evaluated in only one dataset, which is not sufficiently convincing. I suggest the authors to also experiment the FlashFillTest dataset where string transformation programs are synthesized. \n- A more comprehensive description of the dataset is lacking. \n\n*experiment results*\n- I find it hard to judge the effectiveness of the proposed framework without seeing sufficient qualitative results. I suggest the authors randomly sample some synthesized programs (both success and failure) and present them in the paper.\n- I believe it is important to present some examples of the given I/O pairs, initially synthesized programs (p_1), found distinguishing input (x*), candidate outputs (y), the prediction of the neural oracle (i.e. selected outputs), the augmented examples (I \\cup {(x*, y*)}), and finally the next synthesized program. Without this, it is very difficult to understand the performance of the proposed framework and what could go wrong. \n\n*ablation study: the neural oracle*\nOnly the final performance (i.e. the program synthesis performance) is shown in the paper. I believe it would be helpful if the performance of the neural oracle was also presented. As the whole framework depends on how accurate the neural oracle can select the correct output, it is important to evaluate this. One way to show this is to simply show the performance of all the neural oracles (with different architectures) trained on D_S (the positive samples and the incorrect samples) or even D_{S+}.\n\nDevlin et al. \"RobustFill: Neural Program Learning under Noisy I/O\" in ICML 2017\nSun et al. \"Neural Program Synthesis from Diverse Demonstration Videos\" in ICML 2018", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "SJegExwycB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper handles the challenge of generating generalizable programs from input-output specifications when the size of the specification can be quite limited and therefore ambiguous. When proposed candidate programs lead to divergent outputs on a new input, the paper proposes to use a learned neural oracle that can evaluate which of the outputs are most likely. The paper applies their technique to the task of synthesizing Android UI layout code from labels of components and their positions.\n\nThe experiments compare the method against the baseline InferUI. To summarize the results, we can see that the proposed method in the paper can perform about as well as existing hand-crafted constraints that guide the search process of the previous work, when training an oracle on the dataset with negative examples created by noising the positive examples.\n\nOne limitation of the method is that it would works best when there is a clear latent structure behind the outputs produced by the correct program, such as in the paper's target domain of generating UIs where there are clear aesthetic rules and design guidelines that make it possible to evaluate which output is most preferred. For other domains, it may be more important to evaluate the candidate program together with its output, which would make it similar to a re-ranking approach.\n\nI believe this paper presents a novel and insightful approach to creating programs from imprecise specifications. Therefore, I vote to accept the paper.\n\nSome questions for the authors:\n- How big was $\\mathcal{I}_i$ in the supervised dataset $\\mathcal{D}_{S+}$? Was it always 3?\n- I wasn't able to find any evaluation of a model trained on $\\mathcal{D}_U$, did I miss it in the paper?", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper consider the problem of program induction from a small dataset of input-output pairs; the small amount of available data results a large set of valid candidate programs.
The authors propose to train an neural oracle by unsupervised learning on the given data, and synthesizing new pairs to augment the given data, therefore reducing the set of admissible programs.
This is reminiscent of data augmentation schemes, eg elastic transforms for image data.

The reviewers appreciate the simplicity and effectiveness of this approach, as demonstrated on an android UI dataset.
The authors successfully addressed most negative points raised by the reviewers in the rebuttal, except the lack of experimental validating on other datasets.

I recommend to accept this paper, based on reviews and my own reading.
I think the manuscript could be further improved by more explicitly discussing  (early in the paper) the intuition why the authors think this approach is sensible:
The additional information for more successfully infering the correct program has to come from somewhere; as no new information is eg given by a human oracle, it was injected by the choice of prior over neural oracles.
It is essential that the paper discuss this. 
Decision: Accept (Poster)