Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme (2020)

Abstract: We present a novel method for embedding trees in a vector space based on Tensor-Product Representations (TPRs) which allows for inversion: the retrieval of the original tree structure and nodes from the vectorial embedding. Unlike previous attempts, this does not come at the cost of intractable representation size; we utilize a method for non-exact inversion, showing that it works well when there is sufficient randomness in the representation scheme for simple data and providing an upper bound on its error. To handle the huge number of possible tree positions without memoizing position representation vectors, we present a method (Cryptographic Role Embedding) using cryptographic hashing algorithms that allows for the representation of unboundedly many positions. Through experiments on parse tree data, we show a 30,000-dimensional Cryptographic Role Embedding of trees can provide invertibility with error < 1% that previous methods would require 8.6 × 1057 dimensions to represent.

## introduction: compositional structure in neural representations one thing that critics and advocates of deep learning (dl) agree on is that dl models would benefit greatly from stronger compositional generalization: the ability to freely generalize, on relatively scant training data, to novel combinations of familiar constituents (lake and @xcite @xcite . symbolic systems achieve strong compositional generalization -especially in language -by leveraging compositional structure within the model's internal representations themselves @xcite . while it is conceivable that dl models in nlp will achieve strong compositional generalization without compositional representations @xcite , we believe it is important to investigate neural instantiations of the one method known to underlie such generalization: structured representations. but how can compositional structure be encoded without sacrificing the hallmarks -and sources of power -of neural computation: distributed representation (as opposed to physically separate encodings of constituents) and fully parallel processing (as opposed to operating sequentially on separate constituents)? the question of distributed neural representations with compositional structure has been debated for decades. that such representations are even possible, claims to the contrary notwithstanding @xcite , was established early on, by several techniques @xcite @xcite . it turns out that all these techniques are, up to elementwise nonlinear squashing, special cases of a general technique: tensor product representations (tprs) @xcite . this suggests that tprs may be a universal form of compositional distributed representation, raising the question of whether standard dl models learn them spontaneously. this has recently shown to be true, up to an affine transformation, for simple, highly compositional functions and extensive training data @xcite . alongside this provocative suggestion that tprs may be necessary for compositional encoding in neural nets, there are formal demonstrations of the sufficiency of tprs to enable nns to compute recursive symbolic functionsstrongly compositional behavior @xcite . these representations are typically fully distributed (each neuron contributes to the encoding of each constituent) and the function computation is fully parallel (for many complex functions, a single step). tprs introduce bona fide structure to neural representations via the neural embedding of roles that define a particular type of compositional structure. for binary trees, one such role could be left-child-of-rightchild-of-root. the fillers of these roles, whether they are atomic or structures themselves, are bound to their respective roles by taking the tensor product of the neural embedding of each filler and the embedding of its structural role. the sum of these tensor-product filler-role bindings is the tpr for the whole structure. when the embeddings of the roles are orthonormal vectors, the filler of any given role r with embedding r can be exactly recovered from the embedding s of the structure as a whole simply by taking the inner product: s • r (see sec. 2.2, which also shows that the same invertibility property holds if the role embeddings are merely linearly independent.) this unbinding process can lead to an error if another role has an embedding r that is not orthogonal to r: unbinding r will induce an intrusion of the filler of r with a magnitude proportional to the inner product r • r. orthogonality of the role embeddings is of course possible only if their dimension is at least as large as the number of possible roles. thus for a k-branching tree of depth δ, the size of the tpr is proportional to k δ . this contrasts with the size of a corresponding symbolic representation, which is proportional to the occupancy of the tree: the number of roles with non-null fillers. in nlp, where parse trees are often relatively sparse, this can be a large difference. the source of this disparity is that, unlike symbolic representations, distributed neural representations must pre-allocate space for all possible items that may need to be encoded: here, a dimension of the tpr for each possible atomic-filler/role pair, which is required for exact invertibility. however, we know that, in high-dimensional vector spaces, randomly chosen vectors are most likely to be approximately orthogonal (see sec. 2.3). the work presented here investigates the occupancy-scaling hypothesis: in high-dimensional embedding spaces, tprs for trees can be invertible to a good approximation provided the occupancy k of the tree is smaller than γ times the role-embedding dimension n, @xmath0, where γ = o(1). the hypothesis will hold if, under such conditions, role vectors can be assigned so that, with sufficiently high probability, pairs of occupied roles have embedding vectors that are sufficiently close to orthogonal: then intrusion will not lead to unbinding errors. if true, this means that tprs scale like their symbolic counterparts: the number of possible roles is irrelevant; only the number of occupied roles matters. the contributions of the paper consist in a sequence of tests of the occupancy-scaling hypothesis in settings of varying difficulty. in sec. 3, we first investigate the hypothesis in the case of random symbol strings, with random embeddings both of the roles and of the symbols that fill them. we next examine the case of natural-language sentences, considered as strings of word tokens: now the fillers are not random, although the filled roles are still predictable (positions 1 through @xmath1. we then present experimental verification of a new theoretical worst-case bound on unbinding error (appendix b). the main contributions of the paper lie in sec. 4, where we consider encodings of constituency-parsed sentences in which the roles filled in the parse tree are variable across sentences and the number of possible roles (tree positions) is essentially infinite. the primary innovation of the paper, the cryptographic role embedding technique, is shown to effectively encode a huge number of role vectors in a fixed embedding dimension. our results show that, even when embeddings of symbols are highly compressed and an unbounded set of structural positions are embedded in a modest-sized space, the occupancy-scaling hypothesis holds with a scaling coefficient particular to the type of data being represented. for example, in sec. 4.3 we show that where exact invertibility would require an embedding dimension of 8.6 × 10 57 , a 30,000-dimensional cryptographic role embedding of trees can provide invertibility with @xmath2. ## lower and upper bounds on unbinding error first, we consider a lower bound on error: fully random tprs. in this case, both filler vectors and role vectors are drawn uniformly from the unit sphere, and filler-role bindings are selected from the uniform distribution. this eliminates some potential contributions to error: there is no special relation between the representations of filler vectors, and no special co-occurence properties of roles or fillers. in this case, the intrusions of other fillers on the unbinding will typically be destructive, and the expected value of the intrusion term will be 0. nevertheless, as the number of bound roles becomes large compared to the role dimension, the variance of the intrusion term becomes larger, resulting in errors. in each simulation run, the size n of the set of possible fillers and the filler embedding dimension d were fixed. we perform a number of samples for each simulation, each time drawing a new set of n-dimensional role vectors {r i } k @xmath3. dings k is fixed and the dimension of the role vectors n is varied, while in others n is fixed and k is varied. the former simulations can be thought of as answering the question "how large of role vectors do i need if my symbolic structures are no larger than k?", while the latter answer "how much information can be packed into tprs using roles of size n?" the filler embedding that will be bound to each ri is drawn iid from a uniform distribution over the set of n possible fillers. for each fixed set of parameters, we select the filler-role bindings and create the tpr according to equation (1). we then unbind all the roles using the self-addressing unbinding procedure, compute the similarities between the result of the unbinding f and each of the filler vectors fj , recording whether an error was made. we divide the number of errors made by the total number of bindings to obtain a simple maximum likelihood estimate of the error probability for any one combination of n , d, n, and k. simulations were computed in batches using pytorch @xcite . this experiment was conducted with both the role dimension n fixed and the number of bindings k varied and vice-versa, for fixed n, @xmath4, 100, 200, with @xmath5, @xmath6, 10000, 50000. results for fixed n and varied k and fixed k and varied n showed analogous patterns of error, suggesting that the ratio of n/k is the relevant factor for error, rather than their independent values. the number of possible fillers n did not seem to substantially effect the error rate. overall, across all combinations of n and k, the error for k/@xmath7. this constitutes a confirmation of the occupancy-scaling hypothesis, with scaling coefficient γ = 2: unbinding error @xmath8. representative results are shown in fig. 2 . another relatively simple but more challenging setting is given by embedding english sentences. we use the reuters corpus from the nltk python package @xcite , taking only the sentences of @xmath9, yielding 49442 sentences. here we construct at tpr as follows: if w i is the ith word in a sentence from the corpus, the filler vector fi is the embedding of w i in some vector space; this is bound to an embedding r i of the role denoting the ith linear position in the sentence. as before, the role vectors are randomly chosen from the uniform distribution on the unit sphere s n-1 ⊂ r n . for the word embeddings, we use 300-dimensional word2vec vectors taken from the google news vectors @xcite . there are a number of potential issues here: the fillers cannot be modeled as being drawn from a uniform distribution; since the fillers are words, common words will appear in tprs more often, being drawn from a distribution which is approximately zipfian @xcite . if a word appears more than once in a sentence (and thus tpr), that increases the chance of constructive interference in the direction of that word. another challenge is the non-uniformity of word2vec vectors: since word2vec creates vectors on the basis that words that occur near each other (e.g. in the same sentence) should have more similar vectorial embeddings. this means the embeddings of the intruding vectors will be closer to the true filler than a random vector would be expected to be, leading to a potential for errors. finally, the density of the filler space in this experiment is much greater than in the previous experiments, as there are approximately 3,000,000 googlenews vectors, with a dimension of 300 (n/@xmath10, increasing the change of a random error. due to this large filler dimension, we also consider a top-5 setting, which reduces errors. despite these potential issues, using role dimension @xmath11, the number of words in the sentence) vary, we again find γ ≈ 2 with a tolerance of 1% error, as shown in fig. 3 . finally, we present a worst-case scenario. consider a tpr where role vectors are uniformly drawn from the unit sphere s n-1 and where each role is bound to one of only two fillers â or b. specifically, r0 is bound to â, and for all @xmath12, ri is bound to b. when unbinding a role from a tpr where the fillers are widely scattered, there will be destructive interference causing cancellation between the intrusions of the fillers of other roles; in this case, however, when unbinding r0 there will be no such destructive interference, but instead constructive interference in the direction of b. thus, we call this scenario maximal intrusion. the in fig. 4 , we can see that this bound is not tight, with the observed error being substantially lower. still, the bound has the property of being exponentially decreasing in n-that is, for a fixed number of bindings k, the error drops off at a rate proportional to 1 e n , so even in this worst-case scenario it is possible to unbind with a low error rate with a number of roles favorably proportional to the number of bindings, provided k is not than the desired n. ## invertible tree representations the tpr embedding of trees is guaranteed to be perfectly invertible if the role embeddings are linearly independent. the roles here are the possible positions in a k-ary tree, so the number of tree roles grows exponentially with the depth of the tree; as such, maintaining the linear independence of all role vectors that is required for exact unbinding would require extremely large role vectors. however, the experiments presented in section 3 suggest that sufficiently-high-dimensional random role vectors may be close enough to orthogonal that trees can be represented with relatively small role vectors while introducing only a small amount of error in inverting the embedding (i.e., only a small probability of unbinding errors). however, purely random roles are not feasible in the tree context, as the number of roles is potentially infinite and grows exponentially in the depth. in this section, we present a scalable role scheme for the representation of tree tprs, and demonstrate its efficiency in representing syntax trees with minimal information loss (as demonstrated by reconstruction). ## summary and conclusion can trees of potentially large depth be encoded as distributed representations in such a way as to enable fully parallel processing and high-accuracy decoding without requiring representations with a dimensionality that grows rapidly with the maximum possible depth? general hand-designed methods for neural encoding of compositional structure, and learned internal neural representations for strongly compositional tasks, have been shown to be cases of tensor product representations (tprs), which provide distributed representations that enable parallel processing and accurate decoding -if the dimension of the representation is very large, growing exponentially with tree depth. a method is presented here for designing distributed tree embeddings (tprs) that, by contrast, have the same scaling properties as symbolic tree representations: they grow with the number of labelled tree nodes, independently of tree depth. this technique uses cryptographic role embeddings to encode tree positions. this is essentially a means of hashing tree positions onto a high-dimensional unit sphere such that nearby tree positions are not mapped to nearby unit vectors, minimizing interference between decoding symbols that are close together in the tree. the use of a cryptographic hash means there are no burdensome requirements of memoization, allowing the flexible handling of extremely large or unbounded role schemes for complex compositional structures. experiments show that trees that would require tprs of size 8.6 × 10 57 to enable exact represent r vectors in an orthonormal basis in which @xmath13. then letting the hyper-surface area of the radius-r sphere s n-1 (r) ⊂ r n be a n-1 (r) = c n-1 r n-1 , we have assume henceforth that n is even: then we can use, for @xmath14: then, from ( 11 ), ( 15 ), ( 19 ) and ( 20 ) we get