Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme

Coleman Haley, Paul Smolensky


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.
Anthology ID:
2020.coling-main.328
Volume:
Proceedings of the 28th International Conference on Computational Linguistics
Month:
December
Year:
2020
Address:
Barcelona, Spain (Online)
Editors:
Donia Scott, Nuria Bel, Chengqing Zong
Venue:
COLING
SIG:
Publisher:
International Committee on Computational Linguistics
Note:
Pages:
3671–3683
Language:
URL:
https://aclanthology.org/2020.coling-main.328
DOI:
10.18653/v1/2020.coling-main.328
Bibkey:
Cite (ACL):
Coleman Haley and Paul Smolensky. 2020. Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme. In Proceedings of the 28th International Conference on Computational Linguistics, pages 3671–3683, Barcelona, Spain (Online). International Committee on Computational Linguistics.
Cite (Informal):
Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme (Haley & Smolensky, COLING 2020)
Copy Citation:
PDF:
https://aclanthology.org/2020.coling-main.328.pdf