Des-q: a quantum algorithm to provably speedup retraining of decision trees

Abstract

Decision trees are widely adopted machine learning models due to their simplicity and explainability. However, as training data size grows, standard methods become increasingly slow, scaling polynomially with the number of training examples. In this work, we introduce Des-q, a novel quantum algorithm to construct and retrain decision trees for regression and binary classification tasks. Assuming the data stream produces small, periodic increments of new training examples, Des-q significantly reduces the tree retraining time. Des-q achieves a logarithmic complexity in the combined total number of old and new examples, even accounting for the time needed to load the new samples into quantum-accessible memory. Our approach to grow the tree from any given node involves performing piecewise linear splits to generate multiple hyperplanes, thus partitioning the input feature space into distinct regions. To determine the suitable anchor points for these splits, we develop an efficient quantum-supervised clustering method, building upon the q-means algorithm introduced by Kerenidis et al. We benchmark the simulated version of Des-q against the state-of-the-art classical methods on multiple data sets and observe that our algorithm exhibits similar performance to the state-of-the-art decision trees while significantly speeding up the periodic tree retraining.

44 pager, 5 figures, 4 tables

References in corpus (21)

• Scikit-learn: Machine Learning in Python
• Quantum algorithm for solving linear systems of equations
• Quantum fingerprinting
• Quantum random access memory
• Quantum Counting
• A quantum-inspired classical algorithm for recommendation systems
• Iterative Quantum Amplitude Estimation
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum Approximate Counting, Simplified
• q-means: A quantum algorithm for unsupervised machine learning
• Practical Quantum Metrology
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Low depth algorithms for quantum amplitude estimation
• Quantum classification of the MNIST dataset with Slow Feature Analysis
• Representation of binary classification trees with binary features by quantum circuits
• The Quantum Version Of Classification Decision Tree Constructing Algorithm C5.0
• Quantum Speedup Based on Classical Decision Trees
• Communication-efficient Quantum Algorithm for Distributed Machine Learning
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• A Quantum Approximation Scheme for k-Means
• Do you know what q-means?