MEASURING COMPOSITIONALITY IN REPRESENTATION LEARNING
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.
Figure 1: Representations arising from a communication game. In this game, an observation (b) is presented to a learned speaker model (c), which encodes it as a discrete character sequence (d) to be consumed by a listener model for some downstream task. The space of inputs has known compositional structure (a). We want to measure the extent to which this structure is reflected (perhaps imperfectly) in the structure of the learned codes.
The success of modern representation learning techniques has been accompanied by an interest in understanding the structure of learned representations. One feature shared by many humandesigned representation systems is compositionality: the capacity to represent complex concepts (from objects to procedures to beliefs) by combining simple parts (Fodor & Lepore, 2002). While many machine learning approaches make use of human-designed compositional analyses for representation and prediction (Socher et al., 2013;Dong & Lapata, 2016), it is also natural to ask whether (and how) compositionality arises in learning problems where compositional structure has not been built in from the start. Consider the example in Figure 1, which shows a hypothetical character-based encoding scheme learned for a simple communication task (similar to the one studied by Lazaridou et al., 2016). Is this encoding scheme compositional? That is, to what extent can we analyze the agents' messages as being built from smaller pieces (e.g. pieces xx meaning blue and bb meaning triangle)?
A large body of work, from early experiments on language evolution to recent deep learning models (Kirby, 1998;Lazaridou et al., 2017), aims to answer questions like this one. But existing solutions rely on manual (and often subjective) analysis of model outputs (Mordatch & Abbeel, 2017), or at best automated procedures tailored to the specifics of individual problem domains (Brighton & Kirby, 2006). They are difficult to compare and difficult to apply systematically.
We are left with a need for a standard, formal, automatable and quantitative technique for evaluating claims about compositional structure in learned representations. The present work aims at first steps toward meeting that need. We focus on an oracle setting where the compositional structure of model inputs is known, and where the only question is whether this structure is reflected in model outputs. This oracle evaluation paradigm covers most of the existing representation learning problems in which compositionality has been studied.
The first contribution of this paper is a simple formal framework for measuring how well a collection of representations (discrete-or continuous-valued) reflects an oracle compositional analysis of model inputs. We propose an evaluation metric called TRE, which provides graded judgments of compositionality for a given set of (input, representation) pairs. The core of our proposal is to treat a set of primitive meaning representations as hidden, and optimize over them to find an explicitly compositional model that approximates the true model as well as possible. For example, if the compositional structure that describes an object is a simple conjunction of attributes, we can search for a collection of "attribute vectors" that sum together to produce the observed object representations; if it is a sparse combination of (attribute, value) pairs we can additionally search for "value vectors" and parameters of a binding operation; and so on for more complex compositions.
Having developed a tool for assessing the compositionality of representations, the second contribution of this paper is a survey of applications. We present experiments and analyses aimed at answering four questions about the relationship between compositionality and learning:
• How does compositionality of representations evolve in relation to other measurable model properties over the course of the learning process? (Section 4) • How well does compositionality of representations track human judgments about the compositionality of model inputs? (Section 5) • How does compositionality constrain distances between representations, and how does TRE relate to other methods that analyze representations based on similarity? (Section 6) • Are compositional representations necessary for generalization to out-of-distribution inputs?
(Section 7)
We conclude with a discussion of possible applications and generalizations of TRE-based analysis.
Edit and a further question: Reading again Section 7, I'm wondering whether the  the high generalization is possible due to the fact that at test time only one of the two candidates is unseen, and the other is seen. Having *both* candidates to be unseen makes the problem significantly harder since the only way for the listener to get it right is to associate the message with the right candidate, rather than relying in some other strategy like whether the message is novel (thus it's the seen candidate) or new (thus it's the unseen candidate). As such, I don't think I can fully trust your conclusions due to this potential confounder. 
--------------------------------------------------------------
The authors propose a measure of compositionality in representations. Given instances of data x annotated with semantic primitives, the authors learn a vector for each of the primitive such that the addition of the vectors of the primitives is very close (in terms of cosine) to the latent representation  z of the input x. The authors find that this measure correlates with the mutual information between the input x and z, approximates the human judges of compositionality on a language dataset and finally presents a study on the relation between the proposed measure and generalizalization performance, concluding that their measure correlates with generalization error as well as absolute test accuracy.
This in an interesting study and attacks a very fundamental question; tracking compositionality in representations could pave the way towards representations that facilitate transfer learning and better generalization. While the paper is very clear with respects to results, I found the presentation of the proposed measure overly confusing (and somewhat more exaggerated that what is really going on). 
The authors start with a very clean example, that can potentially facilitate clarifying in a visual way the process of obtaining the measure. However, I feel that clarity is being traded-off for formality. It needs several reads to really distill the idea that essentially the authors are simply learning vectors of primitives that when added should resemble the representation of the input. Moreover, the name of the measure is a bit misleading and not justified by the experiments and the data. The authors do not deal with trees in any of the examples, but rather with a set of primitives (apparent in the use of addition as a composition function which being commutative does not allow for word-order and the like deep syntactic properties). 
Now, onto the measure. I like the idea of learning basis vectors from the representations and constraining to follow the primitive semantics. Of course, this constraints quite a bit the form of compositionality that the authors are searching for. 
The idea of additive semantics has been explored in NLP, however it's mostly applicable for primitives with intersective semantics (e.g., a white towel is something that is both white and a towel). Do the authors think that this restricts their experiments (especially the natural languages ones)? What about other composition techniques found in the literature of compositional semantics (e.g., by Baroni and Zamparelli, 2010). 
This is good to be clarified.  Moreover, given the simplicity of the datasets in the current study, wouldn't a reasonable baseline be to obtain the basis vector of blue by averaging all the latent representations of blue?  Similarly, how sensitive are conclusions with respect to different composition functions?
Section 4 is potentially very interesting, but I don't seem to understand why it's good news that TRE correlates with I(x;\theta). Low TRE indicates high-degree of compositionality. I suspect that low MI means that input and latent representation are somewhat independent but I don't see the connection to compositional components. Can the authors clarify?
Section 5 is a nice addition. The authors mention that they learn word and phrase representations. Where are the word representations used? My understanding is that you derive basis word representations by using SGD and the phrase vectors and compute TRE with these. If this is the case, an interesting experiment would be to report how similar the induced basis vectors are (either some first-order or second-order similarity) to the pre-trained ones.
Section 8 presents results on discrete representations. Since this is the experiment most similar to the recent work that uses topographic similarity (and since the authors already prime the reader at section 7 about relation between the 2 measures), it would be interesting to see the empirical relation between TRE and topographic and its relation to generalization and absolute performance. 
Baroni and Zamparelli (2010) Nouns are vectors, adjectives are matrices: Representing adjective-noun constructions in semantic space