Differentially private machine learning using a random forest classifier

• US 10,726,153 B2
• Filed: 09/27/2018
• Issued: 07/28/2020
• Est. Priority Date: 11/02/2015
• Status: Active Grant

• Current Assignee: Snowflake, Inc.
• Original Assignee: LeapYear Technologies, Inc. (Snowflake Inc)
• Inventors: Nerurkar, Ishaan, Hockenbrocht, Christopher, Damewood, Liam, Maruseac, Mihai, Rozenshteyn, Alexander
• Primary Examiner(s): Leung, Robert B
• Application Number:
  US16/144,790
• Publication Number:
  US 20190026489A1
• Time in Patent Office: 670 Days
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 20/20 Ensemble learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G16H 10/60 for patient-specific data, e.g. for electronic patient records

Abstract

A request from a client is received to generate a differentially private random forest classifier trained using a set of restricted data. The differentially private random forest classifier is generated in response to the request. Generating the differentially private random forest classifier includes determining a number of decision trees and generating the determined number of decision trees. Generating a decision tree includes generating a set of splits based on the restricted data, determining an information gain for each split, selecting a split from the set using an exponential mechanism, and adding the split to the decision tree. The differentially private random forest classifier is provided to the client.

Claims

1. A method, comprising:

receiving a request from a client to generate a differentially private random forest classifier trained using a set of restricted data stored by a private database system, the request identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ε and

δ

, wherein ε

describes a degree of information released about the set of restricted data due to the request and δ

describes an improbability of the request satisfying (ε

)-differential privacy;

generating the differentially private random forest classifier in response to the request, generating the classifier comprising;

determining a number of decision trees comprising the differentially private random forest classifier;

generating the determined number of decision trees, wherein a decision tree comprises a plurality of leaf nodes representing classification categories, and generating the decision tree comprises;

generating a set of splits based on features of the set of restricted data;

determining an information gain for each split of the set of splits;

selecting a split from the set of splits using an exponential mechanism based at least in part on the determined information gains of the splits in the set and at least one of the privacy parameters;

adding the selected split to the decision tree at a node; and

determining, for a certain leaf node of the plurality of leaf nodes representing a certain classification category of the classification categories, a differentially private count of entities in the set of restricted data in the certain classification category; and

providing the differentially private random forest classifier to the client, the provided differentially private random forest classifier comprising the differentially private count of entities in the certain classification category represented by the certain leaf node.

2. The method of claim 1, wherein determining the information gain for a split of the set of splits comprises evaluating:

3. The method of claim 2, wherein selecting a split from the set of splits using the exponential mechanism is further based on a sensitivity, wherein the sensitivity of the exponential mechanism is determined by:

4. The method of claim 1, wherein generating the random forest classifier in response to the request is based on one or more model parameters, including at least one of a number of decision trees to be used in the classifier, a number of splits to include in the decision trees, a maximum tree height, and a utility gain threshold, and wherein each of the one or more model parameters is at least one of a default value and a value included in the request.

5. The method of claim 1,

wherein the restricted data stores records comprising rows and columns;

wherein the rows are associated with patients having a medical condition;

wherein the columns contain values describing health data for the patients; and

wherein providing the differentially private random forest classifier to the client comprises estimating whether a new patient has the medical condition.

6. The method of claim 1,

wherein the set of data stores records comprising rows and columns;

wherein the rows are associated with customers having a financial account;

wherein the columns contain values describing financial data for the customers; and

wherein providing the differentially private random forest classifier to the client comprises estimating whether a new customer can perform a financial transaction.

7. A non-transitory computer-readable storage medium storing computer program instructions executable by a processor to perform operations, the operations comprising:

receiving a request from a client to generate a differentially private random forest classifier trained using a set of restricted data stored by a private database system, the request identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ε and

δ

, wherein ε

describes a degree of information released about the set of restricted data due to the request and δ

describes an improbability of the request satisfying (ε

)-differential privacy;

generating the differentially private random forest classifier in response to the request, generating the classifier comprising;

determining a number of decision trees comprising the differentially private random forest classifier;

generating the determined number of decision trees, wherein a decision tree comprises a plurality of leaf nodes representing classification categories, and generating the decision tree comprises;

generating a set of splits based on features of the set of restricted data;

determining an information gain for each split of the set of splits;

selecting a split from the set of splits using an exponential mechanism based at least in part on the determined information gains of the splits in the set and at least one of the privacy parameters;

adding the selected split to the decision tree at a node; and

determining, for a certain leaf node of the plurality of leaf nodes representing a certain classification category of the classification categories, a differentially private count of entities in the set of restricted data in the certain classification category; and

providing the differentially private random forest classifier to the client, the provided differentially private random forest classifier comprising the differentially private count of entities in the certain classification category represented by the certain leaf node.

8. The non-transitory computer-readable storage medium of claim 7, wherein determining the information gain for a split of the set of splits comprises evaluating:

9. The non-transitory computer-readable storage medium of claim 8, wherein selecting a split from the set of splits using the exponential mechanism is further based on a sensitivity, wherein the sensitivity of the exponential mechanism is determined by:

10. The non-transitory computer-readable storage medium of claim 7, wherein generating the random forest classifier in response to the request is based on one or more model parameters, including at least one of a number of decision trees to be used in the classifier, a number of splits to include in the decision trees, a maximum tree height, and a utility gain threshold, and wherein each of the one or more model parameters is at least one of a default value and a value included in the request.

11. The non-transitory computer-readable storage medium of claim 7,

wherein the restricted data stores records comprising rows and columns;

wherein the rows are associated with patients having a medical condition;

wherein the columns contain values describing health data for the patients; and

wherein providing the differentially private random forest classifier to the client comprises estimating whether a new patient has the medical condition.

12. The non-transitory computer-readable storage medium of claim 7,

wherein the set of data stores records comprising rows and columns;

wherein the rows are associated with customers having a financial account;

wherein the columns contain values describing financial data for the customers; and

wherein providing the differentially private random forest classifier to the client comprises estimating whether a new customer can perform a financial transaction.

13. A system comprising:

a processor for executing computer program instructions; and

a non-transitory computer-readable storage medium storing computer program instructions executable by the processor to perform operations comprising;

receiving a request from a client to generate a differentially private random forest classifier trained using a set of restricted data stored by a private database system, the request identifying a level of differential privacy corresponding to the request, the identified level of differential privacy comprising privacy parameters ε and

δ

, wherein ε

describes a degree of information released about the set of restricted data due to the request and δ

describes an improbability of the request satisfying (ε

)-differential privacy;

generating the differentially private random forest classifier in response to the request, generating the classifier comprising;

determining a number of decision trees comprising the differentially private random forest classifier;

generating the determined number of decision trees, wherein a decision tree comprises a plurality of leaf nodes representing classification categories, and generating the decision tree comprises;

generating a set of splits based on features of the set of restricted data;

determining an information gain for each split of the set of splits;

selecting a split from the set of splits using an exponential mechanism based at least in part on the determined information gains of the splits in the set and at least one of the privacy parameters;

adding the selected split to the decision tree at a node; and

determining, for a certain leaf node of the plurality of leaf nodes representing a certain classification category of the classification categories, a differentially private count of entities in the set of restricted data in the certain classification category; and

providing the differentially private random forest classifier to the client the provided differentially private random forest classifier comprising the differentially private count of entities in the certain classification category represented by the certain leaf node.

14. The system of claim 13, wherein determining the information gain for a split of the set of splits comprises evaluating:

15. The system of claim 14, wherein selecting a split from the set of splits using the exponential mechanism is further based on a sensitivity, wherein the sensitivity of the exponential mechanism is determined by:

16. The system of claim 13,

wherein the restricted data stores records comprising rows and columns;

wherein the rows are associated with patients having a medical condition;

wherein the columns contain values describing health data for the patients; and

wherein providing the differentially private random forest classifier to the client comprises estimating whether a new patient has the medical condition.

17. The system of claim 13,

wherein the set of data stores records comprising rows and columns;

wherein the rows are associated with customers having a financial account;

wherein the columns contain values describing financial data for the customers; and

wherein providing the differentially private random forest classifier to the client comprises estimating whether a new customer can perform a financial transaction.