QUBO-Based Calibration for Regression Trees

Abstract

Tree-based regression models are widely used in supervised learning, with the Classification and Regression Tree (CART) algorithm serving as a standard reference. CART construction involves solving a sequence of split-selection optimization problems, which are fractional and become combinatorial in nature for categorical predictors. Although, in the single-target regression setting with squared-error loss, this problem admits an efficient exact solution, as shown in Fisher (1958), Breiman et al. (1984), we adopt a QUBO framework to address the categorical split-selection problem. This choice is motivated by the general-purpose nature of QUBO formulations, which provide a unified optimization framework that naturally extends to settings where classical splitting strategies rely on heuristics and may yield suboptimal solutions. We propose a QUBO formulation of the categorical split-selection problem in single-target least-squares regression. The fractional nature of the objective function is handled using Dinkelbach's algorithm (Dinkelbach, 1967) together with a class-based encoding. This leads to a compact sequence of QUBO problems whose size depends only on the number of categories, rather than on the sample size. Using state-of-the-art QUBO solvers, we construct QUBO-based regression trees with predictive performance comparable to standard CART, while yielding higher-quality categorical splits. Overall, this work highlights the relevance of QUBO formulations as a flexible optimization framework for tree-based learning and opens perspectives for future hybrid classical-quantum optimization approaches within CART extensions.

34 pages