Discovering the Compositional Structure of Vector Representations with Role Learning Networks (2020)

Abstract: How can neural networks perform so well on compositional tasks even though they lack explicit compositional representations? We use a novel analysis technique called ROLE to show that recurrent neural networks perform well on such tasks by converging to solutions which implicitly represent symbolic structure. This method uncovers a symbolic structure which, when properly embedded in vector space, closely approximates the encodings of a standard seq2seq network trained to perform the compositional SCAN task. We verify the causal importance of the discovered symbolic structure by showing that, when we systematically manipulate hidden embeddings based on this symbolic structure, the model’s output is changed in the way predicted by our analysis.

## introduction traditional models of cognition, and language in particular, have relied heavily on symbol structures and symbol manipulation. however, in the current era, deep learning research has shown that neural networks (nns) can display remarkable degrees of generalization on tasks traditionally viewed as depending on symbolic structure @xcite , albeit with some important limits to their generalization (lake and @xcite . given that standard nns have no obvious mechanisms for representing symbolic structures, parsing inputs into such structures, nor applying compositional symbol-manipulating rules to them, this success raises the question that we address in this paper: how do nns achieve such strong performance on compositional tasks? could it be that nns do learn symbolic representations-covertly embedded as vectors in their state spaces? @xcite showed that when trained on highly compositional tasks, goal: interpret neural network encodings jump and run twice jump run run rnn decoder rnn encoder encoding jump and run left twice jump lturn run lturn run method: approximate the encodings of a neural network with a more interpretable compositional model ( §4) step 1: assign structural roles to words using a learned role assigner. step 2: combine word and role vectors using a closed-form equation with learned parameters. standard nns learned representations that are functionally equivalent to compositional vector embeddings of symbolic structures (sec. 3). processing in these nns assigns structural representations to inputs and generates outputs that are governed by compositional rules stated over those representations. we refer to the networks we will analyze as target nns, because we will propose a new type of nn (in sec. 4)-the role learner (role)which is used to analyze the target network. in contrast with the analysis model of @xcite , which relies on a hand-specified hypothesis about the structure underlying the learned representations of the target nn, role automatically learns a symbolic structure that best approximates the internal representation of the target network. this yields two advantages. first, role achieves success at analyzing networks for which the underlying structure is unclear. we show this in sec. 5, where role successfully uncovers the symbolic structures learned by a seq2seq rnn trained on the scan synthetic semantic parsing task (lake and @xcite . second, removing the need for hand-specified structural hypotheses reduces the burden on the analyst, who only needs to provide input sequences and their target nn encodings. discovering symbolic structure within a model enables us to perform precise alterations to the internal representations in order to produce desired alterations in the output (sec. 5.3). then, in sec. 6, we turn briefly to partially-compositional tasks in nlp. the novel contributions of this research are: ## nn embedding of symbol structures mccoy et al. showed that, in gru @xcite encoder-decoder networks performing simple, fully-compositional string manipulations, the medial encoding (between encoder and decoder) could be extremely well approximated, up to an affine transformation, by tensor product representations (tprs) @xcite , which are explicitly-compositional vector embeddings of symbolic structures. to represent a string of symbols as a tpr, the symbols in the string 337 might be parsed into three constituents {3 : pos1, 7 : pos3, 3 : pos2}, where posn is the role of n th position from the left edge of the string; other role schemes are also possible, such as roles denoting right-to-left position: {3 : third-to-last, 3 : second-to-last, 7 : last}. the embedding of a constituent 7 : pos3 is e(7 : pos3) = e f (7) ⊗ e r (pos3), where ⊗ is the tensor product (outer product), e r , e f are respectively a vector embedding of the roles and a vector embedding of the fillers of those roles: the digits. the embedding of the whole string is the sum of the embeddings of its constituents. in general, for a symbol structure s with roles {r k } that are respectively filled by the symbols {f k }, e tpr (s) = k e f (f k ) ⊗ e r (r k ). the discover task including the tpr equations is depicted in figure 2 . at a high level, these role embeddings serve a similar purpose as positional embeddings in a transformer @xcite , in that they are vector embeddings of a token's position in a sequence. the roles discussed above-and the positional embeddings used in transformers-illustrate role schemes based on sequential position; nonsequential role schemes such as positions in a tree are also possible. mccoy et al. (2019a) showed that,for a given seq2seq architecture learning a given string-mapping task, there exists a highly accurate tpr approximation of the medial encoding, given an appropriate pre-defined role scheme. the main technical contribution of the present paper is the role learner (role) model, an rnn that learns its own role scheme to optimize the fit of a tpr approximation to a given set of internal representations in a pre-trained target nn. this makes the discover framework more general by removing the need for human-generated hypothe-figure 2 : the discover task and functions. at the top is the target network and question we pose: is the internal embedding a tpr? the middle row is the tpe which follows the provided equation. we train the tpe to minimize the mse between ê and e. in the bottom row, we evaluate our model by passing the approximations ê through the decoder and checking the substitution accuracy -the proportion of examples for which the approximated encoding ê yields the correct output when provided to the decoder . role is an extension of the tensor-product encoder (tpe) introduced in @xcite (as the "tensor product decomposition network") and depicted in figure 3 . crucially, role is not given role labels for the input symbols, but learns to compute them. more precisely, it learns a dictionary of n r d r -dimensional role-embedding vectors, @xmath0, and, for each input symbol s t , computes a soft-attention vector a t over these role vectors: the role vector assigned to s t is then the attention-weighted linear combination the fillers (yellow circles) and roles (blue circles) are first vectorized with an embedding layer. these two vector embeddings are combined by an outer product to produce the green matrix representing the tpr of the constituent. all of the constituents are summed together to produce the tpr of the sequence, and then a linear transformation is applied to resize the tpr to the target encoder's dimensionality. role replaces the role embedding layer and directly produces the blue role vector. role uses an lstm @xcite to compute the role-assigning attentionvectors a t from its learned embedding f of the input symbols s t : at each t, the hidden state of the lstm passes through a linear layer and then a softmax to produce a t (depicted in figure 4 ). let the t th lstm hidden state be q @xmath1; let the output-layer weight-matrix have rows k ρ ∈ r h and let the columns of r be v ρ ∈ r d r , with ρ = 1, . . . , n r . then r @xmath2: the result of query-key attention (e.g., @xcite with query q t to a fixed external memory containing key-value pairs {(k ρ , v ρ )} n r ρ=1 . since a tpr for a discrete symbol structure deploys a discrete set of roles specifying discrete structural positions, ideally a single role would be figure 4 : the role learning module. the role attention vector a t is encouraged to be one-hot through regularization; if a t were one-hot, the produced role embedding r t would correspond directly to one of the roles defined in the role matrix r. the lstm can be unidirectional or bidirectional. it is essential to note that, while we impose this regularization on role, there is no explicit bias favoring discrete compositional representations in the target encoder e: any such structure that role finds hidden in the representations learned by e must result from biases implicit in the vanilla rnnarchitecture of e when applied to its target task. ## the scan task returning to our central question from sec. 1, how can neural networks without explicit compositional structure perform well on fully-compositional tasks? our hypothesis is that, though these models have no constraint forcing them to be compositional, they still have the ability to implicitly learn compositional structure. to test this hypothesis, we apply role to a standard rnn-based seq2seq model @xcite trained on a fully compositional task. because the rnn has no constraint forcing it to use tprs, we do not know a priori whether there exists any solution that role could learn; thus, if role does learn anything it will be a significant empirical finding about how these rnns operate. we consider the scan task (lake and baroni, 2018), which was designed to test compositional generalization and systematicity. scan is a synthetic semantic parsing task: an input sequence describing an action plan, e.g., jump opposite left, is mapped to a sequence of primitive actions, e.g., tl tl jump (see sec. 5.3 for a complex example). we use tl to abbreviate turn left, sometimes written lturn; similarly, we use tr for turn right. the scan mapping is defined by a complete set of compositional rules (lake and baroni, 2018, supplementary fig. 7 ). ## partially-compositional nlp tasks the previous sections explored fully-compositional tasks where there is a strong signal for compositionality. in this section, we explore whether the representations of nns trained on tasks that are only partially-compositional also capture compositional structure. partially-compositional tasks are especially challenging to model because a fullycompositional model may enforce compositionality too strictly to handle the non-compositional aspects of the task, while a model without a compositional bias may not learn any sort of compositionality from the weak cues in the training set. we test four sentence encoding models for compositionality: infersent @xcite , skip-thought @xcite , stanford sentiment model (sst) @xcite . for each of these models, we extract the encodings for the snli premise sentences @xcite . we use the extracted embeddings to train role with 50 roles available (additional training information provided in appendix a.8). as a baseline, we also train tpes that use predefined role schemes (hyperparameters described in appendix a.7). for all of the sentence embedding models except skip-thought, role with continuous attention provides the lowest mean squared error at approximating the encoding ( in future work, it would be interesting to perform a similar analysis on transformer architectures @xcite . such models have displayed impressive syntactic generalization (hu @xcite as the single-vector sentence encoding to decompose. jawahar et al. found that these encodings were approximated better by human-specified treeposition roles than by other human-specified candidates (e.g., left-to-right and right-to-left roles). by removing the constraint of requiring human-designed role schemes, role may be able to discover other role schemes that approximate bert's encodings even more closely. ## conclusion we have introduced role, a neural network that learns to approximate the representations of an existing target neural network e using an explicit symbolic structure. role successfully discovers symbolic structure in a standard rnn trained on the fully-compositional scan semantic parsing task, even though the rnn has no such structure explicitly present in its architecture. this yields a closed-form equation for the rnn's encoding of any input string. when applied to sentence embedding models trained on partially-compositional tasks, role performs better than hand-specified hypothesized structures but still provides little evidence that the sentence encodings represent compositional structure. while this work has shown that nns can converge to tprs to solve compositional tasks, it is still unknown how the weights in the nn actually convert the raw input into a tpr. to investigate this process, in future work we plan to apply our technique to representations of partial sequences. for instance, when the complete input is jump right twice, the target rnn must first represent jump right as a well-formed tpr at the point when only those two words have been encountered. the representation then needs to be updated when the next word, twice, is encountered. by studying the nature of that update, we can gain insight into how the target model builds up a tpr from the input elements. uncovering the latent symbolic structure of nn representations learned for fully-compositional tasks is a significant step towards explaining how nns achieve the level of compositional generalization that they do. in addition, by illuminating shortcomings in the representations learned for standard tasks that are not fully-compositional, role can help suggest types of inductive bias for improving models' generalization with standard, partiallycompositional datasets.