summaries: the paper investigates what neural networks learn when trained with gradient descent, in case parts of the inputs are only partially relevant to the output. The main claim is that GD is what prevents compositionality. In a set of synthetic experiments it is shown that indeed GD learns to use all information in the input, which results in poor generalization ood when only a subset of it was relevant. This work analyzes the effect of gradient descent training on the compositionality of the learned model. It is shown that the gradient descent would use all the available information, even when it is redundant to learn the mapping from input to the output. It is then argued that the gradient descent training has the bias against compostionality despite the model architecture. Experiments are conducted on three simple benchmarks to demonstrate that when gradient descent trained model would use redundant information and not generalize compositionally.  This paper addresses the effects of gradient descent methods onto compositionality and compositional generalization of models. The authors claim that the optimization process imposes the models to deviate compositionality, which is defined with conditional independence among random variables of input, predicted output and the ground-truth. Since compositionality is one of important features of human intelligence, it has been interested widely in the field of AI/ML such as vision, language, neuro-symbolic approaches, common sense reasoning, disentangled representation, and the emergence conditions of compositionality. As it has been not much focused on the relationship with optimizers, it is fresh and interesting. However, it is not easy to figure out the position of this paper from two reasons: (1) the definitions on compositionality in this paper are not so compatible with recent related works, which mostly consider certain structures in models [ICLR19, JAIR20] or representative problems such as visual reasoning [CVPR17] and Raven progressive matrices [PNAS17]. (2) The authors do not consider quantitative approaches such as compositionality [ICLR19] or compositional generalization [ICLR20]. 
abstractText: In this paper, we argue that gradient descent is one of the reasons that make compositionality learning hard during neural network optimization. We find that the optimization process imposes a bias toward non-compositional solutions. This is caused by gradient descent, trying to use all available and redundant information from input, violating the conditional independence property of compositionality. Based on this finding, we suggest that compositionality learning approaches considering only model architecture design are unlikely to achieve complete compositionality. This is the first work to investigate the relation between compositional learning and gradient descent. We hope this study provides novel insights into compositional generalization, and forms a basis for new research directions to equip machine learning models with such skills for human-level intelligence. The source code is included in supplementary material.
references.authors: Vanhoucke Vijay Vasudevan Fernanda Viégas Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu Xiaoqiang Zheng
references.title: TensorFlow: Large-scale machine learning on heterogeneous systems
references.authors: Jacob Andreas Marcus Rohrbach Trevor Darrell Dan Klein
references.title: Neural module networks
references.venue: In IEEE Conference on Computer Vision and Pattern Recognition
references.authors: Dzmitry Bahdanau Shikhar Murty Michael Noukhovitch Thien Huu Nguyen Harm de Vries Aaron Courville
references.title: Systematic generalization: What is required and can it be learned
references.venue: In International Conference on Learning Representations,
references.authors: Anas Barakat Pascal Bianchi
references.title: Convergence analysis of a momentum algorithm with adaptive step size for non convex optimization
references.authors: Yoshua Bengio
references.title: The consciousness prior
references.venue: arXiv preprint arXiv:1709.08568,
references.authors: Leon Bottou Frank E Curtis Jorge Nocedal
references.title: Optimization methods for large-scale machine learning
references.venue: SIAM Review,
references.authors: Paco Calvo John Symons
references.title: The Architecture of Cognition: Rethinking Fodor and Pylyshyn’s Systematicity Challenge
references.authors: Xiangyi Chen Sijia Liu Ruoyu Sun Mingyi Hong
references.title: On the convergence of a class of adam-type algorithms for non-convex optimization
references.venue: arXiv preprint arXiv:1808.02941,
references.authors: Thomas M Cover
references.title: Elements of information theory
references.authors: Soham De Anirbit Mukherjee Enayat Ullah
references.title: Convergence guarantees for rmsprop and adam in non-convex optimization and an empirical comparison to nesterov acceleration
references.venue: arXiv preprint arXiv:1807.06766,
references.authors: John Duchi Elad Hazan Yoram Singer
references.title: Adaptive subgradient methods for online learning and stochastic optimization
references.venue: JMLR, 12:2121––2159,
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: Anirudh Goyal Alex Lamb Jordan Hoffmann Shagun Sodhani Sergey Levine Yoshua Bengio Bernhard Schölkopf
references.title: Recurrent independent mechanisms
references.venue: arXiv preprint arXiv:1909:10893v2,
references.authors: Alex Graves Greg Wayne Ivo Danihelka
references.title: Neural turing machines
references.venue: arXiv preprint arXiv:1410.5401,
references.authors: K. He X. Zhang S. Ren J. Sun
references.title: Deep residual learning for image recognition
references.authors: Mikael Henaff Jason Weston Arthur Szlam Antoine Bordes Yann LeCun
references.title: Tracking the world state with recurrent entity networks
references.venue: arXiv preprint arXiv:1612.03969,
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: Drew A Hudson Christopher D Manning
references.title: Gqa: A new dataset for real-world visual reasoning and compositional question answering
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Xisen Jin Junyi Du Xiang Ren
references.title: Visually grounded continual learning of compositional semantics
references.venue: arXiv preprint arXiv:2005.00785,
references.authors: Daniel Keysers Nathanael Schärli Nathan Scales Hylke Buisman Daniel Furrer Sergii Kashubin Nikola Momchev Danila Sinopalnikov Lukasz Stafiniak Tibor Tihon Dmitry Tsarkov Xiao Wang Marc van Zee Olivier Bousquet
references.title: Measuring compositional generalization: A comprehensive method on realistic data
references.venue: In International Conference on Learning Representations,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: arXiv preprint arXiv:1412.6980,
references.authors: Louis Kirsch Julius Kunze David Barber
references.title: Modular networks: Learning to decompose neural computation
references.venue: In Advances in Neural Information Processing Systems,
references.authors: A. Krizhevsky I. Sutskever G.E. Hinton
references.title: Imagenet classification with deep convolutional neural networks
references.venue: In NIPS,
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: 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: Shuai Li Wanqing Li Chris Cook Ce Zhu Yanbo Gao
references.title: Independently recurrent neural network (indrnn): Building a longer and deeper rnn
references.venue: In the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Xiang Lisa Li Jason Eisner
references.title: Specializing word embeddings (for parsing) by information bottleneck
references.venue: In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and 9th International Joint Conference on Natural Language Processing,
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: Yuanpeng Li Liang Zhao Kenneth Church Mohamed Elhoseiny
references.title: Compositional continual language learning
references.venue: In International Conference on Learning Representations,
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: Zhi-Quan Luo
references.title: On the convergence of the lms algorithm with adaptive learning rate for linear feedforward networks
references.venue: Neural Computation,
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: Boris T. Polyak Anatoli B. Juditsky
references.title: Acceleration of stochastic approximation by averaging
references.venue: SIAM J. Control Optim.,
references.authors: Sashank J Reddi Satyen Kale Sanjiv Kumar
references.title: On the convergence of adam and beyond
references.venue: In ICLR,
references.authors: Clemens Rosenbaum Ignacio Cases Matthew Riemer Tim Klinger
references.title: Routing networks and the challenges of modular and compositional computation
references.authors: David E Rumelhart Geoffrey E Hinton Ronald J Williams
references.title: Learning representations by back-propagating
references.venue: errors. nature,
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: Adam Santoro Ryan Faulkner David Raposo Jack W. Rae Mike Chrzanowski Theophane Weber Daan Wierstra Oriol Vinyals Razvan Pascanu Timothy P. Lillicrap
references.title: Relational recurrent neural networks
references.venue: arXiv preprint arXiv:1806.01822,
references.authors: Noam Shazeer Azalia Mirhoseini Krzysztof Maziarz Andy Davis Quoc Le Geoffrey Hinton Jeff Dean
references.title: Outrageously large neural networks: The sparsely-gated mixture-of-experts layer
references.venue: arXiv preprint arXiv:1701.06538,
references.authors: Daniel Smilkov Shan Carter
references.title: Deep playground. online demo, 2016
references.venue: URL https://github. com/tensorflow/playground
references.authors: Alon Talmor Oyvind Tafjord Peter Clark Yoav Goldberg Jonathan Berant
references.title: Teaching pre-trained models to systematically reason over implicit knowledge
references.venue: arXiv preprint arXiv:2006.06609,
references.authors: Tijmen Tieleman Geoffrey Hinton
references.title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude
references.venue: COURSERA: Neural networks for machine learning,
references.authors: Rachel Ward Xiaoxia Wu Leon Bottou
references.title: Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization
references.venue: arXiv preprint arXiv:1806.01811,
references.authors: Y. Wu
references.title: Google’s neural machine translation system: Bridging the gap between human and machine translation
references.venue: In arXiv:1609.08144,
references.authors: D. Yu L. Deng
references.title: Automatic Speech Recognition
references.authors: Matthew D Zeiler
references.title: Adadelta: an adaptive learning rate method
references.venue: arXiv preprint arXiv:1212.5701,
references.authors: Dongruo Zhou Yiqi Tang Ziyan Yang Yuan Cao Quanquan Gu
references.title: On the convergence of adaptive gradient methods for nonconvex optimization
references.venue: arXiv preprint arXiv:1808.05671,
references.authors: Fangyu Zou Li Shen
references.title: On the convergence of adagrad with momentum for training deep neural networks
references.venue: arXiv preprint arXiv:1808.03408,
references.authors: Fangyu Zou Li Shen Zequn Jie Weizhong Zhang Wei Liu
references.title: A subgradientcient condition for convergences of adam and rmsprop
references.venue: arXiv preprint arXiv:1811.09358,
sections.text: In this paper, we argue that gradient descent is one of the reasons that make compositionality learning hard during neural network optimization. We find that the optimization process imposes a bias toward non-compositional solutions. This is caused by gradient descent, trying to use all available and redundant information from input, violating the conditional independence property of compositionality. Based on this finding, we suggest that compositionality learning approaches considering only model architecture design are unlikely to achieve complete compositionality. This is the first work to investigate the relation between compositional learning and gradient descent. We hope this study provides novel insights into compositional generalization, and forms a basis for new research directions to equip machine learning models with such skills for human-level intelligence. The source code is included in supplementary material.
sections.heading: 1 INTRODUCTION
sections.text: Compositional generalization is the algebraic capacity to understand and produce many novel combinations from known components (Chomsky, 1957; Montague, 1970), and it is a key element of human intelligence (Minsky, 1986; Lake et al., 2017) to recognize the world efficiently and create imagination. Broadly speaking, compositional generalization is a class 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. For example, in the image domain, an object is a combination of multiple parts or properties. In the language domain, a sentence is a combination of syntax and semantics. Each component of an output depends only on the corresponding input component, but not on other variables. We call this the conditional independence property, and will formally introduce in Section 3.
  People hope to design machine learning algorithms with compositional generalization skills. However, conventional neural network models generally lack such ability. There have been many attempts to equip models with compositionality (Fodor & Pylyshyn, 1988; Bahdanau et al., 2019), and most efforts focus on designing neural network architectures (Graves et al., 2014; Andreas et al., 2016; Henaff et al., 2016; Shazeer et al., 2017; Li et al., 2018; Santoro et al., 2018; Kirsch et al., 2018; Rosenbaum et al., 2019; Goyal et al., 2019). Recently, multiple approaches showed progress in specific tasks (Li et al., 2019; 2020; Lake, 2019; Russin et al., 2019), but we still do not know why standard approaches seldom achieve good compositionality in general.
  In this paper, we argue that there is a bias to prevent parameters from reaching compositional solutions, when we use gradient descent in optimization (please see Figure 1 for illustrations). This is because gradient seeks the steepest direction, so that it uses all possible and redundant input information, which contradicts to the conditional independence property of compositionality. This problem is not due to how gradient is computed, such as back propagation, but caused by the essential property of gradient. We derive theoretical relation between gradient descent and compositionality with information theory. We also provide examples and visualization to show the detailed process of how gradient resists compositionality. Based on the finding, we propose that compositionality learning approaches with model structure design (manual or searching) alone are not likely to achieve complete compositionality.
  We hope this research provides new insights and forms a basis for new research directions in compositional generalization, and helps to improve machine intelligence towards human-level. The contributions of this paper can be summarized as follows.
  • The novelty of this work is to find the relation between compositional learning and gradient descent in optimization process, i.e., gradient descent resists compositionality.
  • We theoretically derive the result and explain why standard approaches with architecture design alone do not address compositionality.
sections.heading: 2 RELATED WORK
sections.text: Compositionality Humans learn language and recognize the world in a flexible way by leveraging systematic compositionality. The compositional generalization is critical in human cognition (Minsky, 1986; Lake et al., 2017), and it helps humans to connect limited amount of learned concepts for unseen combinations. Though deep learning has many achievements in recent years (LeCun et al., 2015; Krizhevsky et al., 2012; Yu & Deng, 2012; He et al., 2016; Wu & et al, 2016), compositional generalization has not been well addressed (Fodor & Pylyshyn, 1988; Marcus, 1998; Fodor & Lepore, 2002; Marcus, 2003; Calvo & Symons, 2014).
  There are observations that current neural network models do not learn compositionality (Bahdanau et al., 2019). Most recently, multiple approaches are proposed to address compositionality in neural networks (Li et al., 2019; 2020; Lake, 2019; Russin et al., 2019) for specific tasks. However, we are still not sure why compositionality is hard to achieve in general cases, and this work discusses about this problem from optimization perspective.
  Another line of related work is independent disentangled representation learning (Higgins et al., 2017; Locatello et al., 2019). 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 refer to Section 3).
  Compositionality is applied in different areas such as continual learning (Jin et al., 2020; Li et al., 2020), question answering (Andreas et al., 2016; Hudson & Manning, 2019; Keysers et al., 2020), and reasoning (Talmor et al., 2020).
  Gradient Descent Gradient descent is a powerful and general purpose optimization tool for solving large scale problems in deep neural networks. It is usually used in a stochastic way (Stochastic Gradient Descent) with mini-batches, and has many variations such as Momentum (Rumelhart et al., 1986), averaging (Polyak & Juditsky, 1992), AdaGrad (Duchi et al., 2011), AdaDelta (Zeiler, 2012), RMSProp (Tieleman & Hinton, 2012), Adam (Kingma & Ba, 2014).
  Most of the previous work focus on faster reduction of loss and theoretical convergence analysis of SGD (Bottou et al., 2018; Luo, 1991; Reddi et al., 2018; Chen et al., 2018; Zhou et al., 2018; Zou & Shen, 2018; De et al., 2018; Zou et al., 2018; Ward et al., 2018; Barakat & Bianchi, 2019). In particular, this work focuses on investigating why standard neural network training only achieves limited level of compositionality by studying the relationship between gradient descent and compositionality.
sections.heading: 3 CONCEPTS FOR COMPOSITIONALITY AND GRADIENT DESCENT
sections.text: We first formulate compositionality using the conditional independence property, and define compositional generalization. We then review properties of gradient for the derivation in the next section.
  Conditional Independence Property for Compositionality When multiple hidden variables live in the same representation, and cannot be separated by simply splitting the representation, then these variables are entangled in the representation. For example, color and shape are two hidden variables and they share the same representation of image. Also, syntax and semantics are two hidden variables and they share the same representation of sentence. When we extract the hidden variables from their shared representation, we disentangle them.
  We then consider a prediction problem, where input X and output Y have multiple entangled components that are not labeled in data, and they are aligned. For example in machine translation, X1 is input syntax, and X2 is input semantics. Y1 is output syntax, and Y2 is output semantics. The syntax of output Y1 depends only on the syntax of input X1, and the semantics of output Y2 depends only on the semantics of X2. We can formalize the alignments as conditional independence property: Yi depends only on Xi.
  ∀i : P (Yi|X1, . . . , XK , Y1, . . . , Yi−1, Yi+1, . . . , YK) = P (Yi|Xi).
  When a model fits this property, we say it has compositionality. Note that this can be understood as a kind of sparseness property (Bengio, 2017), because it restricts effective connection between input and output components.
  Compositional Generalization In compositional generalization, each sample in either training or test is a combination of several components. A test sample has a combination that does not appear in training, but each component of the test sample appears in training. We need to recombine the seen components to generalize to the test sample. We can define compositional generalization probabilistically as follows.
  In train, In test, ∀i : P (Xi) > 0, P (X1, . . . , XK) = 0, P (X1, . . . , XK) > 0, ∀i : P (Yi|Xi) is high. P (Y1, . . . , YK |X1, . . . , XK) is predicted high.
  Compositionality bridges the gap between training and test distributions to achieve compositional generalization. We first apply chain rule, and then use compositionality as follows.
  P (Y1, . . . , YK |X1, . . . , XK) = K∏ i=1 P (Yi|X1, . . . , XK , Y1, . . . , Yi−1) = K∏ i=1 P (Yi|Xi).
  When P (Yi|Xi) are all high, their product should also be high. Therefore, a model with compositionality—satisfying this conditional independence property—addresses compositional generalization.
  Property of Gradient For a function f(x1, . . . , xK), the gradient∇f is the steepest direction to change the function’s value. Generally, gradient descent methods estimate ∇f using low-order local estimation. By definition, it is the vector of partial derivatives with respective to the inputs.
  ∇f = ∂f ∂x1 , . . . , ∂f ∂xK
  We will use the following definition in later arguments.
  Definition 1 (Partial derivative). Partial derivative for an input is the derivative assuming other inputs are constant.
  ∀i = 1, . . . ,K : ∂f(x1, . . . , xK) ∂xi = df(c1, . . . , xi, . . . , cK) dxi
sections.heading: 4 GRADIENT DESCENT RESISTS COMPOSITIONALITY
sections.text: We focus on the early phase of training to show that gradient descent causes a model to use the redundant information to compute output when it has information to reduce the loss. We develop the arguments step by step. We first analyze the influence of the input on an output variable. We then consider the case of entangled inputs and one output. Finally, we discuss the case with entangled inputs and entangled outputs.
  The gradient is used to reduce loss, so we aim to relate loss reduction and the influence from input to output. To do that, we use mutual information to describe the influence, and use knowledge from information theory (Definition 2, Theorem 1 and Theorem 2). We also study the impact of gradient descent to the influence, so we relate mutual information with gradient with Proposition 1.
  Definition 2 (Markov chain (Cover, 1999) p.34). Random variables X, Y, Z are said to form a Markov chain in that order (denoted by X → Y → Z) if the conditional distribution of Z depends only on Y and is conditionally independent of X .
  Theorem 1 (Data-processing inequality (Cover, 1999) p.34). If X → Y → Z, then I(X;Y ) ≥ I(X;Z).
  Theorem 2 (Chain rule for information (Cover, 1999) p.24). For random variables X,Y, Z, I(X,Y ;Z) = I(Y ;Z|X) + I(X;Z).
  Proposition 1. When ∂Y∂X is defined, I(X;Y ) > 0 ⇐⇒ ∂Y ∂X 6= 0
  Proof. I(X;Y ) > 0 means X and Y are not independent, which means Y is not invariant to X .
sections.heading: 4.1 ONE INPUT AND ONE OUTPUT
sections.text: We first consider a basic setting that the data has a single input X and output Y . A model f with parameters θ has input X and output Ŷ (Figure 2 middle). We optimize a loss function L. Applying the gradient ∇θL(Y, Ŷ ) reduces L(Y, Ŷ ), bringing Y and Ŷ closer. Since Y changes according to X , Ŷ is encouraged to change according to X . We look into details as follows.
  In the common supervised learning setting, givenX , the ground truth Y does not depend on prediction Ŷ , which means they form a Markov chain Ŷ → X → Y . We do not require specific form of the loss function, L, but we assume that when it is reduced, Ŷ moves closer to Y , and increases the mutual information I(Ŷ , Y ). Many widely used loss functions encourage increased mutual information between model output and dataset labels. Also, training algorithms are designed to reduce loss when the input has information to do so. These assumptions are likely to hold especially in the early part of training. We also use local linear approximation when discussing gradients, i.e. dx = ∆x. We derive the proof by studying relations between random variables, and show that gradient descent increases the lower bound of mutual information between model input and output, hence the output is dependent on the input.
  Proposition 2. If a small change of parameters ∆θ increases I(Y ; Ŷθ), then I(X; Ŷθ+∆θ) is positive with parameters θ + ∆θ. ∀∆θ : ∆I(Y ; Ŷθ) > 0 =⇒ I(X; Ŷθ+∆θ) > 0.
  Proof. Since Y and Ŷ are conditionally independent given X , i.e., Ŷ → X → Y , with dataprocessing inequality (Theorem 1), I(Ŷ ;X) ≥ I(Ŷ ;Y ). So I(Y ; Ŷθ+∆θ) is a lower bound of I(X; Ŷθ+∆θ). By definition, ∆I(Y ; Ŷθ) = I(Y ; Ŷθ+∆θ) − I(Y ; Ŷθ), so that I(Y ; Ŷθ+∆θ) = I(Y ; Ŷθ) + ∆I(Y ; Ŷθ). We also have I(Y ; Ŷθ) ≥ 0 by definition. Therefore I(Y ; Ŷθ+∆θ) > 0.
  I(X; Ŷθ+∆θ) ≥ I(Y ; Ŷθ+∆θ) = I(Y ; Ŷθ) + ∆I(Y ; Ŷθ) > 0
  Proposition 3. If X has information to reduce loss L(Y, Ŷ ), ∂Ŷ∂X 6= 0 for updated parameters.
  Proof. Since training algorithm reduces loss, with local linear approximation, gradient descent reduces loss. This increases mutual information, so that Proposition 2 applies. So we have I(X; Ŷθ+∆θ) > 0. With Proposition 1, we have ∂Ŷ∂X 6= 0 for the updated parameters θ + ∆θ.
sections.heading: 4.2 ENTANGLED INPUT AND ONE OUTPUT
sections.text: Then, we study the case where input X is entanglement of multiple hidden input components X1, . . . , XK , and output is a single variable Ŷ that depends only on Xi. We hope to make Ŷ invariant to Xj ,∀j 6= i. For example, in a parsing task (Li & Eisner, 2019), output parse tree Y depends only on the input syntax X1, but not on input semantics X2.
  For the convenience of analysis, we assume we have a fixed differentiable oracle encoder network g and decoder network g−1. g−1 maps X to X1, . . . , XK , and g maps them back.
  X = g(X1, . . . , XK) X1, . . . , XK = g −1(X)
  We extend the model structure with g and g−1 and use the input to g−1 as model input (Figure 2 left and middle).
  Ŷ = fθ ◦ g ◦ g−1(X)
  This model is exactly the same as the original one, because there is no additional trainable parameters, and g ◦ g−1 does not change X .
  Proposition 4. If Xi has information to reduce loss L(Y, Ŷ ), ∂Ŷ∂Xi 6= 0 for updated parameters.
  Proof. With the property of gradient (Definition 1), we can regard Xj ,∀j 6= i as constant values when computing the gradient w.r.t. Xi. So, with linear approximation, Proposition 3 applies.
sections.heading: 4.3 ENTANGLED INPUT AND ENTANGLED OUTPUT
sections.text: We then discuss the case that output Y is also the entanglement of Y1, . . . , YK . Yi depends only on Xi for all i = 1, . . . ,K. This corresponds to the example of machine translation.
  We assume we have a fixed differentiable oracle encoder network h and decoder network h−1. h takes Ŷ as input and produce K outputs Ŷ1, . . . , ŶK = h(Ŷ ), and h maps them back. We extend the model structure with h and h−1 (Figure 2).
  Ŷ = h ◦ h−1 ◦ fθ ◦ g ◦ g−1(X)
  This model is the same as the original one, because there is no additional trainable parameters and h ◦ h−1 does not change Ŷ . We derive proof with this extended model. The intuitive idea is that the reduction of loss will make each Yi contain more information of Y , and for each Yi, we can apply previous discussion. We denote Ŷ6=i = Ŷ1, . . . , Ŷi−1, Ŷi+1, . . . , ŶK .
  Proposition 5. If Xj has information to reduce loss L(Y, Ŷ ) through the change of Ŷi, then ∂Ŷi∂Xj 6= 0,∀j 6= i for updated parameters.
  Proof. We first use chain rule of gradient to separate the gradient to sum ofK terms, each corresponding to a Ŷi: ∂L∂θ = ∑K i=1 ∂Ŷi ∂θ ∂L ∂Ŷi . We look at a term for ∂Ŷi∂θ ∂L ∂Ŷi . Ŷ6=i are constant when computing
  ∂L ∂Ŷi (Definition 1), and Ŷ6=i are not included in ∂Ŷi∂θ , so that we can treat Ŷ6=i as constant for this term. We then look at the conditional mutual information I(Ŷi;Y |Ŷ6=i) for this term. With chain rule for information (Theorem 2), we have I(Ŷ ;Y ) = I(Ŷi;Y |Ŷ6=i) + I(Ŷ6=i;Y ). Since Y and Ŷ6=i are both fixed, I(Ŷ6=i;Y ) is fixed. So the change of I(Ŷ ;Y ) equals to the change of I(Ŷi;Y |Ŷ6=i). Therefore, the reduction of loss L increases the mutual information for the component. We can then apply Proposition 4. With linear approximation, the change of parameters (∆θ) computed with gradient descent is the sum of changes of parameters (∆θi) for each term, i.e., ∆θ = ∑K i=1 ∆θi. It is unlikely that a ∆θi can be cancelled by the sum of other ∆θj , j 6= i, because each component corresponds to different underlying factors, and they are not contradictory. Hence, this proposition holds.
  In Proposition 4 and Proposition 5, the gradient is not zero, so an output depends on redundant input (Proposition 2) in both cases. Therefore, gradient descent resists conditional independence property of compositionality.
sections.heading: 5 EXAMPLES
sections.text: In this section, we show example cases to emphasize that the theoretical result occurs practically. We focus on the conditional independence property, and we design the experiments in the following way. To test the compositionality, we use different training and test distributions, and the test prediction requires compositional generalization. We measure training and test accuracy to evaluate the ability for compositional generalization.
  We use two settings in each experiment. In the first setting (A), we use both X1 and X2 as input to the model. In the second setting (B), we only use X1, and remove information of X2 by setting it to be a random input. The model architecture and other settings are the same. By comparing the test performance in the two settings, we show that a model can be trained faster with X2, but it does not hold compositionality. We run experiments for 5 times, and plot the mean and variance at each training step.
sections.heading: 5.1 IMAGE CLASSIFICATION
sections.text: We use MNIST dataset (LeCun et al., 1998) in this experiment. The dataset contains pairs of input image and output label. An image is gray scale with fixed size, and a label is in the set of ten possible values {0, 1, . . . , 9}. We use two original samples (X1, Y1), (X2, Y2) to make one sample (X,Y ). X is the horizontal concatenation of X1 and X2, and Y = Y1. Note that a generated sample does not directly use the label of the second sample Y2.
  We have two different settings in the experiment. In the first setting, we have the following data distribution. In training, the data are generated from the original training dataset. The samples are chosen uniformly at random in the corresponding conditions. Y1 is chosen from all possible labels, and X1 with the label is chosen. Y2 is chosen from {Y, Y + 1} (we use modular for labels), and X2 with the label is chosen. In test, the data are generated from the original test dataset. Y1, X1 are chosen in the same way as in training, but Y2 is chosen from the other eight classes {Y +2, Y +3, . . . , Y +9}, and then X2 with the label is chosen. This means, in training, X2 contains a part of information for Y , and X1 contain all information for Y . This is because Y2 is Y with half chance, and Y1 is always Y . We hope the model is trained to make Y not dependent on X2.
  The second setting has the same test distribution as the first setting, but the training distributions are different. In training of the second setting, Y2 is chosen from all possible labels, so that X2 does not have information for Y .
  For both the first and second settings, we use a standard convolutional neural network model with three convolution layers and two fully-connected layers. The details of model design and optimization can be found in Appendix A.
  The results are shown in Figure 3a. The training accuracy improves faster in the first setting than in the second one, indicating that X2 helps to train the model quickly. In the first setting, the gap of training and test accuracy is significantly larger than that in the second setting, meaning the model does not learn compositionality in the first setting. Therefore, this experiment shows that the redundant information X2 is used to help training model quickly, but the model does not learn compositionality.
sections.heading: 5.2 LANGUAGE LEARNING
sections.text: We also run an experiment of instruction language learning with SCAN dataset (Lake & Baroni, 2018). We focus on Jump task, the most difficult task in the dataset. The input is a command instruction, and the output is a corresponding action sequence. The training data include a one-word command “jump”, but other training data do not contain the word. In test data, the word “jump” appears in a multiple-words sentence with other words. Please see Table 1 for examples.
  In this task, syntax and semantics are two entangled components, and it requires compositional generalization to new combinations. Syntax is the way the actions are organized, and semantic is the mapping from word to action. We also design two settings in this experiment. In the first setting, we use the original training and test data, which are from different distributions. In the second setting, we remove the dependency of input semantics to output syntax by using action words uniformly at random, but we still keep the correspondence between input words and output actions.
  We use a standard sequence-to-sequence model with LSTM and attention. More details can be found in Appendix B. Following previous works on SCAN dataset, we use sentence accuracy as the evaluation metric. The results are shown in Figure 3b. We can observe that the training accuracy increases faster during the early training (steps 10-25) in the first setting than in the second setting. Also, the gap of training and test accuracy is significantly larger in the first setting than in the second setting, so the model does not learn compositionality in the first setting.
sections.heading: 6 DISCUSSION
sections.text: We use a simple case to visualize the process for better understanding. We consider two random variables Y1, Y2 ∈ {0, 1}. In training, their joint distribution is uniform on combinations (Y1, Y2) ∈ {(0, 0), (0, 1), (1, 0)}, and zero on (1, 1). In test, (Y1, Y2) = (1, 1). We use uniform noises with range of 1, by subtracting them from the values (Figure 4).
  X1 = Y1 − U [0, 1] X2 = Y2 − U [0, 1] We study a prediction problem with two inputs X1, X2 and one output Y1. This problem has a property that X1 contains entire information of Y1, but X2 only contains part of information of Y1. Y1 can be predicted from X1 alone, and X2 is redundant for Y1. We want to train a model f with parameters θ. f has X1, X2 as input and Ŷ as output: Ŷ = f(X1, X2; θ).
  This problem requires compositional generalization, and the model needs to have compositionality. The model has three fully-connected hidden layers with ReLU activations, and each hidden layer has eight nodes. More details can be found in Appendix C.
  Figure 5 shows the decision boundary for each training step. We see that the initialized parameters at step 0 output wrong predictions for samples in the upper left area, so that the samples in this area are useful to reduce loss, and they push the updated boundary in step 1 to the middle of upper right area. In the following steps, the loss is low and do not change much, so that the boundary remains stable. Therefore, the trained model does not have good compositionality. Note that there can be different solutions for this problem. We use different random seeds, and show that the trained model do not have compositionality (Figure 6).
  This visualization shows an example of process for how the gradient descent makes the model to be non-compositional.
sections.heading: 7 CONCLUSIONS
sections.text: In this paper, we investigate why standard neural network training seldom achieves compositional generalization by studying the relation between compositionality learning and gradient descent during
  training. We find that the optimization process poses a bias towards non-compositional solutions, and this is caused by gradient descent. It tends to use all possible and redundant information from input, so that it violates conditional independence property of compositionality. Based on this study, we suggest that if only model structure design is considered in compositionality learning, it is hard to achieve good compositionality. We hope this finding provides new understanding of compositional generalization mechanisms and helps to improve machine learning algorithms for higher level of artificial intelligence.
sections.heading: B LANGUAGE LEARNING
sections.text: We use a standard sequence to sequence architecture. It has embedding layer, bidirectional LSTM encoder, and unidirectional LSTM with attention decoder. The first and last states of encoder are concatenated as initial state of decoder. The embedding size is 32. The state size is 16 for encoder, and 64 for decoder. We run experiment on Jump task in SCAN dataset. The task contains 14,670 training and 7,706 test samples. In the first setting, we use the original dataset. In the second setting, we changed ’jump’ to other action word and corresponding output symbol uniformly at random.
  We use Adam for optimization, with cross entropy loss. We ran 2,000 training steps. Each step has a mini-batch of 256 samples randomly and uniformly selected from training data with replacement. Initial learning rate is 0.01 and it exponentially decays by a factor of 0.96 every 100 steps. We use TensorFlow for implementation.
  C VISUALIZATION
  The model is a fully-connected neural network, with two input nodes and two output nodes. It has three hidden layers with ReLU activations, and each hidden layer has eight nodes. We use mini-batch size of 10, and we run 1024 steps in training with learning rate 0.1. Please see the original work (Smilkov & Carter, 2016) for more information.