Structurally Diverse Sampling for Sample-Efficient Training and Comprehensive Evaluation (2022)

Abstract: A growing body of research has demonstrated the inability of NLP models to generalize compositionally and has tried to alleviate it through specialized architectures, training schemes, and data augmentation, among other approaches. In this work, we study a different approach: training on instances with diverse structures. We propose a model-agnostic algorithm for subsampling such sets of instances from a labeled instance pool with structured outputs. Evaluating on both compositional template splits and traditional IID splits of 5 semantic parsing datasets of varying complexity, we show that structurally diverse training using our algorithm leads to comparable or better generalization than prior algorithms in 9 out of 10 dataset-split type pairs. In general, we find structural diversity to consistently improve sample efficiency compared to random train sets. Moreover, we show that structurally diverse sampling yields comprehensive test sets that are a lot more challenging than IID test sets. Finally, we provide two explanations for improved generalization from diverse train sets: 1) improved coverage of output substructures, and 2) a reduction in spurious correlations between these substructures.

## introduction systematic compositionality-expressing novel complex concepts as systematic compositions of expressions for simpler concepts-is the property underlying human languages' expressive power @xcite . however, nlp models struggle to generalize to novel composite expressions in the context of semantic parsing (lake and @xcite @xcite . data augmentation has been extensively explored for compositional generalization @xcite @xcite @xcite . however, instances in semantic parsing possess structure, such as abstract syntax trees (asts) of target programs (figure 1 ). randomly selecting instances from a grammar, or even from human annotators, while ignoring similarity in their structure is likely to produce skewed distributions with spurious correlations between substructures. this task ambiguity and underspecification are known to cause overparameterized models to have high variance and poor generalization @xcite . in contrast, a structurally diverse set of instances containing a variety of structures should better cover the combinatorial space of structures and yield more sample-efficient train sets. moreover, this improved coverage should yield more comprehensive test sets than the traditional iid test sets. prior work on diverse sampling has shown improved sample efficiency in compositional (non-iid) splits, by selecting instances to have diverse program templates @xcite or ast bigrams @xcite (see figure 1 for examples). however, for reasonably-sized programs, templates are very large structures, and bigrams very small; focusing on either does not necessarily improve diversity across a range of differently-sized structures. moreover, there is little evidence of sample efficiency of diverse train sets in the iid setting and no exploration of diverse test sets. in this study, we take a broader look at the advantages of structural diversity. we propose a general, substructure, and model-agnostic recipe for structurally diverse subsampling algorithms that interleaves selecting unseen substructures with selecting instances containing those substructures. experimenting with different substructure and instance selection criteria, we show improved performance from 1) prioritizing the selection of more frequent unseen substructures in the training pool, 2) using subtrees 1 as substructures that are neither too granular (bigrams) nor too large (templates), and 3) simultaneously diversifying over both small (subtree) and larger (template) substructures. we evaluate on template and iid splits of five semantic parsing datasets of varying complexities and find that training on diverse train sets consistently outperforms random train sets. in particular, our proposed subtree diversity algorithm is the most consistent, performing comparably with or better than the template and bigram diversity in 9 out of 10 splits, with both bigram and template algorithms often performing worse than random subsampling in iid splits. we study the efficacy of diversely sampled test sets and show that our diverse sampling algorithm yields test sets that are harder and more comprehensive than iid tests, especially with iid training sets. finally, by comparing random and structurally diverse subsamples, we show that the latter 1) better cover the space of substructures, especially those in the long tail, and 2) have weaker spurious correlations between substructures, explaining their benefits in training and evaluation. to conclude, our results demonstrate the effectiveness of structurally diverse train sets in inducing generalization and of structurally diverse test sets as comprehensive evaluations. we hope these insights will encourage the use of structural diversity as a criterion when sampling train or test sets from a pool of labeled instances. a setting where we expect our algorithm will be particularly useful is that of prototyping semantic parsers in zero-data settings, where a pool of programs is sampled from a grammar and mapped to canonical utterances (wang et al., 2015; herzig and berant, 1 these could also be called subgraphs but we'll stick to "subtree" as the whole structures are trees. 2019; @xcite ). another potential application could be in exemplar selection for in-context learning. our code, data, and models are available at https://github.com/ shivanshu-gupta/structural-diversity . ## setup semantic parsing, the task we focus on, involves parsing an utterance x into a program or logical form y. following @xcite and @xcite , we will assume access to a pool of instances d @xmath0, . . . , e n }, where e @xmath1, y i ), from which we wish to sample instances. as the example in figure 1 shows, logical forms possess hierarchical structure which can be represented as trees called abstract syntax trees (asts). these structures are composed of smaller substructures such as subtrees of the ast, that are shared across logical forms. we can thus view each instance as a bag of output substructures: c(e i ) = c(x i , y i ) = c(y i ) = {c {i} 1 , . . . , c {i} m } ⊆ c, where c is the mapping from instances to their substructures and c is the set of all unique substructures. the goal of structurally-diverse sampling is to select instances that contain among them a variety of different substructures. our hypotheses, that we verify in §6, are that a collection of such instances would both better cover the combinatorial space of structures and reduce spurious correlations between substructures compared to random instances. a structurally diverse train set should thus give the model more information about the system underlying the instances' structure and hence improve generalization. similarly, its improved coverage should also make a structurally diverse test set more comprehensive. this is analogous to how one would choose to evaluate on a test set with balanced classes even when the training data might have a considerable imbalance. ## experiments given a dataset d of utterance-program pairs, we create three different types of splits with each split consisting of a training pool d pool and test set d test . we then compare the various subsampling algorithms described in §3 by using them to sample training sets d train of varying budget size b from d pool and evaluating on d test . ## analysis having seen that structurally diverse datasets improve generalization, we now investigate why they do so. in §2 we hypothesize that structural diversity has two benefits over random sampling: (1) improved coverage of the space of substructures, and (2) reduced spurious correlations. we now evaluate whether this is indeed the case. we will view each instance as the set of subtrees contained in it, i.e., e i ⊂ c where c is the set of all subtrees in the dataset. we define the frequency of a subtree, s, in a set of instances a as the number of instances containing it, i.e. f a (s) = |{@xmath2: @xmath3. the frequency of a pair of subtrees, s i , s j , is analogously defined as f a (s i , s j ) = |{s i , s @xmath4: @xmath5. the rank of a subtree in a is defined as its position in a list of all subtrees descending in frequency, with equally-frequent subtrees assigned the average of their ranks. ## conclusion in this work, we studied the benefits of structural diversity for the task of semantic parsing. we proposed a novel model-agnostic algorithm for sampling structurally diverse instances by diversifying over subtrees in program asts. evaluating on multiple datasets with varying complexities and on both iid and compositional splits, we demonstrated that diversity almost always, and often significantly, improves generalization. we further demonstrated that structural diversity also yields more comprehensive test sets than traditional iid test sets. finally, we showed that these benefits of structural diversity are likely a manifestation of improved coverage of the long-tail of substructures as well as a reduction in spurious correlations between them. we hope that our results demonstrating the importance of structural diversity will encourage future research on better structurally diverse sampling algorithms as well as their use to guide train and test set construction. the algorithms in this work are applicable whenever a large pool of possible output programs is available. one such setting is of prototyping a semantic parser in a zero-data setting where a pool of outputs can be sampled from a grammar and mapped to canonical utterances that can subsequently be paraphrased for linguistic variation either manually or automatically @xcite . another scenario is that of selecting instances for in-context or fewshot learning @xcite . perhaps more importantly, our results indicate that the failure of nlp models on compositional generalization may be due in part to the lack of diversity in them, suggesting the need to create more diverse benchmarks.