PaperlayerView exact revision on arXiv

Source-linked AI summary

Compositionality decomposed: how do neural networks generalise?

Dieuwke Hupkes, Verna Dankers, Mathijs Mul, Elia Bruni

arXiv:1908.08351v2cs.CLcs.AIcs.LGstat.ML

TL;DR

Neural networks’ compositional generalisation remains unsettled partly because compositionality lacks an agreed definition and evaluation method. The paper proposes five theory-grounded tests and applies them to PCFG SET and three sequence-to-sequence architectures, finding weak generalisation to unseen word combinations and sequence lengths.

  • Problem

    Whether neural networks generalise compositionally remains unresolved because researchers disagree about what compositionality means and how to test it.

  • Method

    The paper develops five theoretically motivated, task-independent tests and applies them to PCFG SET and recurrent, convolutional, and transformer sequence-to-sequence models.

  • Results

    Systematicity scores fell 33%, 34%, and 22% below overall accuracy for LSTMS2S, ConvS2S, and Transformer, while no architecture showed strong generalisation to unseen sequence lengths.

  • Takeaways & Limitations

    Compositionality evaluation should examine multiple theoretically distinct abilities rather than rely on accuracy from a single downstream task.

  • Takeaways & Limitations

    The evaluation covers several but not all aspects of compositionality and is therefore presented as a stepping stone rather than an endpoint.

Abstract

from arXiv · show

Despite a multitude of empirical studies, little consensus exists on whether neural networks are able to generalise compositionally, a controversy that, in part, stems from a lack of agreement about what it means for a neural model to be compositional. As a response to this controversy, we present a set of tests that provide a bridge between, on the one hand, the vast amount of linguistic and philosophical theory about compositionality of language and, on the other, the successful neural models of language. We collect different interpretations of compositionality and translate them into five theoretically grounded tests for models that are formulated on a task-independent level. In particular, we provide tests to investigate (i) if models systematically recombine known parts and rules (ii) if models can extend their predictions beyond the length they have seen in the training data (iii) if models' composition operations are local or global (iv) if models' predictions are robust to synonym substitutions and (v) if models favour rules or exceptions during training. To demonstrate the usefulness of this evaluation paradigm, we instantiate these five tests on a highly compositional data set which we dub PCFG SET and apply the resulting tests to three popular sequence-to-sequence models: a recurrent, a convolution-based and a transformer model. We provide an in-depth analysis of the results, which uncover the strengths and weaknesses of these three architectures and point to potential areas of improvement.

1. Introduction

The paper addresses the unresolved question of whether neural networks generalise compositionally by translating different interpretations of compositionality into a task-independent evaluation suite. It demonstrates the suite on PCFG SET using recurrent, convolution-based, and transformer sequence-to-sequence models.

  • Evaluation framework: The evaluation suite is intended to assess whether neural composition functions are appropriate beyond standard representation usefulness, scalability, sample efficiency, and computational-feasibility evaluations.The introduction motivates explicit assessment of the composition functions implemented by different model types.
  • Motivation: Empirical studies have not resolved whether neural networks learn and behave compositionally, partly because researchers interpret compositionality differently.The principle that a whole’s meaning depends on its parts and their syntactic combination has broad support but lacks consensus about its practical interpretation.
  • Contribution: The authors connect theories of compositionality from symbolic language models and semantic composition with effective neural language models without proposing a new definition.Instead, they identify different interpretations and turn them into tests for neural models.
  • Demonstration: The tests are applied to recurrent, convolution-based, and transformer sequence-to-sequence models to uncover strengths and weaknesses across the three architectures.The study also raises whether explicit compositionality is necessary for modelling data with compositional underlying structure.

2. Related work

Related work evaluates neural compositionality through both specially designed grammatical datasets and analyses of models trained on uncontrolled data, but neither approach fully resolves what compositionality models learn. The review therefore frames compositional generalisation and hierarchy as important yet open questions requiring clearer theoretical links between tests and compositionality.

  • Neural compositionality and hierarchy: Research on neural compositionality has expanded substantially, especially around whether models represent hierarchy and trees.The topic has been studied since early connectionist models for natural language and has recently regained attention.
  • Artificial compositional datasets: Grammar-generated datasets assume that models reach the test-set solution only by interpreting training data compositionally.The paper reviews datasets built around this assumption, including arithmetic, mathematical question-answering, SCAN, lookup-table composition, and logical entailment tasks.
  • Artificial compositional datasets: Results across artificial datasets are mixed: transformers can outperform LSTMs on several extrapolation tests, while models often struggle with intermediate computations or compositional splits.Other studies find compositional behaviour in only a very small fraction of models, whereas recursive or recurrent architectures can perform well under particular task designs.
  • Naturalistic model analyses: A second research strand probes syntactic or representational properties in models trained on independent, uncontrolled data, including long-distance agreement and machine-translation representations.These studies address aspects related to compositionality but do not directly establish how compositional the learned representations are.
  • Limitations of existing approaches: The review concludes that task-based datasets lack explicit links to clearly defined notions of compositionality, whereas naturalistic evaluations lose the direct connection between compositionality and downstream success.Because compositionality is multifaceted and its necessary role in natural-language tasks is unknown, whether neural networks learn compositionally remains unresolved.

3. Testing compositionality · 3.1 Systematicity · 3.2 Productivity

The paper grounds five task-independent tests in theories of compositionality, focusing here on systematicity and productivity. Systematicity tests recombination of unseen constituent combinations, while productivity tests understanding sequences longer than those seen during training.

  • 3. Testing compositionality: The framework translates interpretations of compositionality into five tests: systematicity, productivity, substitutivity, localism, and overgeneralisation.These tests examine recombination, length generalisation, synonym robustness, locality of composition operations, and preference for rules or exceptions.
  • 3.1 Systematicity: Systematicity concerns whether models recombine known constituents and rules to understand or produce new complex expressions.The property is defined through connections between abilities involving related sentences and contrasts with storing every sentence as an atomic mapping.
  • 3.1 Systematicity: Systematicity generalisation also raises whether the model’s recombination rules and constituents match those underlying the relevant data set or language.A model that generalises outside its training space should construct outputs from parts perceived during training and a recombination rule.
  • 3.1.1 Testing systematicity: The paper evaluates systematicity by testing combinations of words a and b that were not seen together during training but are plausible in the corpus.The model is familiarised with a without b and with b without a before being evaluated on the combination a b.
  • 3.2 Productivity: Productivity concerns the open-ended generation of new sentences from finite stored resources because natural language appears infinite.Both systematicity and productivity recombine known constituents, but productivity’s infinitude cannot be empirically proven.
  • 3.2.1 Testing productivity: The productivity test isolates unboundedness by asking whether models understand sentences longer than those encountered during training.Sequences are separated by length, and models trained on shorter sequences are evaluated on longer ones.

3.3 Substitutivity · 3.4 Localism · 3.5 Overgeneralisation

Sections 3.3–3.5 operationalise compositionality through tests of synonym substitution, local versus global composition, and models’ treatment of exceptions. Together, these tests examine how models map parts and rules to meanings and when they generalise beyond observed cases.

  • 3.3 Substitutivity: The substitutivity principle is qualified because synonymous expressions can produce nonsensical substitutions across semantic categories or embedded belief contexts.The paper excludes belief-embedding cases and focuses on when substitutivity is salient for neural networks.
  • 3.3 Substitutivity: Substitutivity asks whether replacing an atomic unit with an artificially introduced synonym preserves the model’s prediction.The test compares prediction changes under synonym replacement, including cases where synonymous words occur equally often in comparable contexts.
  • 3.4 Localism: Localism tests whether a model assigns the same meaning to a sequence alone and inside a larger compound.The broader compositionality principle is formally vacuous without constraints on admissible combination, motivating explicit local-versus-global analysis.
  • 3.4 Localism: The localism procedure compares processing a composed sequence X from parts A and B with separately processing A and B before combining their outputs.This comparison distinguishes local composition operations from operations that depend on the larger compound.
  • 3.5 Overgeneralisation: Overgeneralisation occurs when a learner applies a general rule to a case that forms an exception to that rule.The paper relates such errors to evidence for symbolic rules in human language acquisition.
  • 3.5 Overgeneralisation: The paper treats applying a rule where the data contradict it as evidence that a model internalised the rule.A model’s inclination to apply rules is therefore interpreted as an expression of compositionality.
  • 3.5 Overgeneralisation: Overgeneralisation is evaluated by monitoring model behaviour on exceptions during training.The experiment asks when models consistently follow a global rule set and when they instead overfit individual training samples.

4. Data

PCFG SET generates compositional input-output data by recursively applying string-edit operations described by a probabilistic context-free grammar. Its grammar and corpus construction allow control over sequence length and parse-tree depth while matching natural English distributions and separating training, validation, and test data.

  • PCFG SET: PCFG SET inputs use unary and binary string-edit operations, sequence elements, and a separator for binary-function arguments.Examples include append, copy, reverse, and symbolic elements such as A, B, A1, and B1.
  • PCFG SET: A recursive PCFG generates infinitely many admissible sequences with arbitrarily deep and long nested parse trees.Grammar probabilities and the number of input characters control the data set’s distributional properties.
  • PCFG SET: Outputs are formed by recursively applying interpretation functions to the operations specified in each input sequence.This defines a systematic mapping from input expressions to output sequences without exhaustively enumerating input-output pairs.
  • Data selection: The grammar is tuned to resemble English WMT 2017 in expression length and parse-tree depth.The authors derive these target statistics from the English side of the WMT 2017 machine-translation corpus.
  • Data selection: The corpus contains around 100 thousand distinct input-output pairs, with 85% for training, 5% for validation, and 10% for testing.The string alphabet has size 520, and function arguments are limited to length 5.

5. Architectures

The paper compares recurrent, convolutional, and transformer sequence-to-sequence architectures through their encoding mechanisms and potential compositionality strengths and limitations. LSTMS2S processes sequences sequentially, ConvS2S uses local convolutions, and Transformer relies on global attention without recurrent cells or convolutions.

  • Overview: The study compares recurrent, convolutional, and transformer architectures for sequence-to-sequence language processing tasks.These architectures are evaluated as popular approaches in machine translation, speech processing, and language understanding.
  • LSTMS2S: LSTMS2S uses bidirectional recurrent encoding, sequential decoding, and attention to focus on important parts of the input.Its sequential processing may limit hierarchical recombination, although attention can support hierarchical input processing.
  • ConvS2S: ConvS2S encodes sequences with convolutions and generates outputs through multi-step attention, while position embeddings explicitly represent order.Its convolutional mechanism contextualises information locally and sequentially.
  • Transformer: Transformer replaces recurrence and convolution with stacked feed-forward layers containing multi-head attention and feed-forward sub-layers.Position embeddings provide sequential order, while equal treatment of near and distant symbols can facilitate long-distance dependencies and hierarchical structure but makes the receptive field global.

6. Experiments and results

The experiments evaluate the proposed tests across three architectures using repeated training runs and validation-based model selection. Because hyperparameters were chosen from prior comparable studies rather than grid-searched, the results illustrate the tests’ usefulness rather than provide fully optimized comparisons.

  • Experimental setup: All architectures were trained for 25 epochs or until convergence, with the best model selected by validation performance.Each experiment used three runs per architecture, reporting average scores and standard deviations.
  • Experimental setup: The study did not grid-search hyperparameters, instead selecting reasonable settings from prior work on comparable data.Changing these hyperparameters could change the experimental results.
  • Interpretation: The reported experiments and results are intended to illustrate the usefulness of the proposed tests under fixed data and chosen hyperparameters.They should not be interpreted as fully optimized architectural comparisons.

6.1 Task accuracy

On PCFG SET, the Transformer achieves the highest overall sequence accuracy, followed by ConvS2S and LSTMS2S. Accuracy decreases as input sequences become deeper, longer, or contain more functions, while function difficulty is broadly shared across models except for architecture-sensitive performance on reverse.

  • Overall task accuracy: 0.92 accuracy makes Transformer significantly better than ConvS2S at 0.85 and LSTMS2S at 0.79 on PCFG SET.ConvS2S is also significantly better than LSTMS2S, and scores show low variation across runs.
  • Accuracy by input difficulty: All three architectures become less accurate as input depth, sequence length, or number of functions increases.These measures define increasing difficulty in the PCFG SET inputs.
  • Function difficulty: Function-difficulty rankings are similar across models, suggesting that objective function complexity contributes more than model-specific biases.The comparison uses composed input sequences and separate corpora in which each function is applied to those same sequences.
  • Function difficulty: Transformer handles reverse comparably to echo, swap, and shift, whereas reverse is difficult for LSTMS2S and ConvS2S.For LSTMS2S, repeat is even harder than reverse; the contrast follows from architectural differences in encoding ordered information.

6.2 Systematicity

The systematicity test examines whether models can interpret function pairs absent from training by recombining separately learned functions. On four held-out pairs, Transformer outperforms LSTMS2S and ConvS2S, while the latter two do not differ significantly.

  • Test design: Systematicity specifically tests whether models can interpret pairs of functions that were never seen together during training.Task success already reflects recombination of functions and input strings not seen together, whereas this test isolates unseen function-pair combinations.
  • Test design: The test evaluates models on four function pairs that never co-occur in training: swap repeat, append remove second, repeat remove second, and append swap.The redistributed training set contains 82 thousand input-output pairs, and the test set contains 10 thousand examples.
  • Results: Transformer scores higher than both LSTMS2S and ConvS2S on the systematicity test, with p ≈10−2 and p ≈10−3, respectively.The comparison concerns average accuracies across all four held-out function pairs.
  • Results: The difference between LSTMS2S and ConvS2S is statistically insignificant, with p ≈10−1.The reported results are in row 2 of Table 1 and summarized as average accuracies in Table 2.
  • Interpretation: A possible explanation for performance discrepancies is that under-sampling held-out functions leads models to develop weaker function representations or learn different solutions.Another proposed mechanism is that models may learn direct combinations of frequently observed functions instead of applying separate function representations consecutively.

6.3 Productivity

The productivity test withholds longer sequences from training, and all models struggle to extrapolate to them. Transformer retains higher productivity than LSTMS2S and ConvS2S, but its absolute performance remains poor.

  • Productivity results: All models show decreasing accuracy on longer sequences, even when those lengths fall within the training range, and on deeper inputs represented during training.Thus, longer and deeper sequences are intrinsically difficult in addition to testing productive extrapolation.
  • Productivity test: Training uses sequences containing up to eight functions, while evaluation uses sequences containing at least nine functions.The training set contains 81 thousand sequences, and the test set contains 11 thousand sequences.
  • Productivity results: 0.50 mean accuracy for Transformer contrasts with test accuracies of 0.30 for LSTMS2S and 0.31 for ConvS2S.Removing evidence for longer sequences caused relative drops of 46%, 62%, and 64%, respectively.
  • Architecture patterns: LSTMS2S and ConvS2S are relatively insensitive to increasing token length, while unseen shorter lengths are as challenging as extremely long lengths.This sharp seen-versus-unseen length difference is reported as characteristic of LSTMS2S representations.

6.4 Substitutivity

The substitutivity tests assess whether models treat meaning-invariant function synonyms interchangeably, both when synonyms are equally distributed and when they appear only in primitive contexts. Transformer and ConvS2S are highly consistent in the easier condition, while all models become less consistent in the primitive condition and much of that consistency comes from correct outputs.

  • Primitive synonyms: The primitive setup is harder because Fsyn appears only in primitive contexts and in 0.1% of training samples, making F and Fsyn distributionally dissimilar.Models receive substantially less evidence for synonym meaning than in composed contexts.
  • Evaluation: Models are evaluated by whether synonym-substituted inputs produce the same predictions, using a consistency score rather than task accuracy.This isolates robustness to meaning-invariant substitutions from overall task performance.
  • Equally distributed synonyms: In the equally distributed setup, Transformer and ConvS2S achieve consistency scores of 0.98 and 0.95, respectively, while LSTMS2S fails to identify the synonyms reliably.Transformer and ConvS2S also place words and synonyms closely in embedding space, unlike LSTMS2S.
  • Primitive synonyms: In the primitive setup, consistency falls to 0.60 for LSTMS2S, 0.58 for ConvS2S, and 0.90 for Transformer, although all models still detect some synonym similarity.Synonym embeddings remain closer than their average distances to other function embeddings.
  • Synonymity vs few-shot learning: Primitive-test consistency conflates few-shot learning of word meanings with bootstrapping information from synonyms, so the score alone cannot establish synonym inference.Error consistency is introduced to separate these abilities, but models are seldom consistent on incorrect outputs and most consistency comes from correct outputs.

6.5 Localism

The localism test compares ordinary processing with explicitly unrolled hierarchical computation, asking whether substituting constituent meanings preserves a model’s output. None of the architectures achieves high consistency, and performance on longer-than-trained string inputs is generally poor.

  • Localism test: The localism test evaluates whether replacing subsequences with their predicted meanings leaves the model’s output unchanged under hierarchical composition.Models are also evaluated by comparing ordinary outputs with outputs produced through explicitly unrolled processing of smaller constituents.
  • Results: Consistency scores are 0.46 for LSTMS2S, 0.59 for ConvS2S, and 0.54 for Transformer, with ConvS2S significantly outperforming both alternatives.The reported significance levels are p ≈10−4 against LSTMS2S and p ≈10−2 against Transformer.
  • Error analysis: The most common unrolling errors involve function applications to string inputs longer than five characters.This pattern was identified by manually analysing 300 samples, with 100 samples from each model type, containing at least one unrolling mistake.
  • Function representations: The results suggest that learned function representations do not reliably support applying functions to strings of arbitrary length.The experiment tests whether models use general rather than length-specific representations by varying the lengths of function arguments.
  • Input string length: All models achieve near-perfect accuracy through length five, but none performs well on longer strings; LSTMS2S drops immediately to zero beyond the training maximum.The maximum character-string length observed during training was five, while Transformer and ConvS2S generalise only a little beyond it for most functions.

6.6 Overgeneralisation

The overgeneralisation test examines whether models initially apply compositional rules to exceptions and how much evidence they need to memorise those exceptions. Across architectures, exception frequency strongly controls this trade-off, while learning dynamics differ substantially between models.

  • Test design: Exceptions are created by remapping four function pairs to alternative meanings, with a main frequency of 0.1% and a grid spanning 0.01%–0.5%.The selected pairs are reverse echo, prepend remove first, echo remove first, and prepend reverse.
  • Test design: The test tracks, during training, whether models predict exception outputs or overgeneralise the compositional meaning implied by the surrounding data.Overgeneralisation strength is the percentage of exceptions receiving the rule-consistent output at each training point.
  • Exception frequency: All architectures overgeneralise when exceptions occur below 0.5%, but show hardly any overgeneralisation when exceptions comprise 0.5% of a function’s occurrences.At very low exception percentages, models also have difficulty memorising the exceptions.
  • Learning dynamics: Transformer and ConvS2S initially overgeneralise, then gradually learn the exception outputs as evidence accumulates, with this transition strongest for ConvS2S.The profile indicates a thin intermediate region between overgeneralisation and memorisation for ConvS2S.
  • Learning dynamics: LSTMS2S struggles to accommodate rules and exceptions simultaneously, eventually producing outputs matching neither the exception target nor the original target.After convergence, its exception-sequence accuracy is substantially below its overall corpus accuracy.

7. Discussion

The paper proposes five theoretically motivated, task-independent tests for evaluating distinct aspects of compositionality in neural models. Applied to PCFG SET and three sequence-to-sequence architectures, the tests reveal that high overall accuracy does not ensure representation of the underlying generative system.

  • Evaluation framework: The framework translates theoretical concepts of language compositionality into five independent behavioural tests for neural models.The tests examine systematic recombination, generalisation to unseen lengths, locality of composition, synonym robustness, and preference for rules or exceptions.
  • Evaluation framework: The tests were instantiated on PCFG SET, an artificial sequence-to-sequence translation task whose meanings require recursively applying string-edit operations generated by a probabilistic context-free grammar.Its design aims to require a compositional solution while isolating compositional processing from signals present in naturalistic data.
  • Results: Despite relatively high overall accuracy, none of the three architectures successfully generalised to word pairs absent together from training.Systematicity scores were 33%, 34% and 22% lower than overall task accuracy for LSTMS2S, ConvS2S and Transformer, respectively; the authors attribute this partly to differing input segmentations and multi-function chunking.
  • Results: The substitutivity test found that no model truly treated words and their counterparts as synonyms when evaluating consistency on incorrect outputs.Transformer was the most consistent but achieved only 0.34, while LSTMS2S appeared better at inferring synonymy and ConvS2S was better at learning from few examples.
  • Implications and limitations: The findings support using the test collection as an evaluation paradigm for clarifying which aspects of compositionality neural architectures represent, while leaving their expression in natural-data settings open.The authors also caution that the results are not general claims about the architectures because hyper-parameter and learning-regime effects were not investigated.

Appendix A. Naturalisation of artificial data

The appendix describes a procedure for transforming artificially generated PCFG SET data to mimic the feature distribution of a natural-language dataset. It partitions natural and generated data by discretized feature vectors, selects the closest transformed sample distribution, and uses estimated PCFG parameters to generate additional data.

  • The procedure begins by extracting a feature set from a natural-language dataset and computing each feature for every sentence.
  • A large PCFG SET sample is generated with random production-rule probabilities before distributional transformation.
  • Natural-language instances are grouped by partitioning vectors formed from discretized feature values, and generated data are partitioned in the same way.
  • Among transformed datasets produced with different feature increments, the method selects the set whose fitted multivariate Gaussian has the lowest Kullback–Leibler divergence from the natural-language approximation.
  • Maximum likelihood estimates PCFG parameters from the selected transformed data, which are then used to generate more PCFG SET data and optionally repeat the transformation.
Loading 1908.08351v2…