Source-linked AI summary
Measuring Compositionality in Representation Learning
Jacob Andreas
TL;DR
Machine learning lacks general-purpose, graded tools for testing whether known compositional structure is reflected in learned representations. The paper introduces TRE, which infers primitives and measures how closely their compositions approximate observed representations, then applies it across four representation-learning questions. The results relate compositionality to learning dynamics, human judgments, similarity, and generalization, while leaving extension beyond oracle derivations as an open limitation.
Problem
Machine learning lacks general-purpose tools for producing graded measurements of compositional structure in non-string representation spaces.
Method
TRE infers hidden primitive representations and measures how well an explicitly compositional model approximates the true representation-producing model.
Results
The paper applies TRE to four representation-learning problems involving learning dynamics, linguistic compositionality, similarity, and generalization.
Takeaways & Limitations
TRE provides graded judgments for examining compositional structure across discrete- and continuous-valued representations and its relationships with other model properties.
Takeaways & Limitations
Extending TRE to settings without oracle derivations requires jointly solving the evaluation equation and an unsupervised grammar-induction problem.
Abstract
from arXiv · showhide
Many machine learning algorithms represent input data with vector embeddings or discrete codes. When inputs exhibit compositional structure (e.g. objects built from parts or procedures from subroutines), it is natural to ask whether this compositional structure is reflected in the the inputs' learned representations. While the assessment of compositionality in languages has received significant attention in linguistics and adjacent fields, the machine learning literature lacks general-purpose tools for producing graded measurements of compositional structure in more general (e.g. vector-valued) representation spaces. We describe a procedure for evaluating compositionality by measuring how well the true representation-producing model can be approximated by a model that explicitly composes a collection of inferred representational primitives. We use the procedure to provide formal and empirical characterizations of compositional structure in a variety of settings, exploring the relationship between compositionality and learning dynamics, human judgments, representational similarity, and generalization.
1 INTRODUCTION
The paper introduces a formal, quantitative framework for measuring whether known compositional structure in inputs is reflected in learned representations. It applies this tool to questions about learning dynamics, human judgments, representational similarity, and generalization.
- The communication-game example treats learned character sequences as representations whose structure may imperfectly reflect the known compositional structure of inputs.
- Existing evaluations of compositionality are often manual and subjective or automated but tailored to individual domains, making them difficult to compare and apply systematically.
- The paper addresses this gap by studying an oracle setting where input compositional structure is known and only its reflection in model outputs is evaluated.
- TRE measures compositionality by optimizing hidden primitive representations so an explicitly compositional model approximates observed discrete- or continuous-valued representations.
- The paper surveys how compositionality relates to learning dynamics, human judgments, representational similarity, and generalization.
2 RELATED WORK
Prior work evaluates compositionality through linguistic analyses, manual inspection, task-specific procedures, or surrogate measures. These approaches are specialized, difficult to reproduce or compare, and often do not transfer straightforwardly to general representation spaces.
- Linguistic techniques for compositionality are specialized to formal and natural languages, particularly the algebraic structure of grammars.
- Manual analyses can reveal organization in representation spaces but are time-consuming and non-reproducible.
- Other evaluations exploit task-specific structure, limiting their systematic application across problem domains.
- Some studies instead use representation similarity or generalization to structurally novel inputs as surrogate measures for compositionality.
- Work on learning composition functions for distributed linguistic representations is complementary to this evaluation framework.
3 EVALUATING COMPOSITIONALITY
The paper evaluates whether learned representations reflect known compositional structure by fitting explicitly compositional models to representations and measuring approximation error. TRE handles discrete or continuous representations, supports graded judgments, and requires restricted composition functions to avoid trivial solutions.
- A representation-learning problem consists of inputs, a representation space, and a model producing representations used in a larger task.
- The evaluation assumes an oracle supplies tree-structured derivations built from primitive elements and binary composition.
- General representation spaces create two challenges: identifying primitive parts without a predefined syntax and measuring approximate rather than exact compositionality.
- TRE searches over hidden primitive representations so an explicitly compositional model approximates the true representation-producing model as closely as possible.
- TRE is zero for every input if and only if the representation model exactly satisfies the compositional homomorphism condition.
- The evaluator may choose the distance and composition operator, but unrestricted learned operators can force TRE to zero and therefore require prior restriction.
- For differentiable continuous representations, TRE can be optimized with gradient descent; discrete representations may use a continuous relaxation.
4 COMPOSITIONALITY AND LEARNING DYNAMICS
The paper studies whether compositional representations emerge during learning, using a few-shot visual-concept classification task and comparing TRE with mutual information between inputs and representations.
- Task and setup: The study uses meta-learning on few-shot visual concepts formed from single attributes or attribute conjunctions.Learners receive two example images and classify whether a held-out image depicts the same concept.
- Task and setup: The model represents classifiers with θ and is trained by minimizing logistic loss on held-out labels.The task takes example images x1 and x2, a test image x∗, and label y∗ as inputs.
- Task and setup: At convergence, validation accuracy averages 75.2% across ten training runs.The dataset contains 9000 balanced image triplets and a 500-example validation set; perfect accuracy is unattainable because two examples do not fully determine the classifier.
- Learning dynamics: TRE and mutual information initially increase together, then decrease together after mutual information reaches its maximum.The same pattern appears across multiple training runs and during the postulated compression phase.
- Learning dynamics: The joint decrease in TRE and mutual information is consistent with compression being associated with discovery of compositional representations.Small TRE indicates a higher degree of compositionality.
5 COMPOSITIONALITY AND HUMAN JUDGMENTS
The paper tests whether TRE identifies compositional phrase embeddings by comparing bigram-level scores with human judgments of noun–noun compounds. TRE is negatively associated with human-rated compositionality.
- Motivation: The study asks whether individual phrase representations, rather than phrase embeddings in aggregate, are compositionally explained by their constituent words.It treats low-TRE bigrams as essentially compositional and high-TRE bigrams as potentially non-compositional expressions.
- Embedding setup: Word and bigram embeddings are trained with CBOW using 100-dimensional vectors, a context size of 5, and 250M words from Gigaword.The implementation uses FastText.
- TRE evaluation: TRE compares phrase embeddings with compositions of constituent word embeddings using vector addition and cosine distance.Words have primitive derivations, while bigrams use derivations of the form ⟨w1, w2⟩.
- Results: ρ = −0.34, p < 0.01: TRE is anticorrelated with human judgments of noun–noun compound compositionality.Human ratings range from 0 to 5, with conventionalized phrases receiving lower scores.
- Results: The lowest-TRE collocations include application form, polo shirt, and research project, while fine line, lip service, and nest egg have the highest TRE.These examples correspond respectively to the approach’s most and least compositional ratings.
6 COMPOSITIONALITY AND SIMILARITY
The paper relates TRE-based compositionality to topographic similarity through tree-edit distances on oracle derivations. Under stated metric conditions, derivational distance approximately bounds representational distance, but small TRE alone does not ensure topographic similarity.
- Formal relationship: The analysis compares TRE with topographic similarity, which evaluates whether distances between representations correlate with distances between their derivations.Because the derivations are trees, the paper uses tree edit distance.
- Formal relationship: Under the proposition’s assumptions, tree-edit distance is an approximate upper bound on distance between representations produced by the corresponding derivations.The distance on representations must satisfy the stated identity and compositional subadditivity conditions.
- Interpretation: Compositionality constrains how far representations can be from one another relative to the derivations that produce them.The proposition applies when the approximation has TRE(x) ≤ ϵ for all x.
- Limitation: Small TRE is not sufficient for topographic similarity because different derivations can map to the same representation.Arithmetic expressions represented only by their results provide the paper’s example.
7 COMPOSITIONALITY AND GENERALIZATION
The communication experiment tests whether compositionality predicts generalization in discrete speaker–listener protocols. TRE correlates with smaller train–test gaps, but low TRE can also reflect trivial, poorly performing strategies and is not necessary for good generalization.
- Communication task: Agents communicate target object pairs through discrete messages, and listeners reconstruct the objects from those messages.Training holds out one-third of possible reference candidates to evaluate generalization.
- Results: TRE is significantly correlated with generalization error, measured as the difference between training and test reward.The reported relationship is r = 0.50, p < 1e−6.
- Experimental setup: 100 randomly initialized speaker–listener pairs are evaluated on both training and held-out test sets.The speaker sends a character sequence, while the listener predicts attribute sets and receives partial credit for partly correct reconstructions.
- Results: TRE is also significantly correlated with absolute reward, with more compositional languages often emerging from poor communication strategies.Figure 5 reports r = 0.57, p < 1e−9 for absolute performance; the relationship persists among successful runs.
- Interpretation: Many low-TRE languages use trivial strategies, such as sending the same message regardless of the observation, producing poor overall performance.This explains why compositionality and absolute reward can be positively associated while compositionality still tracks smaller generalization gaps.
- Results: Low TRE is not necessary for good generalization: training runs can achieve good generalization at both low and high compositionality.Figure 6 shows languages with substantially different TRE but similar listener performance on training and test rewards.
8 CONCLUSIONS
The paper introduces TRE as a graded measure of compositional structure in representations and applies it across four representation-learning settings. A central open problem is extending TRE beyond settings with known oracle derivations.
- Contribution: TRE infers primitive meaning representations whose composition approximates observed representations, then measures the approximation quality.The method applies to discrete- or continuous-valued representations when the input structure is known.
- Applications: TRE-based analyses relate compositionality to learning dynamics, linguistic compositionality, similarity, and generalization across four representation-learning problems.These applications broaden the empirical study of compositional structure beyond a single representation type or task.
- Limitation and future work: Extending TRE to settings without oracle derivations requires solving the compositional model jointly with an unsupervised grammar-induction problem.The conclusion identifies this as the most immediate open question.
- Resources: Code and data for all experiments are provided in the paper’s public repository.The repository is identified by the URL https://github.com/jacobandreas/tre.
A MODELING DETAILS
The experiments use task-specific neural models and optimization procedures, including CNNs, FastText embeddings, and recurrent communication agents. Communication models use discrete messages trained with policy gradients.
- Few-shot classification: The CNN is trained with ADAM at learning rate .001 and batch size 128 until held-out performance stops improving.Training uses a held-out set for early stopping.
- Word embeddings: Word embeddings use FastText trained on the first 250 million words of the NYT section of Gigaword.Bigram representations are obtained by treating each relevant bigram as a single word during vector estimation.
- Communication: Communication agents use GRU encoder and decoder RNNs with 256-dimensional embeddings and hidden states, a 16-token vocabulary, and messages of length 4.Training runs for 500 steps with ADAM and a policy-gradient objective using the running average reward as baseline.
B PROPOSITION 1
This appendix defines derivation size and tree edit distance, then proves that representation distance is bounded by derivation distance plus an approximation term. The proof proceeds by induction over derivation structure.
- Definitions: The appendix defines derivation size as a structural quantity used in the analysis of composed derivations.
- Definitions: Tree edit distance compares derivations through recursive edit costs for matched, inserted, or deleted subderivations.The displayed cases combine subtree distances with derivation-size penalties.
- Proposition: Representation distance satisfies δ(θ, θ′) ≤ ∆(d, d′) + 2ϵ for inputs whose derivations are d and d′.The proposition transfers structural similarity between derivations into an upper bound on representation distance.
- Proof: The proof handles base derivations directly from the proposition’s conditions and composed derivations by induction on derivation size.The inductive argument uses zero auxiliary representations in the composed case.
- Proof: The inductive step separates edits that match two child subderivations from edits that match one child while accounting for the other’s size.The second case is reduced to the first by introducing a zero derivation.