Elamur Research⌕
☰
home / papers / 2016 / Learning Continuous Semantic Representations of Symbolic Expressions

Learning Continuous Semantic Representations of Symbolic Expressions

Paper · 2016 · Miltiadis Allamanis, Pankajan Chanthirasegaran, Pushmeet Kohli et al.

Summary

The authors set out to learn how to map algebraic and logical expressions to continuous vectors so that semantically equivalent formulas receive identical or very close representations, even when they are written very differently. They call these vectors SemVec. The main difficulty is that the representation is built from the syntax tree, while a small change in notation, such as an added negation, can completely change the meaning. Ordinary TreeNNs cannot handle this: they group expressions by similarity of notation rather than by meaning. The authors propose the EqNet architecture. It has a separate two-layer MLP with a residual connection for each node type, normalizes the vectors, and is trained on equivalence classes rather than on individual pairs. EqNet also uses subexpression autoencoding, which pulls the representations of a single class into tight clusters. For evaluation, the authors assembled datasets of Boolean and polynomial expressions. On these, EqNet substantially outperforms TreeNNs and RNNs. This is a step toward combining symbolic and neural reasoning, in particular toward heuristics for symbolic solvers.

Key points

  • The paper appeared at ICML 2017 (PMLR 70). The authors are from Microsoft Research, the University of Edinburgh, DeepMind and the Alan Turing Institute.
  • Two classes of tasks were created for evaluation: BOOL (Boolean expressions) and POLY (polynomials). The code and data are available at groups.inf.ed.ac.uk/cup/semvec.
  • The key components of EqNet are COMBINE (a two-layer MLP with a residual connection and L2 normalization) and SubexpAe (an autoencoder that reconstructs a node's children from the parent node and vice versa). Deeper networks did not improve the results.
  • Compared with the work of Zaremba et al. (2014), which covered only homogeneous polynomials in a single variable, EqNet handles a broader class of expressions and does not require search.
  • Limitations in the authors' words: fixed-size vectors have limited capacity because the space of values grows exponentially. More complex procedures will likely require variable-size representations.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of EdinburghEdinburgh · United Kingdom396 works · 82,279 citations🏢Google DeepMindLondon · United Kingdom82 works · 84,829 citations🔬The Alan Turing InstituteLondon · United Kingdom35 works · 5,111 citations🏢Microsoft Research (United Kingdom)Cambridge · United Kingdom15 works · 3,537 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputational Theory and Mathematics · 496 works

Cite

Cite as Miltiadis Allamanis, Pankajan Chanthirasegaran, Pushmeet Kohli and Charles Sutton. 2016. Learning Continuous Semantic Representations of Symbolic Expressions. arXiv:1611.01423.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1611.01423 · arXiv 1611.01423

@misc{allamanis2016learning,
  title = {{Learning Continuous Semantic Representations of Symbolic Expressions}},
  author = {Miltiadis Allamanis, Pankajan Chanthirasegaran, Pushmeet Kohli and Charles Sutton},
  year = {2016},
  doi = {10.48550/arxiv.1611.01423},
  eprint = {1611.01423},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1611.01423}
}

References

24 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alemi, Alex A, Chollet, Francois, Irving, Geoffrey, Szegedy, Christian, and Urban, Josef. DeepMath – Deep sequence models for premise selection. arXiv preprint arXiv:1606.04442, 2016.
  2. Allamanis, Miltiadis, Peng, Hao, and Sutton, Charles. A convolutional attention network for extreme summarization of source code. In ICML, 2016.
  3. Ba, Jimmy Lei, Kiros, Jamie Ryan, and Hinton, Geoffrey E. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
  4. Bahdanau, Dzmitry, Cho, Kyunghyun, and Bengio, Yoshua. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
  5. Chopra, Sumit, Hadsell, Raia, and LeCun, Yann. Learning a similarity metric discriminatively, with application to face verification. In CVPR, 2005. find
  6. Dyer, Chris, Ballesteros, Miguel, Ling, Wang, Matthews, Austin, and Smith, Noah A. Transition-based dependency parsing with stack long short-term memory. In ACL, 2015.
  7. Graves, Alex, Wayne, Greg, and Danihelka, Ivo. Neural Turing machines. arXiv preprint arXiv:1410.5401, 2014. find
  8. Grefenstette, Edward, Hermann, Karl Moritz, Suleyman, Mustafa, and Blunsom, Phil. Learning to transduce with unbounded memory. In NIPS, 2015. find
  9. Gruau, Frédéric, Ratajszczak, Jean-Yves, and Wiber, Gilles. A neural compiler. Theoretical Computer Science, 1995. find
  10. Joulin, Armand and Mikolov, Tomas. Inferring algorithmic patterns with stack-augmented recurrent nets. In NIPS, 2015. find
  11. Kaiser, Łukasz and Sutskever, Ilya. Neural GPUs learn algorithms. In ICLR, 2016. find
  12. Loos, Sarah, Irving, Geoffrey, Szegedy, Christian, and Kaliszyk, Cezary. Deep network guided proof search. arXiv preprint arXiv:1701.06972, 2017.
  13. Mou, Lili, Li, Ge, Zhang, Lu, Wang, Tao, and Jin, Zhi. Convolutional neural networks over tree structures for programming language processing. In AAAI, 2016. find
  14. Neelakantan, Arvind, Le, Quoc V, and Sutskever, Ilya. Neural programmer: Inducing latent programs with gradient descent. In ICLR, 2015. find
  15. Neto, João Pedro, Siegelmann, Hava T, and Costa, J Félix. Symbolic processing in neural networks. Journal of the Brazilian Computer Society, 8(3):58–70, 2003. find
  16. Piech, Chris, Huang, Jonathan, Nguyen, Andy, Phulsuk-sombati, Mike, Sahami, Mehran, and Guibas, Leonidas J. Learning program embeddings to propagate feedback on student code. In ICML, 2015. find
  17. Reed, Scott and de Freitas, Nando. Neural programmer-interpreters. ICLR, 2016. find
  18. Salimans, Tim and Kingma, Diederik P. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, 2016. find
  19. Siegelmann, Hava T. Neural programming language. In Proceedings of the 12th National Conference on Artificial Intelligence, 1994. find
  20. Snoek, Jasper, Larochelle, Hugo, and Adams, Ryan P. Practical Bayesian optimization of machine learning algorithms. In NIPS, 2012. find
  21. Socher, Richard, Pennington, Jeffrey, Huang, Eric H, Ng, Andrew Y, and Manning, Christopher D. Semi-supervised recursive autoencoders for predicting sentiment distributions. In EMNLP, 2011.
  22. Socher, Richard, Huval, Brody, Manning, Christopher D, and Ng, Andrew Y. Semantic compositionality through recursive matrix-vector spaces. In EMNLP, 2012.
  23. Socher, Richard, Perelygin, Alex, Wu, Jean Y, Chuang, Jason, Manning, Christopher D, Ng, Andrew Y, and Potts, Christopher. Recursive deep models for semantic compositionality over a sentiment treebank. In EMNLP, 2013.
  24. Zaremba, Wojciech, Kurach, Karol, and Fergus, Rob. Learning to discover efficient mathematical identities. In Advances in Neural Information Processing Systems, pp. 1278–1286, 2014. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/allamanis-2016-learning-continuous-semantic-representations-symbolic/