Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

Abstract

There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. Here we extend this result by training ML models to select the variable ordering directly, and by trying out a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human-made heuristics for the problem: the Brown heuristic and sotd. On this dataset all of the ML approaches outperformed the human-made heuristics, some by a large margin.

Original languageEnglish
Title of host publicationIntelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings
EditorsCezary Kaliszyk, Edwin Brady, Andrea Kohlhase, Claudio Sacerdoti Coen
PublisherSpringer
Pages93-108
Number of pages16
Volume11617
ISBN (Electronic)978-3-030-23250-4
ISBN (Print)978-3-030-23249-8
DOIs
Publication statusPublished - 8 Jul 2019
Event12th Conference on Intelligent Computer Mathematics - Prague, Czech Republic
Duration: 8 Jul 201912 Jul 2019
Conference number: 12th
https://www.cicm-conference.org/2019/cicm.php

Publication series

NameLecture Notes in Artificial Intelligence
PublisherSpringer Verlag
Volume11617
ISSN (Electronic)0302-9743

Conference

Conference12th Conference on Intelligent Computer Mathematics
Abbreviated titleCICM 2019
CountryCzech Republic
CityPrague
Period8/07/1912/07/19
Internet address

Fingerprint

Learning systems
Machine Learning
Choose
Decomposition
Decompose
Heuristics
Support vector machines
Support Vector Machine
Model
Mathematical Software
Python
Computing
Maple
Symbolic Computation
Multilayer neural networks
Decision trees
Decision Support
Perceptron
Decision tree
Margin

Keywords

  • Computer algebra
  • Cylindrical algebraic decomposition
  • Machine learning
  • Non-linear real arithmetic
  • Symbolic computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

England, M., & Florescu, D. (2019). Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition. In C. Kaliszyk, E. Brady, A. Kohlhase, & C. Sacerdoti Coen (Eds.), Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings (Vol. 11617, pp. 93-108). (Lecture Notes in Artificial Intelligence; Vol. 11617). Springer. https://doi.org/10.1007/978-3-030-23250-4_7

Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition. / England, Matthew; Florescu, Dorian.

Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings. ed. / Cezary Kaliszyk; Edwin Brady; Andrea Kohlhase; Claudio Sacerdoti Coen. Vol. 11617 Springer, 2019. p. 93-108 (Lecture Notes in Artificial Intelligence; Vol. 11617).

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

England, M & Florescu, D 2019, Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition. in C Kaliszyk, E Brady, A Kohlhase & C Sacerdoti Coen (eds), Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings. vol. 11617, Lecture Notes in Artificial Intelligence, vol. 11617, Springer, pp. 93-108, 12th Conference on Intelligent Computer Mathematics, Prague, Czech Republic, 8/07/19. https://doi.org/10.1007/978-3-030-23250-4_7
England M, Florescu D. Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition. In Kaliszyk C, Brady E, Kohlhase A, Sacerdoti Coen C, editors, Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings. Vol. 11617. Springer. 2019. p. 93-108. (Lecture Notes in Artificial Intelligence). https://doi.org/10.1007/978-3-030-23250-4_7
England, Matthew ; Florescu, Dorian. / Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition. Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings. editor / Cezary Kaliszyk ; Edwin Brady ; Andrea Kohlhase ; Claudio Sacerdoti Coen. Vol. 11617 Springer, 2019. pp. 93-108 (Lecture Notes in Artificial Intelligence).
@inproceedings{b662d9603dd94114afd7b9565b8ac743,
title = "Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition",
abstract = "There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. Here we extend this result by training ML models to select the variable ordering directly, and by trying out a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human-made heuristics for the problem: the Brown heuristic and sotd. On this dataset all of the ML approaches outperformed the human-made heuristics, some by a large margin.",
keywords = "Computer algebra, Cylindrical algebraic decomposition, Machine learning, Non-linear real arithmetic, Symbolic computation",
author = "Matthew England and Dorian Florescu",
year = "2019",
month = "7",
day = "8",
doi = "10.1007/978-3-030-23250-4_7",
language = "English",
isbn = "978-3-030-23249-8",
volume = "11617",
series = "Lecture Notes in Artificial Intelligence",
publisher = "Springer",
pages = "93--108",
editor = "Cezary Kaliszyk and Edwin Brady and Andrea Kohlhase and {Sacerdoti Coen}, Claudio",
booktitle = "Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings",

}

TY - GEN

T1 - Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition

AU - England, Matthew

AU - Florescu, Dorian

PY - 2019/7/8

Y1 - 2019/7/8

N2 - There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. Here we extend this result by training ML models to select the variable ordering directly, and by trying out a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human-made heuristics for the problem: the Brown heuristic and sotd. On this dataset all of the ML approaches outperformed the human-made heuristics, some by a large margin.

AB - There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. Here we extend this result by training ML models to select the variable ordering directly, and by trying out a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human-made heuristics for the problem: the Brown heuristic and sotd. On this dataset all of the ML approaches outperformed the human-made heuristics, some by a large margin.

KW - Computer algebra

KW - Cylindrical algebraic decomposition

KW - Machine learning

KW - Non-linear real arithmetic

KW - Symbolic computation

UR - http://www.scopus.com/inward/record.url?scp=85069146674&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-23250-4_7

DO - 10.1007/978-3-030-23250-4_7

M3 - Conference proceeding

SN - 978-3-030-23249-8

VL - 11617

T3 - Lecture Notes in Artificial Intelligence

SP - 93

EP - 108

BT - Intelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings

A2 - Kaliszyk, Cezary

A2 - Brady, Edwin

A2 - Kohlhase, Andrea

A2 - Sacerdoti Coen, Claudio

PB - Springer

ER -