QUBO-Based Calibration for Regression Trees

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.