Neurosymbolic Deep Generative Models for Sequence Data with Relational Constraints
Authors: Halley Young
Maxwell Du
Osbert Bastani
Venue: ICLR 2022 Submitted (2022)
Keywords: synthesis
music
generative
constraints

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 at the cost of 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 program synthesis 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.

Under review as a conference paper at ICLR 2022
NEUROSYMBOLIC DEEP GENERATIVE MODELS FOR SEQUENCE DATA WITH RELATIONAL CONSTRAINTS
Anonymous authors Paper under double-blind review
ABSTRACT
There has been significant recent progress designing deep generative models that generate realistic sequence data such as text or music. Nevertheless, 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 novel approach for incorporating global structure in the form of relational constraints between different subcomponents an example (e.g., lines of poem 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 program synthesis algorithm that infers the relational constraints present in the training data, and then learn generative model based the resulting constraint data. In 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.
INTRODUCTION
There has been tremendous recent progress in designing deep generative models for generating sequence data such as natural language (Vaswani et al. (017)) or music (Huang et al. (019). 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, new examples can 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, 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 in 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. (219)) proposed newrosymbolic 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 is to leverage program synthesis to extract structure from data-in particular, given an example image x, they devise an algorithm A that extracts program e = A(z)) that represents the set of 2D repeating patterns present in training examples Then, using the pairs (x, c). they train two generative models: (i) model Ps (c) that generates program, and (ii) model po(x c) that generates an image that contains the structure represented by e. 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) for generating programs and (o c) for generating images conditioned c.
We represent the relational constraints er present in an example x by relating each subcomponent w of given example x with a prototype w, which can be thought of as the "original" subcomponent from which w is constructed. In particular, the relationship between w and v is labeled with a set of relations R, which encodes the constraint that w and te should satisfy relation for each R.

---

Under review as a conference paper at ICLR 2022
Importantly, while each subcomponent is associated with single prototype, each prototype may be associated with multiple subcomponents. As a consequence, different subcomponents associated with the same prototype 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 generate.
related in some way. This representation is compact, only requiring
Then, we design a synthesis algorithm that can extract an optimal representation of the structure present in training example x (i.e., the relational constraints C.)) We show how express the synthesis problem as a constrained combinatorial optimization problem, which we solve using an SMT solver Z3 (De Moura& & Bjomer (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(2 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 a 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 ootte--f-theaarr models in terms of low-level structure, while significantly outperforming them in terms of high-level structure. We also perform user study in the poetry domain to determine user-perceived quality of the generated poetry along three dimensions (structure, lyricism, and coherence), and found that on average, our approach outperformed state-of-the-ar 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 I illustrates how our approach is applied to generate poetry. During training, our approach uses program synthesis to infer relational constraints Cg present in the examples æ. and uses both æ and Cæ to train the generative models. Here, C2 is a bipartite graph, where the LHS vertices are prototypes, and the RHS vertices correspond lines of x. Each vertex on the right connected to exactly one prototype, and is labeled with constraints on how it should relate to its prototype. To generate new examples, it first samples relational constraints c, and then samples an example x that satisfies e-i.e., we need to choose a line to fill each RHS node in way that the line satisfies the relations with its prototype. Furthermore, a user can modify the sampled constraint e 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 strueture in drawings (Ellis eet al. 2015) and to reinforcement learning (Verma et al.) 2018). These techniques have benefits such as improving interpretability (Verma et al. 2018 Ellis al.. 2020), enabling learning from fewer examples (Ellis et al.] 2015). generalizing more robustly (Inala et al. 2019). and being easier to formally verify (Bastani et al. 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 (Valkoy et al. 2018). In contrast to these approaches, our focus is on 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 few decades has focused on music and poetry generation, and on using relational constraints neural models; include a discussion of the most relevant such research in Appendix A
2 BACKGROUND ON NEUROSYMBOLIC GENERATIVE MODELS
Consider the problem of learning a generative model given training data from the underlying distri- bution. Given training examples x æ1, Ty. ~ p", our goal is to learn a generative model pa R p" pa. We consider sequence data-i.e.. an example
from which we can draw additional samples x E X is a sequence r = (W1,- ..., wm) E mm For example, each subcomponent w may be a line of poem measure of music, and may be poem or song.
We use fixed simplify our exposition; our approach trivially extends variable m.
2

---

Under review as a conference paper at ICLR 2022
"Futher," said, "Father, cunnot play The horp
The terp that okde give sligk
dayma
didst me, and
dhymo, midor
Lsst in idleness, while to and fro About me thy serene, grave servants goi And I um weary of my lonely ease. Better a perilous journey overseus Away from thee, than this, the life lead,
And anvecary of leady cai,
drymo
Mayy from taaithstte th Miee
(hymos. mndel
fhymes, meter
rhymo,
To sit all day in the sunshine like weed grows naught-
fhymes
more they Who serve thee most; serve thee in no way
dhyms, mider
diyso, meter
Training Example
Relational Constrinnts Cz
Mudic to song, ns the city
Hymess, meter
Music on the city air little music to live upon
fiee opin
Bymos
Sonp anea pour with sas,
dhymes, meler
song, yes, yes, long with
0.5
Uni al resaly for recriggii mel
fhymos
And all together if they are all ten,
the ciptall wita chaio.
dhymas, mila
Until all ready for men again and
And man aroend
fhymes,
To the capital hall ride with chase,
1.2.
Thonght sgos dorae
thynes, meter
And look like men tied full all around
dlyasss
You, and whisper that I shall found,
fhymas miter
Though I'm not built upon a little dome,
fyymes
say, made home, make
Sample Latent Vector p()
Sample Relational Constraints
Sample Exumple
p2(-12)
--pg(11c)
Figure 1: Top: For each training example v, our algorithm uses program synthesis to infer the relational constraints c₂ AA(x) present in æ. Then, uses Cg and æ to train pa(ce) and pa cz). Bottom: Process for generating a sample from the learned VAE Pa(ca | z) (where 2 is Gaussian noise) and model po Cz). Lines with the same prototype are shown in the same color; metrical constraints are represented as purple and rhyme constraints as green edges.
We interested in domains where likely examples satisfy latent relational constraints E C over the subcomponents. For instance, e may say that two measures w; and w of x start with the same series of pitches, or that two lines w; and wy of rhyme. We assume given set of relations R (e.g.. r E RR might be "rhyme" or "equal"), and a function f' W x W x R + [0, 1] such that f'we w'rr) indicates what extent and w/ satisfy relation r. Then, is a compact representation of the relations present in an input x. We describe the structure of c in detail in Section [.T,, 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 on a latent value 2 E 2 Z-iee
(r, = // po(x: (e) po(e) 2) p(z)dz.
o//
CEC
Then, Young et al. (2019) considers the variational distribution
qī(c, 2 2)) qz(2 e) q(cc [z)
and q(c x)) 5(c
(x)c-c). cx).
Here, 8 is the Dirac delta function and c, is single representative generated from x using program synthesis algorithm (David& & Kroening 1i..) an algorithm A that takes as input an example and outputs a program
A(x) encoding the relational constraints present in æ. Next, Young et al. (211)) derive an evidence lower bound
log (x) 2 log (x)) + Eegg(lc,) Pogg [=] DKI. (gg(2 (x) p(=)).
where DKr. is the KL divergence and H is information entropy. The first term is the log-likelihood of a generative model predicting the probability of example x given relational constraints cz. and the second and third terms form the loss of a variational autoencoder (VAE) Po(c 2) and 9g(2 X', this approach separately learns (1) a VAE to generate c, trained on the relational constraints c₂ synthesized from each training example æ, and (ii) model to generate given cz: the latter take multiple forms such second VAE or a generative adversarial network (GAN) (Goodfellow et al.] 2014). This approach is called Synthesi--guidde generative models (SGM) since it uses program synthesis guide training.
c) (Kingma& & Welling 2019). In summary, given training examples
3

---

Under review as a conference paper at ICLR 2022
To leverage this framework, we have to instantiate (i) the space of relational constraints C, (ii) the synthesis algorithm A : X' - used to extract a program encoding the structure of z, and (iii) the architectures of pa(c 2). 9g(2 c). and po( c). In prior work, Young al. (2019) used heuristics specific to the the image domain to achieve these goals-in particular, they used (1) simple equality constraints on sub-regions of the image designed to capture 2D repeating patterns, (ii) a custom synthesis algorithm that greedily adds constraints in the data to the program, and (iii) a representation of Ca as an image, in which case Po is a generative model over images, and pe, 4g based on an encoding of e as a fixed-length vector.
We design synthesis algorithm that expresses the synthesis problem constrained combinatorial optimization problem, which it solves using an SMT solver called Z3 (De Moura & Bjømer (008). In terms of (ii), our programs encode declarative constraints rather than imperative renderings, so the previous architectures of Pa. and 43 cannot be used. Instead, we use expert domain-specific heuristics, transformers (Vaswani et al., 2017). or graph neural networks (GNNs) (Kipf & Welling 2017) for Pe and 9z- For po. we propose several methods for imposing the constraints encoded by when generating an example x.
RELATIONAL CONSTRAINTS FOR SEQUENCE DATA
We describe how we represent relational constraints r, as well as our algorithm A for synthesizing the relational constraints cz = -Azz) present in an example sequence
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 z that satisfies c. Thus, for each training example x, we need to design relational program that encode constraints on the structure of 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 c encodes a set of relational constraints.
A relational constraint call w E W a protolype subcomponent. An example x satisfiex & to extent h (denoted æ F d) if (wū, wi; r) h, where w; is the ith subcomponent of x. 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 dxx)= = 1 if satisties the maximal extent and ((z) 0 if does not satisfy Φ at all.
+ W x I x R, where I = {1, m) is tuple é = =(w, i);;
Next, relational program encodes set of relational constraints on examples x. We represent cas an undirected labeled bipartite graph (V, V, E) with vertices V and V and edges E x x 2R, where R is the set of relations and 2 the power set of R. The vertices u E V are prototype subcomponents き E W: equivalently, they may be vector embeddings of prototype subcomponents. The vertices E V = {1, m are the indices subcomponents æ. The edges e E E are tuples [o, R] For tractability of synthesis, we impose the constraint that each v E V is part of a single edge (w, v, R) (though ō E may be part of multiple edges). Finally, c encodes the set of relational constraints
e = (w, i, R), where
4 ((,,ir,)) h) (w, R) EART]
In other words, includes the relational constraint that each subcomponent w, of æ should have all relations r E R with prototype i to extent h, where u is connected to i.
In this paper, for most examples, informally state that a pair w, i does not have relationship r if f(ū, r, = O. However, as we show in our experiments, non-boolean functions with values between 0 and can be used as well.
consider binary relationships that have 0 or I as values, and
For example, in Figure]] I the graph shown on the top right encodes a relational constraint cas and the top right shows an example that satisfies all the constraints ø E &., with value greater than O. The nodes on the left-hand side of c₂ are prototype subcomponents v E W, each of which is a line of poetry. The nodes the right-hand side correspond indices i (from 1 top to
10
4

---

Under review as a conference paper at ICLR 2022
on the bottom); each one is labeled with set of relations RŞ. Then, &. contains constraints Φ = (w, R.) for each edge úi - in the graph, which says that line i of æ should have relations E R, with i. For instance, the last (10th) node in C2 has constraints R1o {rhyme, meter), and is connected to prototype line vi T"hhe harp that thou..." Thus, this edge encodes a constraint (i0, 10, R1o) saying that the last line of should rhyme and have the same meter w. Indeed, the last line of x is w10 ="Who serve thee most...", which satisfies this constraint.
Remark 3.1. We use prototypes rather than direct relationships between components to ensure the 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 experiments, we show that approach significantly outperforms attempting to generate full graphs (i.e., adjacency tensors).
size of the graph is tractable-
Remark 3.2. We refer to as program since can be interpreted as Datalog program (Ceri et 1989) (i.e., a relational logic program); in particular, & is set of Datalog relations over z E X.
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 C₂ 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, es 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 binary vector H E IB"" and binary matrix K E _B Intuitively, H4, indicates whether subcomponent w, of a prototype subcomponent in c, and Kij indicates whether is the prototype for subcomponent w/.
Constraints. Our optimization problem has the following three constraints:
4/ = Kimin <
Σ
H: kimax
2/2
Kij 1,
4/
Kij S m Hi.
First, th says that the number of prototype subcomponents is between kiii and kmmx Next, 2/2 says that every subcomponent w corresponds to exactly one prototype subcomponent wy. Finally, 4/3 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 IR. mmm, where Di, measures the similarity between components w; and wy: smaller values indicate greater degree of similarity. In particular, define
Dij "FER((W,,
i.e., Dij is the extent which each R satisfied by my and my- Then, objective (which is to be minimized) has the following three terms:
m Σ
m
J Σ Kij Dig. 1==1
J==
II
Kej
Dij-
J3=
Σ H; H Dig- iJ=1
fJ==
First, J1 says that subcomponents should be similar to their prototypes. Second, J/ says that subcomponents should also be similar other subcomponents that share the same prototype. Third, J3 says that different prototype subcomponents should be dissimilar.
Optimization problem. Our algorithm A uses Z3 solve the optimization problem
(H* K*) arg min {A J1 + Xa J2 + Aa JaJ H.K
subj. to ti A 1/2 A vas
(1)
where \1, A2, A E R2 are hyperparameters. Finally, to construct Ca. A chooses
V = (w; H; = 1), == (1,...,. E = [(W,, Rij) KiJ = 1},
5

---

Under review as a conference paper at ICLR 2022
where R.j for E R f(W,, w) 11 V are the prototype subcomponents according to H", E are the edges according to K and R. 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, 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 way that captures desired structure for any domain.
RELATIONAL CONSTRAINTS IN NEUROSYMBOLIC GENERATIVE MODELS
We describe our model for generating examples z. Recall that our approach proceeds in two steps: (i) generate c, and (ii) generate x given &e. 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 D. using a VAE-i.e. Pa(c 2) VAE with p(2) (2; 0, I) being a Gaussian distribution. The main choice is the architecture to use for the VAE. In particular, we consider representation of с as sequence (81,...,,m) 8m), where &; E {0. .....k) k} for each i; intuitively, 8; encodes that subcomponent wy should have the same prototype subcomponent as Wi-s,, or if 8; S O, that Wy 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 & to be as large as m 1.
More precisely, we initialize &. Ø. Then, we generate the sequence 8, E {0, 1,.., k} and T, E {0, 10......, m. (where r; is represented as a binary vector of length n = [R] using either: (i) an LSTM- VAE, (ii) feedforward network whose output is iteratively sampled from as a categorical distribution and then used as input in the next step (see Appendix C.1 for details). For each i, we generate (10, R,) based on 8t and r; according to the following approach: If 0, generate new prototype subcomponent tē using a domain-speciin generative model, and add di = (w0, i, R:) o.. If > O, we let Φ; (wi- i, R.).
4.2 STEP GENERATING EXAMPLES GIVEN RELATIONAL CONSTRAINTS
Next, we describe how we implement the second step po c) of our generative model. We propose three approaches for generating x given b.; we give details in Appendix B
Approach 1: Constrained sampling. We sample values Po(+) from a pretrained generative model (w)). . We do so using rejection sampling at each step i..., sample w; po(-) until we find w; satisfying ['i wi,r) r) Rs h for each (w,,, r,, 4.. In addition, to speed up sampling, at each step of sampling wi (e.g., a word in a line or a pitch in a measure), we eliminate choices that violate 4..
po(:) by sequentially sampling w,
Approach 2: Constraint-award embeddings. We train a conditional variational autoencoder (cVAE) pa (W), ... Wm. c) in the form of graph convolutional network (GCN) that simultaneously generates all m subcomponents in a way that satisfies and sample x = (Wi..., Wm) po c). The GCN takes as input embeddings of each prototype and subcomponent of x, and the adjacency matrix is given by the edges in (where the relation is encoded as an edge attribute). 'hen, the
GCN-cVAE is trained using the standard VAE objective (Kingma Welling 2019), along with a semantic consistency loss that encourages the generated examples to satisfy
Approach 3: Combinatorial optimization. We sample x (- by sequentially generating w, by solving optimization problem whose objective is to maximize adherence to 4 plus additional terms encoding domain-specific heuristics encouraging w; 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

---

Under review as a conference paper at ICLR 2022
Models
FD
GCN Disc.
RF
SGM (Ours)
43.4
0.54
0.89
Models
NLL
GCN Dise.
RF
SGM (Ours) (A2)
32.7
0,63
0.79
SGM (Ours) (A3)
37.5
0.43
0.91
SGM (Ours) (A2)
1028.4
0.63
0.79
SGM (Ours) (A2, No Synth. Ablation)
42.1
0.42
0.89
MusicVAE
1158.6
0.50
0.85
SGM (Ouns) (A2, Greedy Synth. Ablation)
40.5
0.50
0.88
MusicAutobot
1760.0
0.51
0.95
SGM (Ours) (A2, Continuous Relation)
33.2
0.46
0.88
Atteation-RNN
39.9
0.47
0.88
MusicAutobot
53.7
0.95
StructureNet
44.0
0.45
0.91
Table I: Results for the music domain. Left: We show negative log-likelihood ("NLL", lower is better) on the held-out human test set (i.e., by estimating the ELBo using sampling). Right: We show Fréchet distance Vus 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 random forest trained to do the same thing on a handcrafted featurization of the programs ("RF", lower is better). The highest score in each column is bolded. As can be seen, our 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).
5.1 MUSIC GENERATION
We evaluated our approach on a music generation, where x is a song and wr 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 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 I po(- c). For A1, we use a pretrained transformer called MusicAutoBot (Shaw 2020). For A2, we require generative model that constructs vector embeddings of measures; we use the pretrained version of Magenta's 's MusicVAE 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 MusicAutoBot, a pretrained and finetuned attention LSTM (Attention- RNN) (Waite) 2016), Magenta's 1 16-bar Music VAE (pretrained and finetuned), and StructureNet, which integrates structure into an LSTM (Medeot et al. 2018). To show the importance of synthesis, we compare to an ablation that uses A2 but with full adjacency tensors instcad of synthesizing compact representations of relational constraints, and one that uses greedy synthesizer-ise at each step. greedily choose the single prototype and its relations that most increases (T). Finally, we consider using 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 Music MusicAutobot, and our approach with strategy A2. The remaining approaches are not probabilistic (or estimating probabilities is intractable). For these approaches, we use a variant of the standard Fréchet distance (FD) score used to evaluate GANs (Borji -ic.. the Fréchet distance between the VAE (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 e, A(x). Then, given a collection Cgen = (c2 x Xgen] of synthesized structure for generated examples, along with a collection Chuman {cz synthesized structure for the held-out human examples, we train a graph convolutional neural network (GCN) try and discriminate Ogen from Chuman- as well as random forest (RF) over handcrafted features (see Appendix C.4). Intuitively, higher discriminative power should indicate less realistic structure. In both cases, random predictions have accuracy 0.5. Recent work has shown that such discriminator-baan based metrics valid for evaluating quality of generated examples (Lopez-Paz Paz & Oquab] 2016).
X human of
balanced dataset (i.e., 50% human held-out and 50% generated) so
Results. In Table I 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, approach (SGM) with sampling
7

---

Under review as a conference paper at ICLR 2022
Models
GCN Disc.
FD
SGM (Ours, A1)
SGM (Ours, A3)
0.62
13,51
SGM (No Learned Structure Ablation)
0.59
21.2
GPT2
0.47
14.3
GPT2- Opt
0.56
144
BERT
0.50
54.9
RichLyrics
0.51
23.0
Table 2: 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 our approach with sampling strategy A3 outperforms all baselines in high-level structure and is also competitive with GPT-2-based models in FD scores.
strategy A2 outperforms all other models in both tables, in terms of both high-level structure and low-level structure. In Table (lef), the closest alternative is Music VAE, 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. In contrast, A3 performs well in terms of high-level structure, but is mixed in terms of low-level structure, most likely since it does not use learning-basee model 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 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, x is a poem, and w is a line. We consider two relations, rhyming and equal meter; Appendix C.3 for details.
Dataset. We use from Project Gutenberg's 's poetry collection (Parrish 2018), focusing on 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- line embeddings, we did not perform A2. In applying A1, rather than sample words going forward, we sample them backwards, making it easier to sample lines that satisfy rhyming constraints; see Appendix B Thus, we use BERT to sample (Devlin et al.] 2018), since it is bidirectional. We apply A3 by performing constrained optimization to satisfy as many relations as possible while maintaining a low NLL.
Baselines. We compare to generation using beam search for BERT and GPT2 RRdford et al. 2019 Vaswani et al. 2017). both finetuned on our dataset. We also consider a variant GPT2-Opt of GPT2 where we use beam search choose line breaks in 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 a given rhyme and meter, but the search space was too large and failed to generate a single poem even after several hours. We also compare to an implementation of Richl -yrics (Castro & Attarian 2018), where the consecutive parts of speech for each line given the previous line and the ability to fill in 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.
Metrics. For lowelevel structure, we use FD score on SentenceBert embeddings, which are unaware of rhyme and meter (Reimers & Gurevych 2019); we cannot evaluate likeeiiodoood since using constrained sampling. For high-level structure, we train a GCN to discriminate synthesized programs for generated examples vs, test examples.
8

---

Under review as a conference paper at ICLR 2022
One was done. Another was done.
One was done. Another was done.
And I wish you know the way.
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 soldier, fair fair beautiful grace That men turn't 'd toward. Another race Together, married. Much to see, the dead Were gone. The man who ascended to the head Office retired, and gave birth to trace That doesn't tell name, but tells face.
Full name and date to whom this story pour
And know a lot of things that were called war See soldier, fair fair beautiful grace That men turn't '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 was old and not intended bed.
Left: Poetry generated using relational constraints c ~ P.()). Right: user modified variant of where the last two lines share prototype with the two lines before them.
Figure 2:
Method
Average Score
Lyricism
Coherence
Rhyme/Meter
SGM
3.66
3.81
GPT2 Finetune
3.30
2.90
3.91
3.12
BERT-Finetune
2.28
2.11
2.00
2.77
RichLyrics
3.09
3.24
3.09
2.93
Table 3: A user study evaluation in the poetry domain. While GPT2-Finetune outperforms model in terms coherence (presumably due to the well-known superiority of GPT-2 over BERT for generation), our method outperforms terms of overall lyricism (i.e., whether the poem reads like poetry or prose), prominence of thythmic/metrical structure, and average score.
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 Al performs even better in terms of programmatic structure, is not competitive with respect better at natural language generation than BERT.
Results. We show results in Table 2
scores, presumably due to fact that GPT-2 is significantly
User study. We also performed a 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 that the user can modify the relational constraints (or construct their own from scratch) for use in the second step po(2: c). giving the user a way to guide the generative process. An example the poetry domain is shown in Figure 5.2 and musical examples shown in Appendix D.2
CONCLUSION
We have presented a 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-used 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 approach to other applications such as dialog generation and summarization, which may require novel programmatic structure compared to the ones we study.
Reproducibility. We strove maintain reproducibility for code. Included in the supplement is all the material to obtain our results with instructions for running it and significant documentation, except for the code for the approach (A1) in the music domain (which performed the worst out of the three approaches). We do not provide the data sets for attribution rights reasons, but include the links by which users can obtain that data.

---

Under review as a conference paper at ICLR 2022
REFERENCES
V Atanassova and S Pulov. Prolog realization of a poetry generator. In Proceedings First International IEEE Symposium Intelligent Systems, volume 3, pp. 52-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. 2494-2504, 2018.
Ali Borji. Pros and cons of gan evaluation measures. Computer Vision and Image Understanding, 179:41 1-6,, 2019.
Pablo Samuel Castro and Maria Attarian. Combining learned lyrical structures and vocabulary for improved lyric generation. CoRR, abs/1811.04651, 2018. URL http:::t:/a/z/w.or/////aa/
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 expert system for computer-assisted composition. Computer Music Journal, 11(4):30- 46, 1987. ISSN 01489267, 15315169. TtLLhttp:// www. jstor. org/ wttpg//aaleee366222
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, htss1992.02164, 2019. URL UBL.ttpp//axxxv.cc//////////3//3
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: 10. 20..0098/sta.2215.4444
Leonardo De Moura and Nikolaj Bjømnr. Z3: An efficient smt solver. Berlin, Heidelberg, 2008.
Springer-Verlag. ISBN 3540787992.
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805, 2018. URL
http://arxiv. org/ abs/
04805
Kevin Ellis, Armando Solar-Lezamaa 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 daadd images. CoRR, abs/1707.009621 2017. |
//arxiv. werxiv.org/abs/11700
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lue Cary, Lucas Morales, Luke B. Hewitt, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-slcep bayesian program learning. CoRR, org abs 2006.
abs/2006.0838/ 2020. URL
Ian 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/ htlpp//ppe///// were-eeeeeeeiiieeeeeeeeeeeeeeeee adversarial -ettriiiallneesss.eem nets. pdd
26800. Curran Associates, Inc., 2014. URL http://papers: nips
C. Horton and L. Ritchey. Workbook for Harmony Through Melody: The Interaction of Melody, Counterpoint, and Harmony in Western Music, Scarecrow Press, 2000, ISBN 9781461664
http://ooooooooooloeee//o gwogle.
wwtpo//le.....oo.oooooooeooooooe com/ wttpoo/sscxxxxps//ckkk....
Cheng Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Noam Shazeer, Ian Simon, Curtis Hawthorne, Andrew Dai, Matt Hoffman. Monica Dinculeseu, and Douglas Eck. Music transformer: Generating music with long-term structure. 2019. URL https: arxiv. orq/ /bs///b////// aba/ /1809 04281
10

---

Under review as a conference paper at ICLR 2022
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Anmando Solar- 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 http::/tt///bb uni -trierrreee biee/b// con cm cm10019 html #JeoocKKN1
Gullapalli Keerti, A N Vaishnavi, Prerana Mukherjee, A Sree Vidya, Gattineni Sai Sreenithya, and Deeksha Nayab. Attentional networks for music generation. ArXiv, abs/2002.03854, 2020.
Diederik P. Kingma and Max Welling. An introduction to variational autoencoders. CoRR, 022699966.26,,, 2019. http: http://aaa......t//////9...... 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. URL httt:s:://peereviiiiicc http:///p.paapaeeeeeeeeeeeeeenna
net http:/ooommmmm--04aaaaaa
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/1807 907.03491, 2018. URL
http:://axxi http:///aawiw..oaab/b///////
www.orgg/ss....... 1807 1807.03491111110
Xiang Lisa Li and Alexander M. Rush. Posterior control of blackbox generation. CoRR,
abs/2005. 044600, 2020. Ut////ttpps///arxx..r//////////p
04560
Yi Liao, Yasheng Wang, Qun Liu, and Xin Jiang. bop--based for classical chinese poetry. CoRR, htbs/1907.00151, 2019a. URL O0LL:ppp.//aaxi..ccc///////00000
Yi Liao, Yasheng Wang. Qun Liu, and Xin Jiang. gene-batid for classical chinese poetry. CoRR, abs/1900.00111, 2019b. URL httpp://arx....oor////////000000
David Lopez-Paz and Maxime Oquab. Revisiting classifier two-sample tests. arXiv preprint 16100:5610 2016.
Gabriele Medeot, Srikanth Cherla, Katerina Kosta, Matt Me 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:://immr//0/ ircam. fr/doc/ pdds/1255 Paper. pdf
Hongyuan Mei, Guanghui Qin, Minjic Xu, and Jason Eisner. Neural datalog through time: Informed temporal modeling via logical specification. CoRR, abs/2006. 11t2/2006.66233, 2020a. URL https
//arxii.orc//bs/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
//axxiv.org/as////00
Ning Miao, Hao Zhou, Lili Mou, Rui Yan, and Lei Li. CGMH: constrained sentence generation by metropolis-hasting sampling. CoRR, abs/1811.10996. 2018, URL httt::://axxxv..rr//
abs/ 11111811111 10996
Islam Elgamal Muhammad Faisal, Islam Faisal. Generating random, yet, constrained music. 2017. URL holl:httts::/decltytt http::/w........laaaaaaaooaaaaaa
OpenAl. Musenet, 2019. URL attp:///peenai..c////o////ssssss
Russell Ovans and Rod Davison. An iterative constraint-based expert assistant for music composi- tion. In Proceedings of the Biennial Cnnference-Canadiin Society for Computational Studies of Intelligence, pp. 76-76. Citeseer, 1992.

---

Under review as a conference paper at ICLR 2022
Allison
Parrish,
2018.
URL
https:://gitubb.commm/eee
Jeffrey Pennington. Richard Socher, and Christopher D. Manning. Glove: Global vectors for word
representation. In Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543,
2014. URL http::/tp::/wt acw.wwwwcclla....o.............. www.ww..ww.b..o................. wttp://aathooooyy11---LL1
Donya Quick. Learning production probabilities for musical grammars. Journal of New Music Research, 45:295-311 -333, 10 2016. doi: 10. 10.1080009292215.0011 1228680..
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/1908. 1019908..008444 10084, 2019.
/908 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/ 1sss/8033,5,2,, 2018. URL
http://arxi:: org/ /tab//1803 05428
Asir Saeed, Suzana llie, and Eva Zangerle. Creative gans for generating poems, lyrics, and metaphors. CoRR, habs/1909.095344 2019. URL
1909. 09534
Örjan Sandred, Mikael Laurson, and Mika Kuuskankare. Revisiting the illiac suite a rule-based approach stochastic processes. Sonic Ideas/Ideas Sonicas, 2:42 46, 01 2009.
H. Schaffrath. The essen folksong collection in the humdrum kern format. 1995.
Andrew Shaw, 2020. http::/:: thub. com cecom/beate bew can/mus cwwtooot.
Y. Cem Sübakan and Paris Smaragdis. Diagonal mns in symbolic music modeling. CoRR, abs/1704.05420,, 2017, URL [tttt:/p///axiii ort/obgg/////. /tobs//1044 05420
Dima Suleiman, Arafat Awajan, and Wael Al Etaiwi. The use of hidden markov model in natural arabic language processing: survey. Procedia Computer Science, 113:240-224 2477 2017. ISSN 1877-0509. doi: https://doi.org//
URL https The 8th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EU- International Conference on Current and Future Trends of Information and The 7th
httw:/wwwiene...ccccoocctocccctt www.sscceeccciiccm rectt com/ cttpm//ccciiieeer...cl//////////
SPN 2017) The
Communication Technologies in Healthcare (ICTH-2017), Affiliated Workshops.
Mattt Thompson. Möbius: Exploring a new modality for poctry 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
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. Programmatically interpretable reinforcement learning. In International Conference Machine Learning, pp. 5045-505. 2018.
Elliot Waite, 2016.
URL
Cookback-mmn-ttteniiio.
Zhe Wang, Wei He, Hua Wu. Haiyang Wu, Wei Li. Haifeng Wang, and Enhong Chen. Chinese poctry generation with planning based neural network. CoRR, abs/1610.09889, 2016. URL
http://arxiv. org/ abs/ / 610.0... 09889
Li-Chia Yang, Szu- Yu Chou, and Yi-Hsuan Yang. Midinet: A convolutional generative adversarial network for symbolic-doman music generation using 1d and 2d conditions. CoRR, abs/1703. 108477 2017a. URL htLhttp::/ //arxi v. wwwgg/bs////00 103. 10847
12

---

Under review as a conference paper at ICLR 2022
Xiaopeng Yang, Xiaowen Lin, Shunda Suo, and Ming Li. Generating thematic chinese poetry with conditional variational autoencoder. CoRR, abs/1711.07632, 2017b. URL http:://rxiv
org/abs/17Li 1711 07632
Halley Young, Osbert Bastani, and Mayur Naik. Learning neurosymbolic generative models via program synthesis. 2019.
13

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL RELATED WORK
Music and poetry generation. Both early music generation and poetry generation approaches were rule-based (Ovans Davison 1992 Atanassova & Pulov 2002) or used simple statistical models such as Markov models (Sandred et al. [ 1987 Suleiman et al.) 2017) or probabilistic CFGs (Quick 2016; Thompson| 2009). Recent work has used deep learning to generate music (Huang et al.] 2019 OpenAl| 2019) and poetry (Liao et al. 2019a); our experiments show that these approaches have difficulty generating realistic high-level structure.
Music generation has been approached using many machine learning techniques, including convolu- tional neural networks (CNN's) (Yang et al. 2017a), graph convolutional networks (GCN's) (Jeong et al. 2019), recurrent neural networks (RNN's) (Sūbakan & Smaragdis 2017)), and transform- ers (Huang et al.] 2019). In particular, we leverage attention- RNN's ' (Keerti et al. 2020) and transformers for constrained sampling of program structure.
Poetry has been approached with a variety of techniques as well, including relying on finetuned transformers (an approach extend) (Liao al., 2019h), RNN-based conditional-VAN (Yang) ct al., 2017b). RNN-based planning (Wang et al. 2016). and GANs with both transformer and LSTM backends (Saced et al. (219))
Approaches have incorporated structure into deep learning to generate music (Medeot et al. 2018 or poetry (Castro & Attarian 2018). but they are domain specific; we find they do not perform at a human level on capturing global (and sometimes local) structure. Some approaches incorporate expert-prove expert-provided constraints such as rhyme and meter to generate poetry (Lau et al.) 2018); unlike our approach, they cannot automatically learn and generate these constraints from data.
Constrained text generation. There has been work on constraining language models to produce outputs that satisfy a given decision function, or that maximize given scoring function (Li & Rush 2020; Miao et al., 2018 Dathathri et al., 2019). In contrast, our work focuses on settings where constraints are generated, and furthermore the distribution over constraints must itself be learned.
Relational constraints and neural models. Several previous works have focused on learning datalog programs, one component of our project. Mei et al. (2020b) learn Datalog programs which represent certain point processes, and use this to predict future events. Similarly, Mei et al. (2020a) also learn Datalog programs, and is able achieve great success in certain autoregressive domains; however, they do not frame their problem as a generative process to generate realistic human data from their output.
B GENERATING EXAMPLES GIVEN RELATIONAL CONSTRAINTS
B. APPROACH 1: CONSTRAINED SAMPLING
In the music domain, we choose the pretrained generative model (o(w) to be a pretrained version of MusicAutoBot. To generate I, we sequentially sample each measure conditioned on all prior measures W1,..., W/-1- Each measure is sampled by sequentially sampling sequence of pitch- duration pairs until the total duration is 16 beats (i.e., the length of measure). During sampling, we mask pitch-duration pairs that cannot satisfy &. (i.e., we set their sampling probability to zero and rescale the remaining probabilities). For instance, if the "has similar interval" relation is supposed to hold between the the prototype measure and measure i, and we are sampling the second note of measure i, then we mask any pitch ls in measure i such that
(pitch, pitch..1) - (pitch, -itchh
where pitch, is pitch l in the prototype corresponding to wi. In other words, we eliminate pitches that would cause sampling to violate this constraint.
In the the poetry domain, we finetune a pretrained BERT model on our dataset, by taking the pretrained models weights and then training the model on our dataset with a strong gradient weight decay. BERT has the ability to complete masked words in sentence. We leverage this ability to sample lines that rhyme and have the same meter, which is a challenging task since such lines are tiny fraction of the search space. We describe how we simultaneously handle rhyming and equal
14

---

Under review as a conference paper at ICLR 2022
meter; the cases where only of these two constraints has to hold are similar. Given prototype iü, we work backwards- on each step j. we sample from BERT a word word, that has the same number of syllables the corresponding word wordg in the prototype. More precisely, we feed BERT the sequence
word - MASK, wordk+1;...
and ask it fill in the masked word, setting the probability of any word with different number of syllables as word, to zero.
In addition, to avoid producing line which is similar to the original line, we also set the probability of any word too similar to the original word in terms of GloVe cosine similarity (Pennington et al.) 2014) to zero, except for in the case of the last word, where we instead restrict to words that rhyme with wordg. To increase diversity, we sample the remaining words twice-(i) backwards- torrddtttofowordd from word & - to word I, where k is the number of words, and (ii) resample each of the & words (i.e., except the last word) in a random order. We discard any lines which, according to BERT, after being sampled are determined to be too unlikely when preceded by the previously generated lines.
B.2 APPROACI 2: CONSTRAINT-WWARR EMBEDDINGS
This approach uses a graph convolutional network (GCN) conditional variational autoencoder (cVAE), or GCN-eVAE, which consists of a GCN encoder qe (a' z, Cz) and a GCN decoder Po(x: 2 cz).
In more detail, we assume e.g., in the music domain, we use MusicVAE, ps: encode Then, the latent encoding z' consists of an embedding vector for each subcomponent of
(Wi...., .... Wm)) is represented as a sequence of vectors (u1, Um
qp(- w) or decode w popo u).
Next, is incorporated into each GCN by converting it into tensor with dimensions [ú] x [ | used as the adjacency matrix of that GCN (the last dimension is the edge attribute). Intuitively, the edges in relations in between subcomponents and prototypes.
This GCN-eVAR trained using the usual VAE objective (Kingma & Welling 2019: (i) KI. divergence term encouraging the embeddings z' to be Gaussian, and (ii) reconstruction loss in terms of sucan-squared error. We also include a semantic consistency loss to enforce the satisfaction of the constraints 2.. In particular, we train classifier Pa (u, r'; that predicts whether two subcomponents u, satisfy relation r (more precisely, when decoded by P&). The model Pa is trained examples (u, u' .r) from the training data Then, we include the loss
Σ (1.
Pa (ū, u4, r),
where u ~ ps(. w) is the encoding of w. u, ( w;) is the encoding of w; and is relation.
For the music domain, we use a pretrained Music for p and qui unlike the MusicVAE we use for evaluation, finetune model that decodes 1 measure of music from 356-dimensional vector.
B.3 APPROACH 3: COMBINATORIAL OPTIMIZATION
Given sampled program c, this approach attempts to generate values x = (wo..... Wm) such that }= 4. by solving system of constraints. However, when generated using a neural network. relational constraints o o. are not always consistent with one another, so we convert the constraint == 4. into an objective-iss i.e.
VIL
x arg max
1(R(ū, w; + (0,,,)) E $2).
The ability encode this optimization problem that Z3 can solve depends the domain and relations. For this approach to work, we may need to include additional, handcrafted terms in the objective that encourage the generated example is realistic.
15

---

Under review as a conference paper at ICLR 2022
For the music domain, the optimization variables are the optimal sequence of pitches and their durations. The objective function is a linear combination of the degree to which I satisfies c, along with domain-specifie heuristics c.g.. minimizing large jumps in pitch values (i.e., ppitch--1 pitch,| 2 4), not having any intervals of length (i.e., |pitch pitch, = 6) due to the unpleasant harmonic nature of that interval, and not having two consecutive jumps in pitch (i.e., |pttch k+2
pitch 2 5) A |pitch pitch & 2 5). These heuristics are based on standard concepts from music theory (Horton & Ritchey 2000p.
For the language domain, we use GPT-2 to sample a line except for the last word; then, the optimiza- tion variables are the last words in each line. This strategy optimizes the relations between each line and its prototype, while leveraging GPT-2 to maintain low NLL for the entire poem.
C EVALUATION DETAILS
C.I EXPERIMENTAL SETUP
Synthesizing programs. The hyperparameters J1, J2, and J3 in the program synthesis task, as deseribed in the main section of this paper, regulate the degree which the optimization favors solutions which have high similarity between prototype and sequence measures, have high similarity between elements sharing a prototype, and have high difference between prototypes, respectively. Their values were different with respect to the two different domains. In the poetry domain, J1, Jz. and J3 were 1, 10, and I, respectively. In the music domain, J1. J2, and J3 were 1, 5, and 1, respectively. These values were arrived at through attempting to arrive at results which closely matched a set of human (author) annotated programs.
Generating c. To generate in the poetry domain, we use an LSTM-VAE with 6 LSTM layers and latent size of 50. This model is trained to reproduce a given sequence of (s;, 7;) pairs which are given as input, with additional requirement that the distribution of their encodings should be roughly equivalent to a Gaussian normal distribution. In the music domain, while we experimented with using an LSTM- VAE, empirically had more success using feedforward 3-layer network which took the previous n (usually n 6) (s,, r.) pairs, and outputted a distribution over the following pair.
Each (st, r4)) pair is represented between objects with the same prototype and is the set of relations.
(S + [R] -dimensional vector, where S is the maximum distance
High-level structure. We evaluate high-level structure by using our algorithm to synthesize the relational constraints in every generated example-is -i.., Cgen = {A(z) x E Xgen). ) where Xgen is the set of examples generated using model. Similarly, we construct Chuman = ({A(x)) 2 Xhuman }. where X Numman is the set of human-created examples held-out from the training dataset. Then, we evaluate high-level structure by training model try to discriminate Cgen from Chuman; if the model achieves lower performance, then the quality of high-level structure is higher. A general approach is to train graph neural network (e.g., a graph convolutional network) do So; this model takes as input the graph structure of relational constraints along with vector embeddings of the prototype subcomponents, and outputs whether E Cgen or Chaman- We balance the data so it consists of 50% human data and 50% generated data. We report the cross-entropy (CE) loss; higher values correspond to better generative models. In the music domain, we additionally used a random forest (RF) trained on manual featurization of c. We report the accuracy of the RF; lower values (i.e., closer to 50%) correspond to better generative models.
C.2 MUSICAL RELATIONS USED
The following are the relations E R used in the music domain:
1. Measures i and j have the same pitch classes.
2. Measures i and j have the same pitch class prefix.
3. Measures i and j have the same pitch class suffix.
4. Measures i and j's pitches have an edit distance of 1.
5. Measures i and have approximately the same interval structure.
16

---

Under review as a conference paper at ICLR 2022
6. Measures i and have the same interval prefix.
7. Measures i and j have the same interval suffix.
8. Measures i and have the same note (pitch duration) prefix.
9. Measures i and j have the same note (pitch duration) suffix.
10. Measures i and have the same rhythm.
11. Measures i and j's rhythm has edit distance of S 2.
12. Either measure i's onsets are subset of measure j's onsets, or measure j's onsets are subset measure onsets.
Measures and j have the same rhythmic and melodic contour.
Measures and j have the same rhythmic and melodic contour prefix.
Measures and j have the same rhythmic and melodic contour suffix.
16. Either the first or second half of measures and j are identical.
Either both or neither of measures and j have leaps.
Measures and j fit within the same diatonic scale.
Either both or neither of measures and j have syncopation.
20. Either both or neither of measures and j have consecutive notes shorter than an eighth note.
21. (Continuous) The cosine similarity between the Peaaure-VABB embeddings of measure i and measure j.
C.3 POETRY RELATIONS USED
The following are the relations r E R used in the poetry domain:
1. Lines and j have the same end rhyme.
2. Lines and j have the same meter.
C.4 RANDOM FOREST FEATURES
The following the manually constructed features used in the random forest discriminator for the music domain:
1. Mean number of relations between prototype and sequence measures.
2. Variance of number of relations between prototype and sequence measures.
3. Variance in histogram of prototype measure mappings.
4. Longest sequence ....j such that ..... W, all have the same prototype measure.
5. Number of pairs (i,j) such that w; úi and W:+1 ūj+1-
6. Mean distance between two measures with the same prototype.
7. Variance in distance between two measures with the same prototype.
C.5 USER STUDY DETAILS
50 participants took place in the study on Mechanical Turk. Each was paid $5 to complete survey with 12 questions (3 poems each from four sources, Ours, GPT2-Finetune, BERT-Finetune, and RichLyrics). All poems datasets according to GPT2-log-likelhhodd The participants were asked to rank the following statements from "strongly disagree" to "strongly agree" (1-5) as follows:
chosen automatically by taking the top examples from the generated
1. It is obvious that this is poem
2. This text is coherent
17

---

Under review as a conference paper at ICLR 2022
Method
Average Score
Lyricism
Coherence
Rhyme/Meter
SGM (Ours)
3.66
3.81
3.59
3.59
GPT2-Finetune
3.30
2.90
3.91
3.12
BERT-Finetune
2.28
2.11
2.00
2.77
RichLyyries
3.09
3.24
3.09
2.93
Table 4: A user study evaluation in the poetry domain. While GPT2-Finetune outperforms our model in terms of coherence (likely because GPT-2 outperforms BERT at generation), our method outper- forms in terms of overall lyricism (i.e., whether the poem reads like poetry or prose), prominence of rhythmic/mettricl structure, and average score.
3. notice that this text has rhyme and meter
D ADDITIONAL RESULTS
D.I COMPARISON CONSTRAINT SOLVING
We also considered comparison to constraint-base based implementation called Motifate, with explicit attention development of musical material (Muhammad Faisal (2017). This approach was designed with heuristics for 3-beat measures, while our evaluation models anticipated 4-beat measures, so we could not obtain FD scores. Nevertheless, we found that even the structure was insufficient- RF discriminator had accuracy 0.91, and its GCN discriminator had cross entropy loss 0.43, both of which are significantly worse than the other approaches.
D.2 CONDITIONING ON USER-PROVIDED STRUCTURES
Here we show how user modifications can occur the music and poetry settings. By explicitly modifying we are able to generate two pieces of poetry or two tunes with similar internal patterns but with different structural characteristics.
Figure 3: A song generated using our approach, and a nearly identical song generated where part of the sampled relational constraints manually modified. These pieces were generated using A3, and the same reference measures V were used, but 4 was slightly perturbed (the similarity relations were changed).
D.3 QUALITATIVE OBSERVATIONS ON THE MUSIC DOMAIN
In addition to quantitative measurements, we evaluated the strengths and weaknesses of our approach using A2 (which was the best according to quantitative metrics). According to observations, the strengths of A2 include clearer phrases with obvious resolutions, likely and plausibly repetitive rhythms, intervals between notes which seemed plausible but overly repetitive, and less variance
18

---

Under review as a conference paper at ICLR 2022
One done. Another done.
done. Another done.
And wish you know the way,
And I wish you know the way,
Full name and date whom this
Full and date whom this story pour
And know lot of things that were called war
And know a lot of things that were called See soldier, fair füir beautiful
See a soldier, fair fair beautiful grace
That men turn' d loward. Another race Together, married. Much to sec, the dead
That men tum '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 was old and not intended for bed.
Were gone. The man who ascended to the head
Office retired, and gave birth to trace That doesn't tell name, but tells face.
Figure 4: Left: Poetry generated using relational constraints pa(.). Right: user modified variant of where the last two lines share prototype with the two lines before them.
in quality, However, the results were not very rhythmically diverse, and certain idiomatic patterns of resolutions of intervals between notes and the end of phrases were not followed. Furthermore, AttentionRNN does better in terms of creating realistic chord progressions (we did not explicitly consider chord progressions in our model; doing so a promising direction for future work). Finally, while global structure is much better than the baselines, examples still relatively infrequently had the full four-bar repetitions characteristic of much folk music.
D.4 EXAMPLES FROM THE MUSIC DOMAIN
We show example of generated songs using approach with each A1, A2, and A3 in Figure Figure 6. and Figure respectively, and show an example generated using each of the baselines MusicVAEIE AttentionRNN, MusicAutoBot, and StructureNet Figures 8 9 I0 II respec- tively. Qualitatively, the generated music and poetry appears plausible, exhibiting realistic high-level structure without sacrificing low-level structure.
Figure 5: An example of song generated using our approach (A1). Measures that have the same prototype are shown in the same color. Note the existence of repeating four-bar phrases, found commonly in folk songs.
Figure 6: An example of song generated using our approach (A2). Measures that have the same prototype are shown in the same color. Note the existence of clear phrase endings marked by long notes or rests, particularly the recurring pattern of fast notes resolving into long notes.
D.5 EXAMPLES FROM POETRY DOMAIN
In Figure D.5 we show example poem generated using our approach (top) along with one generated using GPT2-Opt (bottom). As can be seen, the GPT2-Opt poem does not capture structure in the same way human poems do-e.g., adjacent lines are unrelated, lines have very unequal length, and the only rhymes are the word "the" in the brown lines and the words "to" and "too" in the green lines. There even less structure in poems generated using vanilla GPT2. Thus, GPT2 completely unable to capture high-level structure in the real poetry provided as training data. In contrast. our poem captures structure very similar the human poem shown Figure I such rhyming adjacent lines.
19

---

Under review as a conference paper at ICLR 2022
Figure 7: An example of song generated using our approach (A3). Measures that have the same prototype are shown in the same color. The existence of two-bar and three-bar phrases is apparent. but the close note and rhythm similarities among different prototypes weaken the overall clarity of the song's melody.
Figure 8: An example of song generated using Magenta's hierarchical Music model finetuned on our dataset. While the local structure is extremely coherent, it does not seem to possess the expected internal repetition/development
F
Figure 9: An example of song generated using AttentionRNN trained dataset. Note the existence of erratic rhythms and unclear structure, which are common traits of custom-trained AttentionRNN models.
Figure 10: An example of song generated using MusicAutoBot. Note the repetitive nature and stark contrast between the first half and second half of the song, which are common problems with transformer models.
Figure 11: An example of song generated using StructureNer. While some degree of internal structure is apparent, and the local coherence is high, the pattern of internal repetition seems fairly arbitrary.
We also give examples of poetry generated using our baselines in particular, GPT2 finetuned and optimized for rhyme and meter in Figure 15 BERT finetuned language generation model in
20

---

Under review as a conference paper at ICLR 2022
Figure 17 RichLyrics, and our ablation (i.e., use BERT in conjunction with uniformly randomly sampled 2.) in Figure 18
One was done. Another was done.
nature and Neture Nature to the being ablo in human attars to combine with herself
And wish you date whom this story pour
way.
Full
And know lot of things that were called See soldier, fair fair beautiful grace
Her will and therefore existence Cannot over Even create
nature having
That turn't toward. Another Together. married. Much see, the dead
alone can produce any being
Were gone. The who ascended the head Office retired, und guve birth to trace That docsn't 't tell name, but tells a face.
only
exist becouse the nalure only is
Figure 12: Left: Poetry generated using relational constraints Po(.). Right: Poetry generated by GPT2-Opt. Notice the lack of characteristic structure in GPT2-Opt, despite its coherence.
know many and therefore forgot, Though needed time look ahead.
To understand something. lime fade
though yesterday they
Were common things, free, rather free, to go like the ride; another
Perhaps you know it. A queen, her beautiful son, And another
voices who has war.
They lat us believe in good ressore!
Figure 13: An example of poetry generated using our approach (A1), Lines that have the same prototype are shown the same color.
21

---

Under review as a conference paper at ICLR 2022
your parents have both seen your face, the sun the west. the moon under his robes coronation
the cloud is the sky creation night.
the night that the day is the day station
you are friends your smiles are fair and alteration your friends are good and fair.
friends.
you have no shame to population
Figure 14: An example of poetry generated using our approach (A3).
Through the air and through the sky And through all the world
saw the sun the moon star shine In the midst of the stars
The stars were shining in my eyes my heart Was throbbing with joy felt
My heart was beating with love I was
little child a little town
Where the little boys play
Figure 15: A poem generated using GPT2-Opt. more plausible than BERT in terms of global structure, which may be due to the fact that GPT2 is a better text generation tool than BERT, but is still somewhat repetitive and its structure is not very human-like.
all all and and
and and and and and all all all all and and o and and and
o and and
and and
and of of of and but and and of
and and and and last last last of and and
Figure 16: A poem generated using BERT. It is clearly overly repetitive and not very semantically coherent, and lacks high-level structure.
22

---

Under review as a conference paper at ICLR 2022
and after all text that all more appointment
make its room from sat and all district withour solf' she one is hundred first enjoy her
but her been two you shall be
above she leave enjoying the suffering usual for which more science this day sewing shall two houses for recent contributions and time which have left for self woman and morcover lot use been found called might where any boots accident
Figure 17: A poem generated using RichLyrics. While it is less repetitive than non-conditioned BERT, it is still not very semantically coherent, and lacks high-level structure.
the first independent, , like for the new songs for morning,
little world, they asked them for way she asked them for a night,
with two heds sometimes lying on light- bed. the first for women, with another, one band
with one paul simon never got play on the subject, she bought a different dress for different tent,
and one dress for warning..
Figure 18: A poem generated using our ablation. While it is much more coherent, it lacks the idiomatic rhyme and meter structure our approach.
23


Reviews:
[{"review_id": "b1uCJE1wuF", "reviewer": "Reviewer_33jH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strengths]\n\nThe paper is overall well-written and the method is clearly explained. The literature review is thorough. The idea of formulating the constraint synthesizing as a constrained optimization problem is novel to me.\n\n[Weakness]\n- It is unclear to me how the prototype subcomponents are chosen. One concern is that when the prototype subcomponents are similar to each other, the resulting model might generate similar examples and does not generalize well. I guess the ideal scenario is to choose the prototype subcomponents to be as diverse as possible. But it is unclear how this is guaranteed from what is presented.\n\n- The other concern I have is on the efficiency of the synthesizing relational constraint process. The number of variables involved in the constrained optimization problem in Section 3.2 is quadratic in m, i.e., the number of subcomponents in example x. Further, the number of calls to solve this optimization problem is the size of training data. I wonder how efficient is this process.\n\n- Since this work follows the framework from [1], I wonder whether the generation processes of samples given relational constraints as described in Section 4.2 are original contributions and how are they compared with the generation process in [1].\n\n\n[1] Halley Young, Osbert Bastani, and Mayur Naik. Learning neurosymbolic generative models via program synthesis. 2019.\n", "summary_of_the_paper": "The aim of this work is to derive deep generative models that are able to incorporate relational constraints. The proposed model learns relational constraints from training data by solving constrained optimization problems and further generates examples given relational constraints. Empirical evaluations on music and poetry generation tasks are presented.", "summary_of_the_review": "The generative model for sequential data with relational constraints proposed in this work is interesting to me. Still, I have several concerns as mentioned in the main review.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZngIfqg9FUn", "reviewer": "Reviewer_nfwh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors follow the existing work (Young et al. (2019)) and extend it to handle sequence data. My understanding is that the model can take structure information into account while generating sequences, or more precisely, explicitly incorporate repetitive patterns in sequences into generation. I judge the work from the following perspectives:\n\n1. Technical Novelty: the basic idea comes from the work of Young et al. with some adaptations to sequence data. I would rather view the work as an extension of the approach in Young et al. (2019) to sequence data. There are some new things for the adaptations (e.g., learning the constraints from data), but overall, the key building blocks (e.g., VAE, controllable text generation) have been proposed before and widely used in a lot of work. \n\n2. Empirical Novelty: as far as I know, there has been a lot of work on music generation and poem generation. Particularly, my experience is that it is not that difficult to make a generated poem follow rhyme and meter constraints as long as we have a relatively good language model, since such characteristics are very strong in poetry. Therefore, I would like to see more applications, or probably more important applications of the proposed approach, for example, can we apply it to dialogue generation or summarization? To do that, you may have to go beyond the repetitive patterns, but such applications, in my opinion, could generate more impact. \n\n3. Soundness: the authors pay a lot of effort to formalizing the constraints and describing the learning details of the constraints. However, important details of how to build the generative model are missing in the main part. Even in the appendix, some details are still missing, for example, how to build the GCN to learn \\mu(c) and \\Sigma(c) in B.2?  In Experiments, I see some metrics for structure consistency, but very few metrics for quality of the generated content in addition to NLL. How can we guarantee the quality of the generated content? If it is hard to find other metrics, at least human studies can also be done in music generation. In 5.2, the authors claim that they have to choose BERT because they need to do backward sampling. I do not think this is a strong reason, as BERT is basically not a generative model. I suggest the authors to think about how to adapt their approach to generative language models, or choose other PLMs as the base. \n\n4. Writing: there is a little mess in the organization. For example, Introduction and Related work are combined, and the explanation of the example in Figure 1 above the Related work just breaks the coherence of the Section.  Some descriptions about the related work are placed in appendix, and more seriously, some important details, such as the details of Section 4.2 are also placed in appendix. I think most of these content should be involved in the main part, even though there is page limit. ", "summary_of_the_paper": "The paper presents a neurosymbolic generative model for sequence data. The model extends the one proposed by Young et al. (2019) in which a neurosymbolic generative model is initially proposed for images. Experiments are conducted on two datasets, one for music generation and the other for poem generation. Evaluation results indicate that the proposed model can effectively represent high-level structures in sequence generation.\n\nContributions:\n1. a sequence generation model in which structure information is taken into account in a principled way.\n2. effectiveness of the approach on music generation and poem generation.", "summary_of_the_review": "1. Technical innovation is not enough to meet the bar of the conference. \n2. Empirical studies do not fully convince me the effectiveness of the approach. \n3. There are some issues on organization of the content. \n4. I cannot think about broader applications of the proposed approach in sequence generation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XO57qjTMzR", "reviewer": "Reviewer_gmsG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths of the paper is its novelty and empirical results; its weakness is its clarity and related work discussion. \n\nThe overall framework is well-motivated for certain generation tasks such as music and poetry generation, and learning relational constraints from data is an interesting idea. \nIt does perform as expected in real-world datasets. \n\nHowever, the paper sweeps under the rug some key foundations of the proposed approach. \nThe most important is how to construct the function $f()$. According to appendices, it seems that $f(w,w',r)$ is assigned to 1 or 0 by checking whether $w$ and $w'$ follow a pre-defined relation $r$ and each possible relation $r$ can be automatically verified since they are superficial (e.g., same rhyme or same pitch class). This seems like the crucial premise that the proposed method could work, and it should be clearly stated in the main paper. Moreover, it is worth to discuss the limitations of the proposed method: e.g., if a relation $r$ is more conceptual (e.g., $w$ and $w'$ are talking about the same topic), then would the method still work or what else is needed to make it work? \n\nIt also suffers some inconsistency between the method overview and detailed exposition. The subcomponents of sequence $x$ are defined on the utterance level (e.g., lines of poems) but the content generation is elaborated on the word level, with the same index symbol (i.e., $j$) as the lines, which really confused me. I believe this inconsistency is merely a presentation issue but the authors should make it clearer for the readers to follow the details. \n\nThere is other recent work using relational constraints to configure neural sequential models. E.g., Li et al. uses temporal logic to constrain neural point processes: https://proceedings.mlr.press/v119/li20p.html; Mei et al. uses Datalog programs to compile human knowledge into the architecture of a neural sequence model: https://arxiv.org/abs/2006.16723. Relations with these papers should be discussed: e.g., they all condition sequence modeling on a set of global constraints; constraints of these papers are human-specified while those of this submission are drawn from a learned distribution (though its learning depends on human-specified relational features). \n\n", "summary_of_the_paper": "The paper proposes a hierarchical approach for generating sequences with global structures (e.g., music and poems with repeating elements). The proposed method first draws a template with a few slots already filled and certain global relational constraints across the slots, and then fills the remaining slots with actual content. The global constraints are found out by solving a combinatorial optimization problem: for each training sequence, they select some parts of the sequence as prototypes and relate each of the other parts to one of the prototypes by minimizing the overall dissimilarity among associated parts. Music and poems generated this way turn out to have a higher global coherence, lyricism, and rhyme, compared to what are directly drawn from an autoregressive model. \n\nIt is a novel algorithm, and achieves compelling empirical results in the domains of music and poetry generation. \n", "summary_of_the_review": "Based on the strengths and weaknesses explained above, I believe that this paper is at the borderline; I slightly tend to reject it since the clarity issues that I raise are important. However, if the authors could well address those concerns and we have high confidence in its camera-ready version, then I would consider elevating my rating. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PyIBFYc7nOO", "reviewer": "Reviewer_HkdV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the constrained/guided generation problem is an important one. And the method proposed in this work is interesting. Although it's relatively weak on the neural-symbolic part (since it only touches on a very special type of constraints, and relations are deterministically optimized and this process does not participate in gradient-based learning, which is less exciting to me), but the construction of the model is reasonable and results are promising. I think the amount contribution is moderate. And besides the evaluation/analysis part is unconvincing, I don't see any other reason to reject.\n\n1. The abstract mentioned that many recent works perform well on local coherence at the cost of global coherence. But I don't see this problem in the baseline experiment results though. Basically, while the method is interesting, I don't see what problem it is actually solving.\n\n2. The process of training is confusing to me. It seems that Fig1 bottom shows the inference step of VAE starting with the sampling of latent variables. But I am not sure what is the input at training time. Is it c_x -> z -> c given z -> x given c ??? The paper uses (z given c) and (z given c_x) at different places. I find it confusing.\n\n3. For the poem generation task, only A1 was used. This is less exciting since the constrained sampling could end up pretty slow and bad. The paper mentioned in the appendix B that typical causal language model doesn't fit for generating words with proper rhythm at the end of each sentence. While this makes sense, but there are apparently some heuristics that are easy to come up with to walk around that. Furthermore, for A3, while sequential generation via combinatorial optimization can be intractable, there are span-based generation approaches that can mimic that. I feel there are many options not explored in this task. A refuse of using A2 and A3 sounds like a drawback.\n\n4. I am not sure what story the loss based evaluations can tell. On one hand, the GCN discriminator metric is subject to artifacts in training data and thus potentially can be broken. On the other hand, the FD metric, as also said in this paper, is embedding based, thus does not evaluate rhyme and meter. Then why using them at all in Table 2?", "summary_of_the_paper": "This paper proposes a generative model for sequential data guided by relational constraint. It uses a specific type of high level structure represented by prototype alignment and a VAE framework to formulate the training. The paper experiments the proposed model on music generation and poem generation tasks, showing some substantial improvements given the proposed metrics.", "summary_of_the_review": "I think the major contribution of this paper is the framework. While some evaluation metrics are questionable, but I can see the coverage is better than the last year's submission, and there are improvements over different metrics. Besides, evaluating generated sequence is a challenging task and is out of the scope of this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes an interesting approach for learning the relational constraints of a dataset and then generating according to those constraints. Learning the constraints via a constrained optimization problem is an interesting contribution. The application of constrained generation is also interesting and can be applied to several domains though only music and poetry is examined in this work. However, the music evaluation is unconvincing and the paper lacks clarity in the description of the approach such as building the GCN. Music evaluation could be improved with human evaluation since loss metrics don't paint a full picture. Finally, a more diverse set of experiments and datasets (rather than just one poetry collection and one folk song corpus) and more analysis on the learnt constraints could give a more complete story for this approach's effectiveness on sequence data.
Decision: Reject