Differentially Private Random Decision Forests using Smooth Sensitivity

Abstract

We propose a new differentially-private decision forest algorithm that minimizes both the number of queries required, and the sensitivity of those queries. To do so, we build an ensemble of random decision trees that avoids querying the private data except to find the majority class label in the leaf nodes. Rather than using a count query to return the class counts like the current state-of-the-art, we use the Exponential Mechanism to only output the class label itself. This drastically reduces the sensitivity of the query -- often by several orders of magnitude -- which in turn reduces the amount of noise that must be added to preserve privacy. Our improved sensitivity is achieved by using "smooth sensitivity", which takes into account the specific data used in the query rather than assuming the worst-case scenario. We also extend work done on the optimal depth of random decision trees to handle continuous features, not just discrete features. This, along with several other improvements, allows us to create a differentially private decision forest with substantially higher predictive power than the current state-of-the-art.

Pre-print of 2017 paper published in Expert Systems with Applications, 36 pages; 2021 Addendum added to end of paper

References in corpus (3)

• Differential Privacy and Machine Learning: a Survey and Review
• Differentially Private Random Decision Forests using Smooth Sensitivity
• WaveCluster with Differential Privacy

Cited by in corpus (10)

• Differentially Private Random Decision Forests using Smooth Sensitivity
• Oblique and rotation double random forest
• Not one but many Tradeoffs: Privacy Vs. Utility in Differentially Private Machine Learning
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
• Decision Tree Classification with Differential Privacy: A Survey
• Anonymizing Machine Learning Models
• Data Security and Privacy in Cloud Computing: Concepts and Emerging Trends
• Differentially Private Regression and Classification with Sparse Gaussian Processes
• Boosted and Differentially Private Ensembles of Decision Trees
• PUTWorkbench: Analysing Privacy in AI-intensive Systems