Year: 2021

Abstract:
There has been significant recent progress designing deep generative models that generate realistic sequence data such as text or music. Nevertheless, it remains difficult to incorporate high-level structure to guide the generative process, and many such models perform well on local coherence, but less so on global coherence. We propose a novel approach for incorporating global structure in the form of relational constraints between different subcomponents of an example (e.g., lines of a poem or measures of music). Our generative model has two parts: (i) one model to generate a realistic set of relational constraints, and (ii) a second model to generate realistic data satisfying these constraints. For model (i), we propose a 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.

heading: 1 INTRODUCTION
text: There has been tremendous recent progress in designing deep generative models for generating sequence data such as natural language (Vaswani et al., 2017) or music (Huang et al., 2019). These approaches leverage the vast quantities of data available in conjunction with unsupervised and selfsupervised 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—e.g., rhyming and meter across lines of a poem, or repetition across measures of a 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 a vector embedding) has the benefit that users can modify the structure to guide generation.
Recently, Young et al. (2019) proposed neurosymbolic generative models for incorporating high-level structure into image generation, focusing on simple 2D repeating patterns in images of building facades (e.g., repeating windows). The basic idea is to leverage program synthesis to extract structure from data—in particular, given an example image x, they devise an algorithm A that extracts a program c = A(x) that represents the set of 2D repeating patterns present in training examples x. Then, using the pairs (x, c), they train two generative models: (i) a model pφ(c) that generates a program, and (ii) a model pθ(x | c) that generates an image that contains the structure represented by c. However, their approach is heavily tailored to images in 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 pφ(c) for generating programs c and pθ(x | c) for generating images x conditioned on c. We represent the relational constraints cx present in an example x by relating each subcomponent w of a 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 w̃ is labeled with a set of relations R, which encodes the constraint that w and w̃ should satisfy relation r for each r ∈ R.
Importantly, while each subcomponent is associated with a single prototype, each prototype may be associated with multiple subcomponents. As a consequence, different subcomponents associated with the same prototype are related in some way. This representation is compact, only requiring linearly many constraints in the number of subcomponents in x (assuming the number of prototypes is constant). Compactness ensures the representation both generalizes well and is easy to generate.
Then, we design a synthesis algorithm that can extract an optimal representation of the structure present in a training example x (i.e., the relational constraints cx). We show how to express the synthesis problem as a constrained combinatorial optimization problem, which we solve using an SMT solver Z3 (De Moura & Bjørner, 2008). Next, we represent relational constraints c as sequences, and design the model pφ(c) to be a specialized sequence VAE. Finally, we propose three possible designs of pθ(x | c), all of which try to identify an example x that is realistic (e.g., according to a pretrained model pθ(x)) 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 a constant amount), etc. We show that our approaches outperform or perform similarly to state-of-the-art models in terms of low-level structure, while significantly outperforming them in terms of high-level structure. We also perform a user study in the poetry domain to determine user-perceived quality of the generated poetry along three dimensions (structure, lyricism, and coherence), and found that on average, our approach outperformed state-of-the-art 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 1 illustrates how our approach is applied to generate poetry. During training, our approach uses program synthesis to infer relational constraints cx present in the examples x, and uses both x and cx to train the generative models. Here, cx is a bipartite graph, where the LHS vertices are prototypes, and the RHS vertices correspond to lines of x. Each vertex on the right is 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 c—i.e., we need to choose a line to fill each RHS node in a way that the line satisfies the relations with its prototype. Furthermore, a user can modify the sampled constraint c to guide the generative process. Thus, our approach enables users to flexibly incorporate domain knowledge on the high-level structure of the data into the generative process, both in terms of the relational constraints included and by allowing them to modify the generated relational constraints.
Related work. There has been recent work using program synthesis to improve machine learning. For instance, it has been applied to unsupervised learning of latent structure in drawings (Ellis et al., 2015) and to reinforcement learning (Verma et al., 2018). These techniques have benefits such as improving interpretability (Verma et al., 2018; Ellis et al., 2020), enabling learning from fewer examples (Ellis et al., 2015), generalizing more robustly (Inala et al., 2019), and being easier 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 (Valkov 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 in neural models; we include a discussion of the most relevant such research in Appendix A.

heading: 2 BACKGROUND ON NEUROSYMBOLIC GENERATIVE MODELS
text: Consider the problem of learning a generative model given training data from the underlying distribution. Given training examples x1, ..., xk ∼ p∗, our goal is to learn a generative model pθ ≈ p∗ from which we can draw additional samples x ∼ pθ. We consider sequence data—i.e., an example x ∈ X is a sequence x = (w1, ..., wm) ∈ Wm.1 For example, each subcomponent w may be a line of a poem or a measure of music, and x may be a poem or song.
1We use a fixed m to simplify our exposition; our approach trivially extends to variable m.
We are interested in domains where likely examples satisfy latent relational constraints c ∈ C over the subcomponents. For instance, c may say that two measures wi and wj of x start with the same series of pitches, or that two lines wi and wj of x rhyme. We assume given a set of relationsR (e.g., r ∈ R might be “rhyme” or “equal”), and a function f :W ×W ×R → [0, 1] such that f(w,w′, r) indicates to what extent w and w′ satisfy relation r. Then, c is a compact representation of the relations present in an input x. We describe the structure of c in detail in Section 3.1; for now, the approach we describe works for any choice of c. In particular, we build on neurosymbolic generative models (Young et al., 2019), where c is itself generated based on a latent value z ∈ Z—i.e.,
pθ,φ(x) = ∫ ∑ c∈C pθ(x | c) · pφ(c | z) · p(z)dz.
Then, Young et al. (2019) considers the variational distribution
qφ̃(c, z | x) = qφ̃(z | c) · q(c | x) and q(c | x) = δ(c− cx).
Here, δ is the Dirac delta function and cx is a single representative generated from x using a program synthesis algorithm (David & Kroening, 2017)—i.e., an algorithm A that takes as input an example x and outputs a program c = A(x) encoding the relational constraints present in x. Next, Young et al. (2019) derive an evidence lower bound
log pθ,φ(x) ≥ log pθ(x | cx) + Eqφ̃(z|cx)[log pφ(cx | z)]−DKL(qφ̃(z | cx) ‖ p(z)).
where DKL 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 cx, and the second and third terms form the loss of a variational autoencoder (VAE) pφ(c | z) and qφ̃(z | c) (Kingma & Welling, 2019). In summary, given training examples x ∈ X , this approach separately learns (i) a VAE to generate c, trained on the relational constraints cx synthesized from each training example x, and (ii) a model to generate x given cx; the latter can take multiple forms such as a second VAE or a generative adversarial network (GAN) (Goodfellow et al., 2014). This approach is called synthesis-guided generative models (SGM) since it uses program synthesis to guide training.
To leverage this framework, we have to instantiate (i) the space of relational constraints C, (ii) the synthesis algorithm A : X → C used to extract a program encoding the structure of x, and (iii) the architectures of pφ(c | z), qφ̃(z | c), and pθ(x | c). In prior work, Young et al. (2019) used heuristics specific to the the image domain to achieve these goals—in particular, they used (i) 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 cx as an image, in which case pθ is a generative model over images, and pφ, qφ̃ based on an encoding of c as a fixed-length vector.
We design a synthesis algorithm that expresses the synthesis problem as a constrained combinatorial optimization problem, which it solves using an SMT solver called Z3 (De Moura & Bjørner, 2008). In terms of (iii), our programs encode declarative constraints rather than imperative renderings, so the previous architectures of pφ, and qφ̃ cannot be used. Instead, we use expert domain-specific heuristics, transformers (Vaswani et al., 2017), or graph neural networks (GNNs) (Kipf & Welling, 2017) for pφ and qφ̃. For pθ, we propose several methods for imposing the constraints encoded by c when generating an example x.

heading: 3 RELATIONAL CONSTRAINTS FOR SEQUENCE DATA
text: We describe how we represent relational constraints r, as well as our algorithm A for synthesizing the relational constraints cx = A(x) present in an example sequence x.

heading: 3.1 GRAPH REPRESENTATION OF RELATIONAL CONSTRAINTS
text: Recall that our generative model operates by first generating a relational program c, and then generating an example x that satisfies c. Thus, for each training example x, we need to design a relational program c that encode constraints on the structure of x. A program c encodes a 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 a single relational constraint, and then describe how c encodes a set of relational constraints.
A relational constraint φ ∈ Φ = W × I × R, where I = {1, ...,m}, is a tuple φ = (w̃, i, r); we call w̃ ∈ W a prototype subcomponent. An example x satisfies φ to extent h (denoted x |=h φ) if f(w̃, wi, r) = h, where wi is the ith subcomponent of x. That is, φ says the ith subcomponent wi of x should have relation r with prototype subcomponent w̃. Thus, we can interpret φ as a function φ : X → [0, 1], where φ(x) = 1 if x satisfies φ to the maximal extent and φ(x) = 0 if x does not satisfy φ at all.
Next, a relational program c encodes a set of relational constraints on examples x. We represent c as an undirected labeled bipartite graph c = (Ṽ , V, E) with vertices Ṽ and V and edges E ⊆ Ṽ ×V × 2R, where R is the set of relations and 2R is the power set of R. The vertices w̃ ∈ Ṽ are prototype subcomponents w̃ ∈ W; equivalently, they may be vector embeddings of prototype subcomponents. The vertices i ∈ V = {1, ...,m} are the indices of subcomponents in x. The edges e ∈ E are tuples e = (w̃, i, R), where R = [0, 1]|R|. For tractability of synthesis, we impose the constraint that each v ∈ V is part of a single edge (w̃, v, R) (though ṽ ∈ Ṽ may be part of multiple edges). Finally, c encodes the set of relational constraints
Φc = {(w̃, i, r, h) | (w̃, i, R) ∈ E ∧R[r] = h} .
In other words, c includes the relational constraint that each subcomponent wi of x should have all relations r ∈ R with prototype w̃ to extent h, where v is connected to w̃. In this paper, for most examples, we consider binary relationships that have 0 or 1 as values, and informally state that a pair w̃, i does not have a relationship r if f(w̃, i, r) = 0. However, as we show in our experiments, non-boolean functions with values between 0 and 1 can be used as well.
For example, in Figure 1, the graph shown on the top right encodes a relational constraint cx, and the top right shows an example x that satisfies all the constraints φ ∈ Φcx with a value greater than 0. The nodes on the left-hand side of cx are prototype subcomponents w̃ ∈ W , each of which is a line of poetry. The nodes on the right-hand side correspond to indices i (from i = 1 on top to i = m = 10
on the bottom); each one is labeled with a set of relations Ri. Then, Φcx contains constraints φ = (w̃, i, Ri) for each edge w̃ → i in the graph, which says that line i of x should have relations r ∈ Ri with w̃. For instance, the last (10th) node in cx has constraints R10 = {rhyme,meter}, and is connected to prototype line w̃ =“The harp that thou...”. Thus, this edge encodes a constraint φ = (w̃, 10, R10) saying that the last line of x should rhyme and have the same meter as w̃. Indeed, the last line of 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 size of the graph is tractable—with this choice, the graph is linear in the size of the input (assuming the number of prototypes is constant) rather than quadratic. A compact graph is both each to synthesize (for training) and train a model to generate (for generation). In our experiments, we show that our approach significantly outperforms attempting to generate full graphs (i.e., adjacency tensors). Remark 3.2. We refer to c as a program since it can be interpreted as a Datalog program (Ceri et al., 1989) (i.e., a relational logic program); in particular, Φc is a set of Datalog relations over x ∈ X .

heading: 3.2 SYNTHESIZING RELATIONAL CONSTRAINTS
text: Recall that when training our generative model, we need to design a program synthesis algorithm A that synthesizes a relational program cx = 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̃ to be actual subcomponents in x. Thus, cx encodes that subcomponents of x are each related to one of a small number of distinguished subcomponents of x. As described below, we formulate the problem of synthesizing cx as a constrained optimization problem.
Optimization variables. The variables are a binary vectorH ∈ Bm and a binary matrixK ∈ Bm×m. Intuitively, Hi indicates whether subcomponent wi of x is a prototype subcomponent in c, and Kij indicates whether wi is the prototype for subcomponent wj .
Constraints. Our optimization problem has the following three constraints:
ψ1 ≡ kmin ≤ m∑ i=1 Hi ≤ kmax, ψ2 ≡ m∧ j=1 m∑ i=1 Kij = 1, ψ3 ≡ m∧ i=1 m∑ j=1 Kij ≤ m ·Hi.
First, ψ1 says that the number of prototype subcomponents is between kmin and kmax. Next, ψ2 says that every subcomponent wj corresponds to exactly one prototype subcomponent wi. Finally, ψ3 says that for every i, if wi is the prototype subcomponent of wj according to K, then it must be a prototype subcomponent according to H as well.
Objective. The objective of our optimization problem is expressed in terms of a precomputed distance matrix D ∈ Rm×m, where Dij measures the similarity between components wi and wj ; smaller values indicate a greater degree of similarity. In particular, we define
Dij = 1∑
r∈R(f(wi, wj , r)) ,
i.e., Dij is the extent to which each r ∈ R are not satisfied by wi and wj . Then, our objective (which is to be minimized) has the following three terms:
J1 = m∑ i,j=1 Kij ·Dij , J2 = m∑ i,j=1 (∏ k Kki ·Kkj ) ·Dij , J3 = − m∑ i,j=1 Hi ·Hj ·Dij .
First, J1 says that subcomponents should be similar to their prototypes. Second, J2 says that subcomponents should also be similar to other subcomponents that share the same prototype. Third, J3 says that different prototype subcomponents should be dissimilar.
Optimization problem. Our algorithm A uses Z3 to solve the optimization problem
(H∗,K∗) = arg min H,K {λ1 · J1 + λ2 · J2 + λ3 · J3} subj. to ψ1 ∧ ψ2 ∧ ψ3, (1)
where λ1, λ2, λ3 ∈ R≥0 are hyperparameters. Finally, to construct cx, A chooses
Ṽ = {wi | H∗i = 1}, V = {1, ...,m}, E = {(wi, j, Rij) | K∗ij = 1},
where Rij = {r ∈ R | f(wi, wj , r) = 1}—i.e., Ṽ are the prototype subcomponents according to H∗, E are the edges according to K∗, and Rij are the extent to which relations are satisfied by wi and wj . Z3 is guaranteed to find the optimal solution; in the event that multiple such solutions exist, it chooses one nondeterministically. Intuitively, our approach should perform well when a handful of prototypes are sufficient to approximately capture the relational structure in the data, which appears to be true in the domains of rhyming poetry and melodies. Also, the user can define relations in a way that captures desired structure for any domain.

heading: 4 RELATIONAL CONSTRAINTS IN NEUROSYMBOLIC GENERATIVE MODELS
text: We describe our model for generating examples x. Recall that our approach proceeds in two steps: (i) generate c, and (ii) generate x given Φc. We describe each step in detail below.

heading: 4.1 STEP 1: GENERATING RELATIONAL CONSTRAINTS
text: The first step of our generative model is to generate relational constraints Φc using a VAE—i.e., pφ(c | z) is a VAE with p(z) = N (z; 0, I) being a Gaussian distribution. The main choice is the architecture to use for the VAE. In particular, we consider a representation of c as a sequence (s1, ..., sm), where si ∈ {0, 1, ..., k} for each i; intuitively, si encodes that subcomponent wi should have the same prototype subcomponent as wi−si , or if si ≤ 0, that wi corresponds to a new prototype subcomponent. In practice, we found that in the music domain, the vast majority of examples could be described using k ≤ 6, which decreased the number of possible values that could be predicted and simplified the problem; however, it would be possible in other domains for k to be as large as m− 1. More precisely, we initialize Φc = ∅. Then, we generate the sequence si ∈ {0, 1, ..., k} and ri ∈ {0, 1, ...,m} (where ri is represented as a binary vector of length n = |R|) using either: (i) an LSTM-VAE, or (ii) a 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 (w̃, Ri) based on si and ri according to the following approach: If si = 0, we generate a new prototype subcomponent w̃ using a domain-specific generative model, and add φi = (w̃i, i, Ri) to Φc. If si > 0, we let φi = (w̃i−si , i, Ri).

heading: 4.2 STEP 2: GENERATING EXAMPLES GIVEN RELATIONAL CONSTRAINTS
text: Next, we describe how we implement the second step pθ(x | c) of our generative model. We propose three approaches for generating x given Φc; we give details in Appendix B.
Approach 1: Constrained sampling. We sample values x ∼ pθ(·) by sequentially sampling wi ∼ pθ(·) from a pretrained generative model pθ(w). We do so using rejection sampling at each step—i.e., we sample wi ∼ pθ(·) until we find wi satisfying f(w̃, wi, r) ≈ h for each (w̃, i, r, h) ∈ Φc. 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 Φc.
Approach 2: Constraint-aware embeddings. We train a conditional variational autoencoder (cVAE) pθ(w1, ..., wm | c) in the form of a graph convolutional network (GCN) that simultaneously generates all m subcomponents in a way that satisfies c, and sample x = (w1, ..., wm) ∼ pθ(· | c). The GCN takes as input embeddings of each prototype and subcomponent of x, and the adjacency matrix is given by the edges in c (where the relation is encoded as an edge attribute). Then, 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 c.
Approach 3: Combinatorial optimization. We sample x ∼ pθ(·) by sequentially generating wi by solving an optimization problem whose objective is to maximize adherence to Φc plus additional terms encoding domain-specific heuristics encouraging wi to be realistic.

heading: 5 EXPERIMENTS
text: We evaluate our approach on two domains: music and poetry generation. We provide details on experimental design and additional results in Appendix C.

heading: 5.1 MUSIC GENERATION
text: We evaluated our approach on a music generation, where x is a song and w are measures of music. We consider 20 relations including equality, same rhythm, etc.; see Appendix C.2.
Dataset. We used songs from the Essen folk song corpus (Schaffrath, 1995), using 2223 for training and 555 for testing (after removing examples with less than 16 measures or that were not in the standard 4/4 meter). For this dataset, we used each of the three approaches A1, A2, and A3 described in Section 4 to sample x ∼ pθ(· | c). For A1, we use a pretrained transformer called MusicAutoBot (Shaw, 2020). For A2, we require a generative model that constructs vector embeddings of measures; we use the pretrained version of Magenta’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 (AttentionRNN) (Waite, 2016), Magenta’s 16-bar MusicVAE (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 instead of synthesizing compact representations of relational constraints, and one that uses a greedy synthesizer—i.e., at each step, greedily choose the single prototype and its relations that most increases (1). Finally, we consider using a continuous relation, namely, the cosine similarity of the MagentaVAE embeddings.
Metrics. We compare performance in terms of both high-level and low-level structure. For lowlevel structure, we use the negative log likelihood (NLL) on a held-out test set for MusicVAE, MusicAutobot, and our approach with strategy A2. The remaining approaches are not probabilistic (or estimating probabilities is intractable). For these approaches, we use a variant of the standard Fréchet distance (FD) score used to evaluate GANs (Borji, 2019)—i.e., the Fréchet distance between the MusicVAE (16-bar) embeddings of the generated music and the held-out test set.
For high-level structure, given a generated (or human) example x, we use our synthesis algorithm to synthesize its relational constraints cx = A(x). Then, given a collection Cgen = {cx | x ∈ Xgen} of synthesized structure for generated examples, along with a collection Chuman = {cx | x ∈ Xhuman} of synthesized structure for the held-out human examples, we train a graph convolutional neural network (GCN) to try and discriminate Cgen from Chuman, as well as a random forest (RF) over handcrafted features (see Appendix C.4). Intuitively, higher discriminative power should indicate less realistic structure. In both cases, we use a balanced dataset (i.e., 50% human held-out and 50% generated) so random predictions have accuracy 0.5. Recent work has shown that such discriminator-based metrics are valid for evaluating quality of generated examples (Lopez-Paz & Oquab, 2016).
Results. In Table 1, we show results for models for which we can compute the test set NLL (left) and results for the remaining models (right). As can be seen, our approach (SGM) with sampling
strategy A2 outperforms all other models in both tables, in terms of both high-level structure and low-level structure. In Table 1 (left), the closest alternative is MusicVAE, 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 1 (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 a learning-based model to generate low-level structure. Our ablation where we perform no synthesis performs poorly, especially in terms of structure, as does the one using greedy synthesis, demonstrating the importance of using constraint solving to synthesize compact representations of structure. On the other hand, greedy synthesis can be significantly more scalable than constrained optimization for large examples; thus, improving this strategy is an interesting direction for future work. Finally, using a continuous relation performs competitively in terms of FD score (though interestingly, it performs worse in terms of high-level structure), demonstrating that our approach can be applied with continuous relations.

heading: 5.2 POETRY GENERATION
text: 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; see Appendix C.3 for details.
Dataset. We use from Project Gutenberg’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-aware 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 (Radford 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 to choose line breaks in a way that maximizes occurrences of rhyme and meter. We also tried a 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 it failed to generate a single poem even after several hours. We also compare to an implementation of RichLyrics (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 Φc uniformly randomly rather than from a learned distribution.
Metrics. For low-level structure, we use FD score on SentenceBert embeddings, which are unaware of rhyme and meter (Reimers & Gurevych, 2019); we cannot evaluate log-likelihood since we are using constrained sampling. For high-level structure, we train a GCN to discriminate synthesized programs for generated examples vs, test examples.
Results. We show results in Table 2. Our approach (SGM) with sampling strategy A3 significantly outperforms all baselines in terms of high-level programmatic structure, while also outperforming them in terms of FD scores. Approach A1 performs even better in terms of programmatic structure, but is not competitive with respect to FD scores, presumably due to the fact that GPT-2 is significantly better at natural language generation than BERT.
User study. We also performed a user study, discussed in Appendix C.5, which further confirmed this methods’ strength in the poetry domain. in this domain, with 50 participants.
User modifications. A key benefit of our approach is that the user can modify the relational constraints c (or construct their own from scratch) for use in the second step pθ(x | c), giving the user a way to guide the generative process. An example in the poetry domain is shown in Figure 5.2, and musical examples are shown in Appendix D.2.

heading: 6 CONCLUSION
text: 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 a 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 our 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 to maintain reproducibility for our 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.

heading: A ADDITIONAL RELATED WORK
text: 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., 2009; Cope, 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; OpenAI, 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 convolutional 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 transformers (Huang et al., 2019). In particular, we leverage attention-based 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 we extend) (Liao et al., 2019b), RNN-based conditional-VAEs (Yang et al., 2017b), RNN-based planning (Wang et al., 2016), and GANs with both transformer and LSTM backends (Saeed et al., 2019).
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-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 a 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 to 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.

heading: B GENERATING EXAMPLES GIVEN RELATIONAL CONSTRAINTS

heading: B.1 APPROACH 1: CONSTRAINED SAMPLING
text: In the music domain, we choose the pretrained generative model pθ(w) to be a pretrained version of MusicAutoBot. To generate x, we sequentially sample each measure wi conditioned on all prior measures w1, ..., wi−1. Each measure is sampled by sequentially sampling a sequence of pitchduration pairs until the total duration is 16 beats (i.e., the length of a measure). During sampling, we mask pitch-duration pairs that cannot satisfy Φc (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 k in measure i such that
|(pitchk − pitchk−1)− (p̃itchk − p̃itchk−1)| ≥ 3,
where p̃itchk is pitch k 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 a sentence. We leverage this ability to sample lines that rhyme and have the same meter, which is a challenging task since such lines are a tiny fraction of the search space. We describe how we simultaneously handle rhyming and equal
meter; the cases where only one of these two constraints has to hold are similar. Given a prototype w̃, we work backwards—on each step j, we sample from BERT a word wordk that has the same number of syllables as the corresponding word w̃ordk in the prototype. More precisely, we feed BERT the sequence
w̃ord1, ..., w̃ordk−1,MASK,wordk+1, ...
and ask it to fill in the masked word, setting the probability of any word with different number of syllables as w̃ordk to zero.
In addition, to avoid producing a 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 w̃ordk. To increase diversity, we sample the remaining words twice—(i) backwards-to-forwards from word k − 1 to word 1, where k is the number of words, and (ii) we resample each of the k − 1 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.

heading: B.2 APPROACH 2: CONSTRAINT-AWARE EMBEDDINGS
text: This approach uses a graph convolutional network (GCN) conditional variational autoencoder (cVAE), or GCN-cVAE, which consists of a GCN encoder qθ(z′ | x, cx) and a GCN decoder pθ(x | z′, cx). In more detail, we assume x = (w1, ..., wm) is represented as a sequence of vectors (u1, ..., um)— e.g., in the music domain, we use MusicVAE pψ to encode u ∼ qψ(· | w) or decode w ∼ pψ(· | u). Then, the latent encoding z′ consists of an embedding vector for each subcomponent u of x.
Next, cx is incorporated into each GCN by converting it into a tensor with dimensions |ŵ|× |ŵ|× |R| used as the adjacency matrix of that GCN (the last dimension is the edge attribute). Intuitively, the edges in x are relations in c between subcomponents and prototypes.
This GCN-cVAE it is trained using the usual VAE objective (Kingma & Welling, 2019): (i) a KL divergence term encouraging the embeddings z′ to be Gaussian, and (ii) a reconstruction loss in terms of mean-squared error. We also include a semantic consistency loss to enforce the satisfaction of the constraints Φc. In particular, we train a classifier pα(u, u′; r) that predicts whether two subcomponents u, u′ satisfy relation r (more precisely, when decoded by pψ). The model pα is trained examples (u, u′, r) from the training data x. Then, we include the loss∑
(w̃,i,r)∈Φc
pα(ũ, ui, r),
where ũ ∼ pψ(· | w̃) is the encoding of w̃, ui ∼ pψ(· | wi) is the encoding of wi, and r is a relation. For the music domain, we use a pretrained MusicVAE for pψ and qψ; unlike the MusicVAE we use for evaluation, we finetune a model that decodes 1 measure of music from a 256-dimensional vector.

heading: B.3 APPROACH 3: COMBINATORIAL OPTIMIZATION
text: Given sampled program c, this approach attempts to generate values x = (w0, . . . , wm) such that x |= Φc by solving a system of constraints. However, when generated using a neural network, relational constraints φ ∈ Φc are not always consistent with one another, so we convert the constraint x |= Φc into an objective—i.e.,
x = arg max x∈X m∑ i=1 ∑ r∈R 1(R(w̃, wi, n)⇔ (w̃, i, n) ∈ Φc).
The ability to encode this optimization problem as one that Z3 can solve depends on 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 x is realistic.
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 x satisfies c, along with domain-specific heuristics—e.g., minimizing large jumps in pitch values (i.e., |pitchk+1 − pitchk| ≥ 4), not having any intervals of length 6 (i.e., |pitchk+1− pitchk| = 6) due to the unpleasant harmonic nature of that interval, and not having two consecutive jumps in pitch (i.e., |pitchk+2 − pitchk+1| ≥ 5) ∧ |pitchk+1 − pitchk| ≥ 5). These heuristics are based on standard concepts from music theory (Horton & Ritchey, 2000).
For the language domain, we use GPT-2 to sample a line except for the last word; then, the optimization 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.

heading: C EVALUATION DETAILS

heading: C.1 EXPERIMENTAL SETUP
text: Synthesizing programs. The hyperparameters J1, J2, and J3 in the program synthesis task, as described in the main section of this paper, regulate the degree to 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, J2, and J3 were 1, 10, and 1, 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 c in the poetry domain, we use an LSTM-VAE with 6 LSTM layers and a latent size of 50. This model is trained to reproduce a given sequence of (si, ri) pairs which are given as input, with an 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 we had more success using a feedforward 3-layer network which took the previous n (usually n = 6) (si, ri) pairs, and outputted a distribution over the following pair.
Each (si, ri) pair is represented as a (S+ |R|)-dimensional vector, where S is the maximum distance between objects with the same prototype and R is the set of relations.
High-level structure. We evaluate high-level structure by using our algorithm to synthesize the relational constraints in every generated example—i.e., Cgen = {A(x) | x ∈ Xgen}, whereXgen is the set of examples generated using a model. Similarly, we can construct Chuman = {A(x) | x ∈ Xhuman}, where Xhuman is the set of human-created examples held-out from the training dataset. Then, we evaluate high-level structure by training a model to 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 a graph neural network (e.g., a graph convolutional network) to do so; this model takes as input the graph structure of relational constraints c, along with vector embeddings of the prototype subcomponents, and outputs whether c ∈ Cgen or c ∈ Chuman. 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 a manual featurization of c. We report the accuracy of the RF; lower values (i.e., closer to 50%) correspond to better generative models.

heading: C.2 MUSICAL RELATIONS USED
text: The following are the relations r ∈ 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 j have approximately the same interval structure.
6. Measures i and j have the same interval prefix.
7. Measures i and j have the same interval suffix.
8. Measures i and j have the same note (pitch + duration) prefix.
9. Measures i and j have the same note (pitch + duration) suffix.
10. Measures i and j have the same rhythm.
11. Measures i and j’s rhythm has an edit distance of ≤ 2. 12. Either measure i’s onsets are a subset of measure j’s onsets, or measure j’s onsets are a
subset of measure i’s onsets.
13. Measures i and j have the same rhythmic and melodic contour.
14. Measures i and j have the same rhythmic and melodic contour prefix.
15. Measures i and j have the same rhythmic and melodic contour suffix.
16. Either the first or second half of measures i and j are identical.
17. Either both or neither of measures i and j have leaps.
18. Measures i and j fit within the same diatonic scale.
19. Either both or neither of measures i and j have syncopation.
20. Either both or neither of measures i and j have consecutive notes shorter than an eighth note.
21. (Continuous) The cosine similarity between the Measure-VAE embeddings of measure i and measure j.

heading: C.3 POETRY RELATIONS USED
text: The following are the relations r ∈ R used in the poetry domain: 1. Lines i and j have the same end rhyme.
2. Lines i and j have the same meter.

heading: C.4 RANDOM FOREST FEATURES
text: The following are 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 i . . . j such that wi . . . wj all have the same prototype measure.
5. Number of pairs (i, j) such that w̃i = w̃j and w̃i+1 = w̃j+1.
6. Mean distance between two measures with the same prototype.
7. Variance in distance between two measures with the same prototype.

heading: C.5 USER STUDY DETAILS
text: 50 participants took place in the study on Mechanical Turk. Each was paid $5 to complete a survey with 12 questions (3 poems each from four sources, Ours, GPT2-Finetune, BERT-Finetune, and RichLyrics). All poems were chosen automatically by taking the top 3 examples from the generated datasets according to GPT2-log-likelihood. The participants were asked to rank the following 3 statements from "strongly disagree" to "strongly agree" (1-5) as follows:
1. It is obvious that this is a poem
2. This text is coherent
3. I notice that this text has rhyme and meter

heading: D ADDITIONAL RESULTS

heading: D.1 COMPARISON TO CONSTRAINT SOLVING
text: We also considered a comparison to a constraint-based implementation called Motifate, with explicit attention to 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—its 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.

heading: D.2 CONDITIONING ON USER-PROVIDED STRUCTURES
text: Here we show how user modifications can occur in the music and poetry settings. By explicitly modifying c, we are able to generate two pieces of poetry or two tunes with similar internal patterns but with different structural characteristics.

heading: D.3 QUALITATIVE OBSERVATIONS ON THE MUSIC DOMAIN
text: 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 our observations, the strengths of A2 include clearer phrases with obvious resolutions, likely and plausibly repetitive rhythms, intervals between notes which seemed plausible but not overly repetitive, and less variance
in quality. However, the results were not very rhythmically diverse, and certain idiomatic patterns of resolutions of intervals between notes and at 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 is 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.

heading: D.4 EXAMPLES FROM THE MUSIC DOMAIN
text: We show an example of generated songs using our approach with each A1, A2, and A3 in Figure 5, Figure 6, and Figure 7, respectively, and show an example generated using each of the baselines MusicVAE16, AttentionRNN, MusicAutoBot, and StructureNet in Figures 8, 9, 10, & 11, respectively. Qualitatively, the generated music and poetry appears plausible, exhibiting realistic high-level structure without sacrificing low-level structure.

heading: D.5 EXAMPLES FROM THE POETRY DOMAIN
text: In Figure D.5, we show an 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 is even less structure in poems generated using vanilla GPT2. Thus, GPT2 is completely unable to capture high-level structure in the real poetry provided as training data. In contrast, our poem captures structure very similar to the human poem shown in Figure 1, such as rhyming adjacent lines.
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 as a language generation model in
Figure 17, RichLyrics, and our ablation (i.e., use BERT in conjunction with a uniformly randomly sampled Φc) in Figure 18.

Review summaries:
This paper proposes an approach for generating sequences that possess high-level structure, and in particular structure that can be expressed using hand-crafted symbolic relations. Given a domain and a set of possible relations to consider, this approach first extracts a sequence representation of the relational constraints for each example, then trains a two-stage generative model that first generates relational constraints and then generates the final output conditioned on the constraints. The authors apply their approach to the generation of music and poetry, and show that, compared to simple baselines, the generated outputs are more consistent with human-generated examples (according to other learned models of high- and low-level structure).

This paper proposes a neural-symbolic deep generative model to generate music and poems. Compared to other natural language sentence generation tasks, songs and poems usually require some structural constraints, e.g., rhythm and rhymes. Therefore, their approach first generates a program represented as a set of relational constraints, then generates sequences that satisfy the constraints. During the training time, given a training example, i.e., a sequence, they formulate the program synthesis task as a combinatorial optimization problem, and thus they can find the required constraints using the Z3 solver. They use the SOTA generative models for both of the two sequence generation domains. They propose several variants of the generation approach, to ensure that the generated sequences satisfy the constraints. They evaluate their approach in terms of both the low-level and high-level structures. To measure the low-level structure, they compute the negative log likelihood of the SOTA generative models. To measure the high-level structure, they apply the Z3 solver to solve the relational constraints of each generated sequence, and train some discriminators to distinguish the generated sequences from the human-written ones in the dataset. For the poetry domain, they also evaluate the diversity of the generated sequences. Generally, the neural-symbolic approach generates sequences with better high-level structures, and the generated samples are more diverse.