Collaborative filtering

• US 8,407,226 B1
• Filed: 03/02/2011
• Issued: 03/26/2013
• Est. Priority Date: 02/16/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Garg, Ashutosh, Datar, Mayur
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Chang, Jeffrey
• Application Number:
  US13/039,173
• Time in Patent Office: 755 Days
• Field of Search: 707/736, 707/739
• US Class Current: 707/739
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering

Abstract

Systems, methods, and apparatus, including computer program products, for collaborative filtering are provided. In one implementation, a computer-implemented method is provided. The method includes receiving a shard of data representing a subset of a set of entities and a subset of a set of items, generating an iteration of a maximum likelihood estimate of a probability distribution model of a relationship between the set of entities and the set of items, the probability distribution model comprising a probability distribution of the set of items with respect to latent variables and a probability distribution of the latent variables with respect to the set of users, and generating statistics from results from the generating step which are passed to different shards for use in a next iteration of the maximum likelihood estimate.

Claims

1. A computer-implemented method comprising:

obtaining training data that represents a set of users that includes as members a plurality of users and a set of items that includes as members a plurality of user selectable items;

assigning each of the plurality of users and each of the plurality items to a respective one of a plurality of user groups and item groups;

assigning to each machine in a collection of machines one or more user groups from the plurality of user groups and one or more item groups from the plurality of item groups;

calculating, by each machine, respective latent variable states for each user in the one or more user groups assigned to the machine and respective latent variable states for each item in the one or more item groups assigned to the machine, wherein the calculated latent variable states represent a variational probability distribution relating the user groups and item groups assigned to the respective machine;

determining, using each machine, a respective first probability distribution relating respective latent variable states to users in the one or more user groups assigned to the machine;

determining, using each machine, a respective second probability distribution relating respective latent variable states to items in the one or more item groups assigned to the machine;

determining, each machine, one or more respective parameter values for the first and second probability distributions that were determined by the machine, wherein determining the parameter values includes determining maximum likelihood estimates for parameters of the first probability distribution and the second probability distribution that were determined by the machine using the respective calculated latent variable states;

using the respective first probability distributions and respective second probability distributions for each machine in the collection of machines to model an overall probability distribution relating users of the set of users to items of the set of items; and

recommending items to users using the overall probability distribution.

2. The method of claim 1 wherein the maximum likelihood estimates are determined using an expectation-maximization algorithm.

3. The method of claim 2 wherein the expectation-maximization algorithm is performed for a specified number of iterations.

4. The method of claim 2 wherein the expectation-maximization algorithm is parallelized for the collection of machines using a MapReduce technique.

5. The method of claim 1 wherein the training data further includes event history data, the event history data including (user, item) pairs identifying selections of particular items by particular users.

6. The method of claim 1, further comprising:

receiving a request from a first user in the set of users;

identifying one or more recommended items for a first user using the overall probability distribution; and

presenting the one or more recommended items to the first user.

7. A computer-readable storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

obtaining training data that represents a set of users that includes as members a plurality of users and a set of items that includes as members a plurality of user selectable items;

assigning each of the plurality of users and each of the plurality items to a respective one of a plurality of user groups and item groups;

assigning to each machine in a collection of machines one or more user groups from the plurality of user groups and one or more item groups from the plurality of item groups;

calculating, by each machine, respective latent variable states for each user in the one or more user groups assigned to the machine and respective latent variable states for each item in the one or more item groups assigned to the machine, wherein the calculated latent variable states represent a variational probability distribution relating the user groups and item groups assigned to the respective machine;

determining machine, a respective first probability distribution relating respective latent variable states to users in the one or more user groups assigned to the machine;

determining, using each machine, a respective second probability distribution relating respective latent variable states to items in the one or more item groups assigned to the machine;

determining, using each machine, one or more respective parameter values for the first and second probability distributions that were determined by the machine, wherein determining the parameter values includes determining maximum likelihood estimates for parameters of the first probability distribution and the second probability distribution that were determined by the machine using the respective calculated latent variable states;

using the respective first probability distributions and respective second probability distributions for each machine in the collection of machines to model an overall probability distribution relating users of the set of users to items of the set of items; and

recommending items to users using the overall probability distribution.

8. The computer-readable storage medium of claim 7 wherein the maximum likelihood estimates are determined using an expectation-maximization algorithm.

9. The computer-readable storage medium of claim 8 wherein the expectation-maximization algorithm is performed for a specified number of iterations.

10. The computer-readable storage medium of claim 8 wherein the expectation-maximization algorithm is parallelized for the collection of machines using a MapReduce technique.

11. The computer-readable storage medium of claim 7 wherein the training data further includes event history data, the event history data including (user, item) pairs identifying selections of particular items by particular users.

12. The computer-readable storage medium of claim 7 wherein the operations further comprise:

receiving a request from a first user in the set of users;

identifying one or more recommended items for a first user using the overall probability distribution; and

presenting the one or more recommended items to the first user.

13. A system comprising:

a storage device encoded with instructions; and

data processing apparatus operable to execute the instructions to perform operations comprising;

obtaining training data that represents a set of users that includes as members a plurality of users and a set of items that includes as members a plurality of user selectable items;

assigning each of the plurality of users and each of the plurality items to a respective one of a plurality of user groups and item groups;

assigning to each machine in a collection of machines one or more user groups from the plurality of user groups and one or more item groups from the plurality of item groups;

calculating, by each machine, respective latent variable states for each user in the one or more user groups assigned to the machine and respective latent variable states for each item in the one or more item groups assigned to the machine, wherein the calculated latent variable states represent a variational probability distribution relating the user groups and item groups assigned to the respective machine;

determining, using each machine, a respective first probability distribution relating respective latent variable states to users in the one or more user groups assigned to the machine;

determining, using each machine, a respective second probability distribution relating respective latent variable states to items in the one or more item groups assigned to the machine;

determining, using each machine, one or more respective parameter values for the first and second probability distributions that were determined by the machine, wherein determining the parameter values includes determining maximum likelihood estimates for parameters of the first probability distribution and the second probability distribution that were determined by the machine using the respective calculated latent variable states;

using the respective first probability distributions and respective second probability distributions for each machine in the collection of machines to model an overall probability distribution relating users of the set of users to items of the set of items; and

recommending items to users using the overall probability distribution.

14. The system of claim 13 wherein the maximum likelihood estimates are determined using an expectation-maximization algorithm.

15. The system of claim 14 wherein the expectation-maximization algorithm is performed for a specified number of iterations.

16. The system of claim 14 wherein the expectation-maximization algorithm is parallelized for the collection of machines using a MapReduce technique.

17. The system of claim 13 wherein the training data further includes event history data, the event history data including (user, item) pairs identifying selections of particular items by particular users.

18. The system of claim 13 wherein the operations further comprise:

receiving a request from a first user in the set of users;

identifying one or more recommended items for a first user using the overall probability distribution; and

providing the one or more recommended items to the first user.