🤖 machine learning

Evolving Features vs Evolving Entire Trees with GP for Interpretable Survival Analysis

This paper proposes and evaluates genetic programming approaches that either evolve interpretable feature sets or jointly optimize survival tree structures and split logic, demonstrating that full joint evolution yields the most promising results for creating accurate, shallow, and inherently inspectable survival models.

Original authors: Thalea Schlender, Peter A. N. Bosman, Tanja Alderliesten

Published 2026-05-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Thalea Schlender, Peter A. N. Bosman, Tanja Alderliesten

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a doctor trying to predict how long a patient might live after a diagnosis. This is called Survival Analysis. The tricky part is that you often don't know the exact answer for everyone; some patients drop out of the study or are still alive when the study ends. This is called "censored" data.

To help doctors make decisions, we need models that are not only accurate but also easy to understand (interpretable). If a model is a "black box" (like a complex neural network), doctors can't trust it because they can't see why it made a prediction.

This paper introduces a new way to build these prediction models using Survival Trees. Think of a Survival Tree as a flowchart or a "Choose Your Own Adventure" book for patients. You start at the top, ask a question (e.g., "Is the patient's age over 60?"), and follow the path down to a leaf, which gives a prediction.

The Problem: Simple Trees vs. Complex Reality

The authors explain that simple, shallow trees are easy to read, but they often fail to capture complex medical realities. To get a complex pattern right, a tree usually has to grow very tall and bushy, which makes it hard to follow.

Traditionally, these trees are built using a "greedy" approach. Imagine a hiker trying to find the highest peak by always taking the steepest step immediately in front of them. They might get stuck on a small hill because they never looked ahead to see a bigger mountain nearby. Similarly, greedy trees make local decisions that might miss the global best solution.

The Solution: Evolving Better Features

The paper proposes using Genetic Programming (GP) to solve this. Think of GP as a digital evolution lab. Instead of just feeding the tree raw data (like "Age" or "Tumor Size"), the computer "evolves" new, smarter features by mixing and matching the raw data in creative ways.

For example, instead of just looking at "Weight" and "Height" separately, the computer might evolve a new feature: "Weight divided by Height squared" (BMI). It does this by trying millions of combinations, keeping the ones that work best, and discarding the rest, just like natural selection.

The paper tests three main strategies:

The Greedy Tree with Evolved Features: The computer evolves smart features first, then builds a standard "greedy" tree using those features.
- Analogy: Giving the hiker a better map with pre-marked trails, so even if they take the steepest step, they are on the right path.
The Optimal Tree with Evolved Features: The computer evolves features and then uses a complex math method to find the perfect tree structure for those features.
- Analogy: Giving the hiker the map and then using a supercomputer to calculate the absolute best route to the peak.
The Evolutionary Tree (The New Star): The computer evolves both the smart features and the tree structure at the same time.
- Analogy: Instead of just giving the hiker a map, you evolve the hiker's brain and the map simultaneously. The hiker learns to ask the right questions, and the map is drawn to fit those questions perfectly.

The Experiments

The authors tested these ideas on two things:

A Synthetic Puzzle (The XOR Problem): They created a fake medical problem where the answer only makes sense if you combine two variables in a specific, non-linear way.
- Result: The standard greedy tree failed miserably because it couldn't see the combination. Only the methods that could evolve complex, binary "yes/no" features could solve it.
Real Medical Data: They used two real-world breast cancer datasets (GBSG and METABRIC).
- Result: The new methods, especially the Evolutionary Tree, performed just as well as the most advanced, complex "black box" AI models (like DeepSurv) but remained easy for doctors to read.

Key Takeaways

Shallow is Good: You can keep the tree small and easy to understand if you give it smart, evolved features to work with.
Joint Evolution is Best: The most promising approach is the one that evolves the features and the tree structure together. It's like training a team where the players and the playbook evolve together, rather than training the players first and then writing the playbook.
No "Black Box": These models achieve high accuracy without needing the strict mathematical assumptions that limit other popular medical models. They are transparent, meaning a doctor can look at the tree and say, "Ah, I see why this patient is in this group."

In short, the paper shows that by letting computers "evolve" smarter ways to look at data, we can build medical prediction tools that are both powerful enough to be accurate and simple enough for doctors to trust and use.

Technical Summary: Evolving Features vs. Evolving Entire Trees with GP for Interpretable Survival Analysis

1. Problem Statement

Survival analysis aims to predict the time until a specific event occurs, a task critical in medical domains. A major challenge is handling censored data (patients who do not experience the event during the study) while balancing predictive accuracy with interpretability.

While survival trees offer inherent interpretability by recursively partitioning patient cohorts, they face two primary limitations:

Complexity vs. Interpretability Trade-off: To capture complex, non-linear relationships and interactions between covariates, survival trees often need to grow deep, which compromises their interpretability and increases overfitting risks.
Greedy Induction Limitations: Classical survival tree induction uses greedy, top-down approaches that select the locally optimal split at each node. This often overlooks globally optimal split combinations, particularly when the true data structure requires specific non-linear feature combinations (e.g., XOR-like interactions) that cannot be captured by simple univariate splits.

Existing deep learning approaches (e.g., DeepSurv) achieve high accuracy but lack interpretability and often rely on the restrictive Cox proportional hazards assumption. Conversely, symbolic regression methods like CoxKAN approximate neural networks but remain bound by the proportional hazards assumption and do not optimize for survival prediction directly.

2. Methodology

The authors propose and compare strategies to enhance shallow survival trees using Genetic Programming (GP), specifically the multi-objective GP-GOMEA algorithm. The work extends the PISA (Pipeline for Interpretable Survival Analysis) framework.

2.1 Core Approaches

The study investigates three distinct survival tree learning strategies, all evaluated under a multi-objective optimization framework (balancing Integrated Brier Score [IBS] and model complexity):

Greedy Survival Tree (Greedy ST) with GP-Constructed Features (GFC):
- GP is used to evolve a set of non-linear features (symbolic expressions).
- These features are fed into a standard greedy tree induction algorithm.
- Numeric vs. Binary: The system tests evolving numeric features (where the tree locally finds thresholds) and binary features (where the GP expression itself represents a split, e.g., $x < t$ ).
- Note: In this setup, feature construction and tree induction are separate stages.
Optimal Survival Tree (Optimal ST) with GFC:
- Uses dynamic programming to find provably optimal tree structures given a set of binary input features.
- Features evolved by GP are constrained to be binary (incorporating both the covariate transformation and the threshold).
- Split selection maximizes partial likelihood based on the Cox Proportional Hazards model.
Evolutionary Survival Tree (Evolutionary ST):
- A novel approach where the entire survival tree structure and the split logic are jointly evolved within a single GP population.
- Representation: Uses a multi-tree representation where each GP-tree corresponds to a specific node in the survival tree (assigned breadth-first).
- Constraints: Each GP-tree is constrained to output a binary decision (capturing the feature and threshold simultaneously).
- Enhancements: The authors introduce GP-tree swapping (varying the order of trees in the genotype) and a unique patient stratification initialization strategy to ensure diversity in the initial population and avoid redundant individuals.

2.2 Fitness and Evaluation

Objectives: Minimize the Integrated Brier Score (IBS) and minimize the complexity (size) of the features/tree.
Complexity Calculation:
- For GFC approaches: The sum of the sizes of unique features used. Reused features are counted once.
- For Evolutionary ST: Every reuse of a feature is counted individually, as the tree structure itself is part of the optimization.
Datasets:
- Synthetic XOR Problem: Designed to test the ability to capture non-linear interactions where axis-parallel splits fail.
- GBSG: Node-positive breast cancer survival data (internal and external validation).
- METABRIC: Breast cancer molecular taxonomy data (internal and external validation).
Baselines: Compared against DeepSurv, CoxKAN, Random Survival Forest (RSF), and standard Kaplan-Meier estimators.

3. Key Findings

3.1 Synthetic Data (XOR Problem)

Standard greedy trees with original features failed to model the ground truth.
Greedy trees with pre-provided correct numeric features still failed because the greedy algorithm selected suboptimal root splits based on immediate gain.
Success Condition: The ground truth was only recovered when the greedy tree was provided with the correct binary indicators (the result of the non-linear interaction) or when using Optimal ST or Evolutionary ST.
This demonstrates that for complex interactions, either the features must be pre-constructed to include the interaction logic, or the tree induction must be non-greedy.

3.2 Clinical Benchmarks (GBSG & METABRIC)

Performance: Survival trees using evolved features (GFC) significantly outperformed baselines using original features.
- Depth 3 Trees: GFC-enhanced Greedy STs and Evolutionary STs achieved C-index scores comparable to state-of-the-art DeepSurv and CoxKAN, without relying on the proportional hazards assumption.
- Optimal ST: Performed well but was computationally more expensive than the Evolutionary ST in some configurations.
Feature Construction:
- Surprisingly, for clinical data, GFC Greedy STs using only numeric operators performed on par with those using binary operators. This suggests that for these specific datasets, complex binary interactions were not strictly necessary for high performance, unlike the synthetic XOR case.
- Numeric features allowed the greedy algorithm to locally search for optimal thresholds, providing more expressive power than forcing binary splits in the GP stage.
Evolutionary ST Advantages:
- Computational Efficiency: The Evolutionary ST was the fastest to train (45 minutes for depth 3 on one core) compared to GFC-Greedy (19 hours) because it avoids the exogenous tree-building procedure.
- Global Optimization: It successfully induced locally sub-optimal splits that contributed to a globally optimal tree structure, a capability lacking in greedy approaches.
- Interpretability: It produced multiple shallow, inspectable trees with good performance.

4. Contributions and Significance

The paper claims the following contributions and significance:

Validation of Multi-Objective Feature Construction: The study demonstrates that multi-objective feature construction is the key to making shallow survival trees powerful. It allows for the generation of a Pareto front of models, giving clinicians the choice between complexity and accuracy.
Novel Evolutionary Survival Tree: The introduction of the Evolutionary ST, which jointly optimizes tree structure and split logic, is presented as the approach with the "most promise." It combines the benefits of non-greedy optimization with the interpretability of shallow trees.
Competitive Performance without Proportional Hazards: The proposed methods achieve predictive performance on par with deep learning baselines (DeepSurv, CoxKAN) on real-world clinical datasets, but without the restrictive proportional hazards assumption and with full model transparency.
Practical Interpretability: By keeping trees shallow (depth 2 or 3) and using symbolic features, the resulting models are "inherently inspectable," allowing clinicians to trace predictions back to specific patient characteristics and risk factors.

5. Limitations and Future Directions

The authors modestly note current limitations:

Binary Feature Constraint: The Evolutionary ST currently requires evolving binary features (covariate + threshold combined). The authors suggest that a modular representation allowing the reuse of numerical features with optimized thresholds could offer more flexibility without increasing search space complexity.
Resource Allocation: The study used uniform hyperparameters (population size, generations) across methods. Since the Evolutionary ST solves a more complex problem, future work should investigate whether allocating more computational resources to it would further improve performance.

In conclusion, the paper argues that while feature construction improves greedy trees, the joint evolution of the entire tree structure offers the highest potential for creating accurate, interpretable, and shallow survival models.