Optimal Sparse Survival Trees

Rui Zhang, Rui Xin, Margo I. Seltzer, Cynthia Rudin

Abstract

Interpretability is crucial for doctors, hospitals, pharmaceutical companies, and biotechnology corporations to analyze and make decisions for high-stakes problems that involve human health. Tree-based methods have been widely adopted for survival analysis due to their appealing interpretability and their ability to capture complex relationships. However, most existing methods to produce survival trees rely on heuristic (or greedy) algorithms, which risk producing sub-optimal models. We present a dynamic-programming-with-bounds approach that finds provably-optimal sparse survival tree models, frequently in only a few seconds.

Introduction

Survival analysis—predicting the time until an event occurs, such as a patient’s recovery or a machine’s failure—is a cornerstone of healthcare and engineering. A major challenge in this field is censored data, where we often only know that a subject survived at least until a certain time. While "black-box" machine learning models can handle this complexity, they lack the interpretability required for high-stakes decisions. Conversely, traditional interpretable models like decision trees usually rely on greedy algorithms. These algorithms make the "best" split at each step without considering the global tree structure, often leading to sub-optimal models that are either overly complex or insufficiently accurate.

Optimal Sparse Survival Trees (OSST) addresses this by providing the first practical algorithm to find provably optimal sparse survival trees using a dynamic programming framework. By moving beyond traditional greedy splitting heuristics, OSST produces models that are both more accurate and more interpretable than existing methods.

Methodology

OSST utilizes a dynamic-programming-with-bounds approach to explore the space of possible trees. It minimizes a objective function that combines the Integrated Brier Score (IBS)—a standard survival loss—with a penalty for the number of leaves to ensure sparsity.

Key technical innovations include:

  • Hierarchical Lower Bounds: Mathematical proofs that allow the algorithm to prune large sections of the search space that cannot contain the optimal tree.
  • Equivalent Points: A technique to group data points with identical features, tightening lower bounds and accelerating computation.
  • Reference Model Guessing: The algorithm uses a "black-box" reference model (like a Random Forest) to estimate a baseline error. This helps prune the search space more aggressively, reducing training time by 40% to 95% while maintaining the guarantee of finding the global optimum.

Evaluation and Results

The researchers evaluated OSST on 17 datasets, including 11 real-world survival datasets (e.g., aids, churn, veterans) and 6 synthetic datasets.

OSST consistently finds a superior frontier of models compared to greedy methods like RPART and CTree on the credit dataset.

Key Findings

  • Global Search Superiority: OSST consistently finds a "frontier" of models that are both simpler (fewer leaves) and more accurate than those produced by RPART or CTree. By optimizing the entire tree structure simultaneously, it identifies clever splits that greedy algorithms overlook.
  • Efficiency and Scalability: Despite the theoretical complexity, OSST found optimal trees for most public datasets in seconds. For instance, it solved the aids dataset in ~2.28 seconds. On the household dataset (over 2 million samples), OSST demonstrated better scalability than existing libraries like SkSurv.
  • Holistic Quality: While OSST specifically optimizes for IBS, the resulting trees also performed better on other metrics, such as Harrell’s C-index and AUC, demonstrating robust generalization.
OSST demonstrates superior performance on Harrell's C-index, showing that optimizing for IBS also yields high-quality models across other survival metrics.

Discussion and Future Work

OSST proves that greedy algorithms are not "good enough" for survival analysis when interpretability and optimality are required. The use of black-box models as "teachers" to speed up the search for optimal interpretable models is a particularly powerful paradigm.

However, there remains an inherent trade-off: extremely sparse trees may still struggle to match the raw predictive power of massive black-box ensembles on highly complex data. Future work may involve extending the OSST framework to directly optimize other survival metrics, such as the C-index, and developing more systematic ways to generate reference models for any survival task.

Summary updated

Abstract

Interpretability is crucial for doctors, hospitals, pharmaceutical companies and biotechnology corporations to analyze and make decisions for high stakes problems that involve human health. Tree-based methods have been widely adopted for survival analysis due to their appealing interpretablility and their ability to capture complex relationships. However, most existing methods to produce survival trees rely on heuristic (or greedy) algorithms, which risk producing sub-optimal models. We present a dynamic-programming-with-bounds approach that finds provably-optimal sparse survival tree models, frequently in only a few seconds.
BibTeX
@inproceedings{zhang2024optimal,
  author = {Rui Zhang and Rui Xin and Margo I. Seltzer and Cynthia Rudin},
  title = {{Optimal Sparse Survival Trees}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=I1A8hAWFWL},
}
Figure