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

Research output: Chapter in Book/Report/Conference proceedingChapter

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.
Original languageEnglish
Title of host publicationMathematical Aspects of Computer and Information Sciences 2019
Subtitle of host publicationProc. MACIS 2019
PublisherSpringer International Publishing
Number of pages16
Publication statusAccepted/In press - 12 Nov 2019
EventMathematical Aspects of Computer and Information Sciences 2019 - Istanbul, Turkey
Duration: 13 Nov 201915 Nov 2019

Publication series

NameLecture Notes in Computer Science

Conference

ConferenceMathematical Aspects of Computer and Information Sciences 2019
Abbreviated titleMACIS 2019
CountryTurkey
CityIstanbul
Period13/11/1915/11/19

Fingerprint

Classifiers
Polynomials
Algebra
Learning systems
Experiments
Decomposition

Keywords

  • Machine Learning
  • cross-validation
  • Computer Algebra
  • Symbolic Computation
  • Cylindrical Algebraic Decomposition

Cite this

Florescu, D., & England, M. (Accepted/In press). Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness. In Mathematical Aspects of Computer and Information Sciences 2019: Proc. MACIS 2019 (Lecture Notes in Computer Science). Springer International Publishing.

Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness. / Florescu, Dorian; England, Matthew.

Mathematical Aspects of Computer and Information Sciences 2019: Proc. MACIS 2019. Springer International Publishing, 2019. (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceedingChapter

Florescu, D & England, M 2019, Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness. in Mathematical Aspects of Computer and Information Sciences 2019: Proc. MACIS 2019. Lecture Notes in Computer Science, Springer International Publishing, Mathematical Aspects of Computer and Information Sciences 2019, Istanbul, Turkey, 13/11/19.
Florescu D, England M. Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness. In Mathematical Aspects of Computer and Information Sciences 2019: Proc. MACIS 2019. Springer International Publishing. 2019. (Lecture Notes in Computer Science).
Florescu, Dorian ; England, Matthew. / Improved cross-validation for classifiers that make algorithmic choices to minimise runtime without compromising output correctness. Mathematical Aspects of Computer and Information Sciences 2019: Proc. MACIS 2019. Springer International Publishing, 2019. (Lecture Notes in Computer Science).
@inbook{50474d15ebbf4122a7cd630a9892e474,
title = "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.",
keywords = "Machine Learning, cross-validation, Computer Algebra, Symbolic Computation, Cylindrical Algebraic Decomposition",
author = "Dorian Florescu and Matthew England",
year = "2019",
month = "11",
day = "12",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "Springer International Publishing",
booktitle = "Mathematical Aspects of Computer and Information Sciences 2019",

}

TY - CHAP

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

AU - Florescu, Dorian

AU - England, Matthew

PY - 2019/11/12

Y1 - 2019/11/12

N2 - 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.

AB - 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.

KW - Machine Learning

KW - cross-validation

KW - Computer Algebra

KW - Symbolic Computation

KW - Cylindrical Algebraic Decomposition

M3 - Chapter

T3 - Lecture Notes in Computer Science

BT - Mathematical Aspects of Computer and Information Sciences 2019

PB - Springer International Publishing

ER -