IH
I. Hosu
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
1 records found
1
AnyDTree: An Anytime Solver for Perfect Decision Trees
Finding progressively smaller trees with 100% training accuracy
Finding the smallest decision tree that perfectly fits the training data is NP-complete; yet, such trees remain attractive due to their interpretability and minimal footprint. Existing solutions occupy two extremes: heuristics like CART instantly produce trees but remain far from optimal, whereas exact solvers like Witty give no intermediate output. We introduce AnyDTree, an anytime algorithm that continuously maintains a 100% accurate tree and monotonically shrinks its size. It employs an expand-and-backtrack search that ensures complete solutions at every step, combined with aggressive pruning and caching mechanisms to eliminate redundant exploration. On 70 binary-classification variants of 35 UCI datasets, AnyDTree incurs no statistically significant overhead in finding the optimal size compared with Witty (log-rank p>0.1). On the 46 datasets with known optima, it demonstrates significantly improved anytime behaviour - measured by the confined primal integral - with a median score of 0.00034, outperforming both Witty (0.00059) and CART (0.20) (p<0.001). These results position AnyDTree as a practical middle ground between heuristic and exact solutions.
...
Finding the smallest decision tree that perfectly fits the training data is NP-complete; yet, such trees remain attractive due to their interpretability and minimal footprint. Existing solutions occupy two extremes: heuristics like CART instantly produce trees but remain far from optimal, whereas exact solvers like Witty give no intermediate output. We introduce AnyDTree, an anytime algorithm that continuously maintains a 100% accurate tree and monotonically shrinks its size. It employs an expand-and-backtrack search that ensures complete solutions at every step, combined with aggressive pruning and caching mechanisms to eliminate redundant exploration. On 70 binary-classification variants of 35 UCI datasets, AnyDTree incurs no statistically significant overhead in finding the optimal size compared with Witty (log-rank p>0.1). On the 46 datasets with known optima, it demonstrates significantly improved anytime behaviour - measured by the confined primal integral - with a median score of 0.00034, outperforming both Witty (0.00059) and CART (0.20) (p<0.001). These results position AnyDTree as a practical middle ground between heuristic and exact solutions.