Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness

Dorian Florescu, Matthew England

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

    7 Citations (Scopus)
    49 Downloads (Pure)


    Our topic is the use of machine learning to improve software by making choices which do not compromise the correctness of the output, but do affect the time taken to produce such output. We are particularly concerned with computer algebra systems (CASs), and in particular, our experiments are for selecting the variable ordering to use when performing a cylindrical algebraic decomposition of n-dimensional real space with respect to the signs of a set of polynomials.

    In our prior work we explored the different ML models that could be used, and how to identify suitable features of the input polynomials. In the present paper we both repeat our prior experiments on problems which have more variables (and thus exponentially more possible orderings), and examine the metric which our ML classifiers targets. The natural metric is computational runtime, with classifiers trained to pick the ordering which minimises this. However, this leads to the situation were models do not distinguish between any of the non-optimal orderings, whose runtimes may still vary dramatically. In this paper we investigate a modification to the cross-validation algorithms of the classifiers so that they do distinguish these cases, leading to improved results.
    Original languageEnglish
    Title of host publicationMathematical Aspects of Computer and Information Sciences
    Subtitle of host publicationProc. MACIS 2019
    EditorsDaniel Slamanig , Elias Tsigaridas , Zafeirakis Zafeirakopoulos
    PublisherSpringer International Publishing
    Number of pages16
    ISBN (Electronic)978-3-030-43120-4
    ISBN (Print)978-3-030-43119-8
    Publication statusPublished - 18 Mar 2020
    EventMathematical Aspects of Computer and Information Sciences 2019 - Istanbul, Turkey
    Duration: 13 Nov 201915 Nov 2019
    Conference number: 8

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume11989 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceMathematical Aspects of Computer and Information Sciences 2019
    Abbreviated titleMACIS 2019
    Internet address

    Bibliographical note

    This work is funded by EPSRC Project EP/R019622/1: Embedding Machine Learning within Quantifier Elimination Procedures.

    Publisher Copyright:
    © 2020, Springer Nature Switzerland AG.


    • Machine Learning
    • cross-validation
    • Computer Algebra
    • Symbolic Computation
    • Cylindrical Algebraic Decomposition
    • Cylindrical algebraic decomposition
    • Cross-validation
    • Symbolic computation
    • Computer algebra

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)


    Dive into the research topics of 'Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness'. Together they form a unique fingerprint.

    Cite this