summaries: This paper proposes an architecture that addresses transferability of compositionality. The proposed architecture consists of three components: a network that transforms the input X into a series of hidden representations {H_1, H_2, ... H_K}, a network that reconstructs the input X from this series of hidden representations, and a prediction network that generates a prediction from the hidden representations. The authors propose several datasets meant to address transferability of compositional generalisation, and show that their architecture significantly improves standard DNN architectures as well as humans on these datasets. The paper introduces a “transferability of compositionality” problem and proposes an approach to alleviate it. The said problem may arise when one trains neural models to produce “compositional” representations of the input. In the paper “compositional representations” consist of multiple vectors which are supposed to correspond to semantically meaningful aspects of the input, for example different objects in the case of images or different parts of compound words in the case of linguistic inputs. The transferability problem arises when there is a difference between training and test distributions, namely when certain combinations of objects have different probabilities in training & testing. The proposed solution at inference time is to project object representations to the manifold of individual object representations. The manifold is estimated by saving representations of individual object representations from the training time.  This paper studies "compositionality" and in particular the way in which it "transfers" on test data. They run simple baselines on three experiments (overlapped MNIST, colored MNIST and concatenated month names) and find that the baselines do not learn compositional representation. They proposed the use of an *auxiliary reconstruction network and a regularized optimization* which improves on these baselines. 
abstractText: Compositional generalization is the algebraic capacity to understand and produce large amount of novel combinations from known components. It is a key element of human intelligence for out-of-distribution generalization. To equip neural networks with such ability, many algorithms have been proposed to extract compositional representations from the training distribution. However, it has not been discussed whether the trained model can still extract such representations in the test distribution. In this paper, we argue that the extraction ability does not transfer naturally, because the extraction network suffers from the divergence of distributions. To address this problem, we propose to use an auxiliary reconstruction network with regularized hidden representations as input, and optimize the representations during inference. The proposed approach significantly improves accuracy, showing more than a 20% absolute increase in various experiments compared with baselines. To our best knowledge, this is the first work to focus on the transferability of compositionality, and it is orthogonal to existing efforts of learning compositional representations in training distribution. We hope this work will help to advance compositional generalization and artificial intelligence research. The code is in supplementary materials.
references.authors: Joost Bastings Marco Baroni Jason Weston Kyunghyun Cho Douwe Kiela
references.title: Jump to better conclusions: Scan both left and right
references.venue: BlackboxNLP@EMNLP,
references.authors: Yoshua Bengio
references.title: Deep learning of representations: Looking forward
references.venue: In International Conference on Statistical Language and Speech Processing,
references.authors: Yoshua Bengio
references.title: The consciousness prior
references.venue: arXiv preprint arXiv:1709.08568,
references.authors: Philémon Brakel Stefan Frank
references.title: Strong systematicity in sentence processing by simple recurrent networks
references.venue: In 31th Annual Conference of the Cognitive Science Society
references.authors: Christopher P Burgess Irina Higgins Arka Pal Loic Matthey Nick Watters Guillaume Desjardins Alexander Lerchner
references.title: Understanding disentangling in β-vae
references.venue: arXiv preprint arXiv:1804.03599,
references.authors: Tian Qi Chen Xuechen Li Roger B Grosse David K Duvenaud
references.title: Isolating sources of disentanglement in variational autoencoders
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jerry A Fodor Ernest Lepore
references.title: The compositionality papers
references.authors: Jerry A Fodor Zenon W
references.title: Pylyshyn. Connectionism and cognitive architecture: A critical analysis
references.authors: J. Gama I. Žliobaitė A. Bifet M. Pechenizkiy A. Bouchachia
references.title: A survey on concept drift adaptation
references.venue: ACM computing surveys (CSUR),
references.authors: J. Gorden D. Lopez-Paz M. Baroni D. Bouchacourt
references.title: Permutation eqivariant models for compositional generalization in language
references.venue: In ICLR,
references.authors: I. Higgins
references.title: Scan: Learning hierarchical compositional visual concepts
references.venue: In ICLR,
references.authors: Irina Higgins Loic Matthey Arka Pal Christopher Burgess Xavier Glorot Matthew Botvinick Shakir Mohamed Alexander Lerchner
references.title: β-vae: Learning basic visual concepts with a constrained variational framework
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Jun-Ting Hsieh Bingbin Liu De-An Huang Li F Fei-Fei Juan Carlos Niebles
references.title: Learning to decompose and disentangle representations for video prediction
references.venue: In Advances in Neural Information Processing Systems,
references.authors: J. Johnson
references.title: Clevr: A diagnostic dataset for compositional language and elementary visual reasoning
references.authors: D. Keysers
references.title: Measureing compositional generalization: a comprehensive method on realistic data
references.venue: In ICLR,
references.authors: Hyunjik Kim Andriy Mnih
references.title: Disentangling by factorising
references.venue: In International Conference on Machine Learning,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: arXiv preprint arXiv:1412.6980,
references.authors: Markus Kliegl Wei Xu
references.title: More systematic than claimed
references.venue: Insights on the scan tasks. OpenReview,
references.authors: Abhishek Kumar Prasanna Sattigeri Avinash Balakrishnan
references.title: Variational inference of disentangled latent concepts from unlabeled observations
references.venue: In International Conference on Learning Representations (ICLR),
references.authors: Brenden Lake Marco Baroni
references.title: Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks
references.venue: In International Conference on Machine Learning,
references.authors: Brenden M Lake
references.title: Compositional generalization through meta sequence-to-sequence learning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Brenden M Lake Tomer D Ullman Joshua B Tenenbaum Samuel J Gershman
references.title: Building machines that learn and think like people
references.venue: Behavioral and Brain Sciences,
references.authors: Brenden M Lake Tal Linzen Marco Baroni
references.title: Human few-shot learning of compositional instructions
references.venue: arXiv preprint arXiv:1901.04587,
references.authors: Yann LeCun Léon Bottou Yoshua Bengio Patrick Haffner
references.title: Gradient-based learning applied to document recognition
references.venue: Proceedings of the IEEE,
references.authors: Yuanpeng Li Liang Zhao Jianyu Wang Joel Hestness
references.title: Compositional generalization for primitive substitutions
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),
references.authors: Tal Linzen Emmanuel Dupoux Yoav Goldberg
references.title: Assessing the ability of lstms to learn syntaxsensitive dependencies
references.venue: Transactions of the Association for Computational Linguistics,
references.authors: Francesco Locatello Stefan Bauer Mario Lucic Gunnar Raetsch Sylvain Gelly Bernhard Schölkopf Olivier Bachem
references.title: Challenging common assumptions in the unsupervised learning of disentangled representations
references.venue: In International Conference on Machine Learning,
references.authors: Francesco Locatello Michael Tschannen Stefan Bauer Gunnar Ratsch Bernhard Scholkopf Olivier Bachem
references.title: Disentangling factors of variations using few labels
references.venue: In ICLR,
references.authors: Joao Loula Marco Baroni Brenden M Lake
references.title: Rearranging the familiar: Testing compositional generalization in recurrent networks
references.venue: arXiv preprint arXiv:1807.07545,
references.authors: Laurens van der Maaten Geoffrey Hinton
references.title: Visualizing data using t-sne
references.venue: Journal of machine learning research,
references.authors: Gary F Marcus
references.title: Rethinking eliminative connectionism
references.venue: Cognitive psychology,
references.authors: Gary F Marcus
references.title: The algebraic mind: Integrating connectionism and cognitive science
references.venue: MIT press,
references.authors: Geoff Pleiss Amauri Souza Joseph Kim Boyi Li Kilian Q. Weinberger
references.title: Neural network out-of-distribution detection for regression tasks, 2020. URL https://openreview.net/ forum?id=ryxsUySFwr
references.authors: I. Redko E. Morvant A. Habrard M. Sebban
references.title: Bennanl. A survey on domain adaptation theory
references.venue: arXiv preprint arXiv:2004.11829v1,
references.authors: Paul Rodriguez Janet Wiles
references.title: Recurrent neural networks can learn to implement symbol-sensitive counting
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Jake Russin Jason Jo Randall C O’Reilly
references.title: Compositional generalization in a deep seq2seq model by separating syntax and semantics
references.authors: Gail Weiss Yoav Goldberg Eran Yahav
references.title: On the practical computational power of finite precision rnns for language recognition
references.venue: arXiv preprint arXiv:1805.04908,
references.authors: Francis CK Wong William SY Wang
references.title: Generalisation towards combinatorial productivity in language acquisition by simple recurrent networks
references.venue: In 2007 International Conference on Integration of Knowledge Intensive Multi-Agent Systems,
references.authors: Guangyu Robert Yang Madhura R Joglekar H Francis Song William T Newsome Xiao-Jing Wang
references.title: Task representations in neural networks trained to perform many cognitive tasks
references.venue: Nature neuroscience,
sections.heading: 1 INTRODUCTION
sections.text: Human intelligence (Minsky, 1986; Lake et al., 2017) exhibits compositional generalization, the algebraic capacity to understand and produce large amount of novel combinations from known components (Chomsky, 1957; Montague, 1970). This capacity helps humans to recognize the world efficiently and to be imaginative. It is also beneficial to design machine learning algorithms with compositional generalization skills. Current neural network models, however, generally lack such ability. Compositional generalization is a type of out-of-distribution generalization (Bengio, 2017), where the training and test distributions are different. A sample in such a setting is a combination of several components, and the generalization is enabled by recombining the seen components of the unseen combination during inference. In the image domain, an object is a combination of many parts or properties. In the language domain, a compound word is a combination of multiple words. As an example, we consider two digits are overlapped (Figure 1). Each digit is a component, and it appears in training. A test example has a new combination of two digits.
  The main approach for compositional generalization is to learn compositional representations (Bengio, 2013), which contain several component representations. Each of them depends only on the underlying generative factor, and does not change when other factors change. We call this the compositionality property, and will formally introduce in Section 3. In the digit example, this means that the representation of one digit does not change when the other digit changes.
  Multiple approaches have been proposed to learn compositional representations in the train distribution. However, little discussion has focused on whether the model can still extract the representations in the test distribution. We find that the extraction ability does not transfer naturally, because the extraction network suffers from the divergence of distributions (Bengio, 2017; Pleiss et al., 2020), so that each extracted representation shifts away from the corresponding one in training. Our experiment on the digit example shows that the accuracy drops from 89.6% in training to 49.3% in test (Table 1 in Section 5).
  To address the problem, we hope each representation is consistent with the training one while reflecting the test sample. We use an auxiliary network, which has hidden representations as inputs,
  and the original input as output. For a test sample, we regularize each hidden representation in its training manifold, and optimize them to recover the original input. Then we use the optimized representations for prediction. Experimental results show that the proposed approach has more than a 20% absolute increase in various experiments compared to baselines, and even outperforms humans on the overlapping digit task. Our contributions can be summarized as follows.
  • We raise and investigate the problem of transferability of compositionality to test distribution. This work is orthogonal to many efforts of learning compositionality in training distribution.
  • We propose to address the problem by using an auxiliary reconstruction network with regularized hidden representations as input, and optimize the representations during inference.
  • We empirically show that the transferability problem exists and the proposed approach has significant improvements over baselines.
sections.heading: 2 RELATED WORK
sections.text: Compositional generalization (Chomsky, 1957; Montague, 1970) is critical in human cognition (Minsky, 1986; Lake et al., 2017; Johnson & et al, 2017; Higgins & et al, 2018; Lake et al., 2019). It helps humans to understand and produce large amount of novel combinations from known components. Broadly speaking, compositional generalization is a type of out-of-distribution (o.o.d.) transferring or generalization, which is also called domain adaptation (Redko et al., 2020) or concept drift (Gama et al., 2014). This is different from traditional i.i.d. setting, where the training and the test distributions are identical. The transferring requires prior knowledge of how the distribution is changed, and compositional generalization has a particular form of such change, as mentioned in the later section.
  Compositional generalization is also a desirable property for deep neural networks. Human-level compositional learning (Marcus, 2003; Lake & Baroni, 2018) has been an important open challenge (Yang et al., 2019; Keysers & et al, 2020), although there is a long history of studying compositionality in neural networks. Classic view (Fodor & Pylyshyn, 1988; Marcus, 1998; Fodor & Lepore, 2002) considers conventional neural networks lack systematic compositionality. With the breakthroughs in deep neural networks, there are more contemporary attempts to encode compositionality in deep neural networks. Compositionality in neural networks is actively explored for systematic behaviour (Wong & Wang, 2007; Brakel & Frank, 2009), counting ability (Rodriguez & Wiles, 1998; Weiss et al., 2018) and sensitivity to hierarchical structure (Linzen et al., 2016). Researchers have also proposed multiple related tasks (Lake & Baroni, 2018; Loula et al., 2018; Lake et al., 2019) and methods (Lake et al., 2017; Lake & Baroni, 2018; Loula et al., 2018; Kliegl & Xu, 2018; Li et al., 2019; Lake, 2019; Gorden et al., 2020) for learning compositionality in training distribution. Another line of related work is independent disentangled representation learning (Higgins et al., 2017; Burgess et al., 2018; Kim & Mnih, 2018; Chen et al., 2018; Kumar et al., 2017; Hsieh et al., 2018; Locatello et al., 2019; 2020). Its main assumption is that the expected components are statistically independent in training
  data. This setting does not have transferring problem in test, because all combinations have positive joint probabilities in training (please see Section 3).
  More recently, there have been approaches for better compositional learning in NLP tasks by elaborating RNN models (Bastings et al., 2018), by using pointer networks (Kliegl & Xu, 2018), or by using two representations of a sentence (Russin et al., 2019; Li et al., 2019). In these tasks, the input can be divided into words, which have consistent information in different distributions. However, such property is not always available, e.g. the overlapping digits. In this paper, we propose to acquire the compositional representations with optimization during inference. We will discuss more in the following sections.
sections.heading: 3 COMPOSITIONALITY AND TRANSFERABILITY
sections.text: In this section, we describe compositionality as a model property. We then argue that compositionality may not transfer to test distribution, and discuss ideas of the proposed approach.
  Compositionality Compositional generalization has different training and test distributions. Samples in both training and test data are combinations of K components. For example, in Figure 1, input X has two digits X1, X2, and output Y has corresponding labels Y1, Y2. While a test sample’s combination does not appear in training, each component of the test sample appears in training.
  A key for compositional generalization is to have compositional representation, which has multiple component representations. Each component representation corresponds to an underlying input component, and it does not change when other components change. We call this property as compositionality. A compositional representation is computed from an entangled input, and the extraction network needs to output correct component representations. If the extraction network transfers to test distribution, the representations can be correctly extracted in test, so that the compositional generalization is enabled by recombining them.
  Transferability As mentioned above, to enable compositional generalization, there is an assumption that the property of compositionality should transfer to the test distribution. Since X1, . . . , XK are entangled, the model has the entire X as input. However, input X has different distributions in training and test, so the extraction network suffers from the divergence of distributions (Bengio, 2017; Pleiss et al., 2020). Hence, even if the model is trained to fit the compositionality property in the training distribution, the property is not guaranteed to transfer to the test distribution.
  We propose to obtain compositional representations not from the extractor but reversely from an auxiliary network. We extract compositional representations with optimization, and introduce regularization to make each hidden representation in the corresponding training manifold. We then use the optimized hidden representation for prediction. More details are provided in the next section.
sections.heading: 4 APPROACH
sections.text: In this section, we introduce the proposed approach from model architecture, training and inference perspectives. The architecture contains three modules, trained with routine end-to-end optimization. The inference, different from conventional procedure, includes three steps: extracts initial hidden representations; optimizes hidden representations as module input; predicts output. Figure 2 contains overall flowcharts, and Algorithm 1 is a summary for the approach. We describe details here.
sections.heading: 4.1 MODEL ARCHITECTURE
sections.text: The model takes a sample with input X and label Y . We have a representation extractor g with parameter φ, which takes X as input, and outputs K hidden representations H = H1, . . . ,HK : H = g(X;φ). We also have a prediction network f with parameter θ, which takes hidden representations H as input, and outputs Ŷ : Ŷ = f(H; θ). These networks can be some existing networks for compositionality learning. In addition to them, we have an auxiliary network h with parameters ψ, which takes hidden representations H as input, and combines them to output X̂: X̂ = h(H;ψ).
  Algorithm 1 The proposed approach for training (left) and inference (right). α, β, γ, η are hyper parameters. K is the number of components. M is the number of instances in memory.
  Training sample: X,Y 1: H = H1, . . . ,HK = g(X;φ) 2: H ′ = H + η , ∈ N (0, I) 3: Ŷ = f(H ′; θ), X̂ = h(H ′;ψ) 4: Ltrain = CE(Y, Ŷ ) +αL2(X, X̂) + βL2(H) 5: θ̂, φ̂, ψ̂ = argminθ,φ,ψ Ltrain(X,Y, θ, φ, ψ) 6: Memm = g(Xm; φ̂),m = 1, . . . ,M Inference sample: X 1: H init = g(X; φ̂) 2: X̂ = h(H; ψ̂) 3: Lmanf(H) = ∑K k=1 minm L2(Hk,Mem m k ) 4: Linfer(X,H) = L2(X, X̂) + γLmanf(H) 5: Ĥ = argminH Linfer(X,H), H0 = H init 6: Ŷ = f(Ĥ; θ̂)
sections.heading: 4.2 TRAINING
sections.text: In training, we sequentially use the extractor g and predictor f , by setting the output of the extractor H as input of the predictor. We have a loss Loriginal (containing regularization terms) , such as cross entropy: CE(Y, Ŷ ), to train a model with compositionality by existing algorithms.
  On top of that, we train ψ with H as inputs and X̂ as output. We set auxiliary loss as the difference (L2 distance) between X and X̂: Lauxiliary = L2(X, X̂). We also regularize the L2 norm of H , Lhidden = L2(H), and add noise, H ′ = H + η , ∈ N (0, I), to avoid remembering X . η is a hyper parameter. The whole train loss Ltrain is the combination of the original loss, auxiliary loss Lauxiliary, and regularization Lhidden, with coefficients α, β.
  Ltrain = Loriginal + αLauxiliary + βLhidden
  We train the model in end-to-end manner. This can be a standard training for neural networks.
  θ̂, φ̂, ψ̂ = argmin θ,φ,ψ
  Ltrain(X,Y, θ, φ, ψ)
  After training, we store hidden representations for M training samples. They are used to restrict test representation manifold during inference.
  Memm = g(Xm; φ̂), ∀m = 1, . . . ,M
sections.heading: 4.3 INFERENCE
sections.text: We use optimization to acquire hidden representations during inference. Given a test sample X , the model predicts its output Ŷ . We use the auxiliary network h(H; ψ̂) to search for hidden representations H so that h can output X̂ that is close to the original intput X . This can be achieved by optimization on H with auxiliary loss Lauxiliary. The initial value H init is the output of extractor g: H init = g(X; φ̂).
  We also add a manifold regularization term Lmanf to constrain each hidden representation to lie in the corresponding training manifold. For a test sample, we compute the minimum of L2 distance between each of its hidden representation Hk and the corresponding representations in memory Memmk . We
  then use the sum of the distances as regularization.
  Lmanf(H) = K∑ k=1 min m=1,...,M L2(Hk,Memmk )
  Inference loss Linfer is the combination of auxiliary loss and the regularization, with γ as a coefficient.
  Linfer(X,H) = Lauxiliary(X, X̂) + γLmanf(H)
  Then, we obtain the hidden representations by optimization.
  Ĥ = argmin H
  Linfer(X,H), H0 = H init
  We get prediction from the optimized hidden representations: Ŷ = f(Ĥ; θ̂).
sections.heading: 5 EXPERIMENTS
sections.text: In this section, we show examples that, given a model with compositionality in training distribution, the compositionality does not transfer to test distributions, and how the proposed approach is applied to these cases. As our focus is orthogonal with learning compositional model in training distribution, we obtain this model by directly providing true labels for each compositional component during training. Then we evaluate the transferability to test distribution.
  Since this is the first work for the transferability problem of compositionality, we do not have previous baselines, so that we use standard deep neural network models as baselines, and also compare with variations of the proposed approach. The main changes of the proposed approach include using noise, auxiliary network and manifold regularization. A variation removes one of these changes, so it is also an ablation experiment. The details of hyper parameters and experiment settings can be found in Appendix A. For all the experiments, we use accuracy as metric. A prediction is correct if and only if all the components are correctly predicted. We repeat each experiment five times and report mean and variance.
sections.heading: 5.1 EXPERIMENTS ON OVERLAPPING DIGITS
sections.text: The first experiment is on overlapping hand written digit recognition, as shown in Figure 1. We construct the dataset from MNIST (LeCun et al., 1998). A sample is made by overlapping and taking the average of two original images, the first one in its original form, and the second flipped over up-left to down-right diagonal. The output is a vector of the two labels Y = Y1, Y2 (not exchangeable). Each original label has 10 possible values, so the output has 100 possible values. To evaluate compositional generalization, we use different distributions in training and test. In train, the sum of the two labels is even, i.e. (Y1 + Y2) mod 2 = 0. In test, the sum is odd.
  As a baseline, we use a standard neural network with two sub networks, each for an output. Each of the network is a three layer convolutional neural network. We train the model with cross entropy on both outputs.
  The proposed method uses an auxiliary network that takes hidden layer as input and outputs the reconstruction of the original input. The auxiliary network has two sub-networks each with one
  Input Outputs Hidden januarymarch 0, 2 january march februaryoctober 1, 9 february october januaryfebruary 0, 1 january february augustmay 7, 4 august may
  Table 2: Examples of compound word experiments. The output labels align with corresponding hidden words. Upper is train, lower is test.
  hidden representation as input. Each sub-network is a three layer trans-convolutional neural network, and we average the outputs to recover the original input. We use L2 loss as the auxiliary loss.
  We also collect human performance data through crowd sourcing. There are 27 participants, and each person works on 20 fixed samples randomly selected from test data. Please refer to Appendix B for more details.
  The results in Table 1 (left) show that the proposed method has significant improvement over the baseline by about 20% absolute increase, and it also outperforms humans. The ablation study shows that performances drop in the experiments, indicating that all the modifications in the proposed approach are necessary to achieve the result.
sections.heading: 5.2 EXPERIMENTS ON COMPOUND WORDS
sections.text: We also conduct experiments for language processing. Language has natural units of words, which have consistent information across different distributions. So we design a setting that we cannot use this property. We consider a problem that converts a compound word to two words. We construct compound words from two month names (January to October), e.g. “julyfebruary”. The output label is the zero-based index of the month (0 for January). We have each character as an input unit, and assign a one-hot representation to it. Other problem settings are the same as previous one. Please see Table 2 for more examples.
  In baseline, We use two feed forward neural networks, each for an output. For the auxiliary network, we also use two feed forward neural networks, and average their outputs. Each feed forward network has three hidden layers. The training and other settings for baseline, proposed approach and ablations are the same as the previous experiment.
  The results listed in Table 1 (middle) demonstrate that the proposed method is significantly better than the baseline by around 24% absolute increase. We find removing manifold regularization in ablation study shows slight improvement over the proposed approach. Other ablation experiments have significant reductions. This might be because regularizing manifold is not important when inputs (characters) are discrete.
sections.heading: 5.3 EXPERIMENTS ON COLORED DIGITS
sections.text: We also explore the capability of the proposed approach to another hand written digit problem with different types of components: digits and colors. We construct the dataset from MNIST (LeCun et al., 1998) by changing the color of digits. We use digit label Y1 as a component (0-9), and color label Y2 as another (0-2). Color label is 0, 1, 2 for red, blue, green, respectively. In training, we use label combinations with: Y1 mod 3 6= Y2. In test, we use the rest of the combinations. Please refer to Figure 3 for examples.
  We use two compositional neural networks for each output, respectively. Each network has three hidden layers. For the auxiliary network, we concatenated the hidden representation as input, and use a three layer trans-convolutional neural network. Other settings for the methods and ablation are the same as the overlapping digit experiment.
  The results shown in Table 1 (right) demonstrate that the proposed method is significantly better than the baseline by more than 40% absolute increase. It also outperforms the ablations, indicating
  that all the modifications are necessary. Among them, auxiliary network contributes the most to the performance improvement.
sections.heading: 6 DISCUSSIONS
sections.text: In this section, we perform visualization and error analysis to better understand the experimental results and the behavior of the proposed approach.
sections.heading: 6.1 DISTRIBUTION VISUALIZATION
sections.text: We visualize hidden representations of both baseline and the proposed approach for overlapping digit experiments (Figure 6). We use t-SNE (Maaten & Hinton, 2008) to reduce each of two hidden representations to one dimension, and jointly plot them along horizontal and vertical coordinates, respectively. Training samples are blue, and test samples are orange.
  Our expectation is a chess board like distribution, similar to the true underlying distribution (Figure 4). Note that though there are 10 labels, the expected results may not be 10× 10 colored blocks, because the labels, along with the representation, may not be in order (e.g. switching label 5, 6 reduces two blocks lines), and the first and the second hidden representations may differ for the same digit.
  We find the visualization of the proposed approach (Figure 6b) is closer to the expectation than the baseline one (Figure 6a). The proposed approach has less empty areas, indicating that it can recombine the components in the out-of-distribution setting. This analysis demonstrates that the proposed approach works in the expected way.
sections.heading: 6.2 SAMPLE VISUALIZATION
sections.text: We also hope to visualize concrete samples for the proposed approach. Since we have the auxiliary network with two sub-networks for each hidden component representation, we visualize their outputs, and compare with the ground-truth (Figure 7). The result shows that the original input and hidden components are reasonably recovered for both training and test samples. This means that the proposed approach is able to extract information for each component in training distribution, and transfer the ability in test distribution.
sections.heading: 6.3 TRANSFER ERROR ANALYSIS
sections.text: We analyze errors to show that the inference optimization process helps addressing the transfer problem. When the model makes mistakes in test, the predicted output may correspond to indistribution or out-of-distribution label pairs. We investigate how frequent errors are associated with the distribution transfer. We define a metric of Transfer Error Rate (TER) to measure this. It is the
  number of errors predicted to be in wrong distribution, over all errors. In this setting, the sum of labels is odd in test, and even in training, so TER is the number of errors with even predicted label sum over all errors. If this rate is high (100% is upper bound by definition), it means that most of errors are associated with transfer. If it is around 50%, it means that the errors are balanced in distributions.
  TER is 89.5±0.7% for baseline, and 68.3±2.8% for the proposed approach, with 500 test samples. Also, before the inference optimization in the proposed approach, the value is 88.8±2.0%. The results show that the baseline has most of the errors to be transfer error, and the propose approach reduces it significantly. Also, the reduction is during optimization in inference, because the value is close to baseline before optimization. This indicates that the proposed approach is effective to reduce TER, and optimization is an important factor for it. Please refer to Figure 5 for more details.
sections.heading: 7 CONCLUSION
sections.text: In this paper, we discuss our finding that compositionality does not transfer naturally from training to test data distributions. We further propose to address this problem with an auxiliary reconstruction network and a regularized optimization procedure during the inference stage. Experimental results show that the proposed approach has more than 20% absolute increase in various experiments comparing with baselines, and even outperforms human on the overlapping digit recognition task. We hope this work would reshape our thoughts on transferability of compositionality and help to advance compositional generalization and artificial intelligence research.
sections.heading: A EXPERIMENT SETTINGS
sections.text: A.1 EXPERIMENTS ON OVERLAPPING DIGITS
  The data of overlapping digits experiment are generated from MNIST dataset (LeCun et al., 1998), which contains 60,000 training data and 10,000 test data. We use the original training data in training and the original test data in test. In training, we use the combinations with even label sum. In test, we use the combinations with odd label sum (evaluation on test distribution). As a reference, we also use the combinations with even label sum (evaluation on training distribution).
  Each input image has a shape of 28× 28× 3 for height, width and depth. Extraction network g(·;φ) has two convolutional neural sub-networks. Each of them has three convolutional layers. The first convolutional layer has 3 × 3 kernel and 1 × 1 strides with 32 depth and ReLU activation. It is followed by a max pooling layer with 2× 2 kernel and 1× 1 strides. The second convolutional layer has 3×3 kernel and 1×1 strides with 64 depth and ReLU activation. Then the representation is flatten and fed to a fully connected neural network with 32 hidden nodes and linear activation. Prediction network f(·; θ) has a single layer fully connected neural network with Softmax activation for each pair of hidden representation and output. Auxiliary network h(·;ψ) has two trans-convolutional neural networks. A hidden representation is converted to 7× 7× 32 representation (width, height, depth) by a fully connected neural network with ReLU activation. The first trans-convolutional layer has 3× 3 kernel and 2× 2 strides with 64 depth, SAME padding and ReLU activation. The second trans-convolutional layer has 3× 3 kernel and 2× 2 strides with 32 depth, SAME padding and ReLU activation. The third trans-convolutional layer has 3× 3 kernel and 1× 1 strides with 1 depth, SAME padding and linear activation.
  For the hyper parameters, we use α = 1, β = 0.3, γ = 0.03, η = 1, M = 500. In training optimization, we use Adam optimizer (Kingma & Ba, 2014) for 1,000 steps with batch size 500 and learning rate 0.001. In inference optimization, we also use Adam optimizer for 100 steps with batch size 500 and learning rate 0.3. We find the memory size M does not change the result significantly. We have 69.0±0.6% for M = 100, 68.2±1.0% for 300, 69.4±0.3% for 500 (reported), 69.6±0.5% for 700 and 69.9±0.4% for 900 (Figure 8).
  A.2 EXPERIMENTS ON COMPOUND WORDS
  In the compound words experiment, we have inputs with different lengths. We first patch an additional character symbol to make all inputs the same length of 18. Then, we convert each character to a onehot representation with size 27. we use three layer fully connected neural networks as sub-networks for extractor. The input is flatten and fed to each sub-network. The first layer has 96 hidden nodes with ReLU activation. The second layer has 64 hidden nodes with ReLU activation. The third layer has 32 hidden nodes with linear activation. Prediction network is a single layer fully connected network with Softmax activation for each pair of hidden representation and output. The auxiliary network also has two three layer fully connected sub-networks. The first layer has 64 hidden nodes
  with ReLU activation. The second layer has 96 hidden nodes with ReLU activation. The third layer has 486 hidden nodes with linear activation. Then the nodes are reshaped to 18× 27. For the hyper parameters, we use α = 1, β = 0.1, γ = 0.01, η = 1, M = 500. In training optimization, we use Adam optimizer for 1,000 steps with batch size 500 and learning rate 0.001. In inference optimization, we also use Adam optimizer for 100 steps with batch size 500 and learning rate 0.3.
  A.3 EXPERIMENTS ON COLORED DIGITS
  The data for colored digits experiment are created from MNIST dataset. Each input image is in shape of 28 × 28 × 3 for height, width and depth. The extractor has two sub-networks, each has three convolutional layers. The first convolutional layer has 3× 3 kernel and 1× 1 strides with 32 depth and ReLU activation. A max pooling layer follows it with 2× 2 kernel and 1× 1 strides. The second convolutional layer has 3× 3 kernel and 1× 1 strides with 64 depth and ReLU activation. Then the representation is flatten and fed to a fully connected neural network with 32 hidden nodes with linear activation. Prediction network has a fully connected network for each pair of hidden representation and output with Softmax activation. For auxiliary network, we first concatenate the hidden representations to have 64 nodes. It is then converted to 7 × 7 × 32 representation (width, height, depth) by a fully connected neural network with ReLU activation. The first trans-convolutional layer has 3× 3 kernel and 2× 2 strides with 64 depth, SAME padding and ReLU activation. The second trans-convolutional layer has 3× 3 kernel and 2× 2 strides with 32 depth, SAME padding and ReLU activation. The third trans-convolutional layer has 3× 3 kernel and 1× 1 strides with 3 depth, SAME padding and linear activation.
  For the hyper parameters, we use α = 1, β = 0.3, γ = 0.03, η = 1, M = 500. In training optimization, we use Adam optimizer for 1,000 steps with batch size 500 and learning rate 0.001. In inference optimization, we also use Adam optimizer for 100 steps with batch size 500 and learning rate 0.3.
sections.heading: B CROWD SOURCING FOR HUMAN PERFORMANCE
sections.text: We collect data on human performance through crowd-sourced survey. The survey has training and test sections. We select 20 images uniformly at random from the training distribution as training data. We also select 20 images uniformly at random from the test distribution as test data (Figure 9). In the training section we state that each picture is an overlap of two pictures containing two numbers. Then we ask survey takers to discover the rule through the training examples before they answer questions. In the test section we put up test images, and two multiple-selection (0-9) list boxes under each image. Then we ask the survey takers to identify the correct answers. In this survey we had 27 responses. The mean test accuracy is 10.0% with standard deviation of 7.7%.