Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.06528 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915989696806912 |
|---|---|
| author | Kouarfate, Iro René Dion, Maxime MacKay, Anne Pigeon, Mathieu |
| author_facet | Kouarfate, Iro René Dion, Maxime MacKay, Anne Pigeon, Mathieu |
| contents | 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. For categorical predictors, this problem can be formulated as a combinatorial fractional optimization problem. This structure makes the exact optimization computationally challenging and leads to standard implementations that rely on greedy heuristics, which may result in suboptimal splits. In this work, we reformulate this fractional problem and apply Dinkelbach (1967) algorithm to convert it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. Using state-of-the-art QUBO solvers, we obtain QUBO-based regression trees with predictive performance comparable to standard CART while yielding higher-quality split solutions. These results highlight the potential of QUBO formulations for improving tree-based learning methods and open perspectives for future hybrid classical--quantum implementations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06528 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | QUBO-Based Calibration for Regression Trees Kouarfate, Iro René Dion, Maxime MacKay, Anne Pigeon, Mathieu Computation 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. For categorical predictors, this problem can be formulated as a combinatorial fractional optimization problem. This structure makes the exact optimization computationally challenging and leads to standard implementations that rely on greedy heuristics, which may result in suboptimal splits. In this work, we reformulate this fractional problem and apply Dinkelbach (1967) algorithm to convert it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. Using state-of-the-art QUBO solvers, we obtain QUBO-based regression trees with predictive performance comparable to standard CART while yielding higher-quality split solutions. These results highlight the potential of QUBO formulations for improving tree-based learning methods and open perspectives for future hybrid classical--quantum implementations. |
| title | QUBO-Based Calibration for Regression Trees |
| topic | Computation |
| url | https://arxiv.org/abs/2605.06528 |