FedVoting: A Cross-Silo Boosting Tree Construction Method for Privacy-Preserving Long-Term Human Mobility Prediction

Yinghao Liu, Zipei Fan, Xuan Song, Ryosuke Shibasaki

TL;DR

This paper introduces FedVoting, a novel federated learning approach for privacy-preserving long-term human mobility prediction. By combining Gradient Boosting Decision Trees (GBDTs) with differential privacy and a unique cross-validation and voting mechanism, FedVoting achieves high prediction accuracy while keeping sensitive user data localized.

What Problem Does This Paper Address?

Predicting human mobility is crucial for urban planning, traffic management, and personalized services. However, this prediction relies heavily on granular location data (like GPS trajectories), which raises significant privacy concerns. Organizations collecting this data are often hesitant to share it due to privacy regulations and competitive reasons, leading to "data silos" where valuable collective insights are lost. Traditional federated learning (FL) offers a solution by allowing collaborative model training without sharing raw data, but it struggles with the complex and irregular nature of long-term mobility patterns. Simply aggregating models trained in isolation often leads to suboptimal performance. This paper tackles the challenge of building accurate long-term mobility prediction models within a federated learning framework that robustly protects user privacy.

Methods

The core of this work is the FedVoting mechanism, designed to construct a federated Gradient Boosting Decision Tree (GBDT) ensemble. Here's a breakdown of the key techniques:

  • Gradient Boosting Decision Trees (GBDTs): Chosen as the base model due to their effectiveness in handling high-dimensional and complex data, which is characteristic of mobility patterns.
  • Federated Learning (FL): The overarching framework where multiple "silos" (organizations) collaboratively train a model without sharing their raw data.
  • Differential Privacy (DP): Applied to protect the privacy of the GBDT model's parameters. Crucially, the authors propose a heterogeneous privacy protection approach. This means different levels of noise are added to different parts of the decision trees: more noise is added to the sensitive "leaf nodes" (derived from labels) and less to the "splitting nodes" (derived from features). This aims to balance privacy protection with model performance.
  • FedVoting Mechanism: This is the novel contribution. For each iteration of training, the process involves:
  • Training: Each silo trains a batch of GBDT trees locally on its data, applying DP.
  • Cross-Validation: Each silo's trained model is sent to other silos for validation using their local data.
  • Voting: The validation results from all silos are used to "vote" for the best performing model in that iteration. The model with the lowest validation error is selected as the optimal model for that batch and is aggregated into the final ensemble.

This iterative process ensures that the final ensemble model is built from the best-performing local models, leading to improved accuracy compared to simply averaging or sequentially combining models.

Datasets

The authors utilized the "Konzatsu-Tokei (R)" raw GPS log dataset from NTT DOCOMO, INC. This dataset contains anonymized GPS trajectory data collected from mobile phones with user consent.

  • Data Scope: The study focused on the Greater Tokyo Area over a one-year period (January 2012 to December 2012).
  • Preprocessing: The raw GPS data was transformed into grid-level trajectories and then into travel-frequency patterns. These patterns, representing the frequency of visiting specific grids over a month, served as features for prediction. A distinction was made between weekday and weekend travel patterns to capture more nuanced mobility behaviors.
  • Prediction Tasks: Two long-term human mobility prediction tasks were evaluated:
  • Special Event Attendance: Predicting attendance at the "Comiket" event in Tokyo.
  • Point-of-Interest (POI) Visits: Predicting visits to Disneyland.
  • Data Splitting: The dataset was split into 70% for training and 30% for testing. For federated learning experiments, the training data was further divided into k equal parts for k silos.

Key Insights and Ideas

  • Long-term mobility is inherently complex: Unlike short-term predictions, long-term mobility involves more irregular patterns (weekends, special events) that are harder to model.
  • Federated learning is a necessity, not just an option: The privacy concerns surrounding GPS data make FL the only viable path for collaborative model building.
  • Simple FL aggregation isn't enough: Just combining models trained in isolation (or even averaging them) doesn't capture the full potential of distributed data for complex tasks like long-term mobility prediction.
  • Heterogeneous DP is key for GBDTs: Applying uniform DP to all parts of a GBDT model can severely degrade performance. Differentiating noise levels for splitting nodes and leaf nodes offers a better trade-off.
  • Cross-validation and voting are powerful for model selection: The FedVoting mechanism intelligently selects the best local models at each stage, mimicking a sophisticated ensemble building process within a privacy-preserving framework.
  • Incentives are crucial for FL adoption: The paper highlights that contribution-based incentives can encourage participation in federated learning, especially when data volumes or quality vary across silos.

Key Results

  • Improved Accuracy: FedVoting achieved significantly better classification accuracy compared to models trained independently by each silo (SOLO) and a baseline federated model (SimFL).
  • Near Centralized Performance: The accuracy of FedVoting was very close to that of centralized training (ALL-IN), where all data is pooled, demonstrating its effectiveness.
  • Privacy Protection: The method keeps raw data localized and uses DP to protect model parameters, offering a strong privacy guarantee.
  • Efficiency: The FedVoting process is described as practical and efficient, with the ensemble of GBDTs constructed iteratively.
  • Robustness: The model's performance remained strong even with uneven data distributions across silos. For example, in the Comiket prediction, FedVoting's classification error was consistently lower than SOLO and close to ALL-IN across different numbers of silos and data ratios.

Limitations and Future Work

  • Data Distribution: While the paper explores uneven data volumes, it assumes the data within each silo is identically and independently distributed (IID). Future work could explore non-IID scenarios.
  • Model Complexity: The paper focuses on GBDTs. Exploring other complex models within the FedVoting framework could be beneficial.
  • Incentive Mechanisms: While the paper proposes a contribution-based incentive mechanism, further research into designing and implementing these mechanisms in real-world FL systems is suggested.
  • Advanced Prediction Strategies: The authors suggest exploring context prediction, similarity analysis of historical trajectories, and ensemble methods to further enhance long-term mobility prediction capabilities.
  • Real-world Deployment: Investigating the practical deployment challenges and scalability of FedVoting in diverse urban environments would be a valuable next step.

Summary updated

Abstract

The prediction of human mobility can facilitate resolving many kinds of urban problems, such as reducing traffic congestion, and promote commercial activities, such as targeted advertising. However, the requisite personal GPS data face privacy issues. Related organizations can only collect limited data and they experience difficulties in sharing them. These data are in “isolated islands” and cannot collectively contribute to improving the performance of applications. Thus, the method of federated learning (FL) can be adopted, in which multiple entities collaborate to train a collective model with their raw data stored locally and, therefore, not exchanged or transferred. However, to predict long-term human mobility, the performance and practicality would be impaired if only some models were simply combined with FL, due to the irregularity and complexity of long-term mobility data. Therefore, we explored the optimized construction method based on the high-efficient gradient-boosting decision tree (GBDT) model with FL and propose the novel federated voting (FedVoting) mechanism, which aggregates the ensemble of differential privacy (DP)-protected GBDTs by the multiple training, cross-validation and voting processes to generate the optimal model and can achieve both good performance and privacy protection. The experiments show the great accuracy in long-term predictions of special event attendance and point-of-interest visits. Compared with training the model independently for each silo (organization) and state-of-art baselines, the FedVoting method achieves a significant accuracy improvement, almost comparable to the centralized training, at a negligible expense of privacy exposure.
BibTeX
@inproceedings{liu2021fedvoting,
  author = {Yinghao Liu and Zipei Fan and Xuan Song and Ryosuke Shibasaki},
  title = {{FedVoting: A Cross-Silo Boosting Tree Construction Method for Privacy-Preserving Long-Term Human Mobility Prediction}},
  booktitle = {Sensors},
  year = {2021},
  url = {https://openreview.net/forum?id=CdjtauQyu5F},
}
Figure