Algorithmically generating new algebraic features of polynomial systems for machine learning

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

Abstract

There are a variety of choices to be made in both computer algebra systems (CASs) and satisfiability modulo theory (SMT) solvers which can impact performance without affecting mathematical correctness. Such choices are candidates for machine learning (ML) approaches, however, there are difficulties in applying standard ML techniques, such as the efficient identification of ML features from input data which is typically a polynomial system. Our focus is selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm implemented in several CASs, and now also SMT-solvers. We created a framework to describe all the previously identified ML features for the problem and then enumerated all options in this framework to automatically generation many more features. We validate the usefulness of these with an experiment which shows that an ML choice for CAD variable ordering is superior to those made by human created heuristics, and further improved with these additional features. We expect that this technique of feature generation could be useful for other choices related to CAD, or even choices for other algorithms with polynomial systems for input.
Original languageEnglish
Title of host publicationProceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation
PublisherCEUR Workshop Proceedings
Number of pages15
Volume(In-Press)
Publication statusAccepted/In press - 20 May 2019
Event4th International Workshop on Satisfiability Checking and Symbolic Computation - Bern , Switzerland
Duration: 10 Jul 201910 Jul 2019

Conference

Conference4th International Workshop on Satisfiability Checking and Symbolic Computation
Abbreviated titleSIAM AG 2019
CountrySwitzerland
CityBern
Period10/07/1910/07/19

Fingerprint

Learning systems
Polynomials
Decomposition
Algebra
Identification (control systems)
Experiments

Bibliographical note

Please note publication is with CEUR-WS which do not impose copyright beyond that to publish, hence we can make the pdf open. (once published)

Cite this

Florescu, D., & England, M. (Accepted/In press). Algorithmically generating new algebraic features of polynomial systems for machine learning. In Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation (Vol. (In-Press)). CEUR Workshop Proceedings.

Algorithmically generating new algebraic features of polynomial systems for machine learning. / Florescu, Dorian; England, Matthew.

Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation. Vol. (In-Press) CEUR Workshop Proceedings, 2019.

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

Florescu, D & England, M 2019, Algorithmically generating new algebraic features of polynomial systems for machine learning. in Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation. vol. (In-Press), CEUR Workshop Proceedings, 4th International Workshop on Satisfiability Checking and Symbolic Computation, Bern , Switzerland, 10/07/19.
Florescu D, England M. Algorithmically generating new algebraic features of polynomial systems for machine learning. In Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation. Vol. (In-Press). CEUR Workshop Proceedings. 2019
Florescu, Dorian ; England, Matthew. / Algorithmically generating new algebraic features of polynomial systems for machine learning. Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation. Vol. (In-Press) CEUR Workshop Proceedings, 2019.
@inproceedings{30a71f6493b54b4db873df1120aa3636,
title = "Algorithmically generating new algebraic features of polynomial systems for machine learning",
abstract = "There are a variety of choices to be made in both computer algebra systems (CASs) and satisfiability modulo theory (SMT) solvers which can impact performance without affecting mathematical correctness. Such choices are candidates for machine learning (ML) approaches, however, there are difficulties in applying standard ML techniques, such as the efficient identification of ML features from input data which is typically a polynomial system. Our focus is selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm implemented in several CASs, and now also SMT-solvers. We created a framework to describe all the previously identified ML features for the problem and then enumerated all options in this framework to automatically generation many more features. We validate the usefulness of these with an experiment which shows that an ML choice for CAD variable ordering is superior to those made by human created heuristics, and further improved with these additional features. We expect that this technique of feature generation could be useful for other choices related to CAD, or even choices for other algorithms with polynomial systems for input.",
author = "Dorian Florescu and Matthew England",
note = "Please note publication is with CEUR-WS which do not impose copyright beyond that to publish, hence we can make the pdf open. (once published)",
year = "2019",
month = "5",
day = "20",
language = "English",
volume = "(In-Press)",
booktitle = "Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation",
publisher = "CEUR Workshop Proceedings",

}

TY - GEN

T1 - Algorithmically generating new algebraic features of polynomial systems for machine learning

AU - Florescu, Dorian

AU - England, Matthew

N1 - Please note publication is with CEUR-WS which do not impose copyright beyond that to publish, hence we can make the pdf open. (once published)

PY - 2019/5/20

Y1 - 2019/5/20

N2 - There are a variety of choices to be made in both computer algebra systems (CASs) and satisfiability modulo theory (SMT) solvers which can impact performance without affecting mathematical correctness. Such choices are candidates for machine learning (ML) approaches, however, there are difficulties in applying standard ML techniques, such as the efficient identification of ML features from input data which is typically a polynomial system. Our focus is selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm implemented in several CASs, and now also SMT-solvers. We created a framework to describe all the previously identified ML features for the problem and then enumerated all options in this framework to automatically generation many more features. We validate the usefulness of these with an experiment which shows that an ML choice for CAD variable ordering is superior to those made by human created heuristics, and further improved with these additional features. We expect that this technique of feature generation could be useful for other choices related to CAD, or even choices for other algorithms with polynomial systems for input.

AB - There are a variety of choices to be made in both computer algebra systems (CASs) and satisfiability modulo theory (SMT) solvers which can impact performance without affecting mathematical correctness. Such choices are candidates for machine learning (ML) approaches, however, there are difficulties in applying standard ML techniques, such as the efficient identification of ML features from input data which is typically a polynomial system. Our focus is selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm implemented in several CASs, and now also SMT-solvers. We created a framework to describe all the previously identified ML features for the problem and then enumerated all options in this framework to automatically generation many more features. We validate the usefulness of these with an experiment which shows that an ML choice for CAD variable ordering is superior to those made by human created heuristics, and further improved with these additional features. We expect that this technique of feature generation could be useful for other choices related to CAD, or even choices for other algorithms with polynomial systems for input.

M3 - Conference proceeding

VL - (In-Press)

BT - Proceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation

PB - CEUR Workshop Proceedings

ER -