  Conditional set generation learns a mapping from an input sequence of tokens
to a set. Several NLP tasks, such as entity typing and dialogue emotion
tagging, are instances of set generation. Seq2Seq models, a popular choice for
set generation, treat a set as a sequence and do not fully leverage its key
properties, namely order-invariance and cardinality. We propose a novel
algorithm for effectively sampling informative orders over the combinatorial
space of label orders. We jointly model the set cardinality and output by
prepending the set size and taking advantage of the autoregressive
factorization used by Seq2Seq models. Our method is a model-independent data
augmentation approach that endows any Seq2Seq model with the signals of
order-invariance and cardinality. Training a Seq2Seq model on this augmented
data (without any additional annotations) gets an average relative improvement
of 20% on four benchmark datasets across various models: BART, T5, and GPT-3.
Code to use SETAUG available at: https://setgen.structgen.com.
