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

Abstract

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.

arXiv comment16 pages. Accepted into the Proceedings of MACIS 2019. arXiv admin note: text overlap with arXiv:1906.01455

References in corpus (17)

• SATzilla: Portfolio-based Algorithm Selection for SAT
• Truth Table Invariant Cylindrical Algebraic Decomposition
• Program Verification in the presence of complex numbers, functions with branch cuts etc
• Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
• A Case Study on the Parametric Occurrence of Multiple Steady States
• Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
• Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks
• Optimising Problem Formulation for Cylindrical Algebraic Decomposition
• Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting
• Cylindrical Algebraic Decomposition with Equational Constraints
• Using Machine Learning to Improve Cylindrical Algebraic Decomposition
• Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
• Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
• Machine Learning for Mathematical Software
• Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases
• TheoryGuru: A Mathematica Package to apply Quantifier Elimination
• A "Piano Movers" Problem Reformulated

Cited by in corpus (3)

• New heuristic to choose a cylindrical algebraic decomposition variable ordering motivated by complexity analysis
• A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs
• Lessons on Datasets and Paradigms in Machine Learning for Symbolic Computation: A Case Study on CAD