Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces ternary decision trees, an extension of CART that incorporates an uncertainty zone around each split node, blending predictions from both child subtrees for instances within this zone. The width of the uncertainty zone, delta, is computed locally using five novel methods based on split quality, class overlap, and margin. Empirical evaluation on 72 OpenML datasets demonstrates that ternary trees with probabilistic routing significantly outperform standard CART, with the margin-based method achieving the best efficiency in terms of accuracy gain per unit of boundary-uncertain flagging rate.
Decision trees can now flag uncertain predictions near decision boundaries, boosting accuracy and enabling safer downstream applications.
Decision trees partition the feature space using hard binary thresholds, assigning identical confidence to instances far from a decision boundary and to those directly on it. We introduce ternary decision trees, which augment each split node with an uncertainty zone of half-width delta centered on the optimal threshold. Instances in this zone receive predictions formed by weighted blending of both child subtrees and are flagged as boundary-uncertain, signaling that downstream applications may treat these predictions differently. Crucially, delta is computed locally at each node from statistics already available during standard CART split finding, requiring no external noise specification. We propose and evaluate five delta-estimation methods: quality-plateau (plateau width of the split criterion curve), class-overlap (empirical class-distribution overlap), gain-ratio (split quality relative to split entropy), node-bootstrap (threshold variance under node-level resampling), and margin (SVM-inspired distance to the nearest cross-class training example). Evaluated across 72 OpenML-CC18 datasets with 5-fold cross-validation, all five methods with probabilistic routing significantly outperform standard CART on decided accuracy (Wilcoxon signed-rank, p < 0.001). The margin method achieves the best efficiency (0.104 accuracy gain per unit of boundary-uncertain flagging rate), wins on 42 of 72 datasets, and requires zero additional hyperparameters. Analysis on three Breiman synthetic benchmarks reveals that margin is self-calibrating on clean data while node-bootstrap and quality-plateau best track theoretical irreducible error. Experiments on four medical and financial datasets demonstrate practical value: on mammography, node-bootstrap achieves +0.71% decided accuracy by flagging 10.8% of screening cases as boundary-uncertain.