Year: 2021

Abstract:
Conditional set generation learns a mapping from an input sequence of tokens to a set. Several popular natural language processing (NLP) tasks, such as entity typing and dialogue emotion tagging, are instances of set generation. Sequenceto-sequence models are a popular choice to model set generation but this typical approach of treating a set as a sequence does not fully leverage its key properties, namely order-invariance and cardinality. We propose a novel data augmentation approach that recovers informative orders for labels using their dependence information. Further, we jointly model the set cardinality and output by listing the set size as the first element and taking advantage of the autoregressive factorization used by SEQ2SEQ models. Our experiments in simulated settings and on three diverse NLP datasets show that our method improves over strong SEQ2SEQ baselines by about 9% on absolute F1 score. We will release all code and data upon acceptance.

heading: 1 INTRODUCTION
text: Conditional set generation is the task of modeling the distribution of an output set given an input sequence of tokens (Kosiorek et al., 2020). Several natural language processing (NLP) tasks are instances of set generation, including open-entity typing (Choi et al., 2018; Dai et al., 2021) and fine-grained emotion classification (Demszky et al., 2020). The recent successes of pretrainingfinetuning paradigm have encouraged a formulation of set generation as a sequence-to-sequence generation task (Vinyals et al., 2016; Yang et al., 2018; Ju et al., 2020).
In this paper, we argue that modeling set generation as a vanilla SEQ2SEQ generation task is suboptimal as the SEQ2SEQ formulations do not explicitly account for two key properties of a set output: order-invariance and cardinality. Forgoing order-invariance, vanilla SEQ2SEQ generation modeling treats a set as a sequence, and thus assumes an arbitrary order between the elements it outputs. Similarly, the cardinality of sets is ignored, as the number of elements to be generated is typically not explicitly modeled. Although prior work has highlighted the importance of modeling the orderinvariant nature of both set inputs (Zaheer et al., 2017) and outputs (Vinyals et al., 2016; Rezatofighi et al., 2018), the question of effectively modeling set output using SEQ2SEQ models still remains an open challenge.1
Our method addresses the challenges above by taking advantage of the auto-regressive factorization used by SEQ2SEQ models and (i) imposing an informative order over the label space, and (ii) explicity modeling cardinality. First, the label sets are converted to sequences using informative orders by grouping labels and leveraging their dependency structure. A natural way to model this is to search exhaustively for the best label orders. To efficiently search for such informative orders over a combinatorial space, our method imposes a partial order graph over the labels, where the nodes are the labels and the edges denote the conditional dependence relations. We then generate the training data with a fixed input and orders over the label set that are sampled by performing topological traversals over the graph. Labels that are not constrained by dependency relations are augmented in different positions in each sample, reinforcing the order-invariance. We then create an augmented training dataset, where each input instance is paired with various valid label sequences sampled from the dependency graph. Next, we jointly model a set with its cardinality by simply appending the size of the set as the first element in the sequence.
1Our work focuses on settings where the input is a sequence, and the output is a set.
Figure 1 illustrates the key intuitions behind our method using sample task where given an input x, the output is a set of shapes and their constituents (Y). To see why certain orders might be more meaningful, consider a case where the output is a triangle consisting of a half-square and a line. After first generating triangle as a shape, the model can generate a half-square with certainty (a triangle will always contain a half-square). In contrast, the reverse order (generating half-square first) still leaves room for two possible shapes: square and triangle. The order [triangle, half-square] is thus more informative than [half-square, triangle]. The cardinality of a set can also be helpful. In our example, a triangle is composed of two shapes, and a star with three. A model that first predicts the number of shapes to generate can be more precise in its output and avoid over-generation, a major challenge with language generation models (Welleck et al., 2019; Fu et al., 2021).
Empirically, we establish the utility and soundness of our approach by showing gains on three realworld NLP datasets (∼10% in F–scores). This result is significant - we effectively show that simple techniques such as augmenting cardinality and automated data augmentation approaches can substantially improve sequence to set generation tasks without any additional annotation overhead or architecture changes. We also provide a theoretical grounding for our approach. Treating the order as a latent variable, we show that TSAMPLE serves as a better proposal distribution when viewed via a variational inference framework. Finally, we perform an in-depth analysis of the reasons behind the sensitivity of the SEQ2SEQ framework on order by experimenting with a simulated experiment that realistically mimics a conditional set generation setting.
Our contributions (i) we show an efficient way to model sequence-to-set prediction as an SEQ2SEQ task by jointly modeling the cardinality and proposing a novel TSAMPLE data augmentation approach to add informative sequences. (ii) we show theoretically and empirically that our approach is better suited for set generation tasks than existing approaches.

heading: 2 BACKGROUND AND RELATED WORK
text: Notation Our focus is the setting where we are given a corpus D of {(xt,Yt)}mt=1 where xt is a sequence of tokens and Yt = {y1, y2, . . . , yk} is a set. For example, in multi-label fine-grained sentiment classification, xt is a paragraph, and Yt is a set of sentiments expressed by the paragraph. We use yi to denote an output symbol, [yi, yj , yk] to denote an ordered sequence of symbols and {yi, yj , yk} to denote a set.

heading: 2.1 SET GENERATION USING SEQ2SEQ MODEL
text: Task Given a corpus {(xt,Yt)}mt=1, the task of conditional set generation is to efficiently estimate p(Yt | xt).
In this work, we adopt SEQ2SEQ models for the task. SEQ2SEQ models factorize p(Yt | xt) in an autoregressive (AR) fashion using the chain rule:
p(Yt | xt) = p(y1, y2, . . . , yk | xt)
= p(y1 | xt) k∏ j=2 p(yj | xi, y1 . . . yj−1) (1)
where we have used the order Yt = [y1, y2, . . . , yk] to factorize the joint distribution using chain rule. In theory, any of the k! orders can be used to factorize the same joint distribution. In practice, however, the choice of order is important. For instance, Vinyals et al. (2016) show that output order affects language modeling performance when using LSTM based SEQ2SEQ models for set generation.
Consider an example (xt,Yt = {y1, y2}) pair. By chain rule, we have the following equivalent factorizations of this sequence: p(Yt | xt) = p(y1 | x)p(y2 | x, y1) = p(y2 | x)p(y1 | x, y2). However, order-invariance is only guaranteed with true conditional probabilities, whereas the conditional probabilities used to factorize a sequence are estimated by a model from a corpus. Thus, dependening on the order, the sequence factorizes as either p̂(y1 | x)p̂(y2 | x, y1) or p̂(y2 | x)p̂(y1 | x, y2), which are not necessarily equivalent. Further, one of the two factorizations might closely approximate the true distribution, thus being a better choice.

heading: 2.2 EXISTING TECHNIQUES FOR SET GENERATION
text: Set generation for computer vision problems has received considerable attention. Specifically, Rezatofighi et al. (2018; 2020) investigate set outputs for vision tasks. Their learning procedure involves jointly learning the order and the cardinality of the set. However, their method relies on searching through a combinatorial space of permutations.
Zhang et al. (2019a) propose deep set prediction networks (DSPN), using an auto-encoder framework with a set encoder for conditional generation of digits and image tags with a fixed maximum number of elements. Kosiorek et al. (2020) extend DSPN by additionally modeling the cardinality of the output using an MLP. Finally, Zhang et al. (2020) explore the usage of energy-based models for set prediction. Their learning and inference procedure relies on drawing samples from the set distribution, which is prohibitively expensive for extremely high-dimensional spaces like text. Other examples include works such as Salvador et al. (2019), who aim to extract set of ingredients from food images.
Our approach differs from their work in several important ways: i) instead of performing an exhaustive search over the sample space, we add informative order over labels in the input as a data augmentation step, ii) we model cardinality simply by listing the set size as the first element of the sequence, and thus jointly learn both it with the set output, and iii) Image classification and tagging typically involves a small, independent number of tags. In contrast, NLP tasks have richer and larger label space. Our method is more suitable for such tasks as it does not rely on exhaustive search over label space and leverages label dependencies.
Chen et al. (2021) explored the generation of an optimal order for graph generation given the nodes. They observed that ordering nodes before inducing edges improves graph generation. However, in our case, since the labels themselves are being generated, conditioning on the labels to create the optimal order is not possible for non-trivial setups. Non-SEQ2SEQ set generation These include using deep reinforcement learning for multi-label classification (Yang et al., 2019) and combinatorial problems such as Sudoku (Nandwani et al., 2020), and pointer networks (Ye et al., 2021) for extracting and generating keyphrases. Unlike these works, our focus is on methods that can optimally adapt existing SEQ2SEQ models for set generation, without doing using external knowledge (Wang et al., 2020; Zhang et al., 2019b). Since our approach does not involve directly changing the model parameters or training procedure, we can leverage the advantages of the pretraining-finetuning paradigm and large-scale language models, which have shown immense promise in several NLP tasks.
Connection with Janossy pooling Murphy et al. (2019) generalize deep sets by proposing to encode a set of N elements by pooling permutations of P (N, k) tuples. With k = N , their method
is the same as pooling all N ! sequences, and with k = 1, it reduces to deep sets. Our approach shares the spirit of tractable searching over N ! with Janossy pooling. However, instead of iterating over all possible 2-tuples, our method imposes pairwise constraints on the order of the elements.

heading: 2.3 MODELING SET INPUT
text: A number of techniques have been proposed for encoding set-shaped inputs (Santoro et al., 2017; Zaheer et al., 2017; Lee et al., 2019; Murphy et al., 2019; Huang et al., 2020; Kim et al., 2021). Specifically, Zaheer et al. (2017) propose deep sets, wherein they show that pooling the representations of individual set elements and feeding the resulting features to a non-linear network is a principled way of representing sets. Lee et al. (2019) present permutation-invariant attention to encode shapes and images using a modified version of attention (Vaswani et al., 2017). We note that our work focuses on settings where the input is a sequence, and the output is a set.

heading: 3 METHOD
text: In this section, we present TSAMPLE, a novel method that tractably creates informative orders over sets. We also present our approach of jointly modeling cardinality and set output.

heading: 3.1 ADDING INFORMATIVE ORDERS FOR SET OUTPUT
text: As discussed in Section 2, SEQ2SEQ formulation requires the output to be in a sequence. Prior work (Vinyals et al., 2016; Rezatofighi et al., 2018; Chen et al., 2021) has noted that adding orders that have the highest conditional likelihood given the input is an optimal choice. Unlike these methods, we create training data using orders sampled from TSAMPLE, thus completely sidestepping exhaustive searching during training.
Our core insight is that knowing the optimal order between pairs of symbols in the output drastically reduces the possible number of permutations. We thus impose pairwise order constraints for a subset of labels. Specifically, given an output set Yt = y1, y2, . . . , yk, if yi, yj are independent, they can be added in an arbitrary order. Otherwise, an order constraint is added to the order between yi, yj .
Learning pairwise constraints We estimate the dependence between elements yi, yj using pointwise mutual information: pmi(yi, yj) = log p(yi, yj)/p(yi)p(yj). Here, pmi(yi, yj) > 0 indicates that the labels yi, yj co-occur more than would be expected under the conditions of independence (Wettler & Rapp, 1993). We use pmi(yi, yj) > α to filter our such pairs of dependent pairs, and perform another check to determine if the order between them should be fixed. For each dependent pair yi, yj , the order is constrained to be [yi, yj ] if log p(yj | yi) − log p(yi | yj) > β (yj should come after yi), and [yj , yi] otherwise. Intuitively, log p(yj | yi)− log p(yi | yj) > β implies that knowledge that a set contains yi, increases the probability of yj being present. Thus, fixing the order to [yi, yj ] will be more efficient for generating a set with {yi, yj}.
Generating samples To systematically create permutations that satisfy these constraints, we construct a topological graph Gt where each node is a label yi ∈ Yt, and the edges are determined using the pmi and the conditional probabilities as outlined above (Algorithm 1). The required permutations can then simply be generated as topological traversals Gt (Figure 2). To generate diverse samples, we begin the traversal from a different starting node. We call this method TSAMPLE. Later, we show that TSAMPLE can be interpreted as a proposal distribution in variational inference framework, which distributes the mass uniformly over informative orders constrained by the graph.
Do pairwise constraints hold for longer sequences? While TSAMPLE uses pairwise (and not higher-order) constraints for ordering variables, we note that the pairwise checks remain relevant with extra variables. First, dependence between pair of variables is retained in joint distributions involving more variables (yi 6⊥⊥ yj =⇒ yi 6⊥⊥ yj ,yk) for some yk ∈ Y (Appendix A.1). Further, if yi, yj ⊥⊥ yk, then it can be shown that p(yi | yj) > p(yj | yi) =⇒ p(yi | yj ,yk) > p(yj | yi,yk) (Appendix A.2). The first property shows that the pairwise dependencies hold in the presence of other elements of the set. The second property shows that an informative order continues
to be informative when additional independent symbols are added to it. Thus, our criterion of using pairwise dependencies between the elements of a set is still effective. Finally, we note that using higher-order dependencies might be suboptimal for practical reasons: higher-order dependencies (or including xt) might not be accurately discovered due to sparsity, and thus causing spurious orders.
Complexity analysis Let Y be the label space (i.e., set of all possible labels), (xt,Yt) be a particular training example, N be the size of the training set, and c be the maximum number of elements for any set Yt in the input. Our method requires three steps: i) iterating over the training data to learn conditional probabilities and pmi, and ii) given a Yt, building the topo-graph Gt (Algorithm 1), and iii) traversing Gt to create samples for (xt,Yt).
The time complexity of the first operation is O(Nc2): for each element of the training set, the pairwise count for each pair yi, yj and unigram count for each yi is calculated. The pairwise counts can be used for calculating joint probabilities. In principle, we need O(|Y|2) space for storing the joint probabilities, but only a small fraction of the possible combinations appear together in practice.
Given a set Yt, the graph Gt is created in O(c2) time. Then, generating k samples from Gt requires a topological sort, for O(kc) (or O(c) per traversal). For training data of size N , the total time complexity is O(Nck). The entire process (building the joint counts and creating graphs and samples) takes less than five minutes for all datasets for our experiments (on an 80-core Intel Xeon Gold 6230 CPU) .
Why should augmenting with permutations help? We show that our method of augmenting permutations to the training data can be interpreted as an instance of variational inference with the order as a latent variable, and TSAMPLE as an instance of a richer proposal distribution. Let πj be the jth order over Yt (out of |Yt|! possible orders Π), and πj(Yt) be the sequence of elements in Yt arranged with order πj . Treating π as a latent random variable, the output distribution can then be recovered by marginalizing over Π: log pθ(Yt | xt) = log ∑ πz∈Π pθ(πz(Yt) | xt), Π:
log pθ(Yt | xt) = log ∑ πz∈Π pθ(Yt, πz | xt) where pθ is the SEQ2SEQ conditional generation model. While summing over Π is intractable, standard techniques from the variational inference framework allow us to write a lower bound (ELBO) on the actual likelihood:
log pθ(Yt | xt) = log ∑ πz∈Π pθ(πz(Yt) | xt) ≥ Eqφ(πz) [ log pθ(πz(Yt) | xt) qφ(πz) ] ︸ ︷︷ ︸
ELBO
= L(θ, φ)
In practice, the optimization procedure draws k samples from the proposal distribution q to optimize a weighted ELBO (Burda et al., 2016; Domke & Sheldon, 2018). Crucially, q can be fixed (e.g., to uniform distribution over the orders), and in such cases only θ are learned (Appendix C).
TSAMPLE can thus be seen as a particular proposal distribution that assigns all the weights to the topological ordering over the label dependence graphs. We also experiment with sampling from a
uniform distribution over the samples (referred to as UNIFORM experiments in our baseline setup). We note that the idea of using an informative proposal distribution over space of structures to do variational inference has also been used in the context of grammar induction (Dyer et al., 2016) and graph generation (Jin et al., 2018; Chen et al., 2021). Our formulation is closest in spirit to Chen et al. (2021). However, in their graph generation setting, the set of nodes to be ordered is already given. In contrast, we infer the order and the set elements jointly from the input.

heading: 3.2 MODELING CARDINALITY
text: Let m = |Yt| be the cardinality of Yt (or the number of elements in Yt). Our goal is to jointly estimate m and Yt (i.e., p(m,Yt | xt)). Additionally, we want the model to use the cardinality information for generating Yt. To this end, we simply add the order information at the beginning of the sequence. That is, we convert a sample (xt,Yt) to (xt, [|Yt|, π(Yt)]), and then train our SEQ2SEQ model as usual from x → [|Yt|, π(Yt)]. As SEQ2SEQ models use autoregressive factorization, listing the order information first ensures that the sequence factorizes as p([|Yt|, π(Yt)] | xt) = p(|Yt| | xt)p(π(Yt) | |Yt|,xt). Thus, the generation of Yt is conditioned on both the input and the cardinality as desired (note the p(π(Yt) | |Yt|,xt) term).
Why should cardinality help? Unlike models like deep sets (Zhang et al., 2019a), SEQ2SEQ models are not restricted by the number of elements generated in the output. However, the information about the number of elements to be generated has two potential benefits: i) it can help avoid over-generation (Welleck et al., 2019; Fu et al., 2021), and ii) unlike free-form text output, the distribution of the set output size (p(|Yt| | xt)) might benefit the model to adhere to the set size constraint. Thus, information on the predicted size can be beneficial for the model to predict the elements to be generated. In the following section, we extensively test our proposed method via a simulated setting and empirical analysis on diverse real-world datasets.
4 EXPERIMENTS
4.1 SIMULATION
We design a simulation to investigate the effects of output order and cardinality on conditional set generation, following prior work that has found simulation to be an effective for studying properties of deep neural networks (Vinyals et al., 2016; Khandelwal et al., 2018).
Data generation We use a graphical model (Figure 3) to generate conditionally dependent pairs (x,Y), with different levels of interdependencies among the labels in Y. Let Y = {y1, y2, . . . , yN} be the label space (i.e., label space ). We sample
a dataset of the form {(x,y)}mi=1. x is an N dimensional multinomial sampled from a dirichlet parameterized by α. The output set y = {y1, y2, . . . , yBk} is created in B blocks, each block of size k and yi ∈ Y. A block is created by first sampling k − 1 labels (yp) independently from Multinomial(x). The kth label (ys) is sampled from either a uniform distribution with a probability = or is deterministically determined from the preceding k − 1 labels. For block size of 1 (k = 1), the output is simply a set of size B sampled from x where all the labels are independent. Similarly, k = 2 simulates a situation with a high degree of dependence: each block is of size 2, with yp sampled independently from the input, and the ys determined deterministically from yp. . Gradually increasing the block size increases the number of independent elements.

heading: 4.1.1 SIMULATION RESULTS
text: We use the architecture of BART-base (Lewis et al., 2020) without pre-training for all simulations2.
2All the simulations were repeated using three different random seeds, and we report the averages.
TSAMPLE leads to higher set overlap and helps across all sampling types: To test our method against UNIFORM, we use perplexity and jaccard coefficient. Jaccard coefficient captures the ability of the model to generate more informative sequences, whereas perplexity measures model’s sensitivity to order. We gradually augment the training data with orders sampled from a uniform distribution over orders (UNIFORM) and TSAMPLE, and evaluate the learning and the final set overlap using training perplexity and Jaccard score, respectively. The results show that augmentations done using TSAMPLE help the model converge faster, and to a lower perplexity (Figure 4 left). TSAMPLE also consistently outperforms UNIFORM across block sizes (Figure 4 right). We observe that the efficacy of TSAMPLE reduces with increasing block size. This can be understood by noting that as the number of independent elements increase, the effect of order on the joint distribution diminishes (proof in Appendix A.3). Further, we found that TSAMPLE is not sensitive to the sampling type: across five different sampling types, including nucleus (Holtzman et al., 2020) and greedy sampling, augmenting with TSAMPLE permutations yields significant gains (Table 5 in Appendix E).
SEQ2SEQ models can learn cardinality and use it for better decoding : We created sample data from Figure 3 where the length of the output is determined by sum of the inputs X . We experimented with and without including cardinality as the first element. We found that training with cardinality increases step overlap by over 15%, from 40.54 to 46.13. Further, the version with cardinality accurately generated sets which had the same length as
the target 70.64% of the times, as opposed to 27.45% for the version without cardinality. A number of other findings, including conditions where order matters the most, effect of randomness and independence on our task are included in Appendix E.

heading: 4.2 REAL-WORLD TASKS
text: To establish the efficacy of our approach in real-world data settings, we experiment with three different multi-label classification tasks (examples in Table 3):
• Go-Emotions classification (GO-EMO, Demszky et al. (2020)): Generating a set of emotions for an input paragraph.
• Open Entity Typing (OPENENT, Choi et al. (2018)): Assigning open types (free-form phrases) to the tagged entities in the input text. Here, the set of possible entity types is open, this task allows us to investigate our method in situations where the label space is not constrained.
• Reuters-21578 (REUTERS, Lewis (1997)): A collection of newswire documents from Reuters, where each article has to be labeled with a set of economic subjects mentioned in it.
We treat all the problems as open-ended generation problems, and do not use any specialized preprocessing. For all the datasets, we filter out samples with a single label. For each training sample, we create n permutations over TSAMPLE to create the training data.
Baselines We experiment with the following four baselines (Table 2):
• BART-MULTI-LABEL: A multi-label classifier where the input is encoded using bart-base, and used to make independent (pointwise) predictions the output labels. This baseline represents the standard method for doing multi-label classification (e.g., Demszky et al. (2020)). During inference, we take top k = [1, 3, 5, 10, 50] labels as the true labels, and report the average (Table 9 shows experiments with bert-base-uncased).
• SET SEARCH: each training sample (x, {y1, y2, . . . , yk}) is converted into k different training examples {(x, yi)}ki=1. During inference, unique elements generated by beam search are returned as the set output. The size of the beam is set to the maximum possible set size in the training data (Table 1). This is a popular approach for one-to-many generation tasks (Hwang et al., 2021).
• SEQ2SEQ: set elements are listed in a random order, and each sample is repeated n times. • UNIFORM: n permutations are uniformly sampled from the possible permutations of labels.
Model We use BART-base (Lewis et al., 2020) with pre-trained weights for all the tasks. We use n = 2 for TSAMPLE and UNIFORM. For all the results, we use three epochs and the same number of training samples. This controls for models trained with augmented data improving only because of factors such as longer training time. All the experiments were repeated for three different random seeds, and we report the averages. We conduct a one-tailed proportion of samples test (Johnson et al., 2000) to compare the best model with SEQ2SEQ (we do not use SET SEARCH for calculating significance) and underscore all results that are significant with p < 0.0005. For Algorithm 1, we experiment with α = {0.5, 1, 1.5} and β = {log2(2), log2(3), log2(4)}, and use the implementation of topological sort provided by networkx (Hagberg et al., 2008) and ignore cycles. We found from our experiments that hyperparameter tuning over α, β did not affect the results in any significant way. For all the experiments reported, we use α = 1 and β = log2(3). We use a single GeForce RTX 2080 Ti for all our experiments. Additional hyperparameter details in Appendix D.
Results Table 2 summarizes the empirical results on the tasks. We report macro precision, recall, and F -measure on individual datasets. We observe that across all the datasets, incorporating cardinality and using TSAMPLE improves the performance significantly. When used with baseline approaches across all the datasets, modeling cardinality as part of the output provides significant performance gains. To complement, our TSAMPLE further improves the performance across datasets. More specifically, we observe that both precision and recall improves, showing the overall efficacy of our approach. TSAMPLE improves over UNIFORM and SEQ2SEQ by about 1% absolute F -score on average. Modeling cardinality provides a consistent performance gain of about 6% for SEQ2SEQ, 6% for UNIFORM, and 8% F -score for TSAMPLE. Overall, we achieve a net gain of 9% absolute F -score by incorporating both informative orders and cardinality.
In further analysis, we observed that the comparatively lower performance of SET SEARCH baseline is due to two specific reasons - repeated generation of the same set of terms (e.g., person, business for OPENENT) and generating elements not present in the test set. We also note that UNIFORM does not improve over SEQ2SEQ consistently (both with and without CARD), showing that merely augmenting with random permutations does not help.

heading: 4.3 ANALYSIS
text: To understand the nature of the label dependencies, we use qualitative examples from the datasets for an in-depth analysis. For this analysis, we selected a random subset of 100 samples from each of the datasets from the validation set. What kinds of permutations does TSAMPLE create? As discussed in Section 3.1, TSAMPLE encourages highly co-occuring pairs (yi, yj) to be in the order yi, yj if p(yj | yi) > p(yi | yj). In our analysis, this dependency in the datasets shows that the orders exhibit a pattern where specific labels appear before the generic ones. For example, in case of entity typing, the more generic entity event is generated after the more specific entities home game and match Figure 4.3 (left).
Increasing the number of permutations (n) We compare TSAMPLE and UNIFORM as n increases from n = 2 to 10. Figure 4.3 (right) shows that both TSAMPLE and UNIFORM improve as n is increased, with TSAMPLE outperforming UNIFORM across n.
Role of cardinality From the results in Table 2, we observe that cardinality is crucial to modeling set output. To study whether the models learn to condition on predicted set length, we compute an agreement score - defined as the % of times the predicted cardinality matches the number of elements generated by the model. We observe that the model effectively predicts the cardinality almost exactly in both GO-EMO and REUTERS datasets (average 95%). While the exact match agreement is low in OPENENT (35%), the model is within an error of ±1 in 93% of the cases.
Reversing the order In order to check our hypothesis of whether only informative orders helping with set generation, we invert the label dependencies returned by TSAMPLE for all the datasets and train with the same model settings. Across all datasets, we observe that reversing the order leads to an average of 12% drop in F -score. The reversed order not only closes the gap between TSAMPLE and UNIFORM, but in many instances, the performance is slightly worse than UNIFORM.

heading: 5 CONCLUSION
text: We present a novel method for performing conditional set generation using SEQ2SEQ models that leverages both incorporating informative orders and adding cardinality information. Experiments in simulated settings and real-world datasets show that our method is more effective than strong baselines at set generation. We also present an in-depth analysis of our method along with the empirical results. In the future, we want to extend this work to explore better proposal distributions and to incorporate cardinality information in open-ended generation tasks like dialogue.
ETHICS AND REPRODUCIBILITY STATEMENT
We take the following steps for reproducibility of our results:
1. All the experiments are performed for three different random seeds. In addition, we conduct a proportion of samples hypothesis test to establish the statistical significance of our results. We did not perform extensive hyperparameter tuning and used the same set of defaults for baselines and our proposed method.
2. For all data augmentation experiments, we match the number of training samples and epochs; all the models are trained for the same duration. This alleviates the concern that the models perform well with augmented data merely because of the longer training time.
3. We conduct a proportion of samples test for all the experiments conducted on real-world datasets and use a small p = 0.0005 to measure highly significant results, which are indicated with an underscore.
Our work aims to promote the usage of existing resources for as many use cases as possible. In particular, all our experiments are performed on the BASE-version of the model (BART) that can relatively lower parameter count to conserve resources and help lower our impact on climate change.
We propose a method to use existing pre-trained language models more efficiently for set generation. Our downstream datasets in this work do not contain any societally impactful or social themes. Hence, we do not anticipate any misuse as-is. To the best of our knowledge, we did not encounter any downstream tasks that can leverage our method for any negative impact. Despite that, it is certainly possible we might have missed something, and we are happy to engage anonymously with the reviewers, and the chairs and help address the concerns that may arise.

heading: A PROOFS
text: Let Y be the output space, yi, yj , yk ∈ Y, and yk ∈ Y−yi−yj be a subset of the symbols excluding yi, yj . We assume that all the distributions are non-negative (i.e., p(y) > 0,∀y ∈ Y)
Lemma A.1 yi 6⊥⊥ yj =⇒ yi 6⊥⊥ (yjyk)
Proof Let yi ⊥⊥ (yjyk) by contradiction. Then: p(yi, yjyk) = p(yi)p(yjyk) (2) Also,
p(yi, yj) = ∑
yk∈Z
p(yi, yjyk)
= ∑
yk∈Z
p(yi)p(yjyk) (equation 2)
= p(yi) ∑
yk∈Z
p(yjyk)
= p(yi)p(yj) (3)
However, yi 6⊥⊥ y thus yi 6⊥⊥ y =⇒ yi 6⊥⊥ (yjyk).
Lemma A.2 p(yi | yj) > p(yj | yi) =⇒ p(yi | yj ,yk) > p(yj | yi,yk) if yi, yj ⊥⊥ yk
Proof We have: p(yi | yj) > p(yj | yi)
=⇒ p(yj) < p(yi) (4)
p(yj ,yk) = p(yk | yj)p(yj) < p(yk | yj)p(yi) (Equation 4) = p(yk | yi)p(yi) (yi, yj ⊥⊥ yk =⇒ p(yk | yj) = p(yk | yi) = p(yk)) = p(yi,yk) (5)
Thus,
p(yi | yj ,yk) = p(yi, yj ,yk) p(yj ,yk)
> p(yi, yj ,yk) p(yi,yk) = p(yj | yi,yk) (6)
Lemma A.3 If yi ⊥⊥ yj ∀yi, yj ∈ Y, the order is guaranteed to not affect learning.
Proof Let πj be the jth order over Y (out of |Y|! possible orders Π), and πj(Y) be the sequence of elements in Y arranged with πj .
p(yi | yj) = p(yi) (yi ⊥⊥ yj ∀yi, yj) =⇒ p(yi, yj , yk) = p(yi)p(yj | yi)p(yk | yi, yj)
= p(yi)p(yj)p(yk)
=⇒ p(πm(yi, yj , yk)) = p(πn(yi, yj , yk)) ∀πm, πm ∈ Π In other words, when all elements are mutually independent, all possible joint factorizations will simply be a product of the marginals, and thus identical.
Lemma A.4 The graphs constructed to sample orders for TSAMPLE cannot have cycles.
Proof Let yi, yj , yk form a cycle: yi → yj → yk → yi. By construction, the following conditions must hold for such a cycle to be present:
log p(yj | yi)− log p(yi | yj) > β =⇒ log p(yi) < log p(yj) log p(yk | yj)− log p(yj | yk) > β =⇒ log p(yj) < log p(yk) log p(yi | yk)− log p(yk | yi) > β =⇒ log p(yk) < log p(yi)
Putting the three implications together, we get log p(yi) < log p(yj) < log p(yk) < log p(yi), which is a contradiction. Hence, the graphs constructed for TSAMPLE cannot have a cycle.

heading: C FIXING THE PROPOSAL DISTRIBUTION IN THE VAE FORMULATION
text: log pθ(Y | x) = log ∑ πz∈Π pθ(πz(Y) | x)
= log ∑ πz∈Π qφ(πz) qφ(πz) pθ(πz(Y) | x)
= logEqφ(πz) [ pθ(πz(Y) | x)
qφ(πz) ] ≥ Eqφ(πz) [log pθ(Y, πz | x)]− Eqφ(πz) [log qφ(πz)]
log pθ(Y | x) = log ∑ πz∈Π pθ(πz(Y) | x) ≥ Eqφ(πz) [ log pθ(πz(Y) | x) qφ(πz) ] ︸ ︷︷ ︸
ELBO
= L(θ, φ)
(7)
Where equation 7 is the evidence lower bound (ELBO). The success of this formulation depends on the quality of the proposal distribution q from which the orders are drawn. When q is fixed (e.g., to uniform distribution over the orders), learning only happens for θ. This can be clearly seen from splitting Equation 7 into terms that involve just θ and φ:
∇φL(θ, φ) = 0 ∇θL(θ, φ) = ∇θEqφ(πz) [log pθ(Y, πz | x)]

heading: D HYPERPARAMETERS
text: We list all the hyperparameters in Table 4.

heading: E EXPLORING THE INFLUENCE OF ORDER ON SEQ2SEQ MODELS WITH A SIMULATION
text: We design a simulation to investigate the effects of output order and cardinality on conditional set generation, following prior work that has found simulation to be an effective for studying properties of deep neural networks (Vinyals et al., 2016; Khandelwal et al., 2018).
Data generation We use a graphical model (Figure 3) to generate conditionally dependent pairs (x,Y), with different levels of interdependencies among the labels in Y. Let Y = {y1, y2, . . . , yN} be the set of output labels. We sample a dataset of the form {(x,y)}mi=1. x is an N dimensional multinomial sampled from a dirichlet parameterized by α, and y is a sequence of symbols with each yi ∈ Y. The output sequence y is created in B blocks, each block of size k. A block is created by first sampling k − 1 prefix symbols independently from Multinomial(x), denoted by yp The kth suffix symbol (ys) is sampled from either a uniform distribution with a probability = or is deterministically determined from the preceding k− 1 prefix terms. For block size of 1 (k = 1), the output is simply a set of size B sampled from x (i.e., all the elements are independent). Similarly, k = 2 simulates a situation with a high degree of dependence: each block is of size 2, with the prefix sampled independently from the input, and the suffix determined deterministically from the prefix. Gradually increasing the block size increases the number of independent elements.
Dir(α) X yp ys
k-1
B
M
Figure 6: The generative process for simulation
Figure 7: Perplexity vs. Randomness for varying block sizes
E.1 MAJOR FINDINGS
We now outline our findings from the simulation. We use the architecture of BART-base Lewis et al. (2020) (six-layers of encoder and decoder) without pre-training for all simulations. All the simulations were repeated using three different random seeds, and we report the averages.
Finding 1: SEQ2SEQ models are sensitive to order, but only if the labels are conditionally dependent on each other. We train with the prefix yp listed in the lexicographic order. At test time, the order of is randomized from 0% (same order as training) to 100 (appendixly shuffled). As can be seen from Figure 7 the perplexity gradually increases with the degree of randomness. Further, note that perplexity is an artifact of the model and is independent of the sampling strategy used, showing that order affects learning.
Finding 2: Training with random orders makes the model less sensitive to order As Figure 8 shows, augmenting with random order makes the model less sensitive to order. Further, augmenting with random order keeps helping as the perplexity gradually falls, and the drop shows no signs of flattening.
Finding 3: Effects of position embeddings can be overcome by augmenting with a sufficient number of random samples Figure 8 shows that while disabling position embedding helps the baseline, similar effects are soon achieved by increasing the random order. This shows that disabling position embeddings can indeed alleviate some concerns about the order. This is crucial for pretrained models, for which position embeddings cannot be ignored.
Finding 4: TSAMPLE leads to higher set overlap We next consider blocks of order 2 where the prefix symbol yp is selected randomly as before, but the suffix is set to a special character y ′ p with 50% probability. As the special symbol y′p only occurs with yp, there is a high pmi between each (yp, y ′ p) pair as p(yp | y′p) = 1. Different from finding 1, the output symbols are now shuffled to mimic a realistic setup. We gradually augment the training data with random and topological orders and evaluate the learning and the final set overlap using training perplexity and Jaccard score, respectively. The results are shown in Figure 9. Similar trends hold for larger block sizes, and the results are included in the Appendix in the interest of space.
Finding 5: TSAMPLE helps across all sampling types We see from Table 5 that our approach is not sensitive to the sampling type used. Across five different sampling types, augmenting with topological orders yields significant gains.
Finding 6: SEQ2SEQ models can learn cardinality and use it for better decoding We created sample data from Figure 6 where the length of the output is determined by sum of the inputs X . We experimented with and without including cardinality as the first element. We found that training with cardinality increases step overlap by over 13%, from 40.54 to 46.13. Further, the version with cardinality accurately generated sets which had the same length as the target 70.64% of the times, as opposed to 27.45% for the version without cardinality.

heading: F ADDITIONAL RESULTS
text: We present all the results for the three tasks in Tables 6, 7, and 8.
F.1 CLASSIFICATION RESULTS WITH BERT
Table 9 includes results from a multi-label classification baseline where bert-base-uncased is used as the encoder.

heading: G SAMPLE GRAPHS
text: In this section, we present examples from REUTERS and GO-EMO datasets to further understand the permutations generated by our method. What kinds of permutations does TSAMPLE create? As discussed in Section 3.1, TSAMPLE encourages highly co-occuring pairs (yi, yj) to be in the order yi, yj if p(yj | yi) > p(yi | yj). In our analysis, this dependency in the datasets shows that the orders exhibit a pattern where specific labels appear before the generic ones. For example, in case of entity typing, the more generic entity event is generated after the more specific entities home game and match Figure 4.3 (left).

Review summaries:
The paper proposes an approach to set-generation within a seq2seq framework. The authors propose to train a standard seq2seq model by ordering the discrete elements in the target sets (as a sequence) under a partial order defined by taking $y_i < y_j$ if both $y_i$ and $y_j$ have sufficiently high PMI and $p(y_i | y_j)$ is sufficiently larger than $p(y_j | y_i)$. In particular, the authors sample from orderings consistent with this partial order during training. The authors show that this approach improves over baseline seq2seq approaches for set generation on synthetic and NLP tasks, and also that prepending the cardinality of the set to be predicted to the target sequence is generally helpful.

In this paper, the authors proposed a data augmentation approach to improve the conditional set generation task. The topology sort is used to recovers the informative orders of labels, and set cardinality is added to the target sequence. The authors conducted experiments on simulated data and three NLP data sets to demonstrate the effectiveness of the method.

This paper explores the task of conditional set generation using sequence generation models. The authors propose to model order-invariance and set cardinality into the seq2seq models. Additionally, the authors introduce a novel data augmentation approach based on topological sorting. The proposed model is shown to improve performance when compared to seq2seq baselines on three different datasets.