Explainable AI insights for symbolic computation: a case study on selecting the variable ordering for cylindrical algebraic decomposition

DOI10.1016/J.JSC.2023.102276arXiv2304.12154MaRDI QIDQ6149145FDOQ6149145

Authors: Lynn Pickering, Tereso del Río Almajano, Matthew England, Kelly Cohen 

Publication date: 5 February 2024

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: In recent years there has been increased use of machine learning (ML) techniques within mathematics, including symbolic computation where it may be applied safely to optimise or select algorithms. This paper explores whether using explainable AI (XAI) techniques on such ML models can offer new insight for symbolic computation, inspiring new implementations within computer algebra systems that do not directly call upon AI tools. We present a case study on the use of ML to select the variable ordering for cylindrical algebraic decomposition. It has already been demonstrated that ML can make the choice well, but here we show how the SHAP tool for explainability can be used to inform new heuristics of a size and complexity similar to those human-designed heuristics currently commonly used in symbolic computation.

Full work available at URL: https://arxiv.org/abs/2304.12154

zbMATH Keywords

computer algebracylindrical algebraic decompositionvariable orderingexplainable AIheuristic development

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Symbolic computation and algebraic computation (68W30)

Cites Work

• Scikit-learn: machine learning in Python
• TheoryGuru: a Mathematica package to apply quantifier elimination technology to economics
• Pattern recognition and machine learning.
• Title not available (Why is that?)
• Partial cylindrical algebraic decomposition for quantifier elimination
• Computing cylindrical algebraic decomposition via triangular decomposition
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Solving non-linear arithmetic
• Title not available (Why is that?)
• Real World Verification
• Title not available (Why is that?)
• Code optimization in FORM
• Real quantifier elimination is doubly exponential
• Cylindrical algebraic decomposition using validated numerics
• Optimising problem formulation for cylindrical algebraic decomposition
• MetiTarski: past and future
• Efficient projection orders for CAD
• The complexity of quantifier elimination and cylindrical algebraic decomposition
• Validity proof of Lazard's method for CAD construction
• On using Lazard's projection in CAD construction
• Title not available (Why is that?)
• Identifying the parametric occurrence of multiple steady states for some biological networks
• Fully incremental cylindrical algebraic decomposition
• Cylindrical algebraic decomposition with equational constraints
• Using machine learning to improve cylindrical algebraic decomposition
• Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
• Open non-uniform cylindrical algebraic decompositions
• Improved Cross-Validation for Classifiers that Make Algorithmic Choices to Minimise Runtime Without Compromising Output Correctness
• Efficient subformula orders for real quantifier elimination of non-prenex formulas
• Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
• Variable ordering selection for cylindrical algebraic decomposition with artificial neural networks
• Machine learning the real discriminant locus
• New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
• Advancing mathematics by guiding human intuition with AI
• Special issue on algebraic geometry and machine learning
• A Machine Learning Based Software Pipeline to Pick the Variable Ordering for Algorithms with Polynomial Inputs

Cited In (8)

• Bilinear-form and similarity-reduction visit to a variable-coefficient generalized dispersive water-wave system concerning Acta Mech. 233, 2527 and 233, 2415
• Constrained neural networks for interpretable heuristic creation to optimise computer algebra systems
• Exploring alternative machine learning models for variable ordering in cylindrical algebraic decomposition
• Symbolic integration algorithm selection with machine learning: LSTMs vs tree LSTMs
• Lessons on datasets and paradigms in machine learning for symbolic computation: a case study on CAD
• A dataset for suggesting variable orderings for cylindrical algebraic decompositions
• Algebraic representations for faster predictions in convolutional neural networks
• Recent developments in real quantifier elimination and cylindrical algebraic decomposition (extended abstract of invited talk)

This page was built for publication: Explainable AI insights for symbolic computation: a case study on selecting the variable ordering for cylindrical algebraic decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6149145)