A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs

• URL: http://arxiv.org/abs/2005.11251v1
• Date: Fri, 22 May 2020 16:00:04 GMT
• Title: A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs
• Authors: Dorian Florescu and Matthew England
• Abstract summary: We refer to choices which have no effect on the mathematical correctness of the software, but do impact its performance. In the past we experimented with one such choice: the variable ordering to use when building a Cylindrical Algebraic Decomposition (CAD)
• Score: 1.2891210250935146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We are interested in the application of Machine Learning (ML) technology to improve mathematical software. It may seem that the probabilistic nature of ML tools would invalidate the exact results prized by such software, however, the algorithms which underpin the software often come with a range of choices which are good candidates for ML application. We refer to choices which have no effect on the mathematical correctness of the software, but do impact its performance. In the past we experimented with one such choice: the variable ordering to use when building a Cylindrical Algebraic Decomposition (CAD). We used the Python library Scikit-Learn (sklearn) to experiment with different ML models, and developed new techniques for feature generation and hyper-parameter selection. These techniques could easily be adapted for making decisions other than our immediate application of CAD variable ordering. Hence in this paper we present a software pipeline to use sklearn to pick the variable ordering for an algorithm that acts on a polynomial system. The code described is freely available online.

Related papers

• Gradients of Functions of Large Matrices [18.361820028457718]
  We show how to differentiate workhorses of numerical linear algebra efficiently. We derive previously unknown adjoint systems for Lanczos and Arnoldi iterations, implement them in JAX, and show that the resulting code can compete with Diffrax. All this is achieved without any problem-specific code.
  arXiv  Detail & Related papers  (2024-05-27T15:39:45Z)
• Lessons on Datasets and Paradigms in Machine Learning for Symbolic Computation: A Case Study on CAD [0.0]
  This study reports lessons on the importance of analysing datasets prior to machine learning. We present results for a particular case study, the selection of variable ordering for cylindrical algebraic decomposition. We introduce an augmentation technique for systems that allows us to balance and further augment the dataset.
  arXiv  Detail & Related papers  (2024-01-24T10:12:43Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Explainable AI Insights for Symbolic Computation: A case study on selecting the variable ordering for cylindrical algebraic decomposition [0.0]
  This paper explores whether using explainable AI (XAI) techniques on such machine learning models can offer new insight for symbolic computation. We present a case study on the use of ML to select the variable ordering for cylindrical algebraic decomposition.
  arXiv  Detail & Related papers  (2023-04-24T15:05:04Z)
• Fault-Aware Neural Code Rankers [64.41888054066861]
  We propose fault-aware neural code rankers that can predict the correctness of a sampled program without executing it. Our fault-aware rankers can significantly increase the pass@1 accuracy of various code generation models.
  arXiv  Detail & Related papers  (2022-06-04T22:01:05Z)
• OMLT: Optimization & Machine Learning Toolkit [54.58348769621782]
  The optimization and machine learning toolkit (OMLT) is an open-source software package incorporating neural network and gradient-boosted tree surrogate models. We discuss the advances in optimization technology that made OMLT possible and show how OMLT seamlessly integrates with the algebraic modeling language Pyomo.
  arXiv  Detail & Related papers  (2022-02-04T22:23:45Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  We use a pruning machine learning as a pre-processing step followed by an exact Programming approach to sparsify the travelling salesman problem. Our learning approach requires very little training data and is amenable to mathematical analysis.
  arXiv  Detail & Related papers  (2021-04-19T14:35:14Z)
• Accelerating GMRES with Deep Learning in Real-Time [0.0]
  We show a real-time machine learning algorithm that can be used to accelerate the time-to-solution for GMRES. Our framework is novel in that is integrates the deep learning algorithm in an in situ fashion.
  arXiv  Detail & Related papers  (2021-03-19T18:21:38Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Multi-layer Optimizations for End-to-End Data Analytics [71.05611866288196]
  We introduce Iterative Functional Aggregate Queries (IFAQ), a framework that realizes an alternative approach. IFAQ treats the feature extraction query and the learning task as one program given in the IFAQ's domain-specific language. We show that a Scala implementation of IFAQ can outperform mlpack, Scikit, and specialization by several orders of magnitude for linear regression and regression tree models over several relational datasets.
  arXiv  Detail & Related papers  (2020-01-10T16:14:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.