Optimal Survival Trees: A Dynamic Programming Approach
This provides a more reliable and efficient method for survival analysis, enabling assessment of heuristic optimality gaps, though it is incremental in improving scalability for depth-two trees.
The paper tackles the problem of building survival trees with optimality guarantees by introducing a dynamic programming approach, resulting in a method that achieves similar out-of-sample performance to state-of-the-art heuristics while improving run time in realistic cases.
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.