DIFFERENTIAL PRIVACY PRESERVING RECOMMENDATION

• US 20110064221A1
• Filed: 09/11/2009
• Published: 03/17/2011
• 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
• Granted Patent: US 8,619,984 B2
• Time in Patent Office: Days
• 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;

generating correlation data from the received 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, further comprising removing per-item global effects from the user rating data.

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

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

adding noise to the calculated average rating for each item; and

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

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

9. The method of claim 8, 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.

10. The method of claim 9, further comprising:

selecting a rating interval; and

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

11. A system for providing differential privacy comprising:

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;

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.

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

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

14. The system of claim 11, wherein the correlation engine is further adapted to remove per-user global effects and per-item global effects from the user rating data.

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

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

add noise to the calculated average rating for each item; and

for each rating in the user rating data, subtract the calculated average rating for the rated item from the rating.

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

17. 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;

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.

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

19. The method of claim 17, further comprising generating item recommendations using the covariance matrix.

20. The method of claim 17, wherein the noise is Laplacian noise or Gaussian noise.