L ex S ym: Compositionality as Lexical Symmetry (2023)

Abstract: In tasks like semantic parsing, instruction following, and question answering, standard deep networks fail to generalize compositionally from small datasets. Many existing approaches overcome this limitation with model architectures that enforce a compositional process of sentence interpretation. In this paper, we present a domain-general and model-agnostic formulation of compositionality as a constraint on symmetries of data distributions rather than models. Informally, we prove that whenever a task can be solved by a compositional model, there is a corresponding data augmentation scheme — a procedure for transforming examples into other well-formed examples — that imparts compositional inductive bias on any model trained to solve the same task. We describe a procedure called LexSym that discovers these transformations automatically, then applies them to training data for ordinary neural sequence models. Unlike existing compositional data augmentation procedures, LexSym can be deployed agnostically across text, structured data, and even images. It matches or surpasses state-of-the-art, task-specific models on COGS semantic parsing, SCAN and Alchemy instruction following, and CLEVR-CoGenT visual question answering datasets.

## introduction a central challenge in natural language processing is the design of models and learning algorithms that are simultaneously flexible enough to capture the variability of human language and structured enough to generalize in predictable and humanlike ways. one important source of structure is the principle of compositionality, which (in one formulation) states that sentence meanings can be computed from a lexicon of word meanings and a set of composition rules governing how meanings combine @xcite . a long line of language processing research has operationalized the principle of compositionality as a constraint on model architectures, via independence assumptions or parameter tying schemes that ensure a compositional process of sentence interpretation @xcite . compositional models enjoy sample-efficient learning and strong generalization in tasks from machine translation to question answering @xcite . but much of human language is not (or at least not straightforwardly) compositional. idioms, disfluencies, and context-sensitive meanings present major challenges to models in which all predictions must derive from a sequence of local composition operations. in recent years, more generic model architectures such as recurrent neural networks (rnns) and transformers, with no explicit compositional scaffolding, have consistently outperformed compositional models in language processing tasks with natural data @xcite . however, these models capture linguistic regularities only when trained on enormous amounts of data, and make surprising or problematic predictions when presented with novel word collocations or syntactic structures @xcite . how can we train unstructured neural sequence models that generalize compositionally? recent work has introduced several compositional data augmentation schemes: rule-based procedures or learned models that synthesize artificial training examples to promote generalization @xcite @xcite . while often effective, existing methods are specialized to specific data modalities or datasets. the conditions under which they succeed, and their relationships to the formal principle of compositionality, have remained unclear. this paper presents a framework for understanding and improving such data-centric approaches to compositional modeling. we first provide a mathematical characterization of the principle of compositionality as a constraint on data distributions rather than model architectures. intuitively, we show that whenever a language understanding task can be solved compositionally, that task's data distribution is guaranteed to exhibit specific symmetries. these symmetries are functions that modify data points while preserving semantic acceptability. fig. 1c gives an example of a symmetry in a visual question answering problem: in any wellformed (image, question, answer) triple, swapping the words yellow and green and their associated pixel values yields a valid new triple. such symmetries exist even in complex tasks like instruction following (fig. 1a ), where they may depend not only on word-to-meaning mappings but relations between meanings (like the fact that red and green mix to produce brown). building on this formal link between compositionality and symmetry, we introduce a procedure called lexsym that discovers symmetries automatically, then uses them to synthesize new training examples guaranteed to be correct and informative. crucially, lexsym does not require a complete compositional theory for a given problem domain-only a lexicon of word meanings. these lexicons may themselves be automatically derived for most tasks. this makes lexsym very flexible: it requires little or no task-specific engineering, can be combined with any predictor, and unlike other compositional data augmentation schemes does not require tree-structured or even sequential data. applied to ordinary neural sequence models, lexsym outperforms state-of-the-art models on the clevr cogent visual question answering benchmark @xcite by a wide margin. lexsym is general, and matches or outperforms some specialized data augmentation schemes and models on the cogs semantic parsing task @xcite , and the scan and alchemy instruction following tasks @xcite . this paper thus offers two contributions: a theoretical contribution, in the form of a new lens on the principle of compositionality via symmetries of data distributions; and an empirical contribution, in the form of a data augmentation scheme that improves generalization on diverse language understanding tasks. the recent success of data augmentation approaches highlight the fact that compositional inductive bias need not require compositional models. our work formalizes and generalizes this "data-centric" account of compositionality. foot_0 ## background & approach we begin with a discussion on the more general role of symmetry in machine learning applications. that is, applying f to each element of x leaves x unchanged. a familiar example from computer vision is reflection symmetry: in object recognition problems, image classes are generally invariant under reflection (a zebra seen in a mirror is still a zebra). the set of (image, class) pairs thus has as a symmetry the function (x, y) → (reflect(x), y). in many domains, especially those (like computer vision and computational chemistry) that are constrained by physical laws, knowledge of the symmetries exhibited by a problem domain can dramatically reduce the difficulty of learning @xcite . past work has incorporated symmetry into machine learning problems in two ways. invariant and equivariant modeling approaches structurally enforce symmetries via specialized architectures (improving generalization by decreasing the size of the hypothesis class; @xcite . data augmentation approaches generate new training examples by applying known symmetries like reflections directly to training data (improving generalization by increasing dataset size; @xcite . data augmentation, the focus of this paper, is model-agnostic, and can be used in conjunction with pre-training while producing the same asymptotic effects as specialized model architectures @xcite . the question this paper aims to answer is whether compositionality, like other domainspecific constraints, can be formalized in the language of symmetry. we are not the first to consider this question: @xcite define a theory of semantic equivalence in terms of symmetries of the set of natural language sentences, and @xcite propose a model architecture for compositional semantic parsing via a symmetry that enforces permutation invariance of lexicon entries. lexsym also derives symmetries from lexicons. it builds on past work by (1) characterizing the algebraic relationship between compositionality and symmetry, explaining the effectiveness of both @xcite 's approach as well as other data augmentation schemes based on token and phrase substitution @xcite ; (2) discovering symmetries automatically, and (3) showing how to leverage them in a model-and modality-agnostic way. additional related work is discussed in sec. 6. ## compositionality as lexical symmetry our main theoretical result, and the foundation of our modeling approach, can be stated as follows: in any language understanding task that can be modeled compositionally, data for the task exhibits symmetries in the sense of definition 1. we explain, formalize, and prove this statement below. we consider tasks defined by a space of possible examples x , of which a subset of examples x are well-formed. we assume each example @xmath0, . . . , x n ], with x i drawn from a vocabulary σ. finally, we assume that well-formedness can be computed by a a binary interpretation function i : @xmath1, 1} with i(x) = 1 iff @xmath2. a wide variety of language understanding problems, from very simple to very complex, may be defined in this way: example 1a: arithmetic language modeling. examples x are true sentences of the form a plus b is c, where a, b and c are numbers: i(one plus two is three) = 1 but i(two plus two is five) = 0. example 1b: semantic parsing. examples x are pairs (x nl , x lf ), where x nl is an sentence, x lf is a logical form, and i(x nl , x lf ) = 1 iff x lf represents a possible meaning of x nl (fig. 1b ). ## lexsym: data augmentation with l l l-homomorphisms given a lexicon describing symbols and their relations, we have shown how to turn homomorphisms of the lexicon into transformations of a dataset. each such function f that takes an example x as input, replaces each token x @xmath3, and returns a well-formed example x ′ as output. every l-homomorphism may thus be viewed as a recipe for synthesizing training examples from a small initial training set @xcite . however, to make this a practical modeling tool, we need some way of constucting l-homomorphisms for a task of interest. below, we describe how to do so automatically: first, starting with only a taskspecific lexicon l (sec. 4.1); next, starting with only a dataset and no initial lexicon (sec. 4.2). we term the resulting approach lexsym. ## experiments our experiments aim to evaluate whether lexsym can improve compositional generalization in downstream models. the main goal of these experiments is to evaluate generality across tasks and data modalities. evaluation focuses on three diverse classes of language understanding problems: complex, context-dependent computations (sec. 5.1), large, automatically derived lexicons (sec. 5.2), and multi-modal data (sec. 5.3). ## limitations and future directions while sec. 3 characterizes the effect of general lhomomorphisms, lexsym specifically produces single-token swaps. in images represented as discrete symbol sequences, if a single symbol simultaneously encodes multiple visual features (e.g. color and texture), these features will remain entangled in synthesized examples. it will not exchange substructures larger than a single token, and thus will not synthesize examples longer than those already present in the training set @xcite . this is because lexsym targets compositionality but not recursion, which is also required to model the full range of human-like generalizations in sequence learning problems. lexsym is also sensitive to the nature of the tokenization scheme itself. in morphologically rich languages, for example, lexsym may need to be applied not on top of words or segments, but instead canonicalized morphemes produced by learned morphological analyzers @xcite @xcite (analogous to the use of learned image patch representations rather than pixels in our vqa experiments). finally, lexsym does not induce some of the generalizations obtained other methods for improv-ing compositional generalization, especially those that exploit extra structure (e.g. tree-shaped inputs and outputs) in the semantic parsing domain (e.g. @xcite . it might serve as a platform for future versions of those methods that offer greater generality and formal guarantees. ## conclusion we have presented lexsym, a new data augmentation method that improves compositional generalization of neural models in multiple domains. lexsym is derived from a characterization of the principle of compositionality as a constraint on the symmetries of data distributions, and a procedure for automatically identifying these symmetries using token-level alignments. our results highlight the fact that many inductive biases targeted by specialized models in nlp can be alternatively, and often more flexibly, expressed as a hypothesis about the structure of the distribution to be modeled.