Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decomposition

Lynn Pickering; Tereso del Río; Matthew England; Kelly Cohen

doi:10.1016/j.jsc.2023.102276

Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decomposition

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

Research Centre for Computational Science and Mathematical Modelling

University of Cincinnati

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

161 Downloads (Pure)

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.

Original language	English
Article number	102276
Number of pages	24
Journal	Journal of Symbolic Computation
Volume	123
Early online date	15 Nov 2023
DOIs	https://doi.org/10.1016/j.jsc.2023.102276
Publication status	Published - 1 Jul 2024

Bibliographical note

Funder

Matthew England acknowledges the support of UKRI EPSRC Grant EP/T015748/1, “Pushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition” (DEWCAD). Tereso del Río and Lynn Pickering acknowledge the Coventry University Research Excellence grant that allowed them to work together in person on this paper. Lynn Pickering acknowledges the support of the Rindsberg Fellowship from the University of Cincinnati, the Ohio Space Grant Consortium Research Fellowship, and a University of Cincinnati International Study Abroad Scholarship that allowed her to spend a semester at Coventry University.

Funding

Matthew England acknowledges the support of UKRI EPSRC Grant EP/T015748/1 , \u201CPushing Back the Doubly-Exponential Wall of Cylindrical Algebraic Decomposition\u201D (DEWCAD). Tereso del R\u00EDo and Lynn Pickering acknowledge the Coventry University Research Excellence grant that allowed them to work together in person on this paper. Lynn Pickering acknowledges the support of the Rindsberg Fellowship from the University of Cincinnati , the Ohio Space Grant Consortium Research Fellowship, and a University of Cincinnati International Study Abroad Scholarship that allowed her to spend a semester at Coventry University.

Funders	Funder number
University of Cincinnati
Engineering and Physical Sciences Research Council
Coventry University
Ohio Space Grant Consortium
Engineering and Physical Sciences Research Council	EP/T015748/1
Engineering and Physical Sciences Research Council

Keywords

Explainable AI
Computer Algebra
Heuristic Development
Cylindrical Algebraic
Decomposition
Variable Ordering

Access to Document

10.1016/j.jsc.2023.102276Licence: CC BY

PublishedFinal published version, 1.62 MBLicence: CC BY
1-s2.0-S0747717123000901-mainFinal published version, 1.28 MBLicence: CC BY

Cite this

@article{8e4465a3c4214df1b1f1978ca28466b0,

title = "Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decomposition",

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.",

keywords = "Explainable AI, Computer Algebra, Heuristic Development, Cylindrical Algebraic, Decomposition, Variable Ordering",

author = "Lynn Pickering and \{del R{\'i}o\}, Tereso and Matthew England and Kelly Cohen",

note = "{\textcopyright} 2023 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).",

year = "2024",

month = jul,

day = "1",

doi = "10.1016/j.jsc.2023.102276",

language = "English",

volume = "123",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Elsevier",

}

TY - JOUR

T1 - Explainable AI Insights for Symbolic Computation

T2 - A case study on selecting the variable ordering for cylindrical algebraic decomposition

AU - Pickering, Lynn

AU - del Río, Tereso

AU - England, Matthew

AU - Cohen, Kelly

PY - 2024/7/1

Y1 - 2024/7/1

N2 - 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.

AB - 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.

KW - Explainable AI

KW - Computer Algebra

KW - Heuristic Development

KW - Cylindrical Algebraic

KW - Decomposition

KW - Variable Ordering

UR - https://www.scopus.com/pages/publications/85178647748

U2 - 10.1016/j.jsc.2023.102276

DO - 10.1016/j.jsc.2023.102276

M3 - Article

SN - 0747-7171

VL - 123

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

M1 - 102276

ER -

Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decomposition

Abstract

Bibliographical note

Funder

Funding

Keywords

Access to Document

Other files and links

Fingerprint