Optimal Survival Trees: A Dynamic Programming Approach

Survival analysis studies and predicts the time of death, or other singularunrepeated events, based on historical data, while the true time of death forsome instances is unknown. Survival trees enable the discovery of complexnonlinear relations in a compact human comprehensible model, by recursivelysplitting the population and predicting a distinct survival distribution ineach leaf node. We use dynamic programming to provide the first survival treemethod with optimality guarantees, enabling the assessment of the optimalitygap of heuristics. We improve the scalability of our method through a specialalgorithm for computing trees up to depth two. The experiments show that ourmethod's run time even outperforms some heuristics for realistic cases whileobtaining similar out-of-sample performance with the state-of-the-art.