Neurosymbolic Deep Generative Models for Sequence Data with Relational Constraints
Authors: Halley Young
Maxwell Du
Osbert Bastani
Venue: NeurIPS 2022 Accept (2022)
Keywords: neurosymbolic
sequence
program synthesis
generative
constraint
music
poetry

Abstract: There has been significant recent progress designing deep generative models that generate realistic sequence data such as text or music. Nevertheless, it remains difficult to incorporate high-level structure to guide the generative process, and many such models perform well on local coherence, but less so on global coherence. We propose a novel approach for incorporating global structure in the form of relational constraints between different subcomponents of an example (e.g., lines of a poem or measures of music). Our generative model has two parts: (i) one model to generate a realistic set of relational constraints, and (ii) a second model to generate realistic data satisfying these constraints. For model (i), we propose a constrained optimization algorithm that infers the relational constraints present in the training data, and then learn a generative model based on the resulting constraint data.  In our experiments, we show that our approach significantly improves over state-of-the-art in terms of capturing high-level structure in the data, while performing comparably or better in terms of low-level structure.  We also show that using constrained optimization for part (ii) as well leads to increased controllability with little decrease in quality compared to pure learning-based models.

Neurosymbolic Deep Generative Models for Sequence Data with Relational Constraints
Halley Young
Maxwell Du Department of Computer Science University of Pennsylvania mduê upenn edu
Department of Computer Science University Pennsylvania ha l1 1 lelyeyyeeea upenn. edu
Osbert Bastani
Department of Computer Science University of Pennsylvania obastani@seas. upenn. edu
Abstract
There has been significant recent progress designing deep generative models that generate realistic sequence data such as text or music. Nevertheless, remains difficult incorporate high-level structure guide the generative process, and many such models perform well on local coherence, but less so on global coherence. We propose novel approach for incorporating global structure in the form of relational constraints between different subcomponents of an example (e.g., lines of poem or measures of music). Our generative model has two parts: (i) one model generate realistic set of relational constraints, and (ii) a second model to generate realistic data satisfying these constraints. For model (i), we propose a program synthesis algorithm that infers the relational constraints present in the training data, and then learn generative model based on the resulting constraint data. In our experiments, we show that our approach significantly improves over state-of- toee--f----rtt in terms of capturing high-level structure the data, while performing comparably or better in terms of low-level structure.
Introduction
There has been tremendous recent progress in designing deep generative models for generating sequence data such natural language (Vaswani et al. 2017) music (Huang al. 2019). These approaches leverage the vast quantities of data available in conjunction with unsupervised and self- supervised learning to learn probabilistic models of the data; then, examples be generated by sampling from these models, with the possibility of conditioning on initial elements of the sequence.
A key challenge facing deep generative models is the difficulty incorporating high-level structure into the generated examples-es, ee.. rhyming and meter across lines of a poem, or repetition across measures of piece of music. Capturing high-level structure is important for improving the quality of the generated data, especially low-data regimes where only small numbers of examples are available: intuitively, knowledge of the structure compresses the amount of information the generative model has to learn. Furthermore, explicit representations of structure (i.e., symbolically rather than as vector embedding) has the benefit that users can modify the structure guide generation.
Recently, Young et al. (2199) proposed neurosymbolic generative models for incorporating high-level structure into image generation, focusing on simple 2D repeating patterns in images of building facades (e.g., repeating windows). The basic idea leverage program synthesis to extract structure from data-in particular, given example image they devise algorithm A that extracts
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

program e = A(x) that represents the set of 2D repeating patterns present in training examples r. Then, using the pairs (x, c). they train two generative models: (i) model Pa (c( that generates a program, and (ii) model po( c) that generates an image that contains the structure represented by c. However, their approach is heavily tailored to images two ways. First, their representation of structure is geared towards simple patterns occurring in images of building facades. Second, their algorithm A is specifically designed to extract this kind of program from an image, as are their models (c(c) for generating programs and p0 c) for generating images z conditioned on c.
We represent the relational constraints C2 present in an example by relating each subcomponent w of a given example z with a prototype ú; which can be thought of as the "original" subcomponent from which w is constructed. In particular, the relationship between w and labeled with a set of relations R, which encodes the constraint that w and i should satisfy relation r for each r E R. Importantly, while each subcomponent is associated with a single prototype, each prototype may be associated with multiple subcomponents. As consequence, different subcomponents associated with the same prototype are related some way. This representation compact, only requiring linearly many constraints in the number of subcomponents in (assuming the number of prototypes is constant). Compactness ensures the representation both generalizes well and is easy to generate.
Then, we design a synthesis algorithm that can extract an optimal representation of the structure present in a training example x (i.e., the relational constraints cz). We show how to express the synthesis problem as constrained combinatorial optimization problem, which we solve using an SMT solver Z3 (De Moura & Bjomnr 2008). Next, we represent relational constraints as sequences, and design the model (c(c) to be specialized sequence VAE. Finally, we propose three possible designs of po c). all of which try to identify an example x that is realistic (e.g., according to a pretrained model (z)) while simultaneously satisfies the given constraints c.
We evaluate our approach on two tasks: poetry generation, where the relational constraints include rhyming lines or lines with shared meter, and music generation, where the relational constraints include equality in terms of pitch or rhythm, that one measure is transposition of another (i.e., pitches shifted up or down by constant amount), etc. We show that our approaches outperform or perform similarly to state-of-the-art art models terms of low-level structure, while significantly outperforming them in terms of high-level structure. We also perform a user study in the poetry domain to determine user- peer-perceived quality of the generated poetry along three dimensions (structure, lyricism, and coherence), and found that on average, our approach outperformed state-of- -o--the--rtttttt baselines including GPT-2. Finally, we demonstrate how our approach allows users to guide the generation process without sacrificing overall realism by specifying values of constraints.
Example. Figure illustrates how our approach is applied generate poetry. During training, our approach uses program synthesis to infer relational constraints present in the examples æ. and uses both æ and e₂ to train the generative models. Here, C2 a bipartite graph, where the LHS vertices are prototypes, and the RHS vertices correspond to lines of z. Each vertex on the right is connected to exactly one prototype. and is labeled with constraints on how should relate to its prototype. To generate new examples, it first samples relational constraints and then samples an example x that satisfies c-i.e., we need to choose a line to fill each RHS node in a way that the line satisñies the relations with its prototype. Furthermore, user can modify the sampled constraint to guide the generative process. Thus, our approach enables users to flexibly incorporate domain knowledge on the high-level structure of the data into the generative process, both in terms of the relational constraints included and by allowing them to modify the generated relational constraints.
Related work. There has been recent work using program synthesis to improve machine learning. For instance, it has been applied to unsupervised learning of latent structure in drawings (Ellis et al. 2015) and to reinforcement learning (Verma et al. 2018). These techniques have benefits such as improving interpretability (Verma et al. 2018 Ellis et al. 2020). enabling learning from fewer examples (Ellis et al.] 2015).
generalizing more robustly (Inala et al., 2019), and being easier 2018). More recently, there has been work leveraging program synthesis in conjunction with deep learning where the DNN handles perception and program synthesis handles high-level structure (Ellis et al. 2017), including work in the lifelong learning setting (Valkov et al. 2018). In contrast to these approaches, our focus is generative models. In particular, we extend recent work leveraging these ideas for image generation to incorporating high-level relational structure into sequence generation tasks (Young et al. 2019). Finally, much research over the past
to formally verify (Bastani et al.
2

---

"Father." said, 'Father. connot play The hopp that thou didst Lsit in icleness, while to and fro About thy serene, grave And I am weary of my lonely casc. Retter a perilons, journey oversens Away from thee, than this, the life lead, To sit all day in the sunshine like weed That grows naught-1 love thee Who serve thee most; yet serve thee in no way
The horp dhanheee dite give eu addatie day
rhymes
and all day
Us slones ariad frr
dhymo, mide
anrreary laady
thyme
po:
aeyy
rhyme, mitee
fhymes,
chymes,
Hrymos mider
diymo
they
dhymes, meter
dhymes,
Training Example
Relational Construints
Masic to wog, as dis city
dymess, meter
Music to song, on the city air little music live upon
litte mask lie
frymes,
rhymes, meter Hrymos
Song, song,
long with the sun,
0.5
that al ready far rain agile and thes,
And all togother if they are all ten, Until all ready for aguin and then,
cagisll
fhymes, meter
z
And lask lik can aullil aneed
dyymes mnter
To the capital hall ride with chase.
- 1.2.
Though agis
dlymo,, mider
And look like tied full all around
dyyaues
You, and whisper that I shall found.
dhymes, meter fhymes
Though built upon a little dome,
made a home. mike ronm.
Sumple Latent Vector p(]
Sample Relational Constraints
Sample Example x Pp(-1c)
pp(-12)
For each training example x, our algorithm uses program synthesis to infer the relational constraints c₂ =A(x)) present in z. Then, it uses C₂ and x to train pa(Cz) and po cz)- Bottom: Process for generating a sample r from the learned VAE Po(cz 2) (where & is Gaussian noise) and model (0 Cz). Lines with the same prototype shown in the same color; metrical constraints are represented as purple and rhyme constraints as green edges.
Figure Top:
few decades has focused on music and poetry generation, and on using relational constraints in neural models; we include a discussion of the most relevant such research Appendix A
Background on Neurosymbolic Generative Models
Consider the problem of learning a generative model given training data from the underlying distri- bution. Given training examples Z1 Z 2y ~ p", our goal is to learn a generative model pa s p* from which we can draw additional samples
Pa. We consider sequence data-i.e., an example x E is sequence x = (w1 ..., Wm) E Wm For example, each subcomponent w may be a line of poem measure of music, and may be poem or song.
We are interested in domains where likely examples satisfy latent relational constraints E C over the subcomponents. For instance, may say that two measures w; and wy of æ start with the same series of pitches, or that two lines w; and wy E R. might be "rhyme" or "equal"),, and a function f W x W x R [0. 1] such that f'w w', r)) indicates to what extent w and w' satisfy relation r. Then, e is a compact representation of the relations present in input x. We describe the structure of in detail in Section 3.1 for now, the approach we describe works for any choice of c. In particular, we build on neurosymbolic generative models Young et al. 2019), where is itself generated based latent value 2 2 Z-ie.
rhyme. We assume given a set of relations R (e.g.,
po.0(z) = / (e (c) po(c 2) p(z)dz.
Σ LEC
Then, Young et al. 2019) considers the variational distribution
gg(c, x) (=(= [ c) q(c x))
and q(c| () 5(c-
Here, 8 the Dirac delta function and c, a single representative generated from x using a program
synthesis algorithm (David & Kroening 2017 -ie., an algorithm A that takes as input an example
We use fixed simplify our exposition; our approach trivially extends variable

---

and outputs a program A(x:) encoding the relational constraints present in z. Next, Young al. (219) derive an evidence lower bound
logPe.e pe. (z)) 2 (z cx)) + B (c x)]] - (ga( c2) p(2)) + H.
where DKL. is the KL divergence and И is information entropy. The first term is the log- log-likelihood of a generative model predicting the probability of example x given relational constraints cr. and the second and third terms form the loss of a variational autoencoder (VAE) Po(c =) and 9g(2 X, this approach separately learns (i) a VAE to generate c, trained on the relational constraints C₂ synthesized from each training example z,, and (ii) model to generate given Cy: the latter take multiple forms such second VAE or generative adversarial network (GAN) Goodfellow et al. 2014). This approach is called synthesis-guiddes generative models (SGM) since it uses program synthesis guide training.
c) (Kingma& & Welling 2019). In summary, given training examples
To leverage this framework, we have to instantiate (i) the space of relational constraints C, (ii) the synthesis algorithm A X - C used to extract a program encoding the structure of x, and (iii) the architectures of Pc(c] z). 9z(2 c), and po(r c). In prior work, Young et al. (2119) used heuristics specific to the the image domain to achieve these goals-in partieular, they used (1) simple equality constraints on sub-regions of the image designed to capture 2D repeating patterns, (ii) custom synthesis algorithm that greedily adds constraints in the data to the program, and (iii) a representation of cu as image, in which case pe is generative model over images, and Pa. 9g based encoding of as a fixed-length vector.
We design a synthesis algorithm that expresses the synthesis problem as constrained combinatorial optimization problem, which it solves using an SMT solver called Z3 (De Moura & Björner 2008). In terms of (ii). our programs encode declarative constraints rather than imperative renderings, so the previous architectures of Pa. and 9% cannot be used. Instead, we use expert domain-speciff heuristics, transformers (Vaswani et al. (017). or graph neural networks (GNNs) (Kipl & Welling 2017) for Pe and 93. For pa. we propose several methods for imposing the constraints encoded by when generating an example x.
3
Relational Constraints for Sequence Data
We describe how represent relational constraints r, well algorithm AA for synthesizing the relational constraints c₂ = A(x)) present in an example sequence x.
3.1 Graph Representation of Relational Constraints
Recall that our generative model operates by first generating a relational program c, and then generating an example x that satisfies c. Thus, for each training example x, we need to design relational program that encode constraints on the structure of z. A program encodes set of relational constraints, each of which imposes a constraint that subcomponents of x should have certain kinds of relations. We begin by describing the structure of single relational constraint, and then describe how encodes a set of relational constraints.
A relational constraint & E + = W x I x R, where I (1,...,,, is tuple ø = (w, i)r); we call W W prototype subcomponent. An example x satisfies & to extent h (denoted æ Fv d) [(ū, w4, r) = h. where is the ith subcomponent of ær. That is, says the ith subcomponent w; of x should have relation r with prototype subcomponent w. Thus, we can interpret Φ as a function Φ X > [0, 1]. where (xx) = 1 if satisfies ø to the maximal extent and 6(x) = 0 if does not satisfy @ at all.
Next, a relational program encodes set of relational constraints on examples x. We represent as an undirected labeled bipartite graph = (V.V E) with vertices V' and V and edges E' C VVV x where R is the set of relations and 2 is the power set of R. The vertices / E are prototype subcomponents E W: equivalently, they may be vector embeddings of prototype subcomponents. The vertices E V = {1,..., m) are the indices of subcomponents in æ. The edges e E E. are tuples (w., i, R), where R = [o. 1|]x| Rl. For tractability of synthesis, we impose the constraint that each E V is part of single edge (w, v, R) (though ē e V may be part of multiple edges). Finally,

---

encodes the set of relational constraints
c (,,,i, h) (w,i, E E A h1-
In other words, includes the relational constraint that each subcomponent w, of æ should have all relations r E Rt with prototype v to extent h, where v is connected to ú.
In this paper, for most examples, consider binary relationships that have 0 or 1 as values, and informally state that pair úū i does not have a relationship r if f(ū, é, r) = O. However, as we show in our experiments, non-boolean functions with values between 0 and can be used well.
For example, in Figure D the graph shown on the top right encodes a relational constraint Ca. and the top right shows an example a: that satisfies all the constraints @ E Φ.c, with value greater than O. The nodes on the left-hand side of C2. are prototype subcomponents úi W, each of which a line of poetry. The nodes on the right-hand side correspond indices i (from = 1 on top to = 10 on the bottom); each one is labeled with set of relations R2 Then, Φ. contains constraints e (w, i, R,) for each edge i i in the graph, which says that line i of should have relations r E R3 with it For instance, the last (10th) node in C₂ has constraints R10 = {rhyme, meter). , and is connected to prototype line v =TTh harp that thou..." Thus, this edge encodes constraint = (w, 10, R10) saying that the last line of x should rhyme and have the same meter as w. Indeed, the last line of is wro =Whho serve thee most...", which satisfies this constraint.
Remark 3.1. We use prototypes rather than direct relationships between components to ensure the size of the graph is tractable-with this choice, the graph is linear in the size of the input (assuming the number of prototypes is constant) rather than quadratic. A compact graph is both each to synthesize (for training) and train model to generate (for generation). In our experiments, we show that our approach significantly outperforms attempting to generate full graphs (i.c., adjacency tensors).
Remark 3.2. We refer to as program since it can be interpreted as Datalog program (Ceri et al. (i.e., a relational logic program); particular, &, is set of Datalog relations over x E X.
1989
3.2
Synthesizing Relational Constraints
Recall that when training our generative model, we need to design a program synthesis algorithm A that synthesizes relational program c2 A(x)) that best encodes the latent relational constraints present in each training example x. A key question is where the prototypes come from. We simply choose the prototypes w be actual subcomponents in æ. Thus, e₂ encodes that subcomponents of are each related to one of a small number of distinguished subcomponents of x. As described below, we formulate the problem of synthesizing C₂ as a constrained optimization problem.
Optimization variables. The variables are a binary vector E ! and a binary matrix K E B= Intuitively, H, indicates whether subcomponent w, of is prototype subcomponent in c, and Kij indicates whether w; is the prototype for subcomponent W/j-
Constraints. Our optimization problem has the following three constraints:
TR
m
m
m
m
1/1 = Kimin Σ
H,
kimax:
2/2
A
Σ
Ki 1,
4/3
A
Kij S m Hs.
First, th says that the number of prototype subcomponents is between kinin and kimax- Next, 3/2 says that every subcomponent Wj corresponds to exactly one prototype subcomponent wi. Finally, 1/s says that for every i, if w. is the prototype subcomponent of wy according to K, then it must be prototype subcomponent according to as well.
Objective. The objective of our optimization problem is expressed in terms of precomputed distance matrix D E Rmmx where Dij measures the similarity between components w; and wy; smaller values indicate a greater degree of similarity. In particular, we define
Dij EVER (JW;, r)
i.., Dij is the extent to which each R are not satisfied by w; and wy. Then, objective (which to be minimized) has the following three terms:
m
m
m
J1
Σ 1==1
Kij Dij.
J2
Σ i-==
Σ KEs Kkj)
Dijr
J3 === Σ
H H Diy-
WJ=1
5

---

First, J1 says that subcomponents should be similar to their prototypes. Second, J2 says that subcomponents should also be similar to other subcomponents that share the same prototype. Third, J3 says that different prototype subcomponents should be dissimilar.
Optimization problem. Our algorithm A uses 73 solve the optimization problem
(H" K*) arg min {> J1 + X2 J2 + A Ja) subj. th A 1/2 A v/s,
H.K
where A1, 22, A3 E Rz are hyperparameters. Finally, to construct Cz. A chooses
V= (wi 1); V= (1,-.,m,
E [(w,,, R.y))
where R.j f R f(w;, Wy, 1-==ieee.. i..., V are the prototype subcomponents according to H" E are the edges according to K", and R.j are the extent to which relations are satisfied by w; and wj. Z3 is guaranteed to find the optimal solution; in the event that multiple such solutions exist, it chooses one nondeterministically, Intuitively, our approach should perform well when a handful of prototypes are sufficient approximately capture the relational structure in the data, which appears to be true in the domains of rhyming poetry and melodies. Also, the user can define relations in a way that captures desired structure for any domain.
4 Relational Constraints in Neurosymbolic Generative Models
We describe our model for generating examples x. Recall that our approach proceeds in two steps: (i) generate c, and (ii) generate x given 2.. We describe each step in detail below.
4.1 Step 1: Generating Relational Constraints
The first step of our generative model is to generate relational constraints T. using a VAE -i... Pa(c 2) is VAE with p(2) = (2; 0, I) being a Gaussian distribution. The main choice is the architecture to use for the VAE. particular, we consider representation of c as a sequence encodes that subcomponent we should have the same prototype subcomponent as W4-s;; or if 8; S O, that w; corresponds to a new prototype subcomponent. In practice, we found that in the music domain, the vast majority of examples could be described using S 6, which decreased the number of possible values that could be predicted and simplified the problem; however, it would be possible in other domains for k to be as large
(s1, Sm). where E {0. 1.... k} for each i; intuitivelly
1. More precisely, we initialize & Ø. Then, we generate the sequence st {0, I,..,, k} and E {0, 1,.., m) (where r; is represented as a binary vector of length = [R] using either: (i) an LSTM- VAE, or (ii) feedforward network whose output is iteratively sampled from as a categorical distribution and then used as input in the next step (see Appendix [.. for details). For each i, we generate (w, R&) based on s; and r; according to the following approach: If s; = O. we generate new prototype subcomponent w using domain-specific generative model, and add d = (1i, i, R.)
to & s; > 0, we let 6i = (wi R.).
4.2 Step 2: Generating Examples Given Relational Constraints
Next, we describe how we implement the second step pa(x c) of our generative model. We propose three approaches for generating x given b,; give details in Appendix B
Approach 1: Constrained sampling. We sample values x ~ po()) by sequentially sampling wi ~ po(+) from pretrained generative model po (wr). We do so using rejection sampling at each i.e we sample w; ~ (.(.) until we find w; satisfying f(ū, w,, r) s h for each (w,i, addition, to speed up sampling, at each step of sampling w, (e.g., word in line or pitch in measure), we climinate choices that violate 4
i, r, h) E &.. In
Approach 2: Constraint-aware embeddings. We train conditional variational autoencoder (cVAB) po Po(w....., Wm c) in the form of graph convolutional network (GCN) that simultaneously generates all m subcomponents in way that satisfies c, and sample x (W1, ..., Wm) ~ (- c). The GCN takes as input embeddings of each prototype and subcomponent of ær and the adjacency matrix given by the edges in (where the relation is encoded as edge attribute). Then, the GCN-cVAE trained using the standard VAE objective (Kingma & Welling 2019), along with a semantic consistency loss that encourages the generated examples to satisfy

---

Models
FD
GCN Disc.
RF
SGM (Ours) (A1)
43.4
0.54
0.89
Models
NLL
GCN Disc.
RF
SGM (Ours) (A2)
32.7
0.63
0.79
SGM (Ours)
37.5
0.91
SGM (Ours) (A2)
1028.4
0.63
0.79
SCM (Ouss) (A2. No Syath. Ablation)
42.1
0.42
0.89
MusicVAE
1158.6
(Ours) (A2, Greedy Synth. Ablation)
40.5
MusicAutobot
1760.0
0.51
0,95
SGM (Ours) (A2. Continuous Relation)
33.2
0.46
0.88
Atlention RNN
39.9
0.47
0.88
MusicAutobot
53.7
0.51
0.95
Structureett
44.0
0.45
0.91
Table 1: Results for the music domain. Left: We show negative log-likelihood ("NLL", lower better) on the held-out human test set (i.e., by estimating the ELBo of the entire test set using sampling). Right: We show Fréchet distance on Music embeddings ("FD", lower is better). Both: We show the cross-entropy loss of the graph discriminator trained to distinguish synthesized programs of generated examples vs. held-out test set examples ("GCN Disc.", higher is better), and the accuracy of a random forest trained to do the same thing on handcrafted featurization of the programs ("RF", lower is better). The highest score in each column is bolded. As can be seen, approach with sampling strategy A2 outperforms the baselines on all metrics, also outperforming the ablation using the same strategy but without program synthesis (i.e., using the full adjacency tensor).
Approach Combinatorial optimization. We sample Po(-) by sequentially generating w; by solving an optimization problem whose objective is to maximize adherence to D. plus additional terms encoding domain-specifie heuristics encouraging wy to be realistic.
5
Experiments
We evaluate our approach on two domains: music and poetry generation. We provide details on experimental design and additional results in Appendix
5.1 Music Generation
We evaluated our approach on music generation, where is a song and w are measures of music. We consider 20 relations including equality, same rhythm, etc.; see Appendix C.2
Dataset. We used songs from the Essen folk song corpus (Schaffrath 1995). using 2223 for training and 555 for testing (after removing examples with less than 16 measures or that were not in the standard 4/4 meter). For this dataset, we used each of the three approaches A1, A2, and A3 described in Section 4 to sample x Po(- c). For A1, we use a pretrained transformer called MutooAut (Shaw 2020). For A2, we require generative model that constructs vector embeddings of measures; we use the pretrained version of Magenta's Music which embeds pairs of measures (Roberts et al. 2018) and adapted it to produce single-measure embeddings. We finetune all models on our training examples.
Baselines. We compare to MusicAutoBoot. a pretrained and finetuned attention LSTM (Attention- RNN) (Waite) 2016), Magenta's 16-bar Music VAE (pretrained and finetuned), and StructureNet, which integrates structure into LSTM (Medeot al. 2018). To show the importance of synthesis, we compare to an ablation that uses A2 but with full adjacency tensors instead of synthesizing compact representations of relational constraints, and one that uses a greedy synthesizer-iiee,, each step. greedily choose the single prototype and its relations that most increases (T. Finally, we consider using a continuous relation, namely, the cosine similarity of the Magenta VAE embeddings.
Metrics. We compare performance in terms of both high-level and low-level structure. For low- level structure, use the negative log likelihood (NLL) a held-out test set for MusicVAE, MusicAutobot, and our approach with strategy A2. The remaining approaches are not probabilistic (or estimating probabilities is intractable). For these approaches,
variant of the standard Fréchet distance (FD) score used to evaluate GANs (Borji 2019)- -i.e. the Fréchet distance between the MusicVAE (16-bar) embeddings of the generated music and the held-out test set.
For high-level structure, given generated (or human) example x, we use our synthesis algorithm to synthesize its relational constraints eo A(x). Then, given a collection Cgen (co | x E xgon) ) of
7

---

Models
GCN Disc.
FD
5GM (Ours, Al)
0.69
21.5
SGM (Ours, A3)
0.62
[3.51
SGM (No Learned Structure Ablation)
GPT2
0.47
14,3
GPT2-Opl Opt
BERT
0.50
54.9
Richlyyris
0.51
23.0
Table Results for the poetry domain. We show Fréchet distance on SentenceBERT embeddings ("FD", lower is better), along with the cross-entropy loss of the graph discriminator trained to distinguish synthesized programs of generated examples vs. held-out test set examples ("GCN Disc.", higher is better). The best score in each column is bolded. As can be seen, our approach (SGM) with sampling strategy Al outperforms all other approaches in terms of high-level structure, while approach with sampling strategy A3 outperforms all baselines in high-level structure and is also competitive with GPT-2-based models in FD scores.
synthesized structure for generated examples, along with a collection Chuman = (cz x X Numan] J of synthesized structure for the held-out human examples, we train graph convolutional neural network (GCN) to try and discriminate Cgen from Chuman: as well as a random forest (RF) over handcrafted features (see Appendix C.4). Intuitively, higher discriminative power should indicate less realistic structure. In both cases, we use a balanced dataset (i.e., 50% human held-out and 50% generated) so random predictions have accuracy 0.5. Recent work has shown that such discriminator-base metrics are valid for evaluating quality of generated examples (Lopez-Pat Pazez & Oquab 2016).
Results. In Table D we show results for models for which we can compute the test set NLL (left) and results for the remaining models (right). As can be seen, our approach (SGM) with sampling strategy A2 outperforms all other models in both tables, in terms of both high-level structure and low-level structure. In Table [ (left), the closest alternative is Music for which the NLL is not too much larger; however, it performs significantly worse than our approach in terms of high-level structure. In Table | (right), we find that our other approaches also perform well (though not as well as A2). In particular, A1 performs well in terms of low-level structure, but is more mixed in terms of high-level structure. contrast, A3 performs well in terms of high-level structure, but mixed in terms of low-level structure, most likely since it does not use learning- baamingg-basdd based model to generate low-level structure. Our ablation where we perform no synthesis performs poorly, especially in terms of structure, as does the one using greedy synthesis, demonstrating the importance of using constraint solving to synthesize compact representations of structure. On the other hand, greedy synthesis can be significantly more scalable than constrained optimization for large examples; thus, improving this strategy is an interesting direction for future work. Finally, using a continuous relation performs competitively in terms of FD score (though interestingly. it performs worse in terms of high-level structure), demonstrating that our approach can be applied with continuous relations.
5.2 Poetry Generation
Next, we apply our approach (SGM) to poetry generation: in this case, is a poem, and w is a line. We consider two relations, rhyming and equal meter; see Appendix C.3 for details.
Dataset. We use from Project Gutenberg's poetry collection PParrssh 2018). focusing 10-line poems with rhymes and meter, with 2700 for training and 300 for testing.
Our approach. In the rhyming domain, due to the lack of rhyme-aware line embeddings, we did not perform A2. In applying AI, rather than sample words going forward, we sample them backwards, making it casier to sample lines that satisfy rhyming constraints; see Appendix Thus, we use BERT to sample (Devlin et al. 2018), since it is bidircctional. We apply A3 by performing constrained optimization to satisfy many relations possible while maintaining a low NLL.
Baselines. We compare to generation using beam search for BERT and GPT2 Radford et al. 2019 Vaswani et al. 2017). both finetuned on our dataset. We also consider variant GPT2-Opi of GPT2 where we use beam search to choose line breaks a way that maximizes occurrences of rhyme and meter. We also tried variant of GPT2 that used constrained sampling to try and find poems that fit given rhyme and meter, but the search space was too large and it failed to generate a single poem even after several hours. We also compare to an implementation of RichLyrics (Castro & Attarian
8

---

One was done. Another was done. And I wish you know the way, Full name and date whom this story pour And know a lot of things that were called a war See a soldier, fair fair beautiful grace That men turn't toward. Another race Together, married. Much to sec, the dead Were gone. The man who ascended to head Office retired, and gave birth to a trace That doesn't 't tell name, but tells face.
One was done. Another was done. And I wish you know the way, Full name and date to whom this story pour And know a lot of things that were called a war See a soldier, fair fair beautiful grace That men turn' 'd toward. Another race Together, married. Much to see, the dead Were gone. The man who ascended to the head With full beard and hair was little said But old and not intended for bed.
Figure 2:
Left: Poetry generated using relational constraints c ~ (.).). Right: user modified variant of where the last two lines share prototype with the two lines before them.
Method
Average Score
Lyricism
Coherence
Rhyme/Meter
SGM (Ours, Al)
3.66
3.81
3,59
3,59
3.30
BERT Finetune
2,28
2.11
2,00
2.77
RichI.yrics
3.09
3.24
Table 3: A user study evaluation in the poetry domain. While GPT2-Finetune outperforms our model in terms of coherence (presumably due to the well-known superiority of GPT-2 over BERT for generation), our method outperforms in terms of overall lyrieism (i.e., whether the poem reads like poetry or prose), prominence of rhythmic/metrical structure, and average score.
2018
where the consecutive parts of speech for each line given the previous line and the ability to the correct word for the given part of speech were both learned separately from the corpus. Finally, to show the importance of learning the distribution over constraints, we consider an ablation that uses A1, but sampling &. uniformly randomly rather than from a learned distribution.
Metries. For low-level structure, we use FD score on SentenceBert embeddings, which are unaware of rhyme and meter (Riimers & Gurevych 2019); we cannot evaluate log- likeeiiildood since we are using constrained sampling. For high-level structure, we train a GCN to discriminate synthesized programs for generated examples vs, test examples.
Results. We show results Table 2 Our approach (SGM) with sampling strategy A3 significantly outperforms all baselines in terms of high-level programmatic structure, while also outperforming them in terms of FD scores. Approach A1 performs even better in terms of programmatic structure, but is not competitive with respect FD scores, presumably due the fact that GPT-2 is significantly better at natural language generation than BERT.
User study. We also performed user study, discussed in Appendix C..5 which further confirmed this methods' strength in the poctry domain. in this domain, with 50 participants.
User modifications. A key benefit of our approach is that the user can modify the relational constraints (or construct their own from scratch) for use the second step po(x c). giving the user way to guide the generative process. An example in the poetry domain is shown in Figure 5.2 and musical examples are shown in Appendix
6 Conclusion
We have presented novel approach for representing and synthesizing relational constraints on sequence data, and for generating examples whose relational structure resembles that of the training data. Our experiments demonstrate that we outperform existing approaches in terms of achieving human-like structure, while performing comparably or better on both user study and widely- quantitative metrics that do not explicitly account for structure. Finally, our approach enables users to guide the generative process by modifying constraints. A key direction for future work is to apply our approach to other applications such as dialog generation and summarization, which may require novel programmatic structure compared to the ones study.

---

Limitations & ethical considerations. We discuss limitations and ethical concerns in Appendix
References
Atanassovv and Pulov. Prolog realization of a poetry generator. In Proceedings First International IEEE Symposium Intelligent Systems, volume 3, pp. 53-53. IEEE, 2002.
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Advances in neural information processing systems, pp. 1494-2504, 2018.
Ali Borji. Pros and cons of gan evaluation measures. Computer Vision and Image Understanding, 179:41-65. 2019.
Pablo Samuel Castro and Maria Attarian. Combining learned lyrical structures and vocabulary for improved lyric generation. CoRR, abs/1811.04651, 2018. URL httpp://arxiv..rg/
1811. 04651
Stefano Ceri, Georg Gottlob, Letizia Tanca, et al. What you always wanted to know about datalog(and never dared to ask). IEEE transactions on knowledge and data engineering, 1(1):146-166, 1989.
David Cope. An system for computeer-asiisee composttion.. Computer Music Jourmal, (4)):30 46, 1987. ISSN 01489267, 15315169. URL http: /wwp:///wwwww//.. wastoroogg/aoooe.eeeeeoeooe wttpa//rr///aaaae3222222222
Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. Plug and play language models: A simple approach to controlled text generation. CoRR, abs/1912.02164, 2019. /tt/tttpp///aa....../r/////////1
Cristina David and Daniel Kroening. Program synthesis: challenges and opportunities. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 375(2104): 20150403, 2017. doi:
Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. Berlin, Heidelberg, 2008.
Springer- Verlag. ISBN 3540787992.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805, 2018. URL
04805
Kevin Ellis, Armando Solar-Lezama, and Josh Tenenbaum. Unsupervised learning by program synthesis. In Advances in neural information processing systems, pp. 973-981, 2015.
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Joshua B. Tenenbaum. Learning to infer graphics programs from hand-drawn images. CoRR, abs/1 abs/1707.09627, 2017. URL http
//arxiv.. /arxiv.org/abb/ 1707. 09627
Kevin Ellis, Catherine Wong, Maxwell I. Nye, Mathias Sablé-Meyer, Luc Cary, Lucas Morales, Luke B. Hewitt, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. CoRR, abs/2006.082 08 2020. /Rtp:ttts////xxiv.coo wwtp:/wwwwwwr//////////o//
abs
08381
Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), Advances Neural Information Process- ing Systems 27, cC/ httppaper/55.0 5423 generative adversarial nets ..f..pdf
Curran Associates, Inc., 2014. URL http::/paperr: nips
C. Horton and I.. Ritchey. Workbook for Harmony Through Melody: The Interaction of Melody, Counterpoint, and Harmony in Western Music. Scarecrow Press, 2000. ISBN URL htttttttt:://ookee wwwgle..ooo.....o.oooooooooo.o.. com/
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Noam Shazeer, Ian Simon, Curtis Hawthorne, Andrew Dai, Matt Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer: Generating music with long-term structure. 2019. URL http:/:s////xxvvvvo/vo
04281
10

---

Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Anmando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations, 2019.
Dasaem Jeong, Taegyun Kwon, Yoojin Kim, and Juhan Nam. Graph neural network for music Score data and modeling expressive piano performance. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), ICML, volume 97 of Proceedings of Machine Learning Research, pp. 3060- 3070. PMLR, 2019. URL BtLbttp:/ //bld.l..... uni trierrrie..... de cb/ con cm1 htt.ccmmcmmmimmmmmmmmcmmmmmmmmme html TaillHJenneee #JeoncKKN19
Gullapalli Keerti, A N Vaishnavi, Prerana Mukherjee, A Sree Vidya, Gattineni Sai Sreenithya, and Decksha Nayab, Attentional networks for music generation. ArXiv, abss2200.00384, 2020.
Diederik Kingma and Max Welling. An introduction to variational autoencoders. CoRR.
abs/1906.02691, 2019, URL htth:::: /tapxi///axiv...// org/ htwp://bbb/99... 02691
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the 5th International Conference on Learning Representations, ICLR '17, 2017. htR.httpss// htt.:httts///ppeeeettee www.eeeweeeeeetnnineeeeeeeeeeeee "errumm?ddsSJ44ayyy
net./ forum?
Jey Han Lau, Trevor Cohn, Timothy Baldwin, Julian Brooke, and Adam Hammond. Deep-speare: A joint neural model of poetic language, meter and rhyme. CoRR, abs/ NE011887.03999 2018. URL
http::/arxiyy wwt.////////... 1807 03491
Xiang Lisa Li and Alexander M. Rush. Posterior control of blackbox generation. CoRR, 000//005500460, 2020. URL htt.:tts.///.....og///o////
04560
Yi Liao, Yasheng Wang, Qun Liu, and Xin Jiang. Gpt-based generation for classical chinese poetry. CoRR, abs/1907.00111,, 2019a. UKLL:ttt.///ar2x..or/////////110 10110
Yi Liao, Yasheng Wang, Qun Liu, and Xin Jiang. Gpt-based generation for classical chinese poetry. CoRR, abs/1907.00151, 2019b. URL.ttp::/
David Lopez-Paz and Maxime Oquab. Revisiting classifier two-sample tests. arXiv preprint arXiv:1610.06545. 2016.
Gabriele Medeot, Srikanth Cherla, Katerina Kosta, Matt Micirar, Samer Abdallah, Marco Selvi, Ed Newton-Rex. and Kevin Webster. Structurenet: Inducing structure in generated melodies. In Emilia Gómez, Xiao Hu, Eric Humphrey, and Emmanouil Benetos (eds.), Proceedings of the 19th International Society for Music Information Retrieval Conference, ISMIR 2018, Paris, France, September 23-27, 2018, pp. 725-731, 2018. URL httt:://smirr0000 iream. fr/doc/ pdfs/126 Paper. pdf
Hongyuan Mei, Guanghui Qin, Minjie Xu, and Jason Eisner. Neural datalog through time: Informed temporal modeling via logical specification. CoRR, abs/2006.16723. 2020a. URL https
7/ htrc/aba/2000 16723
Hongyuan Mei, Guanghui Qin, Minjie Xu, and Jason Eisner. Neural datalog through time: Informed
temporal modeling via logical specification. CoRR, abs/2006. 16723, 2020b.
URL https
//arxiv. org/ http:/ab/220000 16723
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: constrained sentence generation by metropolis-hasting sampling. CoRR, 0tss/811.11096. 2018. URL
abs/1811.10999
Islam Elgamal Muhammad Faisal, Islam Faisal. Generating random, yet, constrained music. 2017. URL http:///eeaapppeeooooooaaaaaaaaa
OpenAl. Musenet, 2019. URL http:t/ss///ggnaa...coo//l////pp
Russell Ovans and Rod Davison. An iterative constraint-based expert assistant for music composi- tion. In Proceedings of the Biennial Conference- Canadiaan Society for Computational Sudies of Intelligence, pp. 76-76. Citeseer, 1992.

---

Allison
Parrish,
2018.
URL
http:::/ggtthub.cmm//ppaaa/
gutenlergg-oottyyccrrre
Jeffrey Pennington. Richard Socher, and Christopher Manning. Glove: Global vectors for word
representation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543,
2014. URL http: wwwp wwwwwb.www......... org wttpg///atthhlooyyy-11111
Donya Quick. Learning production probabilities for musical grammars. Journal of New Music Research, 45:295-313, 10 2016. doi: 10.1080/09292215.200 12286880.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. CoRR, abs/ 10084, 2019.
10084
Adam Roberts, Jesse H. Engel, Colin Raffel, Curtis Hawthorne, and Douglas Eck. A hierarchical latent vector model for learning long-term structure in music. CoRR, abs/ 05428, 2018. URL
http://arxiv o abs 180.105438.008
Asir Saeed, Suzana Ilie, and Eva Zangerle. Creative gans for generating poems, lyrics, and metaphors. CoRR, abs/1909.000 0993449944 2019. URL
09534
Örjan Sandred, Mikael Laurson, and Mika Kuuskankare. Revisiting the illiac suite a rule-based approach to stochastic processes. Sonic Ideas/Ideas Sonicas, 2:42-46 1:42-46,00 01 2009.
H. Schaffrath. The essen folksong collection in the humdrum kern format. 1995.
Andrew Shaw, 2020. URL
Y. Cem Sübakan and Paris Smaragdis. Diagonal mns in symbolic music modeling. CoRR, abs/1704.05420, 2017.
abaaaabs//110 05420
Dima Suleiman, Arafat Awajan, and Wael Al Etaiwi. The use of hidden markov model in natural arabic language processing: a survey. Procedia Computer Science, 113:240-247, 2017. ISSN 1877-0509.
doi: https://doi.or//10. http:///00....000.0..00000000000 l/www. w/www.scient.. www.scceeeeeeerr....e....e
URL https
The 8th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EU-
com wwreeecttcooccceneeeeeeeeeeeeeee /ttp:///eeeneerrrrr//////////111
SPN 2017) / The 7th International Conference on Current and Future Trends of Information and
Communication Technologies in Healthcare (ICTH-2017) Affiliated Workshops.
Mattt Thompson. Möbius: Exploring a new modality for poetry generation. 2009.
Lazar Valkov, Dipak Chaudhari, Akash Srivastava, Charles Sutton, and Swarat Chaudhuri. Houdini: Lifelong learning program synthesis. In Advances in Neural Information Processing Systems, pp. 8687-8698, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, abs/1706.03762, 2017. URL
037622
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference Machine Learning, pp. 5045-5054, 2018.
Elliot Waite, 2016.
URL httpps//maggett..eeoooooooooooo.
Lookback rnn attention rnn
Zhe Wang, Wei He, Hua Wu, Haiyang Wu, Wei Li, Haifeng Wang, and Enhong Chen. Chinese poetry generation with planning based neural network. CoRR, abs/1610.09889, 2016. URL
http://arxiv.. orq abs http//bs//61111 1610.09889
Li-Chia Yang, Szu- Yu Chou, and Yi-Hsuan Yang. Midinet: A convolutional generative adversarial network for symbolic-domain music generation using 1d and 2d conditions. CoRR, a 10847,
2017a. URL hRLhttp:: //trxv/...v///////////////aaaaal wwtp./oogg/b////0...1....
12

---

Xiaopeng Yang, Xiaowen Lin, Shunda Suo, and Ming Li. Generating thematic chinese poetry with conditional variational autoencoder. CoRR, abs/1711.07632. 2017b. URL http://arxiv
org/ hrg/abs/1711 07632
Halley Young, Osbert Bastani, and Mayur Naik. Learning neurosymbolic generative models via program synthesis. 2019.
13


Reviews:
[{"review_id": "w6h3gN-TJBi", "reviewer": "Reviewer_Jk4L", "summary": "This paper studies a generative model for sequential data that has relational constraints. It proposes to use a two-stage generation process to (1) generate relation constraints (2) sample/generate the examples based on the relational constraints. Two domains, music and poem, have been used as evaluation data to test the correctness of the proposed method.", "questions": "Personally, I am hoping to see more concrete examples in the main paper to clearly show how the generated examples capture the relations with/without the proposed method.", "limitations": "I didn't find the section describing the limitation of this work other than the conclusion part, despite it is marked as 'Yes' in the checklist. Please correct me if I missed it.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To me, this paper is on the borderline: on one hand, the topic and method presented are interesting and intuitive, while experimental results and analysis might be less convincing.\n\nPros:\n(1) The topic and method are interesting and intuitive. Generating examples based on relational constraints seems to be a promising direction to consider for future work. This could further be extended to other domains.\n(2) The author has spent efforts on user studies to examine the effectiveness of the method.\n\nConcerns:\n(1) The method still requires a lot of human effort in order to work well. I am not sure how easy it is to be used for new tasks.\n(2) It appears to me that there is no golden metric to be used for evaluation in this specific context. The paper proposed at least two ways: the first one is based on NLL, which I am not sure if it really reflects the model is better in terms of capturing low-level structures; and the other is based on trained models, which I suspect if it can be biased for certain groups of methods.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jpyJVEIFatg", "reviewer": "Reviewer_aV2a", "summary": "This paper proposes generative models for poetry and music which have natural relational constraints on their subcomponents -- metric/rhyme on lines for poetry, and repetition of measures. The approach is similar to a variational autoencoder where the continuous latent variable z generates a constraint sketch C, and the poem/music arrangement is generated based upon the sketch C. This sketch is defined with the assumptions that the final artifact has m subcomponents, and uses a subset of these subcomponents as prototypes to define additional relationships between the subcomponents and the prototypes. The sketch C|x is obtained deterministically by an SMT solver Z3, and rest of the model is trained to maximize the MLE via lower bound approximation. Empirical comparison is done with relevant prior work.", "questions": "-- How do you sample/generate from BERT since it is not a probabilistic model? Please describe the procedure for generation and discuss this in greater detail. \nRelevant references:\nBERT has a Mouth, and It Must Speak: BERT as a Markov Random Field Language Model, Wang and Cho\nExposing the Implicit Energy Networks behind Masked Language Models via Metropolis--Hastings, Goyal et al.\n\n-- you mention “Z3 is guaranteed to find the optimal solution”. I am not sure how is it guaranteed. On the surface this looks like a NP-hard problem but their might be simplifying assumptions I may have missed.", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper tackles an important problem of incorporating structural constraints in otherwise opaque neural generative models and provides a clean solution to the domains explored in the paper. This kind of research is welcome in order to build more controllable and interpretable generative models. However, I feel the title/conclusion is slightly overclaiming because this approach I believe is limited only to a subset of relational constraints that are relevant to the domains explored in this paper.\n\nThe comparison is done with relevant baseline which clearly shows the effectiveness of the proposed approach over existing work.\n\nHowever as mentioned earlier, this approach seems like it would work for very specific domains, where there is a clear mapping between prototypes and subcomponents and constraints are only defined on the subcomponents (Moreover, the constraints/algo in this paper only considers constraints over pairs of subcomponents). I am not sure how other kinds of constraints can be tackled in general. For example, even making the number of subcomponents (variable m) variable is not trivial practically, so a discussion about this aspect would improve the paper.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "awRkzcnU2I", "reviewer": "Reviewer_Bid8", "summary": "This paper proposes a deep generative model for sequence data, where the relational constraints between components in the sequence are modeled as latent variables. The overall framework is largely the same as Young et al. (2019) that is designed for image domain, while in the sequence data like text new challenges need to be addressed since the relationation constraints are different. The authors consider binary relations for the poetry and music domain, such as whether two lines of the poetry should rhyme. The model is learned with a VAE objective while being somewhat more complicated due to the symbolic relation variable. Specifically, the relational constraints need to be pre-extracted through solving a constrained optimization problem, then a separate VAE is learned on the relational constraints, and finally the authors propose three different approaches to model the data conditioned on the relation variable and the normal VAE latent variable. The model is overall interesting as a neurosymbolic deep model, which is claimed to model the global coherence better than typical sequence neural models and users could more or less control the generation through specifying the constraints. Experiments including human study confirm its superiority over normal NNs on generation such as MusicAutobot and GPT2. ", "questions": "Questions: Is $f$ in Line 143 pre-known? I feel it is known from Eq. (1), right? If so, do you use prior knowledge/heuristics to obtain the paired relations in advance and compute $f$?\n\nSuggestions: I think many details and the limitations should be included as mentioned in the weaknesses above, the presentation could also be improved.  \n", "limitations": "The authors discussed the potential negative societal impact in the work but I don’t think the limitations were adequately discussed. \n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\n1. I think the authors make an attempt to address an important and difficult problem in sequence modeling by modeling symbolic relational constraints. Even though the method is not perfect (e.g. much more complicated than non-symbolic baselines), I would like to see such papers appear in the conference.  \n2. The method is novel (at least in the application to sequence data) and interesting. For example, extracting prototype subcomponents to obtain linear complexity for paired relations is clever, and solving it as a constrained optimization problem is a nice contribution.   \n3. Empirical results look strong, though I do have some concerns (see below).\n\n### Weaknesses:\n\n1. The method is much more complicated both methodologically and practically than the baselines, thus the empirical impact of the proposed method could be limited in reality – I guess not many people would use it practically. This is an important weakness that I have to mention here, yet I don’t think it is a sufficient reason to reject this paper since I think we should encourage this kind of work. The complexity of the method is expected since modeling symbolic variables in NNs is not easy. However, I think this paper should spare more space to discuss such complexity and limitations of this work. There are many limitations that need a discussion and many details are missing from the paper:  \n(1) There are many hyperparameters added by the method which the baselines do not have. How do you choose those hyperparams? How sensitive are the results to them? In fact, I cannot find the values of many hyperparams, e.g. $k_{min/max}, \\lambda_{1/2/3}$.  \n(2) What is the overall computational cost and how does it compare to the baselines? How different are the efficiencies of the three approaches in Section 4.2? For example, the rejection sampling in Approach 1 may be slow. I think the efficiency aspect of the proposed method warrants a separate paragraph of discussion (at least in the appendix)  \n2. The paper is not well-presented. My overall feeling is that the authors try to compact too much content into the main body of the paper and therefore many details are missing and sometimes it could be difficult to follow. This is particularly true for Section 4 and 5.   \n3. Evaluation is important. Because of the lack of details as mentioned above, I am not sure whether the automatic evaluation in the paper is properly done. For example,  \n  (1) When you compute NLL, did you directly use one sample to estimate ELMO or use importance weighting to compute a tighter lower bound? The former is known to be inaccurate as a surrogate to NLL  \n  (2) When you train classifiers, what is the evidence to ensure that they are trained properly? What hyperparams did you try to train those classifiers? Did you try to tune them?   \nThere is no need to tell too much on these details, but a paragraph in the appendix to convince readers that you did try to make evaluation convincing is much better.   \n4. I appreciate the user study evaluation, but I would like to know more details than the given ones in the appendix, for example, how many users score each example? If multiple users score the same example, do you have the agreement score for them (like variance)? – giving more details would make your results more convincing.\n\n```\nAfter author response:  \nThe author response and the update of the paper addressed most of concerns, and I would like to increase my score to 6.\n```\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2bCEd1beouv", "reviewer": "Reviewer_kJEL", "summary": "This paper proposes a method for generating sequences with relational structure. Specifically, the authors study the generation of poetry and music, where different lines of a poem have rhyme or equal meter constraints, and different measures of music have rhythm or pitch class constraints, etc. They represent these relational constraints as a bipartite graph, where the vertices on the left are the prototype subcomponents (i.e., lines or measures), the vertices on the right are the subcomponents to be generated, and the edge labels indicate the relations that the right endpoints need to satisfy with respect to the left endpoints.\n\nTo extract the relational constraints of a training example, the authors formulate it as a combinatorial optimization problem and use Z3 to solve it. To generate a sequence, they first use a VAE to generate relational constraints, and then generate subcomponents that satisfy these constraints, for which the authors provide three approaches: rejection sampling, conditional VAE, and combinatorial optimization.\n\nExperiments on music and poetry generation show that the proposed method outperforms previous approaches in capturing relational structure.", "questions": "In more general, free-form essays, there are also connections between sentences or paragraphs. Can this method be extended to capture these structures to improve generation quality?\n\nIn line 196, for the objective $J_2$, should it be $\\sum K_{ki}K_{kj}$ instead of $\\prod K_{ki}K_{kj}$?", "limitations": "The proposed method seems to be suitable only for generating highly structured sequences with predefined relations. Also, the algorithm to extract the relational constraints has high time complexity.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "$+$ Despite doing well at generating locally coherent content, large language models still struggle to capture high-level structure. This paper considers relational structure between subcomponents and proposes a novel method to extract and learn to conform to them. This approach is particularly suitable for the generation of poetry and music with explicit relational constraints.\n\n$+$ To implement the relational constraints, this paper makes solid technical contributions, including a program synthesis algorithm and a neurosymbolic generative model.\n\n$-$ Experiments are only conducted on two small datasets with thousands of examples.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept