Abstract
Survival analysis studies and predicts the time of death, or other singular unrepeated events, based on historical data, while the true time of death for some instances is unknown. Survival trees enable the discovery of complex nonlinear relations in a compact human comprehensible model, by recursively splitting the population and predicting a distinct survival distribution in each leaf node. We use dynamic programming to provide the first survival tree method with optimality guarantees, enabling the assessment of the optimality gap of heuristics. We improve the scalability of our method through a special algorithm for computing trees up to depth two. The experiments show that our method's run time even outperforms some heuristics for realistic cases while obtaining similar out-of-sample performance with the state-of-the-art.
Introduction
Survival analysis—predicting the time until an event like a medical recovery or a mechanical failure—is a cornerstone of high-stakes decision-making in medicine, insurance, and reliability engineering. While decision trees are favored for their interpretability, most existing survival trees rely on "greedy" heuristics that make the best local split at each step but often miss the global optimum.
Survival analysis is uniquely difficult due to censoring, where the exact time an event occurred is unknown for some subjects (e.g., a patient leaving a study before it concludes). Traditionally, researchers have used greedy heuristics like CTree or local search methods like OST. However, these methods lack global optimality guarantees, leaving an unknown "optimality gap" in model performance.
Methods: The SurTree Algorithm
Researchers from Delft University of Technology have introduced SurTree, the first algorithm to guarantee globally optimal survival trees for a given size. SurTree utilizes Dynamic Programming (DP) to treat tree-building as a series of independent subproblems, recursively partitioning the dataset and caching optimal subtrees to avoid redundant calculations.
The Loss Function and Leaf Model
To handle censored data, SurTree optimizes a likelihood-based loss function. It assumes a proportional hazards model within each leaf, where the survival curve is a scaled version of a baseline hazard estimated using the Nelson-Aalen estimator. The goal is to find the tree structure and leaf parameters that maximize the likelihood of the observed data.
The "Depth-Two" Speedup
To combat the exponential complexity of DP, the authors developed a specialized algorithm for trees of depth two. By precomputing "event sums" and "hazard sums" for all feature pairs, the algorithm evaluates potential splits almost instantly, resulting in a 45x average speedup compared to standard DP. This optimization makes the search for optimal trees feasible for realistic depths.
Empirical Results
SurTree was evaluated against 15 real-world datasets from the SurvSet repository, ranging from 2,000 to over 50,000 instances. The results demonstrate that a truly globally optimal approach can be both more accurate and, surprisingly, faster than existing local search methods.
Key Findings
- Predictive Accuracy: SurTree consistently outperformed CTree and performed similarly to or better than OST. As shown in the results table, SurTree achieved the most "wins" across both Harrell’s C-index (10 wins) and the Integrated Brier Score (9 wins).
- Efficiency: On real-world datasets for trees of depth three, SurTree was, on average, 100 times faster than OST.
- Optimality Gap: The study quantified the optimality gap for the first time, finding that SurTree’s training score was up to 34% better than greedy methods (CTree) and 4% better than local search (OST) in specific scenarios.
Conclusion
SurTree establishes a new benchmark for interpretable survival modeling by providing the first survival tree method with optimality guarantees. While currently optimized for shallow trees (depth 4 or 5), its efficiency and accuracy make it a powerful tool for high-stakes domains. Future work will explore incorporating more complex models, such as a full Cox proportional hazards model, within each leaf node to further enhance predictive power.
Paper Citation: Tim Huisman, Jacobus G. M. van der Linden, Emir Demirović. "Optimal Survival Trees: A Dynamic Programming Approach." Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI-24).
Summary updated