PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Forest

Yang Liu, Yingting Liu, Zhijie Liu, Junbo Zhang, Chuishi Meng, Yu Zheng

arXiv:1905.10053v1cs.LGstat.ML

TL;DR

Real-world data are fragmented across organizations and constrained by privacy and regulatory requirements, limiting collaborative AI. The paper proposes Federated Forest, a privacy-preserving tree model and secure vertical federated system that trains across aligned samples without exchanging raw data. It reports non-federated accuracy, reduced prediction communication overhead, and practical scalability, while noting a security–efficiency trade-off for label protection.

  • Problem

    Data fragmentation, privacy concerns, and regulations make it difficult to integrate organizational data for collaborative AI.

  • Method

    Federated Forest uses privacy-preserving tree algorithms, encryption, trusted-server coordination, and distributed modeling for clients with aligned samples and different features.

  • Results

    Federated Forest achieves the same performance as a non-federated random forest for classification and regression.

  • Takeaways & Limitations

    The system supports practical and scalable cross-regional learning without exchanging raw data and reduces prediction communication overhead.

  • Takeaways & Limitations

    Protecting labels can trade security against computational efficiency, with encrypted regression labels making modeling extremely time consuming.

Abstract

from arXiv · show

Most real-world data are scattered across different companies or government organizations, and cannot be easily integrated under data privacy and related regulations such as the European Union's General Data Protection Regulation (GDPR) and China' Cyber Security Law. Such data islands situation and data privacy & security are two major challenges for applications of artificial intelligence. In this paper, we tackle these challenges and propose a privacy-preserving machine learning model, called Federated Forest, which is a lossless learning model of the traditional random forest method, i.e., achieving the same level of accuracy as the non-privacy-preserving approach. Based on it, we developed a secure cross-regional machine learning system that allows a learning process to be jointly trained over different regions' clients with the same user samples but different attribute sets, processing the data stored in each of them without exchanging their raw data. A novel prediction algorithm was also proposed which could largely reduce the communication overhead. Experiments on both real-world and UCI data sets demonstrate the performance of the Federated Forest is as accurate as the non-federated version. The efficiency and robustness of our proposed system had been verified. Overall, our model is practical, scalable and extensible for real-life tasks.

1 Introduction

AI depends on data that are fragmented across organizations and constrained by privacy and security requirements. Federated Forest is proposed to enable collaborative, privacy-preserving learning while retaining non-federated accuracy, efficiency, and practical scalability.

  • Motivation: Data islands and privacy regulations limit organizations’ ability to share data for AI applications.Companies treat data as important assets, while government data are highly secured and people are increasingly sensitive about privacy.
  • Motivation: Joint models could support applications including medical study, targeted marketing, urban anomaly detection, and risk management.Examples include banks collaborating with e-commerce companies and governments working with ride-hailing companies.
  • Research gap: Existing methods do not completely resolve the combined challenges of data islands, privacy, and security, motivating new federated approaches.The paper frames bridging real-world applications and data islands as an urgent problem.
  • Contribution: Federated Forest is a privacy-preserving tree-based machine learning model built for the data-sharing challenge.The authors also develop a secure cross-regional machine learning system based on it.
  • Contribution: Federated Forest protects privacy, preserves non-federated accuracy, improves efficiency, and supports practical, scalable classification and regression.Its design uses redesigned tree algorithms, encryption, a trusted third-party server, and limited information exchange.

2 Related Work

Related work establishes federated learning for privacy-preserving collaboration across distributed data and develops variants for vertical, multi-task, recommendation, and tree-based settings. Privacy protection commonly relies on differential privacy or homomorphic encryption, each with documented trade-offs.

  • Federated learning: Federated learning was introduced to train shared models when regulations make centralized use of distributed data difficult.Early systems keep data on user devices and aggregate locally calculated intermediate results.
  • Federated learning: Prior studies extended federated learning to recommendation, multi-task learning, AdaBoost, vertical aggregation, and benchmarking.Vertical settings align sample IDs while distributing unique features across providers.
  • Federated learning: Related work applied tree-boosting, lossless frameworks, and reinforcement learning to privacy-preserving federated settings.These approaches address different combinations of privacy, modeling, and collaboration requirements.
  • Data privacy protection: Differential privacy protects data by adding calibrated noise, but may weaken model performance.The approach generally does not substantially affect computational efficiency.
  • Data privacy protection: Homomorphic encryption supports arithmetic on encrypted data but is computationally expensive and does not directly support nonlinear functions.Prior work therefore used approximations such as Taylor expansion or least squares, with results reported as non-ideal in the authors’ practice.

3 Problem Formulation

The paper formulates vertical federated learning across aligned samples with disjoint feature spaces and encrypted labels. It specifies distributed tree storage and requires Federated Forest performance to remain comparable to a non-federated random forest.

  • 3.1 Data Distribution: The setting uses multiple regional domains whose data share samples but have different feature spaces.Each domain has its own feature set, and feature sets are pairwise disjoint.
  • 3.1 Data Distribution: All domains contain the same number of samples, with sample IDs aligned across domains.The overall data domain and feature space are formed from the union of regional domains and feature sets.
  • 3.1 Data Distribution: Feature names are encoded during modeling to protect privacy.The encoded feature representation is part of the stated data-distribution setting.
  • 3.1 Data Distribution: A master machine serves as the parameter server, while client machines hold regional data domains.Labels are provided by one client and copied to the master and clients in encrypted form.
  • 3.2 Problem Statement: The formal problem gives each client a regional domain and encrypted labels.The clients are indexed from 1 through M.
  • 3.2 Problem Statement: The learned forest stores a complete tree model on the master and a partial tree model on every client.This distributed representation is required for each tree in the forest.
  • 3.2 Problem Statement: The target performance measures, including accuracy, F1-score, and MSE, must be comparable to a non-federated random forest.The formulation treats this as a constraint on Federated Forest.

4 Methodology

Federated Forest builds privacy-preserving trees collaboratively across clients, with the master coordinating split selection while clients retain feature-specific information. Its distributed storage and prediction procedures support joint modeling without centralizing raw data and reduce prediction communication.

  • Federated Forest combines CART and bagging to support classification and regression in the vertical federated setting.
  • Bagging randomly selects features and samples, and the master privately notifies clients about their selected subsets during construction.
  • During tree construction, clients find local optimal splits, and the master selects the global best feature before coordinating the corresponding sample partition.
  • Each client stores a partial tree containing split information for its own features, while the master stores the complete tree model.
  • Clients predict locally through their partial trees, while the master intersects leaf sample sets to obtain complete-tree predictions.
  • The prediction method reduces communication from multiple rounds to one collective round for each tree or the entire forest.

5 Experimental Studies

Experiments across real-world and UCI datasets evaluated Federated Forest against federated and non-federated baselines for accuracy, efficiency, and robustness. Federated Forest matched non-federated random forest performance while maintaining efficient prediction as domains and test sizes increased.

  • Experimental Setup: Nine benchmark datasets tested classification, regression, accuracy, efficiency, and robustness against non-federated and federated baselines.The evaluation included one real-world target-marketing dataset and eight UCI datasets, with varied sample sizes and feature spaces.
  • Experimental Setup: Federated Forest jointly learned random forests across clients while keeping data local and storing the model partly at each client.The comparison included Federated Logistic/Linear Regression, Non-Federated Forest, and single-client Random Forest baselines.
  • Two-Party Scenarios: For most datasets, Federated Forest and Non-Federated Forest outperformed single-client random forests.The single-client methods used insufficient feature spaces, whereas Federated Forest processed each tree globally across regional domains.
  • Two-Party Scenarios: Federated Forest achieved the same performance as non-federated random forest for both classification and regression problems.The authors used 40 tests and Z-tests to assess whether outputs from the two approaches differed significantly; no null hypotheses were rejected.
  • Multi-Party Scenario: As domains increased, Federated Forest accuracy improved consistently, training time grew almost linearly, and prediction-time differences remained negligible.These multi-domain experiments used the Parkinson dataset and duplicated data tenfold for efficiency tests.
  • Prediction Efficiency: The proposed prediction method was highly efficient as maximum depth and test sample size increased.Its communication occurred once per tree, and execution time changed very slowly with test sample size, unlike the classical method's linear growth.

6 Conclusions

The paper concludes that Federated Forest protects privacy while matching non-federated model accuracy. Its supporting system enables joint training across clients without exchanging raw data and reduces prediction communication overhead.

  • Federated Forest is lossless in model accuracy while protecting data privacy.The model is presented as a privacy-preserving tree-based learning model.
  • The system jointly trains models across clients with identical samples but different attribute sets without exchanging raw data.Only limited intermediate values are exchanged between parties.
  • A novel prediction algorithm reduces communication overhead and improves prediction efficiency.
  • Experiments on real-world and UCI data sets found Federated Forest as accurate as a non-federated random forest.The evaluation covered classification and regression tasks.

Reproducibility

The implementation used Python-based machine-learning and privacy-related libraries on CentOS servers with four CPU cores. The data-set information is provided in Table 2.

  • The model was implemented with Python 3.6, Scikit-learn 0.20, Numpy 1.15.4, python-paillier 1.4.1, and mpi4py 3.0.0.
  • Experiments ran on servers with 4 CPU cores using Centos 7.0.
  • Table 2 provides information about all data sets used in the experiments.

Pseudo-code for FF-Regressor

The regression and classification versions differ mainly in how leaf-node results and final predictions are generated.

  • Regression and classification differ mainly in the generation of leaf-node results and final predictions.The differences occur in specified lines of Algorithms 5, 6, and 8.

Notations In Proof

The proof notation defines sample sets, paths, and the complete tree used to formalize the prediction method. It distinguishes locally stored tree paths from paths in the complete tree.

  • S denotes sample IDs, while S_l^i contains IDs reaching leaf l of tree T_i.S_l denotes the sample set reaching leaf l in the complete tree T.
  • H is the test-sample set, and h ∈ H denotes a single test sample.
  • W_i is the set of decision paths by which h reaches leaves of tree T_i.Because of distributed model storage, h may reach more than one leaf in T_i.
  • w* is the decision path for h in the complete tree T, where h reaches only one leaf.Therefore, leaf sample sets in T are disjoint.
  • The complete tree is defined as T = T_1 ∪ T_2 ∪ ··· ∪ T_M.
  • Detailed notation descriptions are provided in Table 3.

Proof of the Proposition 1

The proposition establishes that intersecting leaf sample sets from all client-side partial trees recovers the corresponding leaf set of the complete federated tree. The construction and prediction procedures preserve this correspondence while enabling distributed tree building and reduced prediction communication.

  • Proposition proof: The complete-tree leaf sample set is recovered by intersecting the client leaf sample sets, Sl = Sl_1 ∩ Sl_2 ∩ · · · ∩ Sl_M.The proof uses path containment and rules out a sample appearing simultaneously in incompatible complete-tree leaves.
  • Federated tree construction: Each client builds a partial tree from its local feature set, while the master coordinates encrypted split information and combines the resulting subtrees into a complete forest.The procedures include local split selection, encrypted impurity communication, sample-index exchange, and forest assembly.
  • Proposition proof: For a complete-tree leaf l, every sample h in l follows a path w* contained in the corresponding client path Wi.This containment holds because clients retain split information only for nodes selected from their local features; otherwise, samples proceed through both subtrees.
  • Prediction: Prediction gathers client-side sample IDs, forms complete-tree leaf assignments by intersection, returns leaf labels, and averages tree outputs.The prediction algorithm recursively traverses stored split information and sends sample IDs rather than exchanging raw feature values.
  • Communication complexity: O(2^k(M + 1)) is the training communication complexity, while optimized prediction reduces communication from O(2^(k−1)M) to O(M).Here k is the maximum tree depth and M is the number of regional domains.
Loading 1905.10053v1…