Elamur Research⌕
☰
home / papers / 2022 / Symbolic Regression is NP-hard

Symbolic Regression is NP-hard

Paper · 2022 · Marco Virgolin and Solon P. Pissis

Summary

Symbolic regression (SR) looks for a model of data written as a mathematical formula. The formula is built by composing elements of a primitive set, such as operations, variables and constants. Researchers have long assumed that the task is intractable. Existing methods are either heuristics without optimality guarantees (genetic programming, greedy search, deep learning) or exact solvers that explore only a narrow slice of possible expressions. Until this paper, no formal proof of hardness existed. Virgolin and Pissis formally define the SR search space and frame SR as minimizing a distance-based loss over a training set. They also introduce a decision variant: does some expression reach a loss no larger than a given threshold? They show this variant is NP-complete by reducing the unbounded subset sum problem to it. The reduction uses a dataset whose feature values are item weights and whose label is the target sum. As a consequence, finding an optimal SR model is NP-hard, even when arbitrary constants are available. The result gives a theoretical basis for heuristic approaches and invites further work on complexity bounds for SR variants.

Key points

  • The reduction starts from USSP-Dec, which is NP-complete (Kellerer et al., 2004). The primitive set contains only addition and the k features, and the loss threshold is set to zero. A single observation with x_j = w_j and y = t is used. An exact-fit expression exists exactly when the subset-sum instance has a solution, and the construction takes linear time in k.
  • A corollary shows that SR stays NP-hard when the primitive set must include the random-constant element R. A second, all-zero observation forces any added constant to be zero, which recovers the original setting.
  • The hardness result concerns pure optimization on the training set, with the loss defined as a metric (e.g., MAE, MSE, RMSE). Generalization to unseen data is not part of the proof.
  • As background, the authors cite SRBench (La Cava et al., 2021), which benchmarks more than 20 algorithms on more than 250 datasets. On that benchmark, Operon leads in accuracy, while GP-GOMEA leads for models that are both accurate and compact.

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

🔬Centrum Wiskunde & InformaticaAmsterdam · Netherlands6 works · 6,228 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 Marco Virgolin and Solon P. Pissis. 2022. Symbolic Regression is NP-hard. arXiv:2207.01018.

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

@misc{virgolin2022symbolic,
  title = {{Symbolic Regression is NP-hard}},
  author = {Marco Virgolin and Solon P. Pissis},
  year = {2022},
  doi = {10.48550/arxiv.2207.01018},
  eprint = {2207.01018},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2207.01018}
}

References

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

  1. 117th US Congress. Algorithmic accountability act, 2022. URL https://www.congress.gov/bill/117th-congress/house-bill/6580/. ↗
  2. B. Burlacu, G. Kronberger, and M. Kommenda. Operon C++ an efficient genetic programming framework for symbolic regression. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, pages 1562–1570, 2020. find
  3. A. Cozad. Data-and theory-driven techniques for surrogate-based optimization. PhD thesis, Ph. D. thesis, Department of Chemical Engineering, Carnegie Mellon University, 2014. find
  4. A. Cozad and N. V. Sahinidis. A global MINLP approach to symbolic regression. Mathematical Programming, 170(1):97–119, 2018. find
  5. N. L. Cramer. A representation for the adaptive generation of simple sequential programs. In Proceedings of the First International Conference on Genetic Algorithms, pages 183–187, 1985. find
  6. S. d’Ascoli, P.-A. Kamienny, G. Lample, and F. Charton. Deep symbolic regression for recurrent sequences. arXiv preprint arXiv:2201.04600, 2022.
  7. E. Derner, J. Kubalík, N. Ancona, and R. Babuška. Constructing parsimonious analytic models for dynamic systems via symbolic regression. Applied Soft Computing, 94:106432, 2020. find
  8. A. Ekart and S. Z. Nemeth. Selection based on the pareto nondomination criterion for controlling code growth in genetic programming. Genetic Programming and Evolvable Machines, 2(1):61–73, 2001. find
  9. European Commission. Artificial artificialintelligenceact.eu/. B. C. Falkenhainer and R. S. Michalski. Integrating quantitative and qualitative discovery: The ABACUS system. Machine Learning, 1(4):367–401, 1986. find
  10. B. Fornberg and J. Zuev. The runge phenomenon and spatially variable shape parameters in rbf interpolation. Computers & Mathematics with Applications, 54(3):379–398, 2007. find
  11. D. Gerwin. Information processing, data inferences, and scientific generalization. Behavioral Science, 19(5):314–325, 1974. find
  12. D. Hein, S. Udluft, and T. A. Runkler. Interpretable policies for reinforcement learning by genetic programming. Engineering Applications of Artificial Intelligence, 76:158–169, 2018. find
  13. A. Hernandez, A. Balasubramanian, F. Yuan, S. A. Mason, and T. Mueller. Fast, accurate, and transferable many-body interatomic potentials by symbolic regression. npj Computational Materials, 5 (1):1–11, 2019. find
  14. J. F. Hicklin. Application of the genetic algorithm to automatic program generation. PhD thesis, University of Idaho, 1986. find
  15. X. Hu, C. Rudin, and M. Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019. find
  16. A. Jobin, M. Ienca, and E. Vayena. The global landscape of AI ethics guidelines. Nature Machine Intelligence, 1(9):389–399, 2019. find
  17. P.-A. Kamienny, S. d’Ascoli, G. Lample, and F. Charton. End-to-end symbolic regression with transformers. arXiv preprint arXiv:2204.10532, 2022.
  18. L. Kammerer, G. Kronberger, B. Burlacu, S. M. Winkler, M. Kommenda, and M. Affenzeller. Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplication, pages 79–99. Springer International Publishing, 2020. find
  19. H. Kellerer, U. Pferschy, and D. Pisinger. Introduction to NP-Completeness of knapsack problems. In Knapsack Problems, pages 483–493. Springer, 2004. find
  20. J. R. Koza. Genetic programming: A paradigm for genetically breeding populations of computer programs to solve problems, volume 34. Stanford University, 1990. find
  21. J. R. Koza. Genetic programming as a means for programming computers by natural selection. Statistics and Computing, 4(2):87–112, 1994. find
  22. J. R. Koza et al. Hierarchical genetic algorithms operating on populations of computer programs. In International Joint Conference on Artificial Intelligence, volume 89, pages 768–774, 1989. find
  23. G. Kronberger, M. Kommenda, A. Promberger, and F. Nickel. Predicting friction system performance with symbolic regression and genetic programming with factor variables. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1278–1285, 2018. find
  24. W. La Cava, T. R. Singh, J. Taggart, S. Suri, and J. H. Moore. Learning concise representations for regression by evolving networks of trees. In International Conference on Learning Representations, 2018. find
  25. W. La Cava, P. Orzechowski, B. Burlacu, F. O. de Franca, M. Virgolin, Y. Jin, M. Kommenda, and J. H. Moore. Contemporary symbolic regression methods and their relative performance. In Advances in Neural Information Processing Systems — Datasets and Benchmarks Track, 2021.
  26. P. Langley. Data-driven discovery of physical laws. Cognitive Science, 5(1):31–54, 1981. find
  27. P. Lemos, N. Jeffrey, M. Cranmer, S. Ho, and P. Battaglia. Rediscovering orbital mechanics with machine learning. arXiv preprint arXiv:2202.02306, 2022. intelligence act, 2021. URL https://— [arXiv:2202.02306](https://arxiv.org/abs/2202.02306) find
  28. H. Li, Y. Weng, and H. Tong. CoNSoLe: Convex neural symbolic learning. arXiv preprint arXiv:2206.00257, 2022. — [arXiv:2206.00257](https://arxiv.org/abs/2206.00257) find
  29. Q. Lu, J. Ren, and Z. Wang. Using genetic programming with prior formula knowledge to solve symbolic regression problem. Computational Intelligence and Neuroscience, 2016. find
  30. M. Märtens and D. Izzo. Symbolic regression for space applications: Differentiable cartesian genetic programming powered by multi-objective memetic algorithms. arXiv preprint arXiv:2206.06213, 2022. — [arXiv:2206.06213](https://arxiv.org/abs/2206.06213) find
  31. Y. Matsubara, N. Chiba, R. Igarashi, T. Taniai, and Y. Ushiku. Rethinking symbolic regression datasets and benchmarks for scientific discovery. arXiv preprint arXiv:2206.10540, 2022. — [arXiv:2206.10540](https://arxiv.org/abs/2206.10540) find
  32. T. McConaghy. FFX: Fast, scalable, deterministic symbolic regression technology. In Genetic Programming Theory and Practice IX, pages 235–260. Springer, 2011. find
  33. R. I. McKay, N. X. Hoai, P. A. Whigham, Y. Shan, and M. O’neill. Grammar-based genetic programming: a survey. Genetic Programming and Evolvable Machines, 11(3):365–396, 2010. find
  34. D. J. Montana. Strongly typed genetic programming. Evolutionary Computation, 3(2):199–230, 1995. find
  35. F. Olivetti de França. A greedy search tree heuristic for symbolic regression. Information Sciences, 442-443:18–32, 2018. ISSN 0020-0255. find
  36. M. O’Neill and C. Ryan. Grammatical evolution. IEEE Transactions on Evolutionary Computation, 5(4):349–358, 2001. find
  37. C. Otte. Safe and interpretable machine learning: A methodological review. Computational Intelligence in Intelligent Data Analysis, pages 111–122, 2013. find
  38. B. K. Petersen, M. L. Larma, T. N. Mundhenk, C. P. Santiago, S. K. Kim, and J. T. Kim. 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
  39. B. K. Petersen, M. L. Larma, T. N. Mundhenk, C. P. Santiago, S. K. Kim, and J. T. Kim. Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients. In International Conference on Learning Representations, 2020. find
  40. R. Poli, W. B. Langdon, and N. F. McPhee. A Field Guide to Genetic Programming. Lulu Press, 2008. find
  41. D. Rivero, E. Fernandez-Blanco, and A. Pazos. DoME: A deterministic technique for equation development and symbolic regression. Expert Systems with Applications, 198:116712, 2022. find
  42. M. Schmidt and H. Lipson. Distilling free-form natural laws from experimental data. Science, 324 (5923):81–85, 2009. find
  43. S.-M. Udrescu and M. Tegmark. AI Feynman: A physics-inspired method for symbolic regression. Science Advances, 6(16):eaay2631, 2020.
  44. M. Vastl, J. Kulhánek, J. Kubalík, E. Derner, and R. Babuška. SymFormer: End-to-end symbolic regression using transformer-based architecture. arXiv preprint arXiv:2205.15764, 2022. — [arXiv:2205.15764](https://arxiv.org/abs/2205.15764) find
  45. S. Verstyuk and M. R. Douglas. Machine learning the gravity equation for international trade. Available at SSRN 4053795, 2022. find
  46. M. Virgolin, A. De Lorenzo, E. Medvet, and F. Randone. Learning a formula of interpretability to learn interpretable formulas. In International Conference on Parallel Problem Solving from Nature, pages 79–93. Springer, 2020a. find
  47. M. Virgolin, Z. Wang, T. Alderliesten, and P. A. Bosman. Machine learning for the prediction of pseudorealistic pediatric abdominal phantoms for radiation dose reconstruction. Journal of Medical Imaging, 7(4):046501, 2020b. find
  48. M. Virgolin, T. Alderliesten, C. Witteveen, and P. A. N. Bosman. Improving model-based genetic programming for symbolic regression of small expressions. Evolutionary Computation, 29(2): 211–237, 2021a. find
  49. M. Virgolin, A. De Lorenzo, F. Randone, E. Medvet, and M. Wahde. Model learning with personalized interpretability estimation (ML-PIE). In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1355–1364, 2021b. find
  50. T. Worm and K. Chiu. Prioritized grammar enumeration: Symbolic regression by dynamic programming. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1021–1028, 2013. find
  51. I. Zelinka, Z. Oplatkova, and L. Nolle. Analytic programming–symbolic regression by means of arbitrary evolutionary algorithms. International Journal of Simulation: Systems, Science and Technology, 6(9):44–56, 2005. find
  52. H. Zou and T. Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2):301–320, 2005. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/virgolin-2022-symbolic-regression-np-hard/