A Neural Model for Compositional Word Embeddings and Sentence Processing (2022)

Abstract: We propose a new neural model for word embeddings, which uses Unitary Matrices as the primary device for encoding lexical information. It uses simple matrix multiplication to derive matrices for large units, yielding a sentence processing model that is strictly compositional, does not lose information over time steps, and is transparent, in the sense that word embeddings can be analysed regardless of context. This model does not employ activation functions, and so the network is fully accessible to analysis by the methods of linear algebra at each point in its operation on an input sequence. We test it in two NLP agreement tasks and obtain rule like perfect accuracy, with greater stability than current state-of-the-art systems. Our proposed model goes some way towards offering a class of computationally powerful deep learning systems that can be fully understood and compared to human cognitive processes for natural language learning and representation.

## introduction the word embeddings that deep neural networks (dnns) learn are encoded as vectors. the various dimensions of the vectors correspond to distributional properties of words, as measured in corpora. combining word embeddings into phrasal and sentence vectors can be achieved through various means, often through task-specific models with many parameters of their own, optimised by gradient descent. in this paper we use unitary matrices in place of arbitrary vector embeddings. @xcite propose unitary-evolution recurrent neural networks (urns), to eliminate exploding or vanishing gradients in gradient descent. by the definition of unitary-evolution, at each step, a unitary transformation is applied to the state of the rnn. this means that each input symbol is interpreted as a unitary transformation, or equivalently as a unitary matrix. no activation functions are applied between the time-steps. this design provides a lightweight dnn, with several attractive mathematical and computational properties. urns are strictly compositional. the effect of embeddings can be analysed independently of context. therefore the model is transparent, in the sense that it can be analysed by direct inspection, rather than through black box testing methods. so, for example, researchers are forced to resort to probe techniques @xcite to ascertain the syntactic structure which transformers and other dnns represent. because of the reversibility of unitary transformations, long distance dependency relations can, in principle, be reliably and efficiently recognised, without additional special-purpose machinery of the kind required in an lstm. this has been demonstrated to hold for copying and adding tasks @xcite @xcite (see also section 6.4). here we view the unitary matrices learned by a urn as word embeddings. doing so gives a richer structure to embeddings, with computational and formal advantages that are absent from the traditional vector format that dominates current work in deep learning. we demonstrate these advantages by applying the urn architecture to two tasks: (i) bracket matching in a generalised dyck language, and (ii) the more challenging task of subject-verb number agreement in english. these experiments confirm the long-distance capabilities of urns, even on a linguistically interesting and difficult task. the richer structure of unitary embeddings permits us to measure the relative effects and distances of different words and phrases. we illustrate the application of such metrics for both experiments. in section 2 we describe the design of the urn, and our implementation of it. sections 4 and 5 present our experiments and their results, leverag-ing the theory presented in section 3. 1 we discuss related work in section 6, and we draw conclusions and sketch future work in section 7. the computational perspicuity of urns allows them to be compared to psychologically and neurologically attested models of human learning and representation. most deep neural networks, particularly powerful transformers, use non-linear activation functions which render their operation opaque and difficult to understand. by contrast, the computations of an urn are explicitly given as simple matrix multiplications, and they are open to inspection at each point in the processing sequence. ## models in its full generality, a recurrent network is a function from an input state vector s 0 and a sequence of input vectors x i , such that the state at each timestep is a function of the state at the previous step and the input at that step: s i+1 = f (x i , s i ). the function f is constant across steps, and it is called a "cell" of the network. since the simple recurrent networks of @xcite , the dominant architectures of rnns, including the influential lstm @xcite , use non-linear activation functions (sigmoid , tanh, relu) at each timestep. transformer models, like bert, are even more opaque in their operations, due the their reliance on a large number of attention heads that apply non-linear functions at each level. by contrast our urns invoke only linear cells. in fact, the cell that we use is a linear transformation of the unitary space, 2 so that it takes unit state vectors to unit state vectors, hence the term "unitary-evolution". expressed as an equation, we have f (x, s) = q(x)s, where q(x) is unitary. therefore, only state vectors s i of norm 1 play a role in urns. in our implementation of the urn architecture we limit ourselves to real numbers, and so q(x) is properly described as an orthogonal matrix. we follow this terminology in what follows. let n be the dimension of the state vectors s i , and n the length of the sequence of inputs. we will consider only the case of n even. in all our experiments, we take s 0 to be the vector [1, 0, . . . ] without loss of generality. for predictions, we extract a probability distribution from state vectors 1 the code and relevant linear algebra proofs for our model is available at https://github.com/gu-clasp/ unitary-recurrent-network . 2 the subspace of vectors of unit norm by applying a dense layer with softmax activation to each s i . we need to ensure that q(x) is (and remains) orthogonal when it is subjected to gradient descent. in general, subtracting a gradient to an orthogonal matrix does not preserve orthogonality of the matrix. so we cannot make q(x) a simple lookup table from symbol to orthogonal matrix without additional restrictions. while one could project the matrix onto an orthogonal space @xcite , our solution is to use a lookup table mapping each word to a skew-hermitian matrix s(x). 3 we follow hyland and rätsch (2017) in doing this. we then let q(x) = e s(x) , which ensures the orthogonality of q(x). it is not difficult to ensure that s(x) is skew-symmetric. it suffices to store only the elements of s(x) above the diagonal, and let those below it be their anti-symmetric image, while the diagonal is set at zero. another important issue is that the number of parameters in s(x) grows with the square of n. this would entail that doubling a model's power requires quadrupling the number of its parameters. to remedy this problem we limit ourselves to matrices s(x) which have non-zero entries only on the first k rows (and consequently k columns). in this way we limit the total size of the embedding to (n -1) + (n -2) + • • • + (nk + 1), due to the constraint of symmetry. consequently, s(x) has at most rank 2k. below, we refer to this setup as consisting of truncated embeddings. as an example, the 3×3 skew-symmetric matrix we use the acronym urn to refer to the general class of unitary-evolution networks, k-turn to refer to our specific model architecture with ktruncation of embeddings (fig. 1 ), and full-urn for our model architecture with no truncation. we employ a standard training regime for our experiments. we apply a dropout function on both inputs of f , so that some entries of s i or q(x i ) will be zeroed out according to a bernoulli distribution figure 1: turn architecture. each input symbol x i indexes an embedding layer, yielding a skew-symmetric matrix s(x i ). taking its exponential yields an orthogonal matrix q(x i ). multiplying the state s i by q(x i ) yields the next state, s i+1 . ## properties of orthogonal embeddings the absence of activation functions in the urn make it more amenable to theoretical analysis than the general class of rnns with activation functions, including lstms and grus. the key feature of this design is that the behaviour of the cell is entirely defined by the matrix q(x), the orthogonal embedding of x. the cell only multiplies by word embeddings, and we can focus solely on those embeddings to understand the model. since the work of @xcite , vector embeddings have proven to be an extremely successful modelling tool. however, their structure is opaque. the only way of analysing their relations is through geometric distance metrics like cosine similarity. the unit vectors u and v are deemed similar if u, v is close to 1. here we work with orthogonal matrix embeddings, which exhibit much richer structure. we use mathematical analysis to get a better sense of this structure, and relate it to vector embeddings. composition of embeddings a decisive benefit of unitary (and orthogonal) matrix embeddings is that they form a group. we can obtain the inverse of a word embedding simply by transposing it: q(x) -1 = q(x) t . we can also compose two embeddings to obtain an embedding for the composition. thanks to the associativity of multiplication, we have using this notation, the final state of an urn is q(x 0 . . . x n -1 )s 0 . hence, the urn is compositional by design. 5 it is important to recognise that compositionality is strictly a consequence of the structure of a urn. it follows directly from the use of unitary matrix multiplication, through which the successive states in the rnn's processing sequence are computed, without activation functions, it is not necessary to demonstrate this result experimentally, since it is a formal consequence of the associativity of orthogonal matrix multiplication, as shown above. because urns do not incorporate additional nonlinear activation functions, a simple matrix is always sufficient to express any combination of word and phrasal embeddings. ## natural language agreement task it may seem that the extreme simplicity of the turn architecture renders it unsuitable for any non-trivial processing task. in fact, this is not at all the case. the training data is composed of 1.7 million sentences with a selected subject-verb pair, extracted from wikipedia. the vocabulary size is 50,000, and out-of-vocabulary tokens are replaced by their part-of-speech tag. training is performed for ten epochs, with a learning rate of 0.01, and a dropout rate of ρ = 0.05. we use 90% of the data for training and 10% for validation and testing. a development subset is not necessary since no effort was made to tune hyperparameters. our first experiment proved sufficient to illustrate our main claims. in any case, a turn has few hyperparameters to optimise. @xcite point out that solving the agreement task requires knowledge of hierarchical syntactic structure. that is, if an rnn captures the long-distance dependencies involved in agreement relations, it cannot rely solely on the linear sequence of nouns (in particular their number inflections) preceding the predicted verb in a sentence. in particular, the accuracy must be sustained as the number attractors increases. an attractor is defined as a noun occurring between the subject and the verb which additionally exhibits the wrong number feature required to control the verb. in the above example sentence, "cabinet" is an attractor. figure 2 shows the results for a 50-unit turn with 3-truncated embeddings for the agreement task, for up to 12 attractors. we see that the turn "solves" this task, with error rates well under one percent. crucially, there is no evidence of accuracy dropping as the number of attractors increases. even though the statistical uncertainty increases with the number of attractors, due to decreasing numbers of examples, the turn makes no mistakes for the higher number of attractor cases. ## dyck-language modelling task to evaluate the theoretical long-distance modelling capabilities of an rnn in a way that abstracts away from the noise in natural language, one can construct synthetic data. following bernardy (2018) we use a (generalised) dyck language. this language is composed solely of matching parenthesis pairs. so the strings "{([])}<>" and "{()[<>]}" are part of the language, while "[}" is not. this experiment is an idealised version of the agreement task, where opening parentheses correspond to subjects, and closing parentheses to verbs. an attractor is an opening parenthesis occurring between the pair, but of a different kind. matching of parentheses corresponds to agreement. because we use five distinct kinds of parentheses, the majority class baseline is at 20%. this makes it easier to evaluate the performance of a model on the matching task than for the third person agreement task, where the majority class baseline for the training corpus is above 70%. we complicate the matching task with an additional difficulty. we vary the nesting depth between training and test phases. the depth of the string is the maximum nesting level reached within it. for instance "[{}]" has depth 2, while "{([()]<>)}" has depth 4. in this task, we use strings with a length of exactly 20 characters. we train on 102,400 randomly generated strings, with maximum depth 3, and test it on 5120 random strings of maximum depth 10. training is performed with a learning rate of 0.01, and a dropout rate of ρ = 0.05, for 100 epochs. the training phase treats the urn as a generative language model, applying a cross-entropy loss function at each position in the string. at test time, we evaluate the model's ability to predict the right kind of closing parenthesis at each point (this is the equivalent of predicting the number of a verb). we ignore predictions regarding opening parentheses, because they are always acceptable for the language. by contrast, the urn models remain accurate as the number of attractors grows. perhaps surprisingly, the urn improves in relation to the number of attractors. we will solve this apparent puzzle below, through analysis of the embeddings. the explanation will hinge on the fact that truncating embeddings affects performance only when the number of attractors is low. comparing the arbitrary embeddings model with with full urn highlights the importance of limiting the network to orthogonal matrices. the performance of the full urn is better over the long term and in general, with a validation loss of 1.47213 compared to 1.52914 for the arbitrary case. this happens despite the fact that the orthogonal system 0.33 0.35 1.35 0.46 1.73 0.2 1.09 0.2 0.34 in sum, restricting to orthogonal matrices acts like a regularising constraint which offers a significant net benefit in generalisation and tracking power. ## conclusions and future work in conclusion, we have shown that the urn is a useful architecture for syntactic tasks, for which it can reach or surpass state-of-the art precision. we strongly suspect that it will also prove effective for nlp tasks requiring fine-grained semantic knowledge. unlike other dnns, a urn is transparent and mathematically grounded in straightforward operations of linear algebra. it is possible to trace and understand what is happening at each level of the network, and at each point in the sequence that makes up the processing flow of the network. additionally, urns learn unitary embeddings. these offer two important advantages. first, they have a rich internal structure from which we can analyse the learned model. second they handle compositionality without stipulated constraints, or additional mechanisms. therefore we can obtain unitary embeddings for any phrase or sentence. the refined distance, effect, and relatedness metrics that unitary embeddings facilitate, open up the possibility of more interesting procedures for identifying natural syntactic and semantic word classes. these can be textured and dynamic, rather than static. they can focus on specific dimensions of meaning and structure, and they can be driven by specific nlp tasks. if additional types of input data are encoded in a matrix, such as visual content, then these classes could also be grounded in extralinguistic contexts. in order to render urns efficient, it is necessary to reduce the number of parameters from which the matrix can be derived. we found that a simple k-truncation of underlying anti-symmetric matrices is a useful strategy to limit the size of word embeddings. it also makes the learned embeddings more accessible to formal analysis, because they can be decomposed as rotations along k planes. for the tasks that we considered, truncation does not seriously degrade the performance of the turn model. @xcite recently applied this strategy to another subset of tasks, suggesting general viability of this strategy. in preliminary work we have applied urns to the recognition of mildly context-sensitive languages containing cross serial dependencies of the sort found in swiss german and in dutch. the performance of the model is even more robust and stable than it is for the agreement tasks reported here. we will be extending this work to a variety of other linguistically and cognitively interesting nlp tasks. given the radical computational transparency of urn architecture, these models are natural candidates for comparison with human processing systems, both at the neurological level, and on more abstract psychological planes. identifying and measuring the content of their acquired knowledge for particular tasks can be done through direct observation of their processing patterns, and the application of straightforward distance metrics. in this respect they are of particular interest in the study of the cognitive foundations of linguistic learning and representation.