Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme

Proceedings of the 28th International Conference on Computational Linguistics, pages 3671–3683 Barcelona, Spain (Online), December 8-13, 2020 3671 Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme Coleman Haley1 and Paul Smolensky1, 2 1Department of Cognitive Science, Johns Hopkins University, Baltimore, MD 2Microsoft Research AI, Redmond, WA {chaley7, smolensky}@jhu.edu 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. 1 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 Baroni, 2017; Marcus, 2020; Russin et al., 2020). Symbolic systems achieve strong compositional generalization — especially in language — by leveraging compositional structure within the model’s internal representations themselves (Frege and Beaney, 1997). While it is conceivable that DL models in NLP will achieve strong compositional generalization without compositional representations (Baroni, 2020), 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 (Fodor and Pylyshyn, 1988), was established early on, by several techniques (Pollack, 1989; Smolensky, 1990; Shastri and Ajjanagadde, 1993; Plate, 1995, a.o.). It turns out that all these techniques are, up to elementwise nonlinear squashing, special cases of a general technique: tensor product representations (TPRs) (Smolensky and Tesar, 2006). 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 (McCoy et al., 2019; Soulos et al., 2019). Alongside this provocative suggestion that TPRs may be necessary for compositional encoding in neural …

Content truncated to 500 words