Method for anonymous collaborative filtering using matrix factorization

• US 7,685,232 B2
• Filed: 06/04/2008
• Issued: 03/23/2010
• Est. Priority Date: 06/04/2008
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Gibbs, Simon J., Németh, Bottyán
• Primary Examiner(s): Winder; Patrice
• Assistant Examiner(s): Duong; Thomas
• Application Number:
  US12/133,304
• Publication Number:
  US 20090307296A1
• Time in Patent Office: 657 Days
• Field of Search: 709201-203
• US Class Current: 709/203
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

System and method for performing Collaborative Filtering while preserving complete user anonymity are provided. Each of a group of client devices sends a rating vector anonymously to a server. The cells in each rating vector correspond to a set of items, and selected cells have ratings provided by the user associated with the corresponding client device for the corresponding items. The server aggregates all the rating vectors into a rating matrix, and factorizes the rating matrix into a user feature matrix and an item feature matrix through approximation, such that the rating matrix equals the product of the user feature matrix and the item feature matrix. The item feature matrix is sent to the client devices. Each of the client devices calculates its own user feature vector based on its rating vector and the item feature matrix, and provides personalized recommendations on selected items based on the client'"'"'s user feature vector and the item feature matrix.

Claims

1. A method of providing personalized recommendations to anonymous users, comprising:

at a server,

factorizing a rating matrix, denoted by M_R, into a user feature matrix, denoted by M_U, and an item feature matrix, denoted by M_I, wherein the rows of M_R correspond to a plurality of users, the columns of M_R correspond to a plurality of items, each of the cells of M_R represents a rating associated with a corresponding item for a corresponding user, and M_R=M_U×

M_I, and

transmitting the item feature matrix, M_I, to selected ones of a plurality of client devices associated with the plurality of users; and

at one of the selected ones of the plurality of client devices associated with one of the plurality of users, calculating a user feature vector, denoted by V_U, based on the item feature matrix, M_I, and a rating vector, denoted by V_R, wherein each of the cells of V_R represents a rating associated with a corresponding one of the plurality of items for the one user, and V_R=V_U×

M_I.

2. A method as recited in claim 1, further comprising:

at the server,

receiving a plurality of rating vectors anonymously sent from the plurality of client devices; and

aggregating the plurality of rating vectors into the rating matrix, M_R, wherein selected cells of M_R have received ratings from the corresponding users for the corresponding items.

3. A method as recited in claim 2, wherein factorizing the rating matrix, M_R, at the server is through approximation.

4. A method as recited in claim 3, wherein factoring the rating matrix, M_R, at the server comprises:

assigning predefined initial values to the cells of the user feature matrix, M_U, and the cells of the item feature matrix, M_I;

repeatedly calculating a product matrix, denoted by M_P, such that M_P=M_U×

M_I, and adjusting values of selected cells of M_U and M_I until a difference between selected corresponding pairs of cells from M_P and M_R is less than a first predefined threshold.

5. A method as recited in claim 1, further comprising:

at the one client device associated with the one user,

constructing the rating vector, V_R, wherein selected cells of V_R have received ratings from the one user for the corresponding items; and

anonymously transmitting the rating vector, V_R, to the server.

6. A method as recited in claim 5, wherein calculating the user feature vector, V_U, at the one client device associated with the one user comprises:

assigning predefined initial values to the cells of the user feature vector, V_U;

repeatedly calculating a product vector, denoted by V_P, such that V_P=V_U×

M_I, and adjusting values of selected cells of V_U until a difference between selected corresponding pairs of cells from V_P and V_R is less than a second predefined threshold.

7. A method as recited in claim 1, further comprising:

at the one client device associated with the one user, recommending selected ones of the plurality of items to the one user based on the item feature matrix, M_I, and the user feature vector, V_U.

8. A method as recited in claim 7, wherein recommending selected ones of the plurality of items to the one user at the one client device associated with the one user comprises:

estimating ratings for selected ones of the plurality of items that have not received ratings from the one user based on the item feature matrix, M_I, and the user feature vector, V_U; and

recommending the selected ones of the plurality of items to the one user based on their respective estimated ratings.

9. A method as recited in claim 7, wherein recommending selected ones of the plurality of items to the one user at the one client device associated with the one user comprises:

comparing a first one of the plurality of items that has received a rating from the one user with a second one of the plurality of items that has not received a rating from the one user, wherein the rating for the first one item is greater than or equal to a predefined third threshold; and

recommending the second one item to the one user if the product of an item feature vector for the first one item, denoted by V₁₁, and an item feature vector for the second on item, denoted by V₁₂, is greater than or equal to a predefined fourth threshold.

10. A method as recited in claim 1, wherein the plurality of items is a plurality pieces of media content.

11. A method as recited in claim 1, further comprising:

at an anonymizer,

receiving a rating vector from one of the plurality of client devices; and

forwarding the rating vector to the server without any identifying information with respect to the one client device and its associated user.

12. A method of obtaining an item feature matrix, denoted by M_I, at a server to be used for providing personalized recommendations to anonymous users, comprising:

aggregating a plurality of rating vectors, denoted by V_R, each provided by an anonymous client device, into a rating matrix, denoted by M_R, wherein the rows of M_R correspond to a plurality of anonymous users, the columns of M_R correspond to a plurality of items, each of the cells of M_R represents a rating associated with a corresponding item for a corresponding anonymous user, and selected cells of M_R have received ratings from the corresponding anonymous users for the corresponding items;

factorizing the rating matrix, M_R, into a user feature matrix, denoted by M_U, and an item feature matrix, denoted by M_I, wherein M_R=M_U×

M_I; and

transmitting the item feature matrix, M_I, to selected ones of a plurality of anonymous client devices associated with the plurality of anonymous users.

13. A method as recited in claim 12, wherein factoring the rating matrix, M_R, comprises:

assigning predefined initial values to the cells of the user feature matrix, M_U, and the cells of the item feature matrix, M_I;

repeatedly calculating a product matrix, denoted by M_P, such that M_P=M_U×

M_I, and adjusting values of selected cells of M_U and M_I until a difference between selected corresponding pairs of cells from M_P and M_R is less than a first predefined threshold.

14. A method as recited in claim 12, further comprises:

sending a rating vector request to the plurality of client devices; and

receiving the plurality of rating vectors from the plurality of client devices.

15. A method as recited in claim 12, further comprises:

resending the rating vector request to the plurality of client devices;

receiving a plurality of updated rating vectors from the plurality of client devices;

aggregating the plurality of updated rating vectors into a second rating matrix;

factorizing the second rating matrix into a second user feature matrix and a second item feature matrix; and

transmitting the second item feature matrix to selected ones of the plurality of anonymous client devices.

16. A method of providing personalized recommendations at a client device while maintaining anonymity of the client device and a user associated with the client device, comprising:

anonymously transmitting a rating vectors, denoted by V_R, to a server, wherein each of the cells of V_R represents a rating associated with a corresponding one of a plurality of items for the user, and selected cells of V_R have received ratings from the user for the corresponding items;

receiving an item feature matrix, denoted by M_I, from the server;

calculating a user feature vector, denoted by V_U, based on the item feature matrix, M_I, and the rating vector, V_R, wherein V_R=V_U×

M_I; and

recommending selected ones of the plurality of items that have not received ratings from the user to the user based on the user feature vector, V_U, and the item feature matrix, M_I.

17. A method as recited in claim 16, wherein calculating the user feature vector, V_U, comprises:

assigning predefined initial values to the cells of the user feature vector, V_U;

repeatedly calculating a product vector, denoted by V_P, such that V_P=V_U×

M_I, and adjusting values of selected cells of V_U until a difference between selected corresponding pairs of cells from V_P and V_R is less than a first predefined threshold.

18. A method as recited in claim 16, wherein recommending selected ones of the plurality of items to the user comprises:

estimating ratings for selected ones of the plurality of items that have not received ratings from the user based on the item feature matrix, M_I, and the user feature vector, V_U; and

recommending the selected ones of the plurality of items to the user based on their respective estimated ratings.

19. A method as recited in claim 18, wherein recommending selected ones of the plurality of items to the user comprises:

comparing a first one of the plurality of items that has received a rating from the user with a second one of the plurality of items that has not received a rating from the user, wherein the rating for the first one item is greater than or equal to a predefined second threshold; and

recommending the second one item to the user if the product of an item feature vector for the first one item, denoted by V₁₁, and an item feature vector for the second on item, denoted by V₁₂, is greater than or equal to a predefined third threshold.

20. A method as recited in claim 16, further comprising:

constructing the rating vector, V_R.

21. A method as recited in claim 20, wherein the rating vector, V_R, is constructed automatically based on usage information of the client device.

22. A method as recited in claim 16, further comprising:

constructing an updated rating vector; and

anonymously transmitting the updated rating vectors to the server.

23. A system for providing personalized recommendations to anonymous users, comprising:

a server arranged to factorize a rating matrix, denoted by M_R, into a user feature matrix, denoted by M_U, and an item feature matrix, denoted by M_I, wherein the rows of M_R correspond to a plurality of users, the columns of M_R correspond to a plurality of items, each of the cells of M_R represents a rating associated with a corresponding item for a corresponding user, and M_R=M_U×

M_I, and transmit the item feature matrix, M_I, to selected ones of a plurality of client devices associated with the plurality of users;

an anonymizer arranged to relay communications between the server and the selected ones of the plurality of client devices so that the plurality of client devices and their associated users remain anonymous to the server; and

one of the plurality of client devices arranged to calculate a user feature vector, denoted by V_U, based on the item feature matrix, M_I, and a rating vector, denoted by V_R, wherein each of the cells of V_R represents a rating associated with a corresponding one of the plurality of items for the one user, and V_R=V_U×

M_I.

24. A system as recited in claim 23, wherein factorize the rating matrix, M_R, at the server is through approximation.

25. A system as recited in claim 24, wherein factorize the rating matrix, M_R, at the server comprises:

assign predefined initial values to the cells of the user feature matrix, M_U, and the cells of the item feature matrix, M_I;

repeatedly calculate a product matrix, denoted by M_P, such that M_P=M_U×

M_I, and adjusting values of selected cells of M_U and M_I until a difference between selected corresponding pairs of cells from M_P and M_R is less than a first predefined threshold.

26. A system as recited in claim 23, wherein the server is further arranged to receive a plurality of rating vectors anonymously sent from the plurality of client devices;

and aggregate the plurality of rating vectors into the rating matrix, M_R, wherein selected cells of M_R have received ratings from the corresponding users for the corresponding items.

27. A system as recited in claim 23, wherein the one client device is further arranged to construct the rating vector, V_R, wherein selected cells of V_R have received ratings from a user associated with the one client device for the corresponding items;

and anonymously transmit the rating vector, V_R, to the server.

28. A system as recited in claim 23, wherein calculate the user feature vector, V_U, at the one client device comprises:

assign predefined initial values to the cells of the user feature vector, V_U;

repeatedly calculate a product vector, denoted by V_P, such that V_P=V_U×

M_I, and adjusting values of selected cells of V_U until a difference between selected corresponding pairs of cells from V_P and V_R is less than a second predefined threshold.

29. A system as recited in claim 23, wherein the one client device is further arranged to recommend selected ones of the plurality of items to a user associated with the one client device based on the item feature matrix, M_I, and the user feature vector, V_U.

30. A method as recited in claim 29, wherein recommend selected ones of the plurality of items to the user at the one client device comprises:

estimate ratings for selected ones of the plurality of items that have not received ratings from the one user based on the item feature matrix, M_I, and the user feature vector, V_U; and

recommend the selected ones of the plurality of items to the user based on their respective estimated ratings.

31. A computer program product for providing personalized recommendations to anonymous users, the computer program product comprising a computer-readable medium having a plurality of computer program instructions stored therein, which are operable to cause at least one computing device to:

at a server,

factorize a rating matrix, denoted by M_R, into a user feature matrix, denoted by M_U, and an item feature matrix, denoted by M_I, wherein the rows of M_R correspond to a plurality of users, the columns of M_R correspond to a plurality of items, each of the cells of M_R represents a rating associated with a corresponding item for a corresponding user, and M_R=M_U×

M_I, and

transmit the item feature matrix, M_I, to selected ones of a plurality of client devices associated with the plurality of users; and

at one of the selected ones of the plurality of client devices associated with one of the plurality of users, calculate a user feature vector, denoted by V_U, based on the item feature matrix, M_I, and a rating vector, denoted by V_R, wherein each of the cells of V_R represents a rating associated with a corresponding one of the plurality of items for the one user, and V_R=V_U×

M_I.

32. A computer program product as recited in claim 31, wherein the plurality of computer program instructions are further operable to cause the at least one computing device to:

at the server,

receive a plurality of rating vectors anonymously sent from the plurality of client devices; and

aggregate the plurality of rating vectors into the rating matrix, M_R, wherein selected cells of M_R have received ratings from the corresponding users for the corresponding items.

33. A computer program product as recited in claim 32, wherein factorize the rating matrix, M_R, at the server is through approximation.

34. A computer program product as recited in claim 33, wherein factoring the rating matrix, M_R, at the server comprises:

assign predefined initial values to the cells of the user feature matrix, M_U, and the cells of the item feature matrix, M_I;

repeatedly calculate a product matrix, denoted by M_P, such that M_P=M_U×

M_I, and adjusting values of selected cells of M_U and M_I until a difference between selected corresponding pairs of cells from M_P and M_R is less than a first predefined threshold.

35. A computer program product as recited in claim 31, wherein the plurality of computer program instructions are further operable to cause the at least one computing device to:

at the one client device associated with the one user,

construct the rating vector, V_R, wherein selected cells of V_R have received ratings from the one user for the corresponding items; and

anonymously transmit the rating vector, V_R, to the server.

36. A computer program product as recited in claim 35, wherein calculate the user feature vector, V_U, at the one client device associated with the one user comprises:

assign predefined initial values to the cells of the user feature vector, V_U;

repeatedly calculate a product vector, denoted by V_P, such that V_P=V_U×

M_I, and adjusting values of selected cells of V_U until a difference between selected corresponding pairs of cells from V_P and V_R is less than a second predefined threshold.

37. A computer program product as recited in claim 31, wherein the plurality of computer program instructions are further operable to cause the at least one computing device to:

at the one client device associated with the one user, recommend selected ones of the plurality of items to the one user based on the item feature matrix, M_I, and the user feature vector, V_U.

38. A computer program product as recited in claim 37, wherein recommend selected ones of the plurality of items to the one user at the one client device associated with the one user comprises:

estimate ratings for selected ones of the plurality of items that have not received ratings from the one user based on the item feature matrix, M_I, and the user feature vector, V_U; and

recommend the selected ones of the plurality of items to the one user based on their respective estimated ratings.

39. A computer program product as recited in claim 31, wherein the plurality of computer program instructions are further operable to cause the at least one computing device to:

at an anonymizer,

receive a rating vector from one of the plurality of client devices; and

forward the rating vector to the server without any identifying information with respect to the one client device and its associated user.