Introduction
Federated Learning (FL) has revolutionized the way we train machine learning models by allowing collaborative learning without the need to share raw, sensitive data. While much of the existing research focuses on deep neural networks, Decision Trees (DTs) remain a staple for tabular data due to their interpretability and efficiency. However, implementing DTs in a federated setting presents unique challenges, particularly regarding privacy and model personalization. FedGA-Tree introduces a novel framework that leverages Genetic Algorithms (GA) to evolve tree structures, offering a robust alternative to traditional greedy, noise-heavy methods.
The Challenges of Federated Decision Trees
Standard tree-building algorithms like CART or ID3 are inherently problematic for FL for two primary reasons:
- Privacy Leaks: These algorithms place actual data values into decision nodes. Sharing these nodes directly reveals sensitive information about the underlying local datasets.
- The "DP" Tax: Current solutions often rely on Differential Privacy (DP) to mask these values. However, DP adds noise at every split. This noise compounds as the tree grows, forcing models to be shallow and inaccurate, often limiting their utility to categorical data.
Furthermore, most FL methods attempt to build a single "global" tree. In heterogeneous environments where clients have different data distributions, a one-size-fits-all model often performs poorly for a significant portion of the participants.
The FedGA-Tree Approach
FedGA-Tree shifts the paradigm from traditional greedy "top-down" construction to an evolutionary approach. Instead of calculating splits based on raw data statistics, the central server maintains a population of "search trees." These are essentially tree skeletons that define feature splits but leave specific thresholds to be determined locally.
Genetic Algorithm Workflow
The process follows a standard GA cycle: generating an initial population, evaluating fitness, selecting candidates for reproduction, and applying crossover and mutation. Trees are encoded as fixed-length integer strings using pre-order depth-first traversal, allowing for efficient genetic operations like swapping branches or flipping nodes.
Local Personalization and Privacy
During each round, the server distributes these skeletons to clients. Each client fits the skeleton to their local data to find optimal thresholds and leaf labels. This means two clients using the same global structure can have different split points, tailoring the model to their specific data nuances. Crucially, clients only return their "fitness scores" (e.g., F1 score or MSE) and a noisy version of their sample size. No raw data or specific thresholds ever leave the client's device, significantly enhancing privacy without the heavy accuracy tax of split-level DP.
Experimental Evaluation
The researchers evaluated FedGA-Tree across a massive suite of 28 datasets (14 for classification and 14 for regression). This included standard benchmarks like adult and creditcard, as well as curated tabular sets designed to test tree-based models against deep learning. The framework was compared against local training and the industry-standard IBM benchmark, which utilizes traditional DP-based federated trees.
Key Results and Discussion
FedGA-Tree demonstrated significant improvements over existing methodologies in both accuracy and client satisfaction.
- Superior Accuracy: In classification tasks, FedGA-Tree achieved an average 5.58% improvement in F1 score over local models. In contrast, the IBM benchmark actually performed 2.58% worse than local models on average, highlighting the detrimental effect of excessive DP noise.
- Widespread Client Benefit: On average, 75% of clients saw better performance by joining the federation than by training alone. This suggests that the global search for tree structures effectively captures patterns that local datasets are too small to identify.
- Robustness to Participation: The method maintained high performance even with only 10% client participation. Unlike DP methods where noise doesn't "average out" with fewer clients, FedGA-Tree’s reliance on fitness scores makes it remarkably stable.
- Reduced Complexity: Interestingly, FedGA-Tree produced trees with fewer nodes than local trees, suggesting better generalization and a lower risk of overfitting.
Conclusion and Future Work
FedGA-Tree proves that evolutionary algorithms can overcome the privacy and accuracy trade-offs that have long plagued federated decision trees. By separating global structure from local thresholds, it achieves a high degree of personalization and robustness.
Future research will focus on addressing unbounded metrics in regression (like MSE) by moving toward bounded metrics like $R^2$ to prevent single-client outliers from skewing the global population. Additionally, the authors plan to explore the framework's resilience against active membership inference attacks and its performance in extremely non-IID data environments.
Summary updated