A quantum representation of decision trees, paired with a post pruning method built on quantum random walks. Same classifications as classical approaches, with significant memory gains and faster traversal.
Quantum Post Pruning to Combat Overfitting in Classical Decision Tree Classifiers
Abstract
Decision trees are popular models for making decisions in various domains, and there are numerous algorithms for building such trees. Overfitting tends to worsen the performance of these models, so techniques have been developed to post prune decision trees to mitigate this issue. This research focuses on incorporating quantum computing into the post pruning process to improve speed and performance by the use of quantum supremacy, a term referring to the ability of certain quantum algorithms to outperform any classical algorithm. A quantum representation of a decision tree is proposed and shown to work on a classification task, and a post pruning method using quantum random walks is put forward and shown to work with classical random walks. Finally, it is suggested how readers can build on this work in combination with existing work to further explore quantum post pruning.
Experiments looking at the limitations and advantages of such approaches have been performed, notably comparing a quantum Markov chains decision process against synthetic datasets and faster tree traversal to identify post pruning opportunities in this representation. The results showed comparable classifications to classical computing approaches, but highlighted significant memory gains and speed opportunities in attempting post pruning operations.