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
- 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)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/2020.coling-main.328.pdf