Anytime Minimum-Size Perfect Decision Trees

Abstract

This thesis addresses the Minimum-Size Decision Tree (MSDT) problem, which seeks the smallest decision tree that perfectly classifies all training data. Smaller perfect decision trees may generalize better to unseen data, are easier to interpret and validate, require less memory, and have faster inference. These properties are particularly valuable in high-stakes domains such as healthcare (Amann et al. 2020), where decisions must be understandable and auditable, and in resource-constrained systems such as microcontrollers, where memory and computation power are limited. Existing methods for continuous features mainly optimize classification accuracy under a depth constraint, while specialized MSDT methods do not exploit branch-and-bound techniques developed for continuous features and may fail to return a valid perfect tree when the search is interrupted. To address this gap, we extend a branch-and-bound framework for continuous features to the MSDT setting by redefining the objective and adding several problem-specific lower bounds alongside a randomized CART-based upper bound. Additionally, we propose a memory-aware hybrid search strategy to balance efficiency and resource usage. Experimental results show that the proposed approach provides useful anytime performance by maintaining a valid perfect decision tree throughout the search and progressively improving its size as the search continues. Although it proves optimality on fewer difficult instances than a state-of-the-art baseline, it can still return increasingly strong feasible solutions when the search is interrupted. The experiments further show that the pair-size lower bound is the most effective practical bound, while the memory-aware hybrid search strategy reduces the risk of memory exhaustion during search.