Elamur Research⌕
☰
home / papers / 2022 / Deep Symbolic Regression for Recurrent Sequences

Deep Symbolic Regression for Recurrent Sequences

Paper · 2022 · Stéphane d'Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample et al.

Summary

The paper tackles symbolic regression for sequences. Given the first terms of an integer or float sequence, the goal is to recover a recurrence relation u_n = f(n, earlier terms) that generates it. This is the familiar "guess the next number" puzzle from IQ tests, and earlier symbolic regression work, which targeted plain y = f(x) mappings, had mostly left it aside. The authors pretrain Transformers on a large synthetic corpus. They build random unary-binary expression trees from operator sets (a compact integer-closed set and a broader float set), draw random initial terms and unroll each sequence. A symbolic model emits the formula, while a numeric counterpart with the same architecture directly forecasts the upcoming values. On unseen synthetic recurrences, extrapolating with the predicted formulas is more precise than using the numeric model. On a subset of OEIS sequences, both models beat Mathematica's built-in tools. The float model can also express constants and special functions missing from its vocabulary through approximations such as 1.64493 ≈ π²/6. The approach replaces costly search with a single forward pass and could assist mathematical discovery.

Key points

  • On OEIS sequences with 25 input terms, next-term accuracy (tolerance 10⁻¹⁰) was:
    • symbolic model: 34.5%
    • numeric model: 54.9%
    • Mathematica FindLinearRecurrence: 21.2%
    • Mathematica FindSequenceFunction: 8.1%
  • Operator vocabularies differ by setting:
    • Integer generator: abs, sqr, sign, relu, add, sub, mul, intdiv, mod.
    • Float generator: adds sqrt, inv, log, exp, trig functions, atan and real division.
  • When constants are drawn from a continuous range outside the training vocabulary, the symbolic model's approximate accuracy (≤10 operators, tolerance 0.01) falls from about 60% to 42%.
  • The model finds asymptotic approximations for scipy.special functions, e.g. bessel0 and Catalan numbers, and outperforms the numeric model even on non-polynomial families.
  • Published at ICML 2022. Code is at github.com/facebookresearch/recur, and an interactive demo is available online.

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

🎓Sorbonne UniversitéParis · France35 works · 7,416 citations🔬École Normale Supérieure - PSLParis · France25 works · 4,704 citations🔬LIP6Paris · France7 works · 1,665 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksMathematics · 233 worksPhysics and Astronomy · 70 worksStatistical and Nonlinear Physics · 60 worksModeling and Simulation · 12 works

Cite

Cite as Stéphane d'Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample and François Charton. 2022. Deep Symbolic Regression for Recurrent Sequences. arXiv:2201.04600.

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

@misc{dascoli2022deep,
  title = {{Deep Symbolic Regression for Recurrent Sequences}},
  author = {Stéphane d'Ascoli, Pierre-Alexandre Kamienny, Guillaume Lample and François Charton},
  year = {2022},
  doi = {10.48550/arxiv.2201.04600},
  eprint = {2201.04600},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2201.04600}
}

References

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

  1. Allamanis, M., Chanthirasegaran, P., Kohli, P., and Sutton, C. Learning continuous semantic representations of symbolic expressions. In International Conference on Machine Learning, pp. 80–88. PMLR, 2017.
  2. Arabshahi, F., Singh, S., and Anandkumar, A. Towards solving differential equations through neural programming. In ICML Workshop on Neural Abstract Machines and Program Induction (NAMPI), 2018. find
  3. Augusto, D. A. and Barbosa, H. J. Symbolic regression via genetic programming. In Proceedings. Vol. 1. Sixth Brazilian Symposium on Neural Networks, pp. 173–178. IEEE, 2000. find
  4. Biggio, L., Bendinelli, T., Neitz, A., Lucchi, A., and Parascandolo, G. Neural symbolic regression that scales. arXiv preprint arXiv:2106.06427, 2021. — [arXiv:2106.06427](https://arxiv.org/abs/2106.06427) find
  5. Charton, F. Linear algebra with transformers. arXiv preprint arXiv:2112.01898, 2021.
  6. Charton, F., Hayat, A., and Lample, G. Learning advanced mathematical computations from examples. arXiv preprint arXiv:2006.06462, 2020.
  7. Cobbe, K., Kosaraju, V., Bavarian, M., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.
  8. Davies, A., Velickovic, P., Buesing, L., Blackwell, S., Zheng, D., Tomasev, N., Tanburn, R., Battaglia, P., Blundell, C., Juhasz, A., et al. Advancing mathematics by guiding human intuition with ai. Nature, 2021. find
  9. Kaiser, Ł. and Sutskever, I. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015. find
  10. Kamienny, P.-A., d’Ascoli, S., Lample, G., and Charton, F. End-to-end symbolic regression with transformers. arXiv preprint arXiv:2204.10532, 2022.
  11. Kim, S., Lu, P. Y., Mukherjee, S., Gilbert, M., Jing, L., Čeperić, V., and Soljačić, M. Integration of neural network-based symbolic regression in deep learning for scientific discovery. IEEE Transactions on Neural Networks and Learning Systems, 2020. find
  12. Lample, G. and Charton, F. Deep learning for symbolic mathematics. arXiv preprint arXiv:1912.01412, 2019.
  13. McKay, B., Willis, M. J., and Barton, G. W. Using a tree structured genetic algorithm to perform symbolic regression. In First international conference on genetic algorithms in engineering systems: innovations and applications, pp. 487–492. IET, 1995. find
  14. Meurer, A., Smith, C. P., Paprocki, M., Čertı́k, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J. K., Singh, S., et al. Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103, 2017. find
  15. Murari, A., Peluso, E., Gelfusa, M., Lupelli, I., Lunga-roni, M., and Gaudio, P. Symbolic regression via genetic programming for data driven derivation of confinement scaling laws without any assumption on their mathematical form. Plasma Physics and Controlled Fusion, 57(1): 014008, 2014. find
  16. Nam, H., Kim, S., and Jung, K. Number sequence prediction problems for evaluating computational powers of neural networks, 2018. find
  17. Paccanaro, A. and Hinton, G. E. Learning distributed representations of concepts using linear relational embedding. IEEE Transactions on Knowledge and Data Engineering, 13(2):232–244, 2001. find
  18. Petersen, B. K., Larma, M. L., Mundhenk, T. N., Santiago, C. P., Kim, S. K., and Kim, J. T. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. arXiv preprint arXiv:1912.04871, 2019. — [arXiv:1912.04871](https://arxiv.org/abs/1912.04871) find
  19. Raayoni, G., Gottlieb, S., Manor, Y., Pisha, G., Harris, Y., Mendlovic, U., Haviv, D., Hadad, Y., and Kaminer, I. Generating conjectures on fundamental constants with the ramanujan machine. Nature, 590(7844):67–73, 2021. find
  20. Ragni, M. and Klein, A. Predicting numbers: An ai approach to solving number series. In Bach, J. and Edelkamp, S. (eds.), KI 2011: Advances in Artificial Intelligence, pp. 255–259. find
  21. Springer Berlin Heidelberg, 2011. find
  22. Ryskina, M. and Knight, K. Learning mathematical properties of integers. arXiv preprint arXiv:2109.07230, 2021. find
  23. Sahoo, S., Lampert, C., and Martius, G. Learning equations for extrapolation and control. In International Conference on Machine Learning, pp. 4442–4450. PMLR, 2018. find
  24. Saxton, D., Grefenstette, E., Hill, F., and Kohli, P. Analysing mathematical reasoning abilities of neural models. arXiv preprint arXiv:1904.01557, 2019.
  25. Schmidt, M. and Lipson, H. Distilling free-form natural laws from experimental data. science, 324(5923):81–85, 2009. find
  26. Sloane, N. J. The on-line encyclopedia of integer sequences. In Towards mechanized mathematical assistants, pp. 130– 130. Springer, 2007. find
  27. Trask, A., Hill, F., Reed, S., Rae, J., Dyer, C., and Blunsom, P. Neural arithmetic logic units. arXiv preprint arXiv:1808.00508, 2018. find
  28. Valipour, M., You, B., Panju, M., and Ghodsi, A. Symbolicgpt: A generative transformer model for symbolic regression. arXiv preprint arXiv:2106.14131, 2021. van der Maaten, L. and Hinton, G. Visualizing data using t-SNE. Journal of Machine Learning Research, 9:2579– 2605, 2008. — [arXiv:2106.14131](https://arxiv.org/abs/2106.14131) find
  29. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. In Advances in neural information processing systems, pp. 5998–6008, 2017.
  30. Wu, C. W. Can machine learning identify interesting mathematics? an exploration using empirically observed laws. arXiv preprint arXiv:1805.07431, 2018. — [arXiv:1805.07431](https://arxiv.org/abs/1805.07431) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ascoli-2022-deep-symbolic-regression-recurrent-sequences/