Research map / Learning theory and algorithms / Prediction and decision losses

Beyond the ROC Curve: Classification Trees Using Cost-Optimal Curves, with Application to Imbalanced Datasets

ICML 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Tree ensemble optimization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes cost-optimal curves (COC) for classification trees, showing FN-minimization under an FP-rate constraint equals a weighted 0/1 loss, and optimizes it over oblique/axis-aligned trees with an extended TAO algorithm that decreases the loss monotonically.

Problem

Binary classification with imbalanced classes or asymmetric misclassification costs, where ROC-based trees and surrogate-loss or resampling approaches do not directly optimize the true-positive rate at a given false-positive rate.

Approach

Define the cost-optimal curve as the set of optimal-accuracy classifiers for each FP level, prove it equals a penalized weighted 0/1 loss, and extend Tree Alternating Optimization (TAO) to minimize this weighted 0/1 loss over oblique trees with monotonic decrease, warm-starting along a path of costs.

Key results

• COC (oblique trees trained with TAO) dominates CART, C5.0, and OC1 TP/FP-rate curves across the imbalanced binary benchmarks, with large margins on MNIST and Epsilon.
• On the multiclass Covertype dataset, TAO reaches 7.84 normalized cost-based test error versus 9.68 for C5.0 and 12.01 for CART, using fewer leaves (4850 vs 9300 and 8327).
• On RCV1, TAO reaches 57.15 error versus 62.91 for CART and 69.14 for C5.0, with 867 leaves vs 708 and 1531 respectively.

Measured effects reported in the paper

Surprising findings

• Optimizing a surrogate loss such as cross-entropy (logistic regression) yields TP/FP curves consistently inferior to the optimal weighted 0/1 curve, and the ROC curve from logistic regression roughly matches the weighted cross-entropy curve.
• Exact optimal COC is not required; a single ROC curve from one tree can only prune and relabel leaves, so tree ROC curves are severely limited.

Limitations

• The COC from TAO is only a local optimum approximation of an NP-hard weighted 0/1 problem, not the exact ideal curve.
• Training is more computationally costly than greedy CART/C5.0 and the exact optimal-tree baseline (Lin et al., 2020) did not finish within 2 hours on the smallest dataset.
• Experiments focus on single trees; extension to tree ensembles is left to future work.

Experimental setup

Datasets: MNIST (synthetic imbalanced labels) sensit company bankruptcy connect4 Telco churn Epsilon Email spam ULB Credit Card Fraud Covertype RCV1

Benchmarks: MNIST synthetic sensit company bankruptcy connect4 Telco churn Epsilon Email spam ULB Credit Card Fraud Covertype RCV1

Metrics: TP-rate vs FP-rate curves normalized cost-based 0/1 test error training time

Baselines: CART with class costs C5.0 with class costs OC1 with over/undersampling ROC of logistic regression weighted cross-entropy logistic regression

Builds on: Tree Alternating Optimization (TAO) LIBLINEAR CART C5.0

Closest papers by meaning

• Alternating optimization of decision trees, with application to learning sparse oblique trees (NeurIPS 2018 · similarity 0.86)
• Optimal Binary Classification Beyond Accuracy (NeurIPS 2022 · similarity 0.84)
• The VOROS: Lifting ROC Curves to 3D to Summarize Unbalanced Classifier Performance (AAAI 2025 · similarity 0.83)
• Balancing the Scales: A Theoretical and Algorithmic Framework for Learning from Imbalanced Data (ICML 2025 · similarity 0.83)
• Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.82)
• Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound (AAAI 2025 · similarity 0.82)