Differential privacy preserving recommendation

• US 8,619,984 B2
• Filed: 09/11/2009
• Issued: 12/31/2013
• Est. Priority Date: 09/11/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank D., Mironov, Ilya
• Primary Examiner(s): LE, CHAU D
• Application Number:
  US12/557,538
• Publication Number:
  US 20110064221A1
• Time in Patent Office: 1,572 Days
• Field of Search: 380/252, 713/189
• US Class Current: 380/252
• CPC Class Codes: H04K 1/02 by adding a second signal to make the desired signal unintelligible

Abstract

User rating data may be received at a correlation engine through a network. The user rating data may include ratings generated by a plurality of users for a plurality of items. Correlation data may be generated from the received user rating data by the correlation engine. The correlation data may identify correlations between the items based on the user generated ratings. Noise may be generated by the correlation engine, and the generated noise may be added to the generated correlation data by the correlation engine to provide differential privacy protection to the user rating data.

Claims

1. A method for providing differential privacy comprising:

receiving user rating data at a correlation engine through a network, the user rating data comprising ratings generated by a plurality of users for a plurality of items;

removing per-item global effects from the user rating data by;

calculating an average rating for each item rated in the user rating data;

determining a plurality of fictitious ratings for each item rated in the user rating data, wherein each fictitious rating of an item is set to the calculated average rating of the item;

calculating a stabilized average rating for each item rated in the user rating data using the ratings in the user rating data for the item and the plurality of fictitious ratings for the item; and

for each rating in the user rating data, subtracting the calculated stabilized average rating for the rated item from the rating;

generating correlation data from the user rating data by the correlation engine, the correlation data identifying correlations between the items based on the user generated ratings;

generating noise by the correlation engine; and

adding the generated noise to the generated correlation data by the correlation engine to provide differential privacy protection to the generated correlation data.

2. The method of claim 1, further comprising recommending an item to a user based on the generated correlation data.

3. The method of claim 1, wherein the correlation data comprises a covariance matrix.

4. The method of claim 3, wherein the covariance matrix comprises an entry for each unique item pair from the user rating data, and the each entry comprises the sum of the products of the ratings for the associated item pair for each user and each product is inversely weighted by a function of the number of ratings generated by the user.

5. The method of claim 3, wherein generating the noise by the correlation engine comprises:

generating a matrix of noise values, wherein the matrix of noise values is the same size as the covariance matrix; and

adding the generated matrix of noise values to the covariance matrix.

6. The method of claim 1, wherein removing per-item global effects from the user rating data further comprises:

adding noise to the calculated average rating for each item.

7. The method of claim 1, further comprising removing per-user global effects from the user rating data.

8. The method of claim 7, wherein removing the per-user global effects from the user rating data comprises:

determining an average rating given by each user from the user rating data; and

for each user in the user rating data, subtracting the determined average rating from each rating associated with the user.

9. The method of claim 8, further comprising:

selecting a rating interval; and

recentering each rating in the user rating data to the selected rating interval.

10. A system for providing differential privacy comprising:

a computing device;

a correlation engine adapted to;

receive user rating data, wherein the user rating data comprises a plurality of item ratings generated by a plurality of users;

remove per-item global effects from the user rating data by;

calculating an average rating for each item rated in the user rating data;

determining a plurality of fictitious ratings for each item rated in the user rating data, wherein each fictitious rating of an item is set to the calculated average rating of the item;

calculating a stabilized average rating for each item rated in the user rating data using the ratings in the user rating data for the item and the plurality of fictitious ratings for the item; and

for each rating in the user rating data, subtracting the calculated stabilized average rating for the rated item from the rating;

generate a covariance matrix from the user rating data;

add noise to the generated covariance matrix to provide differential privacy protection to the covariance matrix; and

publish the generated covariance matrix; and

a recommendation engine adapted to;

receive the generated covariance matrix; and

generate item recommendations using the published covariance matrix.

11. The system of claim 10, wherein the generated noise is Laplacian noise or Gaussian noise.

12. The system of claim 10, wherein the correlation engine is further adapted to clean the generated covariance matrix.

13. The system of claim 10, wherein the correlation engine is further adapted to remove per-user global effects from the user rating data.

14. The system of claim 10, wherein the correlation engine adapted to remove per-item global effects further comprises the correlation engine adapted to:

add noise to the calculated average rating for each item.

15. The system of claim 14, wherein the correlation engine is further adapted to publish the calculated average rating for each item.

16. A method for providing differential privacy comprising:

receiving user rating data by a correlation engine through a network, wherein the user rating data comprises a plurality of ratings of items generated by a plurality of users;

removing per-item global effects from the user rating data by the correlation engine by;

calculating an average rating for each item rated in the user rating data;

determining a plurality of fictitious ratings for each item rated in the user rating data, wherein each fictitious rating of an item is set to the calculated average rating of the item;

calculating a stabilized average rating for each item rated in the user rating data using the ratings in the user rating data for the item and the plurality of fictitious ratings for the item; and

for each rating in the user rating data, subtracting the calculated stabilized average rating for the rated item from the rating;

generating a covariance matrix from the user rating data by the correlation engine;

adding noise to the generated covariance matrix to provide differential privacy protection to the user rating data by the correlation engine; and

publishing the generated covariance matrix by the correlation engine.

17. The method of claim 16, further comprising removing per-user global effects from the user rating data.

18. The method of claim 16, further comprising generating item recommendations using the covariance matrix.

19. The method of claim 16, wherein the noise is Laplacian noise or Gaussian noise.