Algorithmically generating new algebraic features of polynomial systems for machine learning

Dorian Florescu, Matthew England

    Research output: Chapter in Book/Report/Conference proceedingConference proceedingpeer-review

    8 Citations (Scopus)
    51 Downloads (Pure)

    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 generate 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. This technique of feature generation could be useful for other choices related to CAD, or even choices for other algorithms in CASs / SMT-solvers with polynomial systems as input.

    Original languageEnglish
    Title of host publicationProceedings of the 4th International Workshop on Satisfiability Checking and Symbolic Computation
    PublisherCEUR Workshop Proceedings
    Number of pages12
    Publication statusPublished - 4 Oct 2019
    Event4th International Workshop on Satisfiability Checking and Symbolic Computation - Bern, Switzerland
    Duration: 10 Jul 201910 Jul 2019

    Publication series

    NameCEUR Workshop Proceedings
    PublisherCEUR Workshop Proceedings
    Volume2460
    ISSN (Print)1613-0073

    Workshop

    Workshop4th International Workshop on Satisfiability Checking and Symbolic Computation
    Abbreviated titleSIAM AG 2019
    Country/TerritorySwitzerland
    CityBern
    Period10/07/1910/07/19

    Bibliographical note

    Copyright © 2019 for the individual papers by the papers' authors. This volume and its papers are published under the Creative Commons License Attribution 4.0 International (CC BY 4.0).

    Keywords

    • machine learning
    • feature generation
    • non-linear
    • real arithmetic
    • symbolic computation
    • cylindrical algebraic decomposition

    ASJC Scopus subject areas

    • Computer Science(all)

    Fingerprint

    Dive into the research topics of 'Algorithmically generating new algebraic features of polynomial systems for machine learning'. Together they form a unique fingerprint.

    Cite this