Elamur Research⌕
☰
home / papers / 2019 / Deep Learning for Symbolic Mathematics

Deep Learning for Symbolic Mathematics

Paper · 2019 · Guillaume Lample and François Charton

Summary

Neural networks are usually seen as good at approximate, statistical pattern matching and weak at exact symbolic manipulation. Lample and Charton question this view by treating two hard tasks, symbolic integration and solving first- and second-order ordinary differential equations (ODEs), as translation problems. Each mathematical expression is turned into a tree and then written in prefix (Polish) notation, so a standard seq2seq model can map a problem to its solution. The authors also describe a sampler that draws random expression trees with uniform probability and count how large the space of possible expressions is. Since no large supervised dataset existed, they built three generators for integration pairs:

  • FWD: integrate random functions with a computer algebra system.
  • BWD: differentiate random functions and use the derivative as the problem.
  • IBP: combine known integrals through integration by parts.

Trained models nearly solve test sets drawn from their own generator. The authors report that the models beat commercial systems such as Matlab and Mathematica. This suggests neural pattern recognition can complement rule-based computer algebra.

Key points

  • Expressions become prefix token sequences, with no parentheses and integers spelled as a sign plus digits. Tree and expression counts follow Catalan and Schroeder numbers.

  • The integration training set has about 4·10^7 examples, while the problem space holds roughly 10^34 expressions. Near-perfect accuracy on same-generator test data therefore reflects generalization, not memorization.

  • Generalization across generators is weak in some directions (beam 50):

    • FWD-trained model on BWD test data: 17.2%.
    • BWD-trained model on FWD test data: 27.5%.
    • FWD-trained model on IBP test data: 88.9%.
    • BWD-trained model on IBP test data: 59.2%.

    The authors attribute this to differing length distributions, since FWD pairs have short inputs and long outputs while BWD pairs show the reverse. Mixing in IBP or FWD data helps.

  • Mathematica (Integrate, DSolve) was tested on 500 integration problems with timeouts from 5 s to 180 s. Its success rose from 77.8% to 84.6%, and its accuracy could not exceed 86.2% even if every timed-out case were solved.

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

🏢MetaMenlo Park · United States214 works · 241,492 citations🏢Meta (United Kingdom)London · United Kingdom54 works · 19,348 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksMathematics · 189 worksComputational Theory and Mathematics · 321 worksModeling and Simulation · 3 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,685 works

Cite

Cite as Guillaume Lample and François Charton. 2019. Deep Learning for Symbolic Mathematics. arXiv:1912.01412.

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

@misc{lample2019deep,
  title = {{Deep Learning for Symbolic Mathematics}},
  author = {Guillaume Lample and François Charton},
  year = {2019},
  doi = {10.48550/arxiv.1912.01412},
  eprint = {1912.01412},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1912.01412}
}

References

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

  1. Miltiadis Allamanis, Pankajan Chanthirasegaran, Pushmeet Kohli, and Charles Sutton. Learning continuous semantic representations of symbolic expressions. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, pp. 80–88. JMLR.org, 2017. find
  2. Forough Arabshahi, Sameer Singh, and Animashree Anandkumar. Combining symbolic expressions and black-box function evaluations for training neural programs. In International Conference on Learning Representations, 2018a. find
  3. Forough Arabshahi, Sameer Singh, and Animashree Anandkumar. Towards solving differential equations through neural programming. 2018b. find
  4. D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations (ICLR), 2015.
  5. M. Bronstein. Symbolic Integration I: Transcendental Functions. Algorithms and combinatorics. Springer, 2005. ISBN 978-3-540-21493-9. find
  6. Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, and Noah A Smith. Recurrent neural network grammars. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 199–209, 2016. find
  7. Akiko Eriguchi, Yoshimasa Tsuruoka, and Kyunghyun Cho. Learning to parse and translate improves neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 72–78, 2017.
  8. Philippe Flajolet and Andrew M. Odlyzko. Singularity analysis of generating functions. SIAM J. Discrete Math., 3(2):216–240, 1990. find
  9. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, New York, NY, USA, 1 edition, 2009. ISBN 0521898064, 9780521898065. find
  10. Karlis Freivalds and Renars Liepins. Improving the neural gpu architecture for algorithm learning. ArXiv, abs/1702.08727, 2017. find
  11. Joachim von zur Gathen and Jurgen Gerhard. Modern Computer Algebra. Cambridge University Press, New York, NY, USA, 3rd edition, 2013. ISBN 1107039037, 9781107039032. find
  12. Keith O. Geddes, Stephen R. Czapor, and George Labahn. Algorithms for Computer Algebra. Kluwer Academic Publishers, Norwell, MA, USA, 1992. ISBN 0-7923-9259-0. find
  13. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735–1780, 1997. find
  14. Lukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. CoRR, abs/1511.08228, 2015. find
  15. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  16. Donald E. Knuth. The Art of Computer Programming, Volume 1 (3rd Ed.): Fundamental Algorithms. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1997. ISBN 0-201-89683-4. find
  17. Philipp Koehn. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Conference of the Association for Machine Translation in the Americas, pp. 115–124. Springer, 2004. find
  18. Sarah Loos, Geoffrey Irving, Christian Szegedy, and Cezary Kaliszyk. Deep network guided proof search. arXiv preprint arXiv:1701.06972, 2017.
  19. MathWorks. Matlab optimization toolbox (r2019a), 2019. The MathWorks, Natick, MA, USA. find
  20. Aaron Meurer, Christopher P. Smith, Mateusz Paprocki, Ondřej Čertı́k, Sergey B. Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K. Moore, Sartaj Singh, Thilina Rathnayake, Sean Vig, Brian E. Granger, Richard P. Muller, Francesco Bonazzi, Harsh Gupta, Shivam Vats, Fredrik Johansson, Fa… — [doi:10.7717/peerj-cs.103](https://doi.org/10.7717/peerj-cs.103) find
  21. Joel Moses. Macsyma - the fifth year. SIGSAM Bull., 8(3):105–110, August 1974. ISSN 0163-5824. find
  22. Myle Ott, Michael Auli, David Grangier, et al. Analyzing uncertainty in neural machine translation. In International Conference on Machine Learning, pp. 3953–3962, 2018.
  23. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting on association for computational linguistics, pp. 311–318. Association for Computational Linguistics, 2002.
  24. Robert H. Risch. The solution of the problem of integration in finite terms. Bull. Amer. Math. Soc., 76(3):605–608, 05 1970. find
  25. David E. Rumelhart, James L. McClelland, and CORPORATE PDP Research Group (eds.). Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. 1: Foundations. MIT Press, Cambridge, MA, USA, 1986. ISBN 0-262-68053-X. find
  26. David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical reasoning abilities of neural models. In International Conference on Learning Representations, 2019.
  27. N. J. A. Sloane. The encyclopedia of integer sequences, 1996. find
  28. Richard P. Stanley. Enumerative Combinatorics: Volume 1. Cambridge University Press, New York, NY, USA, 2nd edition, 2011. ISBN 1107602629, 9781107602625. find
  29. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems, pp. 3104–3112, 2014.
  30. Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language… find
  31. Andrew Trask, Felix Hill, Scott E Reed, Jack Rae, Chris Dyer, and Phil Blunsom. Neural arithmetic logic units. In Advances in Neural Information Processing Systems, pp. 8035–8044, 2018. find
  32. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 6000–6010, 2017.
  33. Oriol Vinyals, Łukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. Grammar as a foreign language. In Advances in neural information processing systems, pp. 2773–2781, 2015. find
  34. H.S. Wilf. generatingfunctionology: Third Edition. CRC Press, 2005. ISBN 978-1-4398-6439-5. URL https://www.math.upenn.edu/˜wilf/gfologyLinked2.pdf. ↗
  35. Wolfram-Research. Mathematica, version 12.0, 2019. find
  36. Wojciech Zaremba and Ilya Sutskever. Learning to execute. arXiv preprint arXiv:1410.4615, 2014. find
  37. Wojciech Zaremba, Karol Kurach, and Rob Fergus. Learning to discover efficient mathematical identities. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1, NIPS’14, pp. 1278–1286, Cambridge, MA, USA, 2014. MIT Press. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lample-2019-deep-learning-symbolic-mathematics/