Should Semantic Vector Composition be Explicit? Can it be Linear? (2021)

Abstract: Vector representations have become a central element in semantic language modelling, leading to mathematical overlaps with many fields including quantum theory. Compositionality is a core goal for such representations: given representations for ‘wet’ and ‘fish’, how should the concept ‘wet fish’ be represented? This position paper surveys this question from two points of view. The first considers the question of whether an explicit mathematical representation can be successful using only tools from within linear algebra, or whether other mathematical tools are needed. The second considers whether semantic vector composition should be explicitly described mathematically, or whether it can be a model-internal side-effect of training a neural network. A third and newer question is whether a compositional model can be implemented on a quantum computer. Given the fundamentally linear nature of quantum mechanics, we propose that these questions are related, and that this survey may help to highlight candidate operations for future quantum implementation.

## introduction semantic composition has been noted and studied since ancient times, including questions on which parts of language should be considered atomic, how these are combined to make new meanings, and how explicitly the process of combination can be modelled. 1 as vectors have come to play a central role in semantic representation, these questions have nat- the word 'human' has meaning, but does not constitute a proposition, either positive or negative. it is only when other words are added that the whole will form an affirmation or denial. during the 20th century, logical semantics was also developed, based very much upon the discrete mathematical logic tradition of @xcite and @xcite rather than the continuous vector spaces that developed from the works of @xcite and @xcite . thus, by the beginning of this century, compositional semantics was developed mathematically, provided frameworks such as montague semantics for connecting the truth value of a sentence with its syntactic form, but provided little insight on how the atomic parts themselves should be represented. good examples in this tradition can be found in @xcite and @xcite . in summary, by the year 2000, there were distributional language models with vectors, symbolic models with composition, but little in the way of distributional vector models with composition. ## explicit composition in semantic vector models the most standard operations used for composition and comparison in vector model information retrieval systems have, for many decades, been the vector sum and cosine similarity (see @xcite , and for an introduction, @xcite ). cosine similarity is normally defined and calculated in terms of the natural scalar product induced by the coordinate system, i.e., while the scalar product is a linear operator because λa • µb = λµ(a • b), cosine similarity is deliberately designed so that cos(λa, µb) = cos(a, b), so that normalizing or otherwise reweighting vectors does not affect their similarity, which depends only on the angle between them. more sophisticated vector composition in ai was introduced with cognitive models and connectionism. the work of @xcite has already been mentioned, and the holographic reduced representations of @xcite is another widely-cited influence (discussed again below as part of vector symbolic architectures). while smolensky's work is often considered to be ai rather than nlp, the application to language was a key consideration: any connectionist model of natural language processing must cope with the questions of how linguistic structures are represented in connectionist models. @xcite 2) the use of more varied mathematical operators to model natural language operations with vectors accelerated considerably during the first decade of this century. in information retrieval, van @xcite explored conditional implication and @xcite developed the use of orthogonal projection for negation in vector models. motivated partly by formal similarities with quantum theory, @xcite proposed modelling a sentence w 1 , . . . , w n with a tensor product w 1 ⊗. . .⊗w n in the fock space ∞ @xmath0. the authors noted that comparing the spaces v ⊗ k and v ⊗ j when @xmath1, and of course the prospect of summing to @xmath2. by the middle of the decade, @xcite and @xcite proposed and experimented with the use of tensor products for semantic composition, and the parallelogram rule for relation extraction. such methods were used to obtain strong empirical results for (intransitive) verb-noun composition by @xcite and for adjective-noun composition by @xcite . one culmination of this line of research is the survey by @xcite , who also addressed the problem of comparing tensors v ⊗ k and v ⊗ j when @xmath3. for example, if (as in baroni & zamparelli 2010)), nouns are represented by vectors and adjectives are represented by matrices, then the space of matrices is isomorphic to v ⊗ v which is not naturally comparable to v , and the authors note @xcite , §3.4): as a result, rome and roman, italy and italian cannot be declared similar, which is counter-intuitive. even more counterintuitively, roman used as an adjective would not be comparable to roman used as a noun. we think that the best way to solve such apparent paradoxes is to look, on a case-by-case basis, at the linguistic structures involved, and to exploit them to develop specific solutions. another approach is to use a full syntactic parse of a sentence to construct vectors in a sentence space s from nouns and verbs as constituents in their respective spaces. this features prominently in the model of @xcite , which has become affectionately known as discocat, from 'distributional compositional categorical'. the mathematics is at the same time sophisticated but intuitive: its formal structure relies on pregroup grammars and morphisms between compact closed categories, and intuitively, the information from semantic word vectors flows through a network of tensor products that parallels the syntactic bindings and produces a single vector in the s space. various papers have demonstrated empirical successes for the discocat and related models. @xcite were among the first, showing comparable and sometimes improved results with those of @xcite . by 2014, several tensor composition operations were compared by @xcite showed that word, phrase, and sentence entailment can be modelled using vectors and density matrices. (the use of density matrices to model probability distributions for entailment was pioneered partly by @xcite and will be discussed further in section 4.) further mathematical tools used in discocat research include copying a vector @xmath4, and uncopying which takes the diagonal elements of a matrix representing a tensor in v ⊗ v and uses these as the coordinates of a vector. with these additional operators, the tensor algebra becomes more explicitly a frobenius algebra. 3 these are used in discocat models by @xcite to represent relative and then possessive pronoun attachments (for example, representing the affect of the phrase "that chased the mouse" as part of the phrase "the cat that chased the mouse"). the method involves detailed tracking of syntactic types and their bindings, and certainly follows the suggestion from @xcite to look at linguistic structures on a case-by-case basis. there are practical concerns with tensor product formalisms. the lack of any isomorphism between v ⊗ k and v ⊗ j when @xmath5, along with the difficulty this poses for comparing elements of each for similarity. also, there is an obvious computational scaling problem: if v has dimension n, then v ⊗ k has dimension n k , which leads to exponential memory consumption with classical memory registers. taking the example of relative pronouns in the discocat models of @xcite these are represented as rank-4 tensors in spaces such as n ⊗ s ⊗ n ⊗ n and variants thereof, and if the basic noun space n and sentence space s have dimension 300 (a relatively standard number used e.g., by fasttext vectors) then the relative pronouns would have dimension 8.1 billion. if this was represented densely and the coordinates are 4byte floating point numbers, then just representing one pronoun would require over 30gb of memory, which is intractable even by today's cloud computing standards. the development of vector symbolic architectures (vsas) @xcite ) was partly motivated by these concerns. vsas grew from the holographic reduced representations of @xcite : no-table works in this intersection of cognitive science and artificial intelligence include those of @xcite and @xcite . at its core, a vsa is a vector space with an addition operator and a scalar product for computing similarity, along with a multiplication or binding operator (sometimes written as * , or ⊗ like the tensor product) which takes a product of two vectors and returns a new vector that it typically not similar to either of its inputs, so that (a * b) • a is small, but which is 'approximately reversible' -so there is an approximate inverse operator where (a * b) b is close to a. 4 the term 'binding' was used partly for continuity with the role-filler binding of @xcite . 5 the vsa community has tended to avoid the full tensor product, for the reasons given above. in order to be directly comparable, it is desirable that a * b should be a vector in the space v . @xcite thoroughly explored the use of circular correlation and circular convolution for these operations, which involves summing the elements of the outer product matrix along diagonals. this works as a method to map v ⊗ v back to v , though the mapping is of course basis dependent. partly to optimize the binding operation to o(n) time, plate (2003, ch 5) introduces circular vectors, whose coordinates are unit complex numbers. there is some stretching of terminology here, because the circle group u (1) of unit complex numbers is not, strictly speaking, a vector space. circular vectors are added by adding their rectangular coordinates in a linear fashion, and then normalizing back to the unit circle by discarding the magnitude, which plate notes is not an associative operation. @xcite departs perhaps even further from the vector space mainstream, using binary-valued vectors throughout, with binding implemented as pairwise exclusive or (xor). vsa binding operations have been used for composition of semantic vector representations, both during the training process to generate composite vector representations of term or character n-grams, or semantic units such as predicate-argument pairs or syntactic dependencies, that are then further assembled to construct representations of larger units @xcite @xcite ); and to compose larger units from pretrained semantic vectors for downstream machine learning tasks @xcite . however, a concern with several of the standard vsa binding operators for the representation of sequences in particular is that they are commutative in nature: x * @xmath6. to address this concern, permutations of vector coordinates have been applied across a range of vsa implementations to break the commutative property of the binding operator, for example by permuting the second vector in sequence such that --→ wet * ( --→ f ish) and --→ f ish * ( --→ wet) result in different vectors @xcite . thanks to their general nature and computational simplicity, permutations have been used for several other encoding and composition experiments. the use of permutations to encode positional information into word vector representations was introduced by @xcite . in this work a permutation (coordinate shuffling) operator was used to rearrange vector components during the course of training, with a different random permutation assigned to each sliding window position such that a context vector would be encoded differently depending upon its position relative to a focus term of interest. a subsequent evaluation of this method showed advantages in performance over the beagle model @xcite , which uses circular convolutions to compose representations of word n-grams, on a range of intrinsic evaluation tasks -however these advantages were primarily attributable to the permutation-based approach's ability to scale to a larger training corpus @xcite . random permutations have also been used to encode semantic relations @xcite ) and syntactic dependencies @xcite ) into distributional models. in high-dimensional space, the application of two different random permutations to the same vector has a high probability of producing vectors that are close-to-orthogonal to one another @xcite . a more recent development has involved deliberately constructing 'graded' permutations by randomly permuting part of a parent permutation @xcite . when this process is repeated iteratively, it results in a set of permutations that when applied to the same vector will produce a result with similarity to the parent vector that decreases in an ordinal fashion. this permits the encoding of proximity rather than position, in such a way that words in proximal positions within a sliding window will be similarly but not identically encoded. the resulting proximity-based encodings have shown advantages over comparable encodings that are based on absolute position (at word and sentence level) or are position-agnostic (at word and character level) across a range of evaluations @xcite @xcite . note that coordinate permutations are all euclidean transformations: odd permutations are reflections, and even permutations are rotations. thus all permutation operations are also linear. this survey of explicit composition in semantic vector models is not exhaustive, but gives some idea of the range of linear and nonlinear operations. ## compositional semantics in neural networks during the past decade, many of the most successful and well-known advances in semantic vector representations have been developed using neural networks. 6 in general, such networks are trained with some objective function designed to maximize the probability of predicting a given word, sentence, or group of characters in a given context. various related results such as those of @xcite are known to demonstrate that, given enough computational resources and training data, neural networks can be used to approximate any example from large classes of functions. if these target functions are nonlinear, this cannot be done with a network of entirely linear operations, because the composition of two linear maps is another linear map -"the hidden units should be nonlinear because multiple layers of linear units can only produce linear functions." (wichert 2020, §13.5). thus, part of the appeal of neural networks is that they are not bound by linearity: though often at considerable computational cost. the skip gram with negative sampling method was introduced by @xcite , imple-mentations including the word2vec 7 package from google and the fasttext package from facebook. 8 the objective function is analyzed more thoroughly by @xcite , and takes the form: here w is a word, c is a context feature (such as a nearby word), d represents observed term/context pairs in the document collection, d represents randomly drawn counterexamples, and -→ w and -→ c are word and context vectors (input and output weights of the network, respectively). σ is the sigmoid function, 1 1+e -x . the mathematical structure here is in the family of logistic and softmax functions -the interaction between the word and context vectors involves exponential / logarithmic concepts, not just linear operations. there have been efforts to incorporate syntactic information explicitly in the training process of neural network models. in the specific case of adjectives, @xcite use the skip gram technique to create matrices for adjectives following the pattern of @xcite discussed in section 2. the most recent culmination of this work is its adaptation to cover a much more comprehensive collection of categorial types by @xcite . another early example comes from @xcite , who train a recursive neural network where each node in a syntactic parse tree becomes represented by a matrix that operates on a pair of inputs. research on tree-structured lstms (see inter alia @xcite ) leverages syntactic parse trees in the input and composes its hidden state using an arbitrary number of child nodes, as represented in the syntax tree. syntax-bert @xcite uses syntactic parses to generate masks that reflect different aspects of tree structure (parent, child, sibling). kermit @xcite ) uses compositional structure explicitly by embedding syntactic subtrees in the representation space. in both cases, the use of explicit compositional syntactic structure leads to a boost in performance on various semantic tasks. in kermit, the embedding of trees and (recursively) their subtrees follows a well-developed line of research on representing discrete structures 7 https://pypi.org/project/word2vec/ 8 https://fasttext.cc/ as vectors, in particular combining circular convolution and permutations to introduce shuffled circular convolution @xcite . even when combined in a recursive sum over constituents called a distributed tree kernel operation, this is still a sum of linear inputs, so this form of composition is still linear throughout. in such methods, the result may be a collection of related linear operators representing explicit syntactic bindings, but the training method is typically not linear due to the activation functions. what these neural net methods and the models described in the previous section have in common is that they encode some explicit compositional structure: a weighted sum of word or character n-grams, a role / value binding, or a relationship in a grammatical parse tree. this raises the question: can neural language models go beyond the bag-of-words drawbacks and encode more orderdependent language structures without using traditional logical compositional machinery? a recent and comprehensive survey of this topic is provided by @xcite . this work provides a valuable survey of the field to date, and conducts experiments with compositional behavior on artificial datasets designed to demonstrate various aspects of compositionality, such as productivity (can larger unseen sequences be produced?) and substitutivity (are outputs the same when synonymous tokens are switched?). this systematic approach to breaking compositionality into many tasks is a useful guide in itself. since then, attention-based networks were developed and have come to the forefront of the field @xcite . the attention mechanism is designed to learn when pairs of inputs depend crucially on one another, a capability that has demonstrably improved machine translation by making sure that the translated output represents all of the given input even when their word-orders do not correspond exactly. the 'scaled dot-product attention' used by @xcite for computing the attention between a pair of constituents uses softmax normalization, another nonlinear operation. the use of attention mechanisms has led to rapid advances in the field, including the contextualized bert @xcite and elmo @xcite ) models. for example, the elmo model reports good results on traditional nlp tasks including question answering, coreference resolution, semantic role labelling, and part-of-speech tagging, and the authors speculate that this success is due to the model's different neural-network layers implicitly representing several different kinds of linguistic structure. this idea is further investigated by @xcite and @xcite , who probe bert and elmo models to find evidence that syntactic structure is implicitly encoded in their vector representations. the survey and experiments of @xcite evaluate three such neural networks on a range of tasks related to composition, concluding that each network has strengths and weaknesses, that the results are a stepping stone rather than an endpoint, and that developing consensus around how such tasks should be designed, tested and shared is a crucial task in itself. at the time of writing, such systems are contributors to answering a very open research question: do neural networks need extra linguistic information in their input to properly work with language, or can they actually recover such information as a byproduct of training on raw text input? for example, a discocat model requires parsed sentences as input -so if another system performed as well without requiring grammatical sentences as input and the support of a distinct parsing component in the implementation pipeline, that would be preferable in most production applications. (running a parser is a requirement than today can often be satisfied, albeit with an implementational and computational cost. requiring users to type only grammatical input is a requirement that cannot typically be met at all.) at the same time, does performance on the current nlp tasks used for evaluation directly indicate semantic composition at play? if the performance of a model without linguistic information in the input is up to par, would the internal operations of such an implicit model be largely inscrutable, or can we describe the way meaningful units are composed into larger meaningful structures explicitly? tensor networks are one of the possible mathematical answers to this question, and continue to build upon smolensky's introduction of tensors to ai. for example @xcite present evidence that the sequence-composition effects of recurrent neural networks (rnns) can be approximated by tensor product decomposition networks, at least in cases where using this structure provides measurable benefits over bag-of-words models. it has also been shown that tensor product networks can be used to construct an attention mechanism from which grammatical structure can be recovered by unbinding role-filler tensor compositions @xcite . while there are many more networks that could be examined in a survey like this, those described in this section illustrate that neural networks have been used to improve results with many nlp tasks, and the training of such networks often crucially depends on nonlinear operations on vectors. furthermore, while tensor networks have been developed as a proposed family of techniques for understanding and exploiting compositional structures more explicitly, in some of the most state-of-the-art models, relationships between such operations to more traditional semantic composition are often absent or at least not well-understood. ## operators from quantum models mathematical correspondences between vector models for semantics and quantum theory have been recognized for some years @xcite , and are surveyed by @xcite . the advent of practical quantum computing makes these correspondences especially interesting, and constructs from quantum theory have been used increasingly deliberately in nlp. in quantum computing, tensor products no longer incur quadratic costs: instead, the tensor product a ⊗ b is the natural mathematical representation of the physical state that arises when systems in states a and b are allowed to interact. heightened interest in quantum computing and quantum structures in general has led to specific semantic contributions already. mathematically, there is a historic relationship between linearity and quantum mechanics: the principle of superposition guarantees that for any state a, the vector ca corresponds to the same physical state for any complex number c (dirac 1930, §5). 9 hence the question of whether a compositional operator is linear or not is particularly relevant when we consider the practicality of implementation on a quantum computer. 10 many developments have followed from the dis-cocat framework, whose mathematical structure is closely related to quantum mechanics through category theory @xcite . as of 2021, the tensor network components of two discocat models have even been implemented successfully on a quantum computer @xcite , and there are proposals for how to implement the syntactic parse on quantum hardware as well @xcite . of particular semantic and mathematical interest, topics such as hyponymy @xcite and negation (lewis 2020) have been investigated, using density matrices and positive operator-valued measures, which are mathematical generalizations of state vectors and projection operators that enable the theory to describe systems that are not in 'pure' states. density matrices have also been used to model sentence entailment @xcite and recently lexical ambiguity @xcite . a comprehensive presentation of the use of density matrices to model joint probability distributions is given by @xcite . this work deliberately takes a quantum probability framework and applies it to language modelling, by way of the lattice structures of formal concept analysis @xcite . this work uses the partial trace of density operators (which are tensors in v ⊗ v ) to project tensors in v ⊗ v to vectors in v . this is analogous to summing the rows or columns of a two-variable joint distribution to get a single-variable marginal distribution. this captures interference and overlap between the initial concepts, and in a framework such as discocat, this might be used to model transitive verb-noun composition (as in @xcite @xcite . another mathematical development is the quantum procrustes alignment method of @xcite , where procrustes alignment refers to the challenge of mapping one vector space into another preserving relationships as closely as possible. procrustes techniques have been used to align multilingual fasttext word vectors @xcite , and it is possible that one day these methods may be combined to give faster and more noise-tolerant multilingual concept alignment. this again is not a complete survey, but we hope it demonstrates that the interplay between quantum theory, semantic vector composition, and practical implementation has much to offer, and that work in this area is accelerating. ## summary, conclusion, and future work this paper has surveyed vector composition techniques used for aspects of semantic composition in explicit linguistic models, neural networks, and quantum models, while acknowledging that these areas overlap. the operations considered are gathered and summarized in in addition, there is emerging evidence that such models can be augmented by approaches that draw on structured semantic knowledge @xcite , suggesting the combination of implicit and explicit approaches to semantic composition as a fruitful area for future methodological research. we hope that this approach of surveying and comparing the semantic, mathematical and computational elements of various vector operations will serve as a guide to territory yet to be explored at the intersection of compositional operators and vector representations of language.