Discovering the compositional structure of vector representations with Role Learning Networks
Authors: Paul Soulos
Tom McCoy
Tal Linzen
Paul Smolensky
Venue:  (2020)
Keywords: compositionality
generalization
neurosymbolic
symbolic structures
interpretability
tensor product representations

Abstract: Neural networks (NNs) are able to perform tasks that rely on compositional structure even though they lack obvious mechanisms for representing this structure. To analyze the internal representations that enable such success, we propose ROLE, a technique that detects whether these representations implicitly encode symbolic structure. ROLE learns to approximate the representations of a target encoder E by learning a symbolic constituent structure and an embedding of that structure into E’s representational vector space. The constituents of the approximating symbol structure are defined by structural positions — roles — that can be filled by symbols. We show that when E is constructed to explicitly embed a particular type of structure (e.g., string or tree), ROLE successfully extracts the ground-truth roles defining that structure. We then analyze a seq2seq network trained to perform a more complex compositional task (SCAN), where there is no ground truth role scheme available. For this model, ROLE successfully discovers an interpretable symbolic structure that the model implicitly uses to perform the SCAN task, providing a comprehensive account of the link between the representations and the behavior of a notoriously hard-to-interpret type of model. 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 also changed in the way predicted by our analysis. Finally, we use ROLE to explore whether popular sentence embedding models are capturing compositional structure and find evidence that they are not; we conclude by discussing how insights from ROLE can be used to impart new inductive biases that will improve the compositional abilities of such models.

Under review as a conference paper at ICLR 2020
DISCOVERING THE COMPOSITIONAL STRUCTURE OF VECTOR REPRESENTATIONS WITH ROLE LEARNING NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks are able to perform tasks that rely on compositional structure even though they lack obvious mechanisms for representing this structure. To analyze the internal representations that enable such success, we propose ROLE, a technique that detects whether these representations implicitly encode symbolic structure. ROLE learns approximate the representations of target encoder & by learning a symbolic constituent structure and an embedding of that structure into E's representational vector space. The constituents of the approximating symbol structure are defined by structural positions roles - that can be filled by symbols. We show that when & is constructed explicitly embed a particular type of structure (string or tree), ROLE successfully extracts the ground-truth roles defining that structure. We then analyze GRU seq2seq network trained perform a more complex compositional task (SCAN), where there is no ground truth role scheme available. For this model, ROLE successfully discovers an interpretable symbolic structure that the model implicitly uses to perform the SCAN task, providing a comprehensive account of the representations that drive the behavior of frequently-usee but hard-to-interprr type of model. We verify the causal importance of the discovered symbolic structure by showing that, when we systematically manipulate hidden embeddings based this symbolic structure, the model's s resulting output is changed in the way predicted by our analysis. Finally, use ROLE explore whether popular sentence embedding models are capturing compositional structure and find evidence that they are not; we conclude by suggesting how insights from ROLE can be used impart new inductive biases to improve the compositional abilities of such models.
OVERVIEW
Certain AI tasks consist in computing function o that is governed by strict rules: e.g., if is the function mapping a mathematical expression to its value (c.g., mapping '19- 22 to 5), then ço obeys the rule that fo( + y) sum(sp(æ), (yy)) for any expressions and y. This rule is compositional: the output of a structure (here, x + y) is a function of the outputs of the structure's constituents (here, x and y). The rule can be stated with full generality once the input assigned symbolic structure giving its decomposition into constituents. For a fully-compositional task, completely determined by compositional rules, AI system that can assign appropriate symbolic structures to inputs and apply appropriate compositional rules to these structures will display full systematic generalization: will correctly process arbitrary novel combinations of familiar constituents. This is core capability of symbolic AI systems. Other tasks, including most natural language tasks such as machine translation, are only partially characterizable by compositional rules because natural language is only partially compositional in nature. For example, if yo is the function that assigns meanings to English adjectives, it generally obeys the rule that çp(in- + x) = not (xxx) (e.g., (((inofeesive)
not (foffensive)) yet there are exceptions: @0inn (iinlammable) (ff1ammabl)) On these ppartiallycomppsittionn Al tasks, this strategy of compositional analysis has demonstrated considerable, but limited, generalization capabilities.
Deep learning research has shown that Neural Networks (NNs) can display remarkable degrees of combinatorial generalization, often surpassing symbolic AI systems for cirtiillycompoosttionnall tasks

---

Under review as a conference paper at ICLR 2020
(Wu et al. 2016), and exhibit good generalization (although generally falling short of symbolic AI systems) on solll--ommositionaa tasks (Lake & Baroni 2018 McCoy et al., (011a)). Given that standard NNs have no obvious mechanisms for representing symbolic structures, parsing inputs into such structures, nor applying compositional symbolic rules to them, this success raises the question we address in this paper: How do NNs achieve such strong generalization on partialyycoompsstional tasks, and good performance on fully-compositional tasks?
An important step towards answering this question was reported in McCoy et al. (2019a), which showed that when trained on highly compositional tasks, standard NNs learned representations that were well approximated by symbolic structures (Sec. 2 Processing in these NNs assigns such representations to inputs and generates outputs that are governed by compositional rules stated over those representations. We refer to the networks to be analyzed as target NNs, because we will propose new type of NN (in Sec.E) the Role Learner (ROLE) which is used to analyze the target network, after first discussing related analysis methods in Sec. 3 In contrast with the analysis model McCoy al. (2019a), which relies on a hand-specified hypothesis about the underlying structure, ROLE automatically learns a symbolic structure that best approximates the internal representation of the target network. Automating the discovery of structural hypotheses provides two advantages. First, ROLE achieves success at analyzing networks for which it is not clear what the underlying structure is. We show this in Sec. [ where ROLE successfully uncovers the symbolic structures learned by a seq2seq RNN trained on the SCAN task (Lake & Baroni 2018). Second, removing the need for hand-specified hypotheses allows the data to speak for itself, which simplifies the burden on the user, who only needs to provide input sequences and associated embeddings.
We first consider fully-compoitiional (hence synthetic) tasks: simple string-manipulationn task in Sec. [ and the richer SCAN task, which has been the basis of previous work on combinatorial generalization in NNs, in Sec. 6
Discovering symbolic structure within model enables us to perform precise alterations to the internal representations in order to produce desired combinatorial alterations in the output (Sec. 66.3 Then, in Sec. 7 we turn briefly to partiall-commositioon tasks in NL.P. In Sec. X we consider how what we have learned about standard NNs can suggest new inductive biases to strengthen compositionality in NN learning.
NN EMBEDDING OF SYMBOL STRUCTURES
We build on McCoy et al. (2019a). which introduced the analysis task DISCOVER (DISsecting COmpositionality in VEctor Representations): take a NN and, to the extent possible. find an pnllcitly-compositiion approximation to its internal distributed representations. McCoy et al. (2019) showed that, in GRU (Cho et al., 2014) encoder-decoder networks performing simple, fully- compositional string manipulations, the medial encoding (between encoder and decoder) could be extremely well approximated, up to a linear transformation, by Tensor Product Representations (TPRs) (Smolensky 1990), which are explicityycoomposiiie compositional vector embeddings of symbolic structures. To represent a string of symbols as TPR, the symbols in the string 337 might be parsed into three constituents (3: posl, 7: pos3, 3: pos2), where posn is the role of th position from the left edge of the string: other role schemes are also possible, such roles denoting right-to-left. position: (3: third-to-last.. 3: 3:sooond-tollast 7: last.. The embedding of a constituent 7: pos3 is e(7: pos3)= = ep(7) (7) @ eR eR (pos3), where eR, eF 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*} J that are respectively filled by the symbols {fx}, eTPR (S) = Σσ (f() @ (r())..
The example above used the role scheme of linear position from the left edge, but other role schemes are possible, such as linear position from the right edge or position in tree. McCoy et al.] (2019a)
showed that- for given seq2seq architecture learning a given string-mappinn 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, a RNN network that learns its own role scheme to optimize the fit of a TPR approximation to a given set of internal representations in pre-trained target NN. This makes the DISCOVER framework more general by removing the need for human- generrted hypotheses as to the role schemes the network might be implementing. Learned role schemes, we will see in Sec. 6. can enable good TPR approximation of networks for which
task there exists a
role schemes fail.
2

---

Under review as a conference paper at ICLR 2020
3 RELATED WORK
This work falls within the larger paradigm of using analysis techniques to interpret NNs (see Belinkov Glass (2019) for a recent survey), often including a focus on compositional structure (Hupkes et al. 2019 2018 Lake & Baroni 2018: Hewitt & Manning 2019). Two of the most popular analysis techniques are the behavioral and probing approaches. In the behavioral approach, a model evaluated on set of examples carefully chosen to require competence in particular linguistic phenomena (Marvin & Linzen 2018 Waan et al. 2018 (asguppa et al.] 2019; Poliak et al., 2018)) Linzen et al.) [016/|McCop et al. 2019b). This technique can illuminate behavioral shortcomings but says little about how the internal representations are structured, treating the model as a black box.
In the probing approach, auxiliary classifier is trained to classify the model's internal represen- tations based on some iinguisticall--eeeeve
distinction (Adi et al.) 2017: Conneau et al., 20118) Conneau & Kiela 2018 Belinkov et al. 2017 Blevins al. 2018| Peters et al.) [0018] Tenney et al. 2019p. In contrast with the behavioral approach, the probing approach tests whether some particular information is present in the model's encodings, but it says little about whether this information is actually used by the model. Indeed, in at least some cases models will fail despite having the necessary information succeed in their representations, showing that the ability of a classifier to extract that information does not mean that the model is using it (Vanmassenhove et al., 2017).
DISCOVER bridges the gap between representation and behavior: reveals not only what information is encoded in the representation, but also shows how that information is causally implicated in the model's behavior. Moreover, provides a much more comprehensive window into the representation than the probing approach does; while probing extracts particular types of information from representation (c.g.. "does this representation distinguish between active and passive sentences?") DISCOVER exhaustively decomposes the model's representational space. In this regard, DISCOVER is most closely related to the approaches of [Andrea (2019), Chrupata & Alishahi] (2019), (Abaa al. (2019), who also propose methods for discovering complete symbolic characterization of set of vector representations, and Omlin & Giles) (1996) and Weiss et al. (2018), which also seek to extract more interpretable symbolic models that approximate neural network behavior.
4 THE ROLE LEARNER (ROLE) MODEL
ROL produces a vector-space embedding of an input string of T symbols S = S1S2 ST by producing TPR T(S) and then passing it through linear transformation W. ROLE is trained to approximate a pre-trained target ttring-encoder E. Given set of N training strings {s(1), (s(1)..... ,..., s(M),
ROLE minimizes the total mean-squared error (MSH) between its output W T($))) and E's corre- sponding output, (.)))
Role Embesdding
Role Atteation Vector d1
Jai
01 Vid
[ai]
[01]m
Softmax
F12
r
Fa1
Linear
Fi_
h
h2
hg
Fid
End
Role Matrix
R
ho
LSTM
LSTM
LSTM
Foteg
f-(as)
Figure 1: The role learning module. The role attention vector is encouraged to be one-hot through regularization; if o, were one-hot, the produced role embedding r, would correspond directly to one of the roles defined in the role matrix R. The LSTM can be unidirectional or bidirectional.
"Code available http:///hhi.ccnmmm22222mmmmooo/o
3

---

Under review as a conference paper at ICLR 2020
ROLE is extension of the Pensor-Product Encoder (TPE) introduced in McCoy et al. (011aa) (as the "Tensor Product Decomposition Network"), which produces a treerll-transformed TPR given a string of symbols and pre-assigned role labels for each symbol (see Appendix A.T for details). Crucially, ROLE is not given role labels for the input symbols, but learns to compute them. More precisely, it learns dictionary of nn dn-dimensional role-embedding vectors, R E Rda Rdax and, for each input symbol Sy, computes a soft-attention vector over these role vectors: the role vector assigned to S, then the ditention-weigheed linear combination of role vectors, r; R a, ROLE simultaneously learns a dictionary of ny dy dp-dimensional symbol-embedding filler vectors F Rdr xnv, the 65th column of which is for the embedding of symbol type Φ; ø E I..... Ty where ny the size of the vocabulary of symbol types. The TPR generated by ROLE is thus T(S) = Σt= fr(s.) @ Te, where (s,)) ) is symbol s, 's type. Finally, ROLE learns linear transformation W to map this TPR into Rd, where d the dimension of the representations of the encoder & it learning to approximate.
ROLE uses an LSTM (Hochreiter & Schmidhuber, 1997) to compute the role-assigning attention- vectors a from its learned embedding F of the input symbols sy: at each t, the hidden state of the LSTM passes through linear layer and then a softmax to produce a, (depicted in Figure
Since a TPR for a discrete symbol structure deploys a discrete set of roles specifying discrete structural positions, ideally single role would be selected for each sy: a, would be one-hot. ROLE training therefore deploys regularization to bias learning towards one-hot a vectors (based on the regularization proposed in |Palangi et al. (2017), developed for the same purpose). See Appendix [A.4 for the precise regularization terms that we used. Although the regularization can yield good results, performing continuous gradient descent on a nearly discrete symbolic landscape can cause networks to get stuck in local optima where the learned symbolic structure is not ideal. For this reason, the performance at convergence can vary appreciably across multiple runs.
It is important to note that, while we impose this regularization on ROLE, there is no explicit bias favoring discrete compositional representations in the targer encoder E: any such structure that ROLE finds hidden in the representations learned by & must be the result of biases implicit in the vanilla RNN-architecture of E when applied to target task.
A SIMPLE FULLY-COMPOSITIONEE TASK
We first apply ROLE to two target Tensor Product Encoder (TPE) models which are fully compo- sitional by design. Since we know what role scheme each target model deploys, we can test how well ROLE learns these ground-truth roles. The TPEs are trained on the fully compositional task of autoencoding sequences of digits.
We use two types of TPEs: one that uses a simple left-to-right role scheme (e. first, second, third) and one that uses complex tree position role scheme (c.g., left child of the root of the tree, right child of the left child of the left child of the root of the tree). where the trees are generated from digit sequence inputs using deterministic parsing algorithm (see Appendix A.2 for explanations and examples of the designed role schemes). The left-to-right TPE was paired with a unidirectional RNN decoder, while the tree-position TPE was paired with the tree-RNN decoder used by McCoy et al. (2019a). Both of these target models attained near-perfect performance on the autoencoding task (Table D. Once the encoders are finished training, we extract the encoding for each sequence in the dataset and use this to train ROLE. See Appendices
A.3 and A.5 for additional training details.
reports the approximation performance of ROLE in two ways. Substitution Accuracy is the proportion of the items for which the decoder produces the correct output string when it is fed the ROLE approximation. The V-Measure (Rosenberg Hirschberg (007) assesses the extent which the clustering of the role vectors assigned by ROLE matches the ground truth role assignments.
The ROLE approximation of the left-to-righh TPE attained perfect performance, with a substitution accuracy of 100% and V-Measure of 1.0, indicating that the role scheme it learned perfectly matched the ground truth. On the significantly more complex case of tree position roles, ROLE achieves
'Let the th LSTM hidden state be q: E IR";; let the output-layer weight-matrix have rows KJ E II" and let the columns R be Up E Rda, with p = 1,..., nR. Then r. = Ra. = Ene up softmax(k, q:): the result of query-key attention (e.g.. Vassani et al. (017) with query q. to fixed external memory containing key-value pairs {(kp, pp)
4

---

Under review as a conference paper at ICLR 2020
Table 1: ROLE mean substitution accuracy and and role scheme v-measure along with one standard deviation across three random initializations on models that are fully compositional by design (TPEs).
Target model
Target model accuracy
ROLE substitution accuracy
ROLE V-Measure
Left-to-right TPE Pree-position TPE
100%
100% +0
1.0 +0 0.815 #.01
98.62%
98.61 +.05%
essentially the same accuracy as the target encoder & and has considerable success at recovering the ground truth roles for the vectors it was analyzing. These results show that, when target model has a known fully compositional structure, ROLE can successfully find that structure.
THE SCAN TASK
We have established that ROLE can uncover the compositional structure used by model that is compositional by design. But, returning to our central question from Sec. []] how can models without explicit compositional structure (namely, standard RNNs) still be as successful at fully compositional tasks as fully compositional models? 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 standard RNN-basce seq2seq (Sutskever et al.) 2014) model trained on a fully compositional task. Because the RNN has no constraint forcing it to use TPRs, do not know priori whether there exists any solution that ROLE could learn; thus, if ROLE does learn anything it will be significant empirical finding about how these RNNs operate.
We consider the SCAN task (Lake & Baroni 2018), which was designed to test compositional generalization and systematicity. SCAN is a synthetic sequence-to-sequencce mapping task, with an input sequence describing action plan, e.g., jump opposite 1eft, t. being mapped to a sequence of primitive actions, e.g., TL TL JUMP (see Sec. (6.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 complete set of compositional rules (Lake & Baroni 2018, Supplementary Fig. 7).
6.1 THE COMPOSITIONAL STRUCTURE OF SCAN ENCODER REPRESENTATIONS
For our target SCAN encoder ε, we trained a standard GRU with one hidden layer of dimension 100 for 100,000 steps (batch-size 1) with dropout of 0.1 on the simple train-test split. (The hidden dimension and dropout rate were determined by a limited hyper-paramedt search; see Appendix (A.6). E achieves 98.47% (full-string) accuracy the test set. Thus & provides what we want: a standard RNN achieving near- peaf-perfect accuracy on a non-trivial fully compositional task.
After training. extract the final hidden embedding from the encoder for each example in the training and test sets. These are the encodings we attempt to approximate as explicitly compositional TPRs. We provide ROLE with 50 roles to Appendix A.7p. We evaluate the substitution accuracy that this learned role scheme provides in three ways. The continuous method tests ROLE in the same way as it was trained, with input symbol st assigned role vector F2 R The continuous method does not use discrete set of role vectors because the weighted sum that generates a allows for continuously-valued weights. The remaining two methods test the efficacy of a truly discrete set of role vectors. First, in the snapped method, a, replaced at evaluation time by the one-hot vector m; singling out role m. arg max(a:) T. R m, This method serves the goal of enforcing the discreteness of roles, but it is expected to decrease performance because it tests ROLE in different way than it was trained. Our final evaluation method, the discrete method, uses discrete roles without having such train/test discrepancy; in this method, we use the one-hot vector m, to output roles for every symbol in the dataset and then train a TPE which does not learn roles but rather case, ROLE acts as an automatic data labeler, assigning a role to every input word.
it wants (additional training information is in
the one-hot vector m. input during training. In this
For comparison, also train TPEs using variety of discrete hand-crafted role schemes: left-to-right (LTR), right-to-left (RTL), bidirectional (Bi), tree position, Wickelrole (Wickel), and bag-of- (BOW) (additional information provided in Appendix A.2.
5

---

Under review as a conference paper at ICLR 2020
Table 2: Mean substitution accuracy for learned (bold) and pre-defined role schemes on SCAN across three random initializations. Standard deviation was below 1% for all schemes except for snapped. Substitution accuracy is measured by feeding ROLE's approximation to the target decoder.
Continuous
Snapped
Discrete
LTR
RTL
Bi
Tree
Wickel
BOW
94.83%
81.71% +7.28
92.44%
6.68%
6.96%
10.72%
4.31%
44.00%
4.52%
The substitution accuracy from these different methods shown Table 2 schemes provide poor approximations, none surpassing 12% accuracy. The role scheme learned by ROLE does significantly better than any of the predefined role schemes: when tested with the basic, continuous role-attention method, the accuracy is 94. 12%. The success of ROLE tells two things. First, it shows that the target model's compositional behavior relies on compositional internal representations: it was by no means guaranteed to be the case that ROLE would be successful here, so the fact that it is successful tells us that the encoder has learned compositional representations. Second, it adds further validation to the efficacy of ROLE, because it shows that it can be a useful analysis tool in cases of significantly greater complexity than the autoencoding task.
All of the predefined role
6.2 INTERPRETING THE LEARNED ROLE SCHEME
Analyzing the roles assigned by ROLE to the sequences in the SCAN training set, we created a symbolic algorithm for predicting which role will be assigned to a given filler. This is described in Appendix [A. and discussed at some length in Appendix (..e.dix(A...2 Though the algorithm was created based only on sequences in the SCAN training set, is equally successful predicting which roles will be assigned to test sequences, exactly matching ROLE's predicted roles for 98.7% of sequences.
and
The details of this algorithm illuminate how the filler-role scheme encodes information relevant the task. First, one of the initial facts that the decoder must determine is whether the sequence is a single command, pair of commands connected by and, a determination is crucial for knowing the basic structure of the output (how many actions to perform and in what order). We have found that role 30 is used for, and only for, the filler and, while role 17 is used in and only in sequences containing after (usually with after as the filler bound to role 17). Thus, the decoder can use these roles tell which basic structure is in play: if role 30 is present, it is an and sequence; if role 17 is present, it is an af after sequence; otherwise it is a single command.
pair of commands connected by after; such
Once the decoder has established the basic syntactic structure of the output, it must then fill in the particular actions. This can be accomplished using the remaining roles, which mainly encode absolute position within a command. For example, the last word of a command before after (e.g.. jump left after walk twice) is always assigned role 8, while the last word of command after after (c.g., jump left after walk twice) is always assigned role 46. Therefore, once the decoder knows (based the presence of role 17) that it is dealing with after sequence, it can check for the fillers bound to roles and 46 to begin to figure out what the two subcommands surrounding after look like. The identity of the last word in command is informative because that is where cardinality (i.c., twice or thrice) appears if there is one. Thus, by checking what filler is at the end of command, the model can learn whether there is a cardinality present and, if so, which one.
This description of how the decoding could take place does not necessarily match how it actually does take place; for example, it is likely that some of the steps we have described as occurring serially, for expository simplicity, actually occur in parallel. We leave for future work the question of which operations are actually being performed and how those operations are instantiated in an RNN.
6.3 PRECISION CONSTITUENT-SURRS ON INTERNAL REPRESENNATIONS TO PRODUCE DESIRED OUTPUTS
The substitution-accural results above show that the entire learned representation is replaced by ROLE's approximation, the output remains correct. But do the individual words in this TPR have the appropriate causal consequences when processed by the decoder
Historically, this question has had considerable significance: the original compositionality challenge to neural network models of cognition by Fodor and colleagues (Fodor Pylyshyn 1988) insisted that constituents

---

Under review as a conference paper at ICLR 2020
run: 11 36 twice: 8 after: : 43 jump: 10 opposite: 17 right: 4 thrice: 46
TR JUMP TR TR JUMP TR TR JUMP TL RUN RUN
Accuracy by number of suesTiTuu ons
run: 11 1ook: : 11 +
TR TR JUMP TR TR JUMP TR TR JUMP TL LOOK TL LOOK
jump:: 10 + walk: 10
00-
TR TR WALK TR TR WALK TR TR WALK TL LODK TL LODK
-left:33 36 + right: 36 -
Accursyy
60
TR TR WALK TR TR WALK TR TR WALK TR LOOK TR LOOK
twice:8 thrice: 8
TR. TR WALK TR TR WALK TR TR WALK TR LOOK LOOK LOOK
20-
opposite: 17 + around: 17 -
WALK WALK WALK TR WALK TR WALK TR WALK TR WALK TR WALK TR WALK TR WALK TR WALK TR WALK 5
Number of substeutions
TR LOOK TR LOOK TR LOOK
Figure 2: Left: Example of successive constituent surgeries. The roles assigned to the input symbols are indicated the first line (e.g., run was assigned role 11). Altered output symbols are in blue. The model produces the correct outputs for all cases shown here. Right: Mean constiteent-uureery accuracy across three runs. Standard deviation is below 1% for each number of substitutions.
To address this causal question (Pearl 2000). of the internal representations by replacing one constituent with another syntactically equivalent one"] and whether this produces the expected change in the output of the decoder. We take the encoding generated by the RNN encoder & for an input such as jump opposite left, subtract the vector embedding of the opposite constituent, add the embedding of the around constituent, and see whether this causes the output to change from the correct output for j jump opposite left (TL JUMP) to the correct output for j jump around 1eft (TL JUMP TL JUMP TL JUMP TL JUMP). The roles in these constituents are determined by the algorithm of Appendix A.8) If changing word leads other roles in the sequence to change (according to the algorithm), we update the encoding with those new roles as well. Such surgery can be viewed as based in more general extension of the analogy approach used by Mikolov al. (2013) for analysis of word embeddings. An example of applying sequence of five such constituent surgeries sequence shown in Figure (left).
actively intervene the constituent structure
7 PARTIALIX-CCOMPOSTTINN NLP TASKS
The previous sections explored fully colloscoopoiiii tasks where there is a strong signal for compo- sitionality. In this section, we explore whether the representations of NNs trained on tasks that only partially-composittee especially challenging to model because cully-compssitional model may enforce compositionality too strictly to handle the con-compositional aspects of the task, while model without a compositional bias may not learn any sort of compositionality from the weak cues in the training set.
also capture compositional structure. Partially-compositionn tasks are
We test four sentence encoding models for compositionality: InferSent (Conneau et al. 2017). Skip- thought (Kiros et al. 2015). Stanford Sentiment Model (SST) (Socher et al., 2013). and SPINN (Bowman et al. (0. For each of these models, we extract the encodings for the SNLI premise sentences (Bowman et al. 2015). We use the extracted embeddings to train ROLE with 50 roles available (additional training information provided in Appendix A.10).
of cognitive representations must individually be causally efficacious in order for those constituents to provide an explanation of the compositionality of cognition (Fodor& & McLaughlin] 1990 Fodor 1997). That TPRs meet
the challenge of explaining compositionality was argued in (mpolenskk [9887 1991).
'We extract syntactic categories from the SCAN grammar (Lake & Baroni 2018 Supplementary Fig. 6) by
saying that two words belong to the same category if every occurrence of one could be grammatically replaced by the other. Based on analysis in Appendix A.8 we do not replace nccurrences of and and after since the presence of either of these words causes substantial changes in the roles assigned to the sequence.
7

---

Under review as a conference paper at ICLR 2020
Table MSE loss for learned (bold) and hand-crafted role schemes on sentence embedding models.
Continuous
Snapped
Discrete
LTR
RTL
Bi
Tree
BOW
InferSent
4.05c-4
4.15e-4
5.76e-4
8.21e-4
9.70e-4
9.16e-4
7.78e-4
4.34e-4
Skip-thought
9.30c-5
9.32c-5
9.85c-5
9.91c-5
1.78c-3
3.95c-4
9.64c-5
8.87e-5
SST
5.58e-3
6.72c-3
6,48c-3
8.35c-3
9.29c-3
8,55c-3
5,99c-3
9.38c-3
SPINN
.139
.151
.147
.184
.189
.181
.178
.176
As baseline, we also train TPEs that use pre-defined role schemes (additional training information in Appendix A.9). For all of the sentence embedding models except Skip-thought, ROLE with continuous attention provides the lowest mean squared error at approximating the encoding (Table 3 The BOW (bag-of-words) role scheme represents TPE that does not use compositional structure by assigning the same role to every filler; for each of the sentence embedding models tested except for SST. performance is within the same order of magnitude as structure- free BOW. Parikh et al. (2016) found that bag-of-words model scores extremely well on Natural Language Inference despite having no knowledge of word order, showing that structure is not necessary to perform well on the sorts of tasks commonly used to train sentence encoders. Although not definitive, these results provide evidence that these sentence embedding models rely on compositional representations.
FUTURE WORK
TPRs provide NNs an aspect of the systematicity of symbolic computation by disentangling fillers and roles. The learner needs learn process fillers - providing, essentially, what each input constituent contributes to the output and to process roles - essentially, how these contributions used in the output. In this work, we used ROLE interpret the workings of a target encoder E, and in future work, we plan to train ROLE in an end-to-ens manner, either using it as the encoder itself, or using regularize a standard (e-g.. RNN) encoder with loss term that rewards learning compositional encodings that ROLE can approximate well. We will test whether such an explicit bias for compositionality allows networks to train faster, or with fewer parameters, and to achieve more systematic generalization. Recent work showed improvements in compositionality by separating out syntax and semantics with attention Russin et al. 2019), and our results suggest that ROLE can also disentangle syntax and semantics.
The structured representations that TPRs provide allow us to structure the processing that occurs over these representations. In colyyscompoiitional tasks, the processing of fillers and roles can be encoded (and hence in principle learned) independently. In partially-cone comilsstioooii tasks, the processing of fillers and roles may be approximately encoded independently, with key interactions when task deviates from full compositionality. In this work, we showed how a hidden embedding can be factored into fillers and roles. Similarly, it is possible to factor weight matrix into weights that process roles and weights that process fillers. An illustration of this with a simple example from the SCAN task is provided in Appendix [I.IT] We plan explore whether providing networks with bias favoring weight matrices that factor in this way can improve systematic generalization.
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 both in models that explicitly define this structure and in an RNN without explicit structure trained on the cally-comosiitional SCAN task. When applied to sentence embedding models trained on partially-compositional tasks, ROLE performs better than hand-specified role schemes but still provides little evidence that the sentence encodings represent compositional structure. Uncovering fully-com compositooo tasks is significant step
the latent symbolic structure of NN representations towards explaining how they can achieve the level of compositional generalization that they do, and suggests types of inductive bias to improve such generalization for partially-composttion tasks.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Samira Abnar, Lisa Beinborn, Rochelle Choenni, and Willem Zuidema. Blackbox meets blackbox: Representational similarity & stability analysis of neural language models and brains. In Proceed- ings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 191-203, Florence, Italy, August 2019, Association for Computational Linguistics. doi: 10.18653/v 1/W19-44913 19-4820.
UtLhttpss:/ www ac web org www.aaatooooyoooo.oooooo 1t4rthoolog//11144822
Yossi Adi, Einat Kermany, Yonatan Belinkov, Ofer Lavi, and Yoav Goldberg. Fine- Fine-grained analysis of sentence embeddings using auxiliary prediction tasks. In Proceedings of ICLR, 2017.
Jacob Andreas. Measuring compositionality in representation learning. In International Confer- ence on Learning Representations, 2019. URL
net mettfformm?o
HJz0500qk7
Yonatan Belinkov and James Glass, Analysis methods in neural language processing: A survey, Transactions of the Association for Computational Linguistics, 7:49-72, 2019.
Yonatan Belinkov, Lluís Mårquez, Hassan Sajja, Nadir Durrani, Fahim Dalvi, and James Glass. Evaluating layers of representation in neural machine translation part-of-speech and semantic tagging tasks. In Proceedings of IJCNLP, 2017.
Terra Blevins, Omer Levy, and Luke Zettlemoyer. Deep RNNs encode soft hierarchical syntax. In Proceedings of ACL, 2018.
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. A large annotated corpus for learning natural language inference. Proceedings of the 2015 Conference Empirical Methods in Natural Language Processing, pp. 632 642, Lisbon, Portugal, September 2015. Association for Computational Linguistics. URL http::tttcthheeeeeee http::/acllbbbbb org/ anthology/ D15-1075
Samuel R. Bowman, Jon Gauthier, Abhinav Rastogi, Raghav Gupta, Christopher D. Manning, and Christopher Potts. A fast unified model for parsing and sentence understanding. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1466-1477. Association for Computational I Linguistics, 2016. URL URL /tttt:://awwwb..... anthology/P16-
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN secoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 1724 1734, Doha, Qatar, October 2014. Association for Computational Linguisties. doi: 10.3115/v1/11411111 URL https: www. aclweb
http//athhoogyyDDee 1179
Grzegorz Chrupata and Afra Alishahi. Correlating neural and symbolic representations of language. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2952-2962, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/v1/P19-1222 1283. URL BRLhttpss: wwww///www/.///////////////// http://wwwww....rr///ooooooooo//
1283
Alexis Conneau and Douwe Kiela. SentEval: An evaluation toolkit for universal sentence represen- tations. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation, 2018.
Alexis Conneau, Douwe Kiela, Holger Schwenk, Loie Barrault, and Antoine Bordes. Supervised learning of universal sentence representations from natural language inference data. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 670-680. Association for Computational Linguistics, 2017. URL htRthtt::// /twawwwwwbbb............... org/ anthology// D17-1 117-1070
Alexis Conneau, Germán Kruszewski, Guillaume Lample, Loic Barrault, and Marco Baroni. What you can cram into a single $&#* vector: Probing sentence embeddings for linguistic properties. In Proceedings of ACI, 2018.

---

Under review as a conference paper at ICLR 2020
Ishita Dasgupta, Demi Guo, Samuel J Gershman, and Noah D Goodman. Analyzing muchine-learmed representations: A natural language case study. arXiv preprint arXiv: 19X.:1199.00585,, 2019.
Jerry Fodor. Connectionism and the problem of systematicity (continued): Why Smolensky's 's solution still doesn't 't work. Cognition, 62(1):109-119) 1997.
Jerry Fodor and Brian P McLaughlin. Connectionism and the problem of systematicity: Why Smolensky's ' solution doesn't 't work. Cognition, 35(2)1183-204, 1990.
Jerry A Fodor and Zenon W Pylyshyn. Connectionism and cognitive architecture: critical analysis.
Cognition, (31-2))3-77 1988.
John Hewitt and Christopher D Manning. A structural probe for finding syntax in word representations. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers),
pp. 4129-4138, 2019.
Sepp Hochreiter and Jürgen Schmidhuber: Long short-term memory. Neural Comput., 978):1735- 1780, November 1997. ISSN 0899-7667. doi: 10.1 (111///cco. 1.977.9...773.. URL http:///x
doi. org/1..00.0... (tt.://.....6//eeeeeeee newo..//eec.cccmmmem 1997. 973.5
Dieuwke Hupkes, Sara Veldhoen, and Willem Zuidema. Visualisation and' diagnostic classifiers' reveal how recurrent and recursive neural networks process hierarchical structure. Journal of Artificial Intelligence Research, 61:907-926, 2018.
Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. The compositionality of neural networks: integrating symbolism and connectionism. arXiv preprint arXiv: 00008,0833,,,1111
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference for Learning Representations, 2015.
Ryan Kiros, Yukun Zhu, Ruslan R Salakhutdinov, Richard Zemel, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Skip-thought vectors. In Advances in Neural Information Processing Systems, pp. 3294-3302, 2015.
Dan Klein and Christopher D Manning. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics- Volume I, pp. 423-430. Association for Computational Linguistics, 2003.
Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the compositional skills of requence-to-sequenee recurrent networks. In ICML, 2018. arXiv 1711.00350v3,
Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. Assessing the ability of LSTMs learn syntax-sensitive dependencies. Transactions of the ACL, 2016.
Rebecca Marvin and Tal Linzen. Targeted syntactic evaluation of language models. In Proceedings of EMNLP, 2018.
R. Thomas McCoy, Tal Linzen, Ewan Dunbar, and Paul Smolensky. RNNs implicitly implement tensor-product reprettttosssssssssssss In International Conference on Learning Representations, 2019a.
URL UR/nttpp://ppeervvvii net. wt:.:/orummiii//o Bat.rrumid-BJxxsxcCCC CC5X
R. Thomas McCoy, Ellie Pavlick, and Tal Linzen. Right for the wrong reasons: Diagnosing syntactic heuristics in natural language inference. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. -2448,, Florence, Italy, July 201 9b. Association for Computational I Linguistics. doi: 00.18653/v//119-1 aclweb. FrLieb..orc/anthooogy/EE 13344
URL htl.ttts::/ www
Tomas Mikolov, Wen-tau Yih, and Geoffrey Zweig. Linguistic regularities in continuous space word representations. Proceedings of NAACL-HLT, pp. 746-751, 2013.
Christian W Omlin and C Lee Giles, Extraction of rules from discrete-time time recurrent neural networks. Neural networks, 9(1 91)::1155 --2222,, 1996.
10

---

Under review as a conference paper at ICLR 2020
Hamid Palangi, Paul Smolensky, Xiaodong He, and Li Deng. Question-answeringg with grammatically- interpretable representations. In AAAI, 2017.
Ankur Parikh, Oscar Täckström, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model for natural language inference. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2249-2255 Austin, Texas, November 2016. Association for Computational Linguisties. doi: 10.18653/v1/D16. 124441144..
URLhttps: www www.aalwwe.oor.
anthology/D16 1244
Judea Pearl. Causality. MIT Press, Cambridge, MA, 2000.
Matthew Peters, Mark Neumann, Luke Zettlemoyer, and Wen-tau Yih. Dissecting contextual word embeddings: Architecture and representation. In Proceedings of EMNLP, 2018.
Adam Poliak, Aparajita Haldar, Rachel Rudinger, J. Edward Hu, Ellie Pavlick, Aaron Steven White, and Benjamin Van Durme. Collecting diverse natural language inference problems for sentence representation evaluation. In Proceedings of EMNLP, 2018.
Andrew Rosenberg and Julia Hirschberg. V-measure: A conditional entropy-based external cluster evaluation measure. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning WELEEENNNLL.LLLI pp. 410 420, 2007.
Jake Russin, Jason Jo, Randall C. O' O'Reilly, and Yoshua Bengio. Compositional generalization in deep seq2seq model by separating syntax and semantics. CoRR, abs/1904.09708, 2019. URL attp:://axxie http://v..rgaabb//////00/ abwp////..00.0
Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artif. Intell., 46(1-2):159-216 November 1990. ISSN 0004-3702. doi: 10. 0016/0004-300((0009000 90007-M
URL http: doi orw.l..rg11.. 10161 10110000011100001111111100000000 (90)
Paul Smolensky. The constituent structure of connectionist mental states: A reply to Fodor and Pylyshyn. Southern Journal of Philosophy, 26(Supplement:1137BB 1987.
Paul Smolensky. Connectionism, constituency, and the language of thought. In Barry Loewer and Georges Rey (eds.), Meaning in Mind: Fodor and his Critics, pp. 201-227. Basil Blackwell, Oxford, 1991.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642, 2013.
Ilya Sutskever, Oriol Vinyals, and Quoc Le. Sequence to sequence learning with neural networks. In Advances Neural Information Processing Systems, pp. 3 3104-3112, 2014.
Ian Tenney, Patrick Xia, Berlin Chen, Alex Wang, Adam Poliak, R. Thomas McCoy, Najoung Kim, Benjamin Van Durme, Sam Bowman, Dipanjan Das, and Ellie Pavlick. What do you learn from context? probing for sentence structure in contextualized word representations. In International Conference on Learning Representations, 2019. URL httpps::/openrev..ee.. idd SJZSgnRcKX
forum?
Eva Vanmassenhove, Jinhua Du, and Andy Way. Investigating 'aspect'in in nmt and smt: Translating the english simple past and present perfect. Computational Linguistics in the Netherlands Journal, 7:109-128, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
11

---

Under review as a conference paper at ICLR 2020
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, 2018.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In ICML, pp. 5244-5253, 2018.
Wayne A. Wickelgren. Sontext-sensitive coding, associative memory, and serial order in (speech) behavior. Psychological Review, 76(1):1-15, 1969.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. Google's neural machine translation system: Bridging the gap between human and machine translation. CoRR, abs/1609, 44, 2016. URL http: arxiv. org/ abs 1609. 08144
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 TENSOR PRODUCT ENCODER (TPE) ARCHITECTURE
E
Linear
Figure 3: The Tensor Product Encoder architecture. The yellow circle is an embedding layer for the fillers, and the blue circle is an embedding layer for the roles. These two vector embeddings are combined by outer product produce the green matrix representing the TPR of the constituent. of the constituents are summed together to produce the TPR of the sequence, and then linear transformation is upplied to resize the TPR to the target encoders dimensionality. ROLE replaces the role embedding layer and directly produces the blue role vector.
A.2 DESIGNED ROLE SCHEMES
We six hand-specified role schemes bascline compare the learned role schemes against. Examples of each role scheme are shown Table 4
1. Left-to-right (LTR)): Each filler's role is its index in the sequence, counting from left to right.
2. Right-to-left (RTL): Each filler's role is its index in the sequence, counting from right to left.
3. Bidirectional (Bi): Each filler's role is pair of indices, where the first index counts from left to right, and the second index counts from right to left.
4. Tree: Each filler's role is given by its position tree. This depends on a tree parsing algorithm.
5. Wickelroles (Wickel): Each filler's role is the filler before it and the filler after it. (Wickel gren 1969)
6. Bfg-of-words (BOW): Each filler assigned the same role. The position and context the filler is ignored.
Table 4: The assigned roles for two sequences, 3116 and 523197. Table reproduced from McCoy al. (209a)).
3
1
6
5
3
9
7
Left-to-right Right-to-left
0
1
2
3
0
2
3
5
2
1
0
5
2
0
Bidirectional
(0, 3)
(1,2)
(2,
1)
(3, 0)
(0, 5)
(1, 4)
(2, 3)
(3, 2)
(4, 1)
(5, 0)
Wickelroles
#
31
16
#
#2
53
2.1
3 9
17
9 #
Tree
L
RLL
RLR
RR
LL
LRLL
LRLR
LRRL
LRRR
R
Bag of words
To
To
To
To
To
To
TO
Fp
To
To
13

---

Under review as a conference paper at ICLR 2020
A.3 TPES TRAINED ON DIGIT SEQUENCE TASKS
We trained two TPEs end-to-end with RNN decoder for our target networks on the digit sequence tasks. The left-to-right (LTR) TPE used a left-to-right role scheme applied to each element in the input and was connected to unidirectional GRU decoder. The tree TPE used tree positions for each element in the input and was connected to a tree GRU decoder; here, the digit strings were parsed as a binary tree by a deterministic algorithm given in McCoy et al. (2019a) App. C). The filler and role dimensions were both 20 for the LTR TPE. The filler dimension was 20 for the Tree TPE, and the role dimension was 120. We used hidden size of 60 for the GRU decoders. We used patience of for early stopping. The seft-to-right TPE achieves 100% accuracy on the test set and the tree TPE achieves 98. 68.6 on the test set.
A.4 ROLE REGULARIZATION
Letting A = {ar)²= the regularization term applied during ROLE training is R = X(R +R2+ Ra). where À is regularization hyperparameter and:
T nn
mn
R1 (A)
aalo(1 [aip)): (2(A) = Σ p=1
Σ
Rs(A)
Σ (1|{s)))))
Since each a results from softmax, its elements are positive and sum 1. Thus the factors in R1 (A) are all non-negative. so R1 assumes its minimal value of 0 when each a has binary elements; since these elements must sum to I, such an a, must be one-hot. Rg (A) is also minimized when each a, is one-hot because when vector's / T,- norm is 1, its I,2 norm is maximized when it is one-hot. Although each of these terms individually favor one-hot vectors, empirically we find that using both terms helps the training process. In a discrete symbolic structure, each position can hold at most one symbol, and the final term R3 in ROLE's regularizer R is designed to encourage this. In the vector S = Σi= at the n&h element is the total attention weight, over all symbols in the string, assigned to the pth role: in the discrete case, this must be 0 (if no symbol is assigned this role) or I (if a single symbol is assigned this role). Thus R3 is minimized when all elements of s are 0 or I (R3 is similar to R1, but with squared terms since we are no longer assured each element is at most 1). It important to normalize each role embedding in the role matrix R so that small attention weights have correspondingly small impacts on the weighted-sun role embedding.
A.5 ROLE TRAINED ON DIGIT SEQUENCE TASKS
Once the TPEs in Sec. A.3 were trained, we extracted the hidden embedding for each item in the training, dev, and test sets.
For both ROLE models trained on the digit sequence task, we used bidirectional 2-layer LSTM (Hochreiter Schmidhuber 1997) with filler dimension of 20, and regularization constant À = 1. For training, we used the ADAM (Kingma & Ba 2015) optimizer with learning rate of ,001, batch size 32, and an early stopping patience of 10. The ROLE model trained on the LTR TPE was given 20 roles each of dimension 20. The ROLE model trained on the Tree TPE was given 120 roles each of dimension 120.
A.6 RNN TRAINED ON SCAN
To train the standard RNN on SCAN, we ran a limited hyperparameter search similar to the procedure in Lake & Baroni 2018 Since our goal was to produce a single emhedding that captured the entire input sequence, we fixed the architecture to GRU with single hidden layer. We did not train models with attention, since we wanted to investigate whether a standard RNN could capture compositionality, The remaining hyperparameters were hidden dimension and dropout. We ran search over the hidden dimension sizes of 50, 100, 200, and 400 as well as dropout with a value of O, .1, and applied to the word embeddings and recurrent layer. Each network was trained with the ADAM optimizer (Kingmal & Ba, (015)) and a learning rate of .001 for 100,000 steps with a batch-size of The best performing network had hidden dimension 100 and dropout of .1.
14

---

The input sequences have three basic types that are relevant to determining the role assignment: sequences that contain and (e.g.. around left and walk thrice), sequences that contain after (e.g.. jump around left after walk thrice), and sequences without and or after (e.g., turn opposite right thrice). Within commands containing and after, it is convenient break the command down into Under review as a conference paper at ICLR 2020
A.7 ROLE TRAINED ON SCAN
For the ROLE models trained to approximate the GRU encoder trained on SCAN, we used a filler dimension of 100, role dimension of 50 with 50 roles available. For training, used the ADAM
(Kingma & Ba 2015) optimizer with a learning rate of .001, batch size 32, and an early stopping patience of 10. The role assignment module used a bidirectional 2-layer LSTM (Hochreiter & Schmidhuber 1997). We performed hyperparameter search over the regularization coeffcientt using the values in the set [.1, .02, .01). The best performing value was .02, and we used this model in our analysis.
A.8 SCAN ROLE ANALYSIS
The algorithm below characterizes our post-hoc interpretation of which roles the Role Learner will assign elements of the input the SCAN model. This algorithm was created by hand based on an analysis of the Role Learner's s outputs for the elements of the SCAN training set. The algorithm works equally well on examples the training set and the test set: on both datasets, exactly matches the roles chosen by the Role Learner for 98. of sequences (20,642 out of 20,910)
A.8.1 A ROLE-ASSIGNMENT ALGORITHM IMPLICITLY LEARNED BY THE SCAN SEQ2SEQ ENCODER
the command before the connecting word and the command after it; for example, the command jump around left after walk thrice, these two components would be jump around left and walk thrice.
Sequence with and:
Elements of the command before and:
Last word: 28
First word (if not also last word): 46
* opposite if the command ends with thrice: 22
* Direction word between opposite and thrice: 2
* opposite if the command does not end with thrice: 2
* Direction word after opposite but not before thrice: 4 around: 22
* Direction word after around:
Direction word between action word and twice thrice: 2
Elements of the command before and:
* First word: 11
* Last word (if not also the first word): 36
* Second-to to-dd-tt-ttt word (if not also the first word):
Second of four words: 24
and: 30
Sequence with after:
Elements of the command before after:
Last word: 8
Second-to-last word: 36
First word (if not the last second-to-He word): 11
* Second word (if not the last or second-to-last word): 3
Elements of the command after after:
Last word: 46
Thhis figure of 98.7% is constant across datasets presumably hecause the synthetic nature of the SCAN datasct means that any reasonably-sizet sample from will be similarly representative of the entire dataset.
15

---

Under review as a conference paper at ICLR 2020
Second-to cocond-to-last word: 4
*
First word if the command ends with around right: 4
* First word if the command ends with thrice and contains rotation: 10
* First word if the command does not end with around right and does not contain both thrice and rotation: 17
Second word if the command ends with thrice: 17
* Second word if the command does not end with thrice: 10
after: 17 if no other word has role 17 or if the command after after ends with around left: 43 otherwise
Sequence without and or after:
Action word directly before a cardinality:
Action word before, but not directly before, a cardinality: 34
thrice directly after an action word: 2
twice directly after an action word: 2
opposite in sequence ending with twice: 8
opposite a sequence ending with thrice: 34
around in sequence ending with cardinality: 22
Direction word directly before cardinality: 2
Action word in sequence without cardinality: 46
opposite a sequence without a cardinality:
Direction after opposite in a sequence without a cardinality: 26
around in sequence without a cardinality: 3
Direction after around in sequence without cardinality: 22
Direction directly after an action in sequence without cardinality: 22
To show how this works with an example, consider the input jump around left after walk thrice. The command before after is jump around left. left, as the last word, is given role 8. around, as the second-to-last word, gets role 36. jump, as a first word that is not also the last or second-to-last word gets role 1 1.. The command after after is walk thrice. thrice, the last word, gets role 46. walk, as the sccond-to-last word, gets role 4. Finally, after gets role 17 because no other elements have been assigned role 17 yet. These predicted outputs match those given by the Role Learner.
A.8.2 DISCUSSION OF THE ALGORITHM
We offer several observations about this algorithm.
1. This algorithm may assigned by such an algorithm support success on the SCAN task. First, a sequence will contain role 30 if and only if it contains and, and it will contain role 17 if and only if it contains after. Thus, by implicitly checking for the presence of these two roles (regardless of the fillers bound to them), the decoder can tell whether the output involves one or two basic commands. where the presence of and or after leads to two basic commands and the absence both leads to one basic command. Moreover, if there are two basic commands, whether it is role 17 role 30 that is present can tell the decoder whether the input order of these commands also corresponds to their output order (when it is and play, i.e., role 30), or if the input order is reversed (when it is after in play, i.e., role 17).
convoluted, but few observations can illuminate how the roles
With these basic structural facts established, the decoder can begin decode the specific commands. For example, if the input is sequence with after, it can begin with the command after after, which it can decode by checking which fillers are bound to the relevant roles for that type of command.
It may seem odd that so many of the roles are based on position (e.g., "first word" and "second-to to-last word"), rather than more amnctionally-reeevan categories such as "direction word." " However, this approach may actually be more efficient: Each command consists single mandatory element (namely, an action word such as walk or jump) followed by several optional modifiers (namely, rotation words, direction words, and cardinalities).
16

---

Under review as a conference paper at ICLR 2020
Because most of the word categories are optional, it might be inefficient to check for the presence of, c.g., a cardinality, since many sequences will not have one. By contrast, every sequence will have last word, and checking the identity of the last word provides much dunetionally-relevam information: if that word is not a cardinality, then the decoder knows that there is no cardinality present in the command (because if there were, it would be the last word); and if it is a cardinality, then that is important to know, because the presence of twice or thrice can dramatically affect the shape of the output sequence. In this light, is unsurprising that the SCAN encoder has implicitly learned several different roles that essentially mean the last element of particular subcommand.
2.
The algorithm does not constitute simple, transparent role scheme. But its job is to describe the representations that the original network produces, and we have no a priori expectation about how complex that process may be. The role-assignment algorithm implicitly learned by ROLE is interpretable locally (each line is readily expressible in simple English), but not intuitively transparent globally. We see this as a positive result, in two respects.
First, it shows why ROLE is crucial: no human-generated role scheme would provide good approximation to this algorithm. Such an algorithm can only be identified because ROLE is able to use gradient descent find role schemes far more complex than any we would hypothesize intuitively. This enables us to analyze networks far more complex than we could analyze previously, being necessarily limited to designes role schemes based on human intuitions about how to perform the task.
Second, when future work illuminates the computation in the original SCAN GRU seq2seq decoder, the baroqueness of the role-assignment algorithm that ROLE has shown to be implicit in the seq2seq encoder can potentially explain certain limitations in the original model, which is known to suffer from severe failures of systematic generalization outside the training distribution (Lake and Baroni, 2018). It is reasonable to hypothesize that systematic generalization requires that the encoder learn an implicit role scheme that is relatively simple and highly compositional. Future proposals for improving the systematic generalization of models on SCAN can be examined using ROLE to test the hypothesis that greater systematicity requires greater compositional simplicity in the role scheme implicitly learned by the encoder.
3. While the role-assignment algorithm of A.8.1 may not be simple, from a certain perspective. it is quite surprising that it is not far more complex. Although ROLE is provided 50 roles to learn to deploy as it likes, it only chooses to use 16 of them (only 16 are ever selected as the arg max (a:); see Sec. 6.1). Furthermore, the SCAN grammar generates 20,910 input sequences, containing a total of 151,688 words (an average of 7.25 words per input). This means that, if one were to generate series of conditional statements to determine which role is assigned to each word in every context, this could in theory require up to 151,688 conditionals (e.g., "if the filler is 'jump' in the context 'walk thrice after opposite left', then assign role 17"). However, our algorithm involves just 47 conditionals. This reduction helps explain how the model performs well on the test set: If it used many more of the 151,688 possible conditional rules, it would completely overfit the training examples in a way that would be unlikely to generalize. The 47-conditional algorithm we found is more likely to generalize by abstracting over many details of the context.
4. Were not for ROLE's ability to characterize the representations generated by the original encoder in terms of implicit roles, providing an equally complete and accurate interpretation of those representations would necessarily require identifying the conditions determining the activation level of each of the 100 neurons hosting those representations. It seems to us grossly overly optimistic to estimate that each neuron's 's activation level in the representation of given input could be characterized by property of the input statable in, say, two lines of roughly 20 words/symbols; yet even then, the algorithm would require 200 lines, whereas the algorithm in A.8. requires 47 lines of that scale. Thus, by even such crude estimate of the degree of complexity expected for an algorithm describing the representations in terms of neuron activities, the algorithm find, stated over roles, is 4 times simpler.
A.9 TPES TRAINED ON SENTENCE EMBEDDING MODELS
For each sentence embedding model, we trained three randomly initialized TPEs for each role scheme and selected the best performing one as measured by the lowest MSE. For each TPF, we used the
17

---

Under review as a conference paper at ICLR 2020
original filler embedding from the sentence embedding model. This filler dimensionality is 25 for SST, 300 for SPINN and InferSent, and 620 for Skipthought. We applied a linear transformation to the pre-trained filler embedding where the input size is the dimensionality of the pre-trained embedding and the output size is also the dimensionality of the pre-trained embedding. This linearly transformed embedding is used as the filler vector in the filler-role binding in the TPE. For each TPE, we use role dimension of 50. Training was done with a batch size of 32 using the ADAM optimizer with a learning rate of ,001.
To generate tree roles from the English sentences, we used the constituency parser released in version 3.9.1 of Stanford CoreNLP (Klein Manning 2003).
A.10 ROLE TRAINED ON SENTENCE EMBEDDING MODELS
For each sentence embedding model, we trained three randomly initialized ROLE models and selected the best performing one as measured by the lowest MSE. We used the original filler embedding from the sentence embedding model (25 for SST, 300 for SPINN and InferSent, and 620 for Skipthought). We applied a linear transformation dimensionality of the pre- pre-trained embedding and the output size is also the dimensionality of the pre-trained embedding. This linearly transformed embedding filler-role binding in the TPE. We also applied similar linear transformation to the pre-trained filler embedding before input to the role learner LSTM. For each ROLE model, we provide up to 50 roles with a role dimension of 50. Training was done with batch size of 32 using the ADAM optimizer with a learning rate of .001. We performed a hyperparameter search over the regularization coefficient À using the values in the set 0.1, 0.01, 0.001, 0.0001); J. For SST, SPINN, InferSent and SST, respectively, the best performing network used À = 0.001, 0.01, 0.001, 0.1.
the pre-trained filler embedding where the input size is the
used as the filler vector in the
A. FACTORING WEIGHTT TO PROCESS FILLERS AND ROLES INDEPENDENTLY IN SCAN
At the end of Sec. we remarked: "the structured representation bias that TPRs provide allows us to also provide biases to structure the processing that occurs over these representations. In fully- compositional tasks, the processing of fillers and roles can be encoded (and hence in principle learned) independently. In this work, we showed how a hidden embedding can be factored into fillers and roles. Similarly, it is possible factor a weight matrix into weights that process roles and weights that process fillers." Here we exemplify this with SCAN.
One of the compositional rules for the mapping & defined by the SCAN task is: sl twice) (p()) p(z);; for example, <owalk twice) = (o(aakk) ((walk) = WALK WALK. For the purposes of illustration, suppose that, given the input string x twice, NN encoder produces a repre- sentation that is approximated by the TPR of a single-constiuentt structure in which the filler assigned the role "argument of twice": x:: Pgee.arg- So the TPR encoding of jump twice is e(jump twice) = e(jump: (2e-aar)))) functions for fillers and roles, respectively. Let us also suppose that the output string is encoded as a TPR with positional roles RG, so that WALK LOOK has fillerrole bindings (WALK: R LOOK: R₂ } and so has TPR e ((WALK: R1, LOOK: R2)) = er (WALK) @ en (R)) + ey (LOOK) @ (R()
er(jump) @ (r( where ep, eR are the embedding
So to generalize correctly to the input jump twice, producing output JUMP JUMP, the system needs to learn two things: how to map the filler - (Jr(jum)) = JUMP - and how to map the role (F(e.aaag)))
{R1, R2). The desired mapping is sp : + e(JUMP JUMP), that is, p : op (j( (jjppp) @ CR (F22 H> (JUMP) 8 CR (R,) + ep (JUMP) @ eR (R2). We now show that this can be accomplished through the separate filler- and role-mappings ypp er(jump) + @JJUMP) and PR en (F2 + en (R,) + eR (R2).
To do this, show that if ypp, PR are respectively computed over embedding vectors through weight matrices Wr, WR in a NN, then the weight tensor W = Wp @ WR will correctly map the embedding
of jump twice to the embedding of JUMP JUMP. The tensor product of weight matrices is defined as
[Wr & WR 11 = [Wr] 1² [WH.] which entails that (Wp @ WR) [ @ r] = [ ff &
W gr). Therefore
Wee(jum twice]] = W W[e(jumu))) Fgee-arg) ) Wee
( jump) @ eg (12cc-arg) = Wee ep (j [mm)) &
[W (T2m_ar)))) = er (JUMP) & en (R, +ea (R2) = ep (JUMP) (R, +e JUMP (R,
e( e(UMMP JUMP), as desired.
18

---

Under review as a conference paper at ICLR 2020
This suggests that greater compositional generalization might be achieved by future models that are explicitly biased to utilize TPRs as internal representations and explicitly biased to factor their processing weights into those that process fillers (independently of their roles) and those that process roles (independently of their fillers), as the SCAN example with W = Wp 69 Wn above.
19


Reviews:
[{"review_id": "S1lCZkVNqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces an approach, called ROLE, that extract symbolic structure from seq2seq networks.  It also provides an interpretable symbolic structure and examines the causal information in the symbolic structure.\n\nThe approach is inspired by the Tensor Product Encoder architecture.\n\nThe scan role analysis part seemed the most hand-wavy with lots of positions in A.7.\n\nNone of the accuracy results have variances attached to them.\n\nI am not an expert on this topic (hence the weak accept), but I liked the paper.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "ByldQye0KB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis work focuses on the understanding of Deep NNs and of their generalization ability for compositional tasks and especially for partially composition tasks such as one encounters in natural language processing.\n\nThe core idea is to design and to learn a neural model (the ROLE network) able to analyse a target neural network (e.g. an encoder in an seq2seq architecture) by identifying the symbolic structures the target network manipulates (the symbols and their roles) in its representations and the compositional rules it has learned on these. The main motivations are the understanding of what is learnt by a such neural network and getting ideas on which architecture to choose for improving generalization on compositional tasks.\n \nThe experimental study shows that ROLE ’s results are relevant when dealing with a fully compositional model by design. This is a kind of sanity check, that ROLE may uncover the ground truth from the data, while no prior information is provided on the nature of the roles. \nThe experiments on the SCAN dataset concern a standard RNN model learned from data. I am not sure of the nature of RNN used here. How many layers, which activation function ? The experimental section also provides insights on what is learned by the ROLE model and on how its (compositional) representations match the ones learned by the RNN.     \n\nAs far as in understand, beyond the understanding of the learned representations in RNNs, the paper motivates the work with the expectation that the gained knowledge might be useful for designing better neural nets, with improved generalization ability. Yet i don’t  see clearly what could be done on this line.  ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkefx69aKS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the problem of understanding the compositional generalization abilities of NNs. A new type of NN, called ROLE, is proposed to learns to approximate the representations of a target NN E by learning a symbolic constituent structure and an embedding of that structure intoE’s representational vector space. A number of tasks are conducted, including a simple fully-compositional task, a SCAN task, a partially-compositional NLP task. Multiple tasks. The experiment results show that the proposed approach can help to understand how NNs achieve strong generalization on partially-compositional tasks, and good performance on fully-compositional task. \nPros:\n1. This work studies an important problem of fundamental AI.\n2. Authors conduct experiments on multiple task to evaluate the effectiveness of the proposed technique and show how it helps to understand the generalization of NNs.\n3. The overall paper is well written, except for some typos, e.g. in page 5, Table 1 Should \"1.0\" be \"100%\"? Should \"0.828 be ''82.80\".  \nCons:\n1. Regarding the Q2 raised in the paper, only simple suggestions are given. It is suggested to evaluate its effectiveness on some real experiments.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work builds directly on McCoy et al. (2019a) and add a RNN that can replace what was human generated hypotheses to the role schemes. The final goal of ROLE is to analyze a network by identifying ‘symbolic structure’. The authors conduct sanity check by conducting experiments with ground truth, and extend the work further to apply it to a complex model. I wonder under what definition of ‘interpretable’ authors have in mind with the final output (figure 2) - the output is very complex. It remains questionable if this will give some ‘insight’ or how would humans parse this info such that it is ‘useful’ for them in some way. 

Overall, though this is a good paper, due to the number of strong papers this year, it cannot be accepted at this time. We hope the comments given by reviewers can help improve a future version. 

Decision: Reject