@inproceedings{haley-smolensky-2020-invertible,
    title = "Invertible Tree Embeddings using a Cryptographic Role Embedding Scheme",
    author = "Haley, Coleman  and
      Smolensky, Paul",
    editor = "Scott, Donia  and
      Bel, Nuria  and
      Zong, Chengqing",
    booktitle = "Proceedings of the 28th International Conference on Computational Linguistics",
    month = dec,
    year = "2020",
    address = "Barcelona, Spain (Online)",
    publisher = "International Committee on Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-emnlp/2020.coling-main.328/",
    doi = "10.18653/v1/2020.coling-main.328",
    pages = "3671--3683",
    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 {\ensuremath{<}} 1{\%} that previous methods would require 8.6 {\texttimes} 1057 dimensions to represent."
}