Year: 2019

Abstract:
Widely used recurrent units, including Long-short Term Memory (LSTM) and the Gated Recurrent Unit (GRU), perform well on natural language tasks, but their ability to learn structured representations is still questionable. Exploiting reduced Tensor Product Representations (TPRs) — distributed representations of symbolic structure in which vector-embedded symbols are bound to vector-embedded structural positions — we propose the TPRU, a simple recurrent unit that, at each time step, explicitly executes structural-role binding and unbinding operations to incorporate structural information into learning. A gradient analysis of our proposed TPRU is conducted to support our model design, and its performance on multiple datasets shows the effectiveness of our design choices. Furthermore, observations on a linguistically grounded study demonstrate the interpretability of our TPRU.

heading: 1 INTRODUCTION
text: Recurrent units are widely used in sequence modelling tasks, including text, speech, DNA/RNA sequencing data, etc. Due to their ability to produce distributed vector representations for sequences with various lengths, and their property of being a universal function approximators (Schäfer & Zimmermann, 2006), they quickly succeeded in numerous research areas. The training algorithm, backpropagation through time (BPTT, Werbos et al., 1990), has remained the same across the years, with known gradient vanishing and exploding issues. Many theoretically justifiable or empirically useful regularisations (Pascanu et al., 2013; Kanai et al., 2017) have been proposed to ease the learning process and to smooth the gradient flow for long sequences, and informative analysis methods have been conducted to visualise the information encoded in the learnt vector representations (Zeiler & Fergus, 2013; Karpathy et al., 2015). The main difficulty in understanding the learning process of a particular RNN unit comes from the extreme nonlinear activation functions, which cause the gradient flow to be chaotic. Here, we aim to propose a recurrent unit that has fewer nonlinear operations by incorporating Tensor Product Representations (Smolensky, 1990).
Tensor product representation (TPR) is an instantiation of general neural-symbolic computing in which symbol structures are embedded in a vector space via a filler-role decomposition: the structure is captured by a set of N roles ri (e.g., left-child-of-root), each of which is bound to a filler fi (a symbol or substructure). A TPR embedding of a symbol structure S derives from vector embeddings of the roles {ri} and their fillers {fi} via the outer or tensor product: S =
∑N i=1 ri ⊗ fi =∑N
i=1 rif > i = RF >, where R and F respectively denote matrices having the role or filler vectors of S as columns. Each ri⊗ fi is the embedding of a role-filler binding: a constituent; ⊗ is the binding operation. The unbinding operation returns the filler of a particular role in S; it is performed by the inner product: fi = u>i S, where ui is the dual of ri, satisfying u>i rj = δij ≡ 1 if i = j else 0. Letting U be the matrix with columns {ui}, we have U>R = I.
Our goal is to propose a recurrent unit that uses a reduced version of a tensor product representation, a vector rather than an order-2 tensor: this arises by reducing the dimension of the filler embeddings to 1; with role embeddings of dimension d, the representation becomes b = ∑N i=1 firi ∈ R
d. We let this sum range over all N possible roles, letting fi = 0 when role ri is unfilled. Then at time t, the hidden state of our RNN — which we call the binding complex — will be bt = ∑N i=1(ft)iri where ft is the vector of filler values (ft)i ∈ R at time t. Now binding is performed by a simple matrix-vector product, and unbinding by a simple inner product:
bt = Rft ft = U >bt (1)
In this paper:
• In the context of related work (Sec. 2) and based on the reduced tensor product representations introduced above, we propose a gated recurrent unit, the TPRU (Sec. 3), along with a set of analyses of the gradient flow to justify our decisions in architecture design (Sec. 4). Even though the number of nonlinear operations is reduced, the success in experiments attests to the flexibility of our TPRU in learning and our analysis on derivatives further supports it.
• Our proposed TPRU demonstrates strong performance on the Logical Entailment task (Evans et al., 2018), Natural Language Inference datasets (Williams et al., 2017), and language modelling, while having comparably many parameters as the GRU, and significantly fewer than the widely-used LSTM (Sec. 5).
• The instantiation of reduced TPRs allows our model to learn decomposable representations, and the filler ft provides an interface for us to inspect the information encoded in bt (Sec. 6). We conducted a linguistically grounded study, which shows that our TPRU is capable of distinguishing multiple senses of a polysemous word and discovering structured information in sentences.

heading: 2 RELATED WORK
text: Recent efforts on understanding RNNs includes these three classes: (i) theoretical analysis through advancements in dynamic systems on the functions learnt by RNN units (Chang et al., 2019); (ii) linguistically grounded analysis by developing sets of probing tasks to illustrate the properties of learnt vector representations of RNNs (Conneau et al., 2018; Chrupała & Alishahi, 2019); and (iii) introducing inductive biases into the architecture of networks and comparing the behaviour of learnt models against those of widely-used counterparts. Our work falls in this last category: learning structured representations by incorporating the inductive biases inherent in TPRs.
Some prior work has incorporated TPRs into RNN representations. Question-answering on SQuAD (Rajpurkar et al., 2016) was addressed (Palangi et al., 2017) with an LSTM with hidden state given by a single TPR binding; the present work deploys complexes containing multiple bindings (albeit reduced ones). TPR-style unbinding was applied in caption generation (Huang et al., 2018), but the representations were deep-learnt and not explicitly designed to be TPRs as in the present work. A contracted version of TPRs, Holographic Reduced Representations, was utilised to decompose input space and output space with filler-role decomposition (Luo et al., 2019). Our work differs from these prior papers in that TPR filler-role binding and unbinding operations are explicitly carried out in our proposed recurrent unit, and the two operations directly determine the update of the hidden states. Closest to the present work is Schlag & Schmidhuber (2018), which performed questionanswering by using TPRs to embed simple knowledge graphs as tensors; our model does not deploy graph-based inference, which is less natural for the inference tasks we address than it is for the question-answering task addressed in Schlag & Schmidhuber (2018).
Our proposed TPRU inherits the explicit binding and unbinding operations in TPRs in the sense that a set of role vectors are shared across time steps and sequences to serve as a basis for composing distributed vector representations. We provide a set of analyses from both theoretical and empirical perspectives: gradient analysis of our model helps us make sense of the architecture design, while empirical results from three different categories of tasks show the effectiveness of the proposed model. Additional study on the linguistic and learning aspects provide evidence that our model indeed inherits the merits of TPRs, which enhance interpretability and the capability of learning structured representations.

heading: 3 PROPOSED RECURRENT UNIT: THE TPRU
text: As shown in both LSTM (Hochreiter & Schmidhuber, 1997) and GRU (Chung et al., 2014) design, a gating mechanism helps the hidden state at the current time step to directly copy information from the previous time step, and alleviate vanishing and exploding gradient issues. Our proposed recurrent unit deploys a single gate, adopting the input gate of the GRU, omitting the reset gate. We expect that further augmenting our TPRU to 2 gates as in the GRU, or 3 gates as in the LSTM, will lead to yet better performance.
At each time step, the TPRU receives two input vectors: bt−1 ∈ Rd, the binding complex from the TPRU at the previous time-step, and xt ∈ Rd ′ from the external input; it produces bt ∈ Rd. An input gate gt ∈ Rd is computed to produce a weighted sum of the information generated at the current time step, b̃t ∈ Rd, and the previous binding complex bt−1,
bt = gt ◦ b̃t + (1− gt) ◦ bt−1, where gt = σ(Wbbt−1 +Wxxt), (2)
σ(·) is the logistic sigmoid function (applied element-wise), ◦ is the Hadamard (element-wise) product, and Wb ∈ Rd×d and Wx ∈ Rd×d ′ are matrices of learnable parameters. As we now explain, the calculation of b̃t is carried out by the unbinding and binding operations of TPRs (Eq. 1).

heading: 3.1 UNBINDING OPERATION
text: Consider a set of hypothesised unbinding vectors U = [u1,u2, ...,uN ] ∈ Rd×N . At time step t, these can be used to unbind fillers fb,t from the previous binding complex bt−1 using Eq. 1. We posit two matrices Vx ∈ Rd×d ′ and Vb ∈ Rd×d that transform the current input xt ∈ Rd ′ and the binding complex bt−1 into the binding space Rd yielding fillers fx,t and fb,t :
fb,t = U >Vbbt−1 ∈ RN , fx,t = U>Vxxt ∈ RN . (3)
Normalisation is applied for stable learning by gradient descent, and the specific technique (Yang et al., 2018) we adopted here also enforces sparsity on both fb,t and fx,t:
(ft)n = (f̃t) 2 n/ ∑N m=1(f̃t) 2 m (4)
where (f̃t)n = max(0, (fb,t)n + bb) + max(0, (fx,t)n + bx) (5)
in which bb and bx are two scalar parameters for stable learning, and (·)n refers to the n-th entry of the vector in the parentheses.

heading: 3.2 BINDING OPERATION
text: Given a hypothesised set of binding role vectors R = [r1, r2, ..., rN ] ∈ Rd×N , applying the binding operation in Eq. 1 to the fillers ft at time t gives the candidate update b̃t for the binding complex,
b̃t = Rft. (6)
The gating mechanism controls the weighted sum of the candidate vector b̃t and the previous binding complex bt−1 to produce a binding complex bt at the current time step, as given by Eq. 2.

heading: 3.3 UNBINDING AND BINDING ROLE VECTORS
text: In the TPRU, there is a matrix of role vectors R used for the binding operation and a matrix of unbinding vectors U used for the unbinding operation. To control the number of parameters in our TPRU, rendering it independent of N , instead of directly learning two sets of vectors, a set of N ddimensional random vectors E is sampled from a normal distribution, and two linear projections Wr,Wu ∈ Rd×d are learnt to transform E to U = WuE and R = WrE.
Therefore, in total, our proposed TPRU has six learnable matrices: Wu, Wr, Vb, Wb ∈ Rd×d and Vx, Wx ∈ Rd×d ′ . The number of parameter matrices the same as that of a GRU and less than that of an LSTM, and, when d′ < d, the number of learnable parameters is less than that of a GRU.

heading: 4 GRADIENT ANALYSIS AND COMPLEXITY
text: This section analyses the derivatives in our proposed TPRU, and aims to justify the architecture design. For simplicity, we omit the derivatives w.r.t. bias terms in our derivations as biases can be absorbed into the weight matrices by adding an extra component 1 to the input.
As known, the gradient of an RNN cell is accumulated in time ∂bT ∂b1
= ∏T−1
t=1 ∂bt+1 ∂bt , therefore, studying the properties of the derivative of the output at the current time step bt (Eq. 2) w.r.t. the output
of the previous time step bt−1 is important for understanding the behaviour of a recurrent unit. For our TPRU, the derivative is shown below:
∂bt ∂bt−1 = ∂bt ∂gt ∂gt ∂bt−1 + ∂bt
∂b̃t
∂b̃t ∂bt−1 + ∂((1− gt) ◦ bt−1) ∂bt−1 = Λ1Wb +Λ2 ∂b̃t ∂bt−1 +Λ3 (7)
where Λ1, Λ2 and Λ3 are diagonal matrices in Rd×d, in which (Λ1)ii = (b̃t)i(gt)i(1−(gt)i), (Λ2)ii = (gt)i and (Λ3)ii = (1 − (gt)i). It is clear that the gating mechanism smooths the gradient flow as it jitters the Jacobian matrix by adding small values to the diagonal terms, and from a dynamic system perspective, it helps stabilise the learning system (Moya-Cessa & Soto-Eguibar, 2011). Now we focus on the following derivative which carries the main information of our proposed TPRU.
∂b̃t ∂bt−1 = ∂b̃t ∂ft ∂ft ∂fb,t ∂fb,t ∂bt−1 = (WrE) (JtNtSb,t) (E >W>u Vb) (8)
where Nt,Sb,t ∈ RN×N are diagonal matrices, in which (Nt)nn = 2/(f̃t)n and (Sb,t)nn = 1(fb,t)n>0, and (Jt)mn = (fb,t)m(δmn − (fb,t)n). Appendix A shows that Jt is a positive semi-definite matrix, and its eigenvalues are all smaller than maxn(fb,t)n ≤ 1.
There are three crucial design choices, including (1) learnable parameter matrices Wr and Wu to transform the basis matrix E separately, (2) learnable linear transformation Vb on the binding complex at each time step bt, and (3) the relu-squared normalisation in Eq. 4. The following analysis shows that certain modifications could lead to issues during learning, and helps understand the necessity of each component.
Modification I. Wr = Wu, Vb = Id and softmax normalisation in Eq. 4. The derivative of the softmax normalisation of outputs w.r.t. the inputs is simply Jt as Sb,t = Nt = IN .1 Given the conditions, the derivative can be simplified to:
∂b̃t/∂bt−1 = WrEJtNtSb,tE >W>u Vb = WrEJtE >W>r 0 (9)
In this case, as the derivative gets multipled several times by BPTT, the gradient w.r.t. each parameter matrix either explodes or vanishes depending on the spectrum of WrE. Also, a careful initialisation is required otherwise the gradient could overflow or underflow after the first iteration.
Modification II. Wr = Wu, and softmax normalisation. Here we allow learnable parameter matrices Vb to transform the binding complex from the previous time step bt−1, thus, the derivative of b̃t w.r.t. bt−1 and that to i-th row of Vb are shown below:
∂b̃t/∂bt−1 = WrEJtE >W>r Vb ∂b̃t/∂(Vb)i· = (WrEJtE >W>r )·ibt−1 (10)
Since WrEJtE>W>r 0, ∂b̃t/∂(Vb)i· always has a non-negative inner product with bt−1, which means that the update of Vb always contains a positive portion of bt−1. The same situation also applies when updating Vx as it keeps a positive portion of xt as well. It limits the learning system from eliminating accumulated useless information. Although it is still possible that, after backpropagation through several time steps, the positive portion of bt−1 could be suppressed, we set Wr and Wu to be independent matrices so that the above constraint isn’t imposed.
Modification III. Softmax normalisation.
The only modification here is to replace the normalisation step in Eq. 4 in our TPRU to a softmax function that also normalises f̃t to form a distribution ft. At each time step, the derivative of b̃t w.r.t. any parameter matrix before the normalisation step contains ∂ft/∂f̃t, and in the softmax normalisation, only the relative difference, (f̃t)n −maxm(f̃t)m, ∀n ∈ {1, 2, ..., N}, matters.
Therefore, there is no explicit regularisation in the derivative of ∂b̃t/∂bt−1 = WrEJtE>W>u Vb to penalise extreme values in f̃t, which could lead to gradients with large norms and make the learning process unstable. This may also explain why, in the transformer module (Vaswani et al., 2017), layer normalisation (Ba et al., 2016) is necessary, as it scales the gradient by the variance of the input.
We don’t rule out the possibility that there exists a suitable initialisation which gives stable learning and decent performance, but the normalisation step we adopted from prior work (Yang et al., 2018) avoids heavy tuning of initialisations for stable learning.
1IN is an identity matrix in RN×N .
Ours. Here, we recall that the derivative of ∂b̃t/∂bt−1 is in Eq. 8. The term Nt scales the derivative by the magnitude of the input f̃t to Eq. 4, which regularises the norm of the gradient to each parameter matrix. Specifically, the following derivative indicates the update of i-th row in Wu:
∂b̃t ∂(Wu)i· = ∂b̃t ∂fb,t ∂fb,t ∂(Wu)i· + ∂b̃t ∂fx,t ∂fx,t ∂(Wu)i· = WrEJtNt (Sb,t(Vbbt−1)i + Sx,t(Vxxt)i)E > (11)
where Nt normalises the contribution from fb,t and fx,t, and Sb,t and Sx,t select positive contributions only, thus the normalisation step in Eq. 4 helps the gradients w.r.t. parameter matrices to stay stable. Eq. 11 also shows that the update of each row in Wu depends on a sparse linear transformation of Wr, which could potentially avoid overfitting as not all dimensions in the representation space are utilised and our TPRU learns to discover the representation space.
Given the derivative above, it is easy to see that the presampled matrix E acts similarly as the preconditioning matrix in solving large linear systems, and with samples from a normal distribution or zero-centred uniform distribution, it smooths the spectrum of the Jacobian matrix and stabilizes the learning system.
Time Complexity in Forward Computation
Table 1 presents the time complexity of calculating each of our proposed TPRU, LSTM and GRU for a single time step. In the calculation, we only kept the terms that involve second order of variables. As shown, the time complexity of TPRU is in between LSTM and GRU when the number of role vectorsN is less than the di-
mension of the recurrent unit d. However, the number of parameters in our TPRU is fewer than in an LSTM, and comparable to a GRU.
In addition, as concerns nonlinearities, our TPRU contains max(x, 0)2 only N times, and sigmoid functions only d times; this is fewer than sigmoid/tanh squashing functions appearing 5d times in an LSTM and 3d times in a GRU. The nonlinear operations are indeed reduced in our TPRU, and the following sections show that our TPRU still provides strong performance on evaluation tasks.

heading: 5 TASKS AND TRAINING DETAILS
text: Three entailment tasks, including an abstract logical entailment task (Evans et al., 2018) and two relatively realistic natural language entailment tasks, including Multi-genre Natural Language Inference (MNLI, Williams et al. (2017)) and Question Natural Language Inference (QNLI, Wang et al. (2018)), as well as a language modelling task on a large corpus and a small one, (WikiText-103 and WikiText-2 (Merity et al., 2018)), are considered to demonstrate the learning ability of our proposed TPRU. Each of the three entailment tasks provides pairs of samples, and for each pair, the model needs to tell whether the first (the premise) entails the second (the hypothesis). Language modelling is used to demonstrate the ability of our proposed model on sequential modelling.
Experiments are conducted in PyTorch (Paszke et al., 2017) with the Adam optimiser (Kingma & Ba, 2014) and gradient clipping (Pascanu et al., 2013). Reported results are averaged from the results of three random initialisations. Our proposed TPRU has only one input gate and also has similar number of parameters, so the GRU is the most relevant comparison partner. LSTM is also included as it is widely-used as well and it generally yields better performance than GRU does. For each model, hyperparameters are searched based on the small selected validation set on each task, including dropout rates, learning rate and batch size. For entailment tasks, we tested both plain and BiDAF architectures (Seo et al., 2017). On both NLI tasks, ELMo (Peters et al., 2018) encoding is applied for embedding words into contextualised vectors. More details about the tasks and the training details can be found in Sections B and C in the Appendix.

heading: 6 DISCUSSION
text: On the Logical Entailment task in Table 2, when it comes to larger dimensionality (N = 512), our TPRU appears to be more stable than GRU during learning as we observed that the GRU with the
BiDAF architecture failed to converge in two out of three trials. On certain test sets, our (singlygated) TPRU slightly underperforms the LSTM, possibly due to the three gates (and more parameters) of the LSTM: future research could incorporate more sophisticated gating mechanisms into the TPRU.
On the MNLI tasks in Table 3, our proposed TPRU consistently outperforms the LSTM when a large number of role vectors is deployed. We omit the results from GRUs as they are worse than LSTMs and often unstable in learning. Unexpectedly, all models perform better on the mismatched dev set than on the matched one, perhaps because it happens to be easier.
On the language modelling task on WikiText-103 and WikiText-2, our TPRU provides similar perplexity on the test set to the LSTM, as shown in Table 4. The learning plot in Figure 4 shows that our TPRU learns faster on the training set than the GRU and the LSTM. The learning plot and the performance table both serve as evidential support for the gradient analysis of our model.

heading: 6.1 POLYSEMY
text: In TPR, multiple senses of a single polysemous word can be encoded by binding the same symbol that represents the polysemous word to different role vectors {ri}. TPR is composing a distributed representation that keeps multiple senses of a polysemous word and recovering each sense with no information loss if a large number of dimensions is available. In our case, the magnitude of each entry in ft determines the contribution of each role vector to the update candidate b̃t (Eq. 6).
We train our TPRU with a BiDAF architecture on the MNLI dataset, and word vectors are obtained from fastText (Bojanowski et al., 2017) as the input to our model so that the vector representation of a polysemous word stays the same even when it is presented in different contexts. After learning, our model provides an interface for us to check whether a specific role vector correlates to a specific sense of a polysemous word in different phrases in the dev set by computing βt = argmaxn(ft)n.
For example, a common polysemous word bank has two senses when it is used as a noun. In the dev set of MNLI, the only case when bank is used in the river-context is in the phrase “bank fishing”, and the rest belong to the other sense in the context of economy. We observed that β is the same when bank occurs in “bank fishing” and we denote it as βriver, thus, P (β = βriver|bank in the river-context) = 1. It is also important to see if the specific βriver is dedicated to the word bank in the river context. After examining the dev set, we have P (bank in the river-context|β = βriver) = P (bank in “the west bank”|β = βriver) = 0.5; clearly, the sense of “bank” relevant to the phrase “the west bank” is the one related to rivers, not finances.

heading: 6.2 POS TAGGING
text: We calculated the pointwise mutual information (PMI) between the following two terms: 1) The maximally selected role vector at each time step βt = argmaxn(ft)n and 2) The part-of-speech tag (POS Tag) provided by a pretrained tagger.2 For a given POS tag, the PMIs of role vectors are sorted in a descending order, and Table 5 presents the top two PMI values for those POS tags for which these two values differ by at least 0.5: this includes 7 out of 17 fine-grained POS tags. The idea is that if the top PMI value is sufficiently greater than the next one, and hence all the rest, then it is justified to say that each POS tag in the table shown below has a role ’dedicated’ to it.
As the model is only trained on MNLI to predict the entailment relationship between a given pair of sentences without access to POS tags, it is interesting that some role vectors become associated with specific POS tags. Since POS tags carry structural information of a given sentence, and since the roles learnt by the TPRU are informative about the POS tags, we have evidence that the roles that explicitly define the structure of the model’s representations are capturing some of the distinctions between words that are believed to be fundamental to linguistic structure.
As pointed out in prior work, models trained on MNLI focus on words in lexical (non-functional) categories in determining the entailment relationship between a sentence pair; here we see that POS tags of lexical words, including NOUN, PROPN, VERB, etc., have a larger gap between the top 2 highest PMI values as they are apparently emphasised by the learning signal. This finding suggests
2https://spacy.io/api/doc
that our learnt model might help to identify the biases in datasets — which could be helpful in improving fairness and inclusiveness.
The above two empirical observations point out that our proposed TPRU inherits the interpretability of the original TPRs, and provides a certain level of human-readability. It provides a simple interface for us to analyse the learnt model through the explicit binding and unbinding operations.

heading: 6.3 EFFECT OF INCREASING THE NUMBER OF ROLE VECTORS
text: In the original TPRs, roles are typically filled by at most a single symbol, so the total number of distinct roles indicates the number of symbols that can be used in the representation of a single data item. Since each symbol is capable of representing a specific substructure of the input data, increasing the number of role vectors eventually leads to more highly structured representations if there is no limit on the dimensionality of role vectors.
Experiments are conducted to show the effect of increasing the number of role vectors on the performance on both Logical Entailment and MNLI. As shown in Table 3, adding more role vectors into our proposed TPRU gradually improves the performance on the two entailment tasks.
Figure 1 presents the learning curves, including training loss and accuracy, of our proposed TPRU with varying number of role vectors on the two entailment tasks. As shown in the graphs, incorporating more role vectors leads to not only better performance, but also faster convergence during training. The observation is consistent on both the Logical Entailment and MNLI tasks.
Interestingly, on the Logical Entailment task, the performance of our proposed TPRU with only eight role vectors matches that of a GRU with the same dimensionality. The number of role vectors required in our TPRU to approximately match the performance of a GRU and an LSTM on the MNLI task is much less than the dimension of the hidden states, which suggests that the distributed vector representations learnt in both the LSTM and GRU are highly redundant and can be reduced to fewer dimensions; this also implies that the LSTM and GRU are not able to extensively exploit the representation space even when the dimensionality of the model is larger than that required for solving the task. Meanwhile, our proposed TPRU explores sparse weighted combinations of role vectors in Eq. 4, and it helps the model to specialise individual role vectors for different purposes, which eventually leads to a more effective exploitation of the representation space.

heading: 7 CONCLUSION
text: We have proposed a simple recurrent unit that leverages the explicit binding and unbinding operations in previously proposed TPRs in a reduced fashion, therefore it is named the TPRU. The explicit execution arms the proposed model with the ability to learn decomposable representations, and by sharing the role vectors across time steps and sequences, our TPRU provides research an intuitive interface through ft to study the information encoded in the learnt distributed vector representations.
Since recurrent neural networks are prone to suffer from the gradient vanishing and exploding issues, we conduct a thorough analysis of the derivatives and the gradient update of our proposed TPRU on
each time step. The conducted analysis supports our decisions in designing TPRU, and it shows that it encourages relatively more stable gradient flow through BPTT. The time complexity for executing one step of our TPRU is lower than that of LSTM, and it has the same or a smaller number of parameters than the GRU does, which justifies the simplicity of our recurrent unit.
The empirical evaluation on five learning tasks in three different categories demonstrate the effectiveness of our TPRU as it performs on a par with or better than the LSTM. The study on increasing the number of role vectors and plots on the loss curves during learning shows that our model converges faster than the GRU and the LSTM in general and it is a result of the stable gradient flow through multiple time steps. In addition, our proposed TPRU enables a faster convergence rate and better performance by increasing the number of role vectors.
A study on correlating the role vectors with linguistic properties of languages shows that our TPRU inherits the strong interpretability of TPRs. In the toy example involving a polysemous word bank, our model can differentiate multiple senses of the word, and can assign a similar sense, even in a named entity, to its closely related one. Also, the PMI values between POS tags and maximally selected role vectors imply that our TPRU is capable of discovering syntactically-structured linguistic information.
Given the current pressing need for interpretable machine learning and learning decomposable representations, our proposed TPRU can be regarded as a more light-weight and human-readable alternative to the widely-used LSTM or GRU. Future work will focus on incorporating full TPRs into the design of an RNN unit and into the Transformer module.

heading: A PROOF
text: 1. Jt is a PSD matrix. For any non-zero vector v, we have
v>Jtv = N∑ n=1 (fb,t)nv 2 n − ( N∑ n=1 (fb,t)nvn) 2 (12)
≥ ( N∑
n=1
(fb,t)nvn) 2 − ( N∑ n=1 (fb,t)nvn) 2 = 0 (Jensen’s Inequality) (13)
Therefore, Jt is a PSD matrix.

heading: B DETAILS ABOUT TASKS
text: Three entailment tasks, including an abstract logical entailment task and two relatively realistic natural language entailment tasks, as well as a language modelling task on a large corpus and a small one, are considered to demonstrate that the learning ability of our proposed TPRU. Each of the three entailment tasks provides pairs of samples, and for each pair, the model needs to tell whether the first (the premise) entails the second (the hypothesis). Language modelling is used to demonstrate the ability of our proposed model on sequential modelling.
As our goal is to learn structured vector representations, the proposed TPRU serves as an encoding function, which learns to process a proposition or sentence one token at a time, and produce a vector representation. During learning, two vector representations are produced by the same recurrent unit given a pair of samples, then a simple feature engineering method (e.g. concatenation of the two representations) is applied to form an input vector for subsequent classification. In general, with a simple classifier, e.g. a linear classifier or a multi-layer perceptron with a single hidden layer, the learning process forces the encoding function to produce high-quality representations of samples, either propositions or sentences; better representations enable stronger performance.
B.1 LOGICAL ENTAILMENT (PROPOSITIONAL LOGIC)
In propositional logic, for a pair of propositions, A and B, the value of A B is independent of the identities of the shared variables between A and B, and is dependent only on the structure of the expression and the connectives in each subexpression. Because of α-equivalence, p∧q q holds no matter how we replace variable p or q with any other propositional variables.3 Logical entailment is
3For example, p ∧ q q ⇔ a ∧ b a.
thus a good test-bed for evaluating a model’s ability to carry out abstract, highly structure-sensitive reasoning (Evans et al., 2018).
Theoretically, it is possible to construct a truth table that contains as rows/worlds all possible combinations of values of variables in both propositions A and B; the value of A B can be checked by going through every entry in each row. As the logical entailment task emphasises reasoning on connectives, it requires the learnt distributed vector representations to encode the structure of any given proposition to excel at the task.
The Logical Entailment dataset4 has balanced positive (A B) and negative (A 2 B) classes and a representative validation set. Five test sets are provided to evaluate the generalisation ability at different difficulty levels: some test sets have significantly more variables and operators than the training and validation sets (see Table 2).
B.2 NATURAL LANGUAGE INFERENCE
Natural Language Inference — determining whether a premise sentence entails a hypothesis sentence — combines the structure-dependence of logical entailment with the NLP tasks of inferring word meaning in context as well as the hierarchical relations among sentence constituents. Two datasets are considered, which are Multi-genre NLI and QNLI (Williams et al., 2017; Wang et al., 2018). Compared to logical entailment, the inference and reasoning in NLI also relies on the identities of words in sentences in addition to their structure. More importantly, the ambiguity and polysemy of language lead to the impossibility of creating a truth table that lists all cases. Therefore, NLI is an intrinsically hard task.
The Multi-genre Natural Language Inference (MNLI) dataset (Williams et al., 2017) collects sentence pairs in ten genres; only five genres are available in the training set, while all ten genres are presented in the development set. QNLI (Wang et al., 2018) is collected from Stanford Question Answering dataset (SQuAD) (Rajpurkar et al., 2016), on which a model needs to predict whether the context sentence contains the answer to the question sentence or not. The relation between sentences in a pair must be classified as Entailment, Neutral or Contradiction.
The performance of a model on the five ‘mismatched’ genres that exist in the development but not the training set reflects how well the structure encoded in distributed vector representations of sentences learnt from genres seen in training generalises to sentence pairs in unseen genres. As the nature of NLI tasks requires inferring both word meaning and structure of constituents in a given sentence, supervised training signals from labelled datasets enforce an encoding function to analyse meaning and structure at the same time during learning, which eventually forces distributed vector representations of sentences produced from the learnt encoding function to be structured. To the extent that the inferences required in an NLI task are demanding of proper analysis of the logical structure implicit in sentence, an inductive bias that enhances the ability to learn to encode the structures of sentences should enhance success on the MNLI task.
B.3 LANGUAGE MODELLING
Language modelling is a fundamental task to test generalisation and sequential modelling. Recent research has shown that models trained on language modelling tasks yield representations that can transfer well to other natural language tasks (Peters et al., 2018; Radford et al., 2018; Devlin et al., 2018). We follow the autoregressive setting of decomposing the joint probability on tokens into a product of conditional probabilities on generating the current token given tokens in the left context.
P (w1, w2, ..., wL) = L∏ l=1 P (wl|wl−1, wl−2, ..., w1). (14)
This requires the learnt representation to capture the potentially highly structured information accumulated prior to the current time step in order to make a confident prediction of the current token. A proper inductive bias towards constructing structured representations should enhance performance on the task. Two corpora used in our experiment are WikiText-103 and WikiText-2 (Merity et al., 2018), in which one contains 103 million tokens in the training set while the other only has 2 million. The results will tell us how well our proposed TPRU generalises across different training scales.
4https://github.com/deepmind/logical-entailment-dataset

heading: C DETAILS ABOUT ARCHITECTURE
text: C.1 PLAIN ARCHITECTURE - INFERENCE:
For both the Logical Entailment task and the MNLI task, we train two-layer recurrent networks built using our proposed TPRU, networks built using its direct comparison counterpart, the GRU, as well as LSTMs. A global max-pooling over time is applied to the hidden states produced by each recurrent unit at all time steps to generate the vector representation for a given logical proposition or sentence. Given a pair of generated representations u and v, a vector is constructed to represent the difference between two vectors [u;v; |u− v|;u ◦ v], where u ◦ v is the Hadamard product and |u− v| is the absolute difference, and the vector is fed into a multi-layer perceptron which has only one hidden layer with ReLU activation function. The feature engineering and the choice of classifier are suggested by prior work (Seo et al., 2017; Wang et al., 2018).
Symbolic Vocabulary Permutation (Evans et al., 2018) is applied as data augmentation during learning on the logical entailment task: exploiting α-equivalence, this systematically replaces the variables in a proposition pair with randomly sampled alternative variables, as only connectives matter on this task. Table 2 presents the results. For the MNLI task, the Stanford Natural Language Inference (SNLI) dataset (Bowman et al., 2015) is included as additional training data as recommended (Wang et al., 2018), and ELMo (Peters et al., 2018) is applied for producing word vectors. The best model is chosen according to the averaged classification accuracy on the five matched and five mismatched dev sets. The results are presented in Table 3. SOTA models come from Alibaba DAMO NLP Group, and the results are available on the GLUE leaderboard. 5
C.2 BIDAF ARCHITECTURE - INFERENCE:
Bi-directional Attention Flow (BiDAF) (Seo et al., 2017) has been successfully applied to various NLP tasks (Seo et al., 2017; Chen et al., 2017), and provides strong performance on NLI tasks (Wang et al., 2018). The BiDAF architecture contains a layer for encoding two input sequences, and another for encoding the concatenation of the output from the first layer and the context vectors determined by the bi-directional attention mechanism. In our experiments, the dimensions of both layers are set to be the same, and the same type of recurrent unit is applied across both layers. The same settings are used for experiments on LSTM and our TPRU models. Specifically, for TPRU, the recurrent units in both layers have the same number of role vectors. Other learning details are as in the plain architecture. Tables 2 and 3 respectively present results on the Logical Entailment and the MNLI task, with BiDAF results in parentheses.
C.3 LANGUAGE MODELLING:
On the language modelling task, the same two-layer architecture (Merity et al., 2018) is adopted in our experiments on LSTM and our proposed TPRU. For WikiText-103, Bytepair encoding (BPE) vocabulary with 100k merges (10k for WikiText-2) are applied to encode the corpus into indices (Sennrich et al., 2016). The output prediction layer is tied to the input word embedding layer as advised in prior work (Press & Wolf, 2017; Inan et al., 2016). Each model is trained for 64 epochs on the training set; the best one is selected based on perplexity on the validation set, and then evaluated on the test set. Table 4 shows the best performance of each model after the hyperparameter search.

heading: D POLYSEMY
text: In the dev set of MNLI, the word bank occurs in the following sentences:
1. according to this plan , areas that were predominantly arab the gaza strip , the central part of the country , the northwest corner , and the west bank were to remain under arab control as palestine , while the southern negev desert and the northern coastal strip would form the new state of israel .
5https://gluebenchmark.com/leaderboard
2. well uh normally i like to to go out fishing in a boat and uh rather than like bank fishing and just like you try and catch anything that ’s swimming because i ’ve had such problems of trying to catch any type of fish that uh i just really enjoy doing the boat type fishing .
3. the other bank pays the fund interest based upon tiered account levels , more typical of a large commercial account .
The above sentences are three examples, there are other sentences in which the word bank occurs. As we show in the main paper, after learning, our TPRU categories the first two cases, in which one refers the West Bank of the Jordan river, and the other refers to the bank in the river context, as the same sense, as there is no clear learning signal that specifies the first one as a named entity, and categorises the third sentence into another sense.

heading: E EFFECT OF INCREASING THE DIMENSIONALITY OF FILLERS/SYMBOLS
text: Both fillers and roles in TPRs (Smolensky, 1990) are tensors with arbitrary dimensions, which empowers the representation ability of TPRs. In our case, as we aim to produce a distributed vector representation of the given input sequence rather than a tensor representation, the fillers are reduced to filler numbers, in which case, the symbol represented by each filler is limited to one-dimensional vector.
In our proposed TPRU, the unbinding operation is instantiated by the dot-product (inner-product) operation between the binding complex and the unbinding vectors. One plausible way to upgrade filler numbers to filler vectors is to split the binding complex into multiple slices, and split each unbinding vector accordingly: then the dot-product is carried out on each pair of slices rather than the entire vector. In this case, the dimension of the resulting filler vectors is determined by the number of slices predefined prior to learning, and is limited by the dimension of the binding complex. The normalisation step is operated on the same dimension on multiple filler vectors independently and in parallel, which results in multiple normalised probability distributions. Each binding role vector is split into the same number of slices, and each distribution is applied to bind the same slices from all binding role vectors into a single slice. All slices are concatenated together to form a single vector which has the same dimensionality as the input binding complex. A similar idea was proposed as the multi-head attention mechanism in prior work and has been shown to be effective in terms of performance gain without additional computational cost (Vaswani et al., 2017). It was widely adopted in prior work on Transformer networks for various tasks.
In our implementation of the Logical Entailment task, the binding complex is split into eight slices, each with the same dimension. Figure 2 shows training logs with eight slices and also with only one slice for three different numbers of role vectors in our proposed TPRU. In general, shifting from filler numbers to filler vectors in our TPRU provides faster convergence and better performance on the training set. However, as the number of role vectors increases, the improvement gained decreases,
which leads to an interesting hypothesis that the effect of increasing number of role vectors might be correlated to that of increasing the dimensionality of filler vectors.

Review summaries:
This paper proposes a novel model of recurrent unit for RNNs which is inspired from tensor product representation (TPR) introduced by Smolensky et al. in 1990. The authors claim that this allows one to better incorporate structural information into learning and easier interpretability for the learned representations. The proposed approach is motivated by a theoretical analysis showing that using TPR in this context acts as a sort of pre-conditioner and stabilizes learning. Experiments on entailment tasks (given two statement, decide whether the first implies the second) are provided to validate the approach.