Method and system for high performance model-based personalization

• US 7,788,123 B1
• Filed: 06/25/2001
• Issued: 08/31/2010
• Est. Priority Date: 06/23/2000
• Status: Active Grant

• Current Assignee: Thalveg Data Flow LLC (Intellectual Ventures LLC)
• Original Assignee: Thalveg Data Flow LLC (Intellectual Ventures LLC)
• Inventors: Ekhaus, Michael A., Driskill, Robert, Mulier, Filip
• Primary Examiner(s): Sterrett; Jonathan G
• Application Number:
  US09/887,528
• Time in Patent Office: 3,354 Days
• Field of Search: 705/10
• US Class Current: 705/26.7
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

The present invention relates to a method and system for generating client preference recommendations in a high performance computing regime. Accordingly, one embodiment of the present invention comprises: providing a sparse ratings matrix, forming a plurality of data structures representing the sparse ratings matrix, forming a runtime recommendation model from the plurality of data structures, determining a recommendation from the runtime recommendation model in response to a request from a user, and providing the recommendation to the user.

Claims

1. A method of preparing a user recommendation comprising:

generating, in memory, a sparse unary ratings matrix from users'"'"' selected preferences, wherein each user'"'"'s selected preferences are represented as unary data entries in said sparse unary ratings matrix, wherein each unary data entry has a value of either zero or one;

forming in at least one data processing device a plurality of data structures representing said sparse unary ratings matrix, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

forming in the at least one data processing device a runtime recommendation model from said plurality of data structures;

determining in the at least one data processing device a recommendation from said runtime recommendation model in response to a request for a recommendation; and

providing said recommendation in response to said request.

2. The method of claim 1 further comprising calculating a unary multiplicity voting recommendation from said runtime recommendation model.

3. The method claim 1 further comprising calculating a non-unary multiplicity voting recommendation from said runtime recommendation model.

4. The method of claim 2 wherein said calculating a unary multiplicity voting recommendation comprises calculating an anonymous recommendation.

5. The method of claim 2 wherein said calculating a unary multiplicity voting recommendation comprises calculating a personalized recommendation.

6. The method of claim 3 wherein said calculating a non-unary multiplicity voting recommendation comprises calculating an anonymous recommendation.

7. The method of claim 3 wherein said calculating a non-unary multiplicity voting recommendation comprises calculating a personalized recommendation.

8. The method of claim 1,

wherein said forming a runtime recommendation model from said plurality of data structures comprises:

mapping said sparse unary ratings matrix into a plurality of sub-space ratings matrices, said mapping comprising multiplying said unary ratings matrices by a mappings matrix between said unary ratings matrices and a plurality of categories, and wherein each of said sub-space ratings matrices corresponds to one of said plurality of categories.

17. The method of claim 1, wherein forming a runtime recommendation model from a plurality of data structures, comprises:

forming a first recommendation model from said plurality of data structures; and

perturbing said first recommendation model to generate a runtime recommendation model.

18. The method of claim 1, wherein forming a runtime recommendation model from a plurality of data structures, comprises:

forming a first recommendation model from said plurality of data structures;

truncating said first recommendation model to generate a runtime recommendation model.

28. The method of claim 1, wherein the matrix of co-rates is an item-item matrix of co-rates.

29. The method of claim 1, wherein the matrix of co-rates is a client-client matrix of co-rates.

32. The method of claim 1, wherein said forming a runtime recommendation model includes using a formulation:

Unary_Multi_Vote(i,j)_k′

(R_u,*,k)=TOP_k′

(<sub>zε

Ru,*</sub>Σ

(_(I-I)M(i,j)^r(k)_z,*)), and

wherein TOP_k′

returns a maximum of k′

values of its argument,

_(I-I)M=R^tR,

R is the sparse unary ratings matrix,

R^t is the transpose of the sparse unary ratings matrix,

R_u,* is a row in the sparse unary ratings matrix for client u,

zε

Ru,* indicates performing the formulation over a set of values in the row in the sparse unary ratings matrix for client u, and

k is a number of neighbors.

9. A method of preparing a user recommendation comprising:

generating, in memory, a sparse unary ratings matrix including ratings data represented as unary data entries, wherein each unary data entry has a value of either zero or one;

providing in a recommendation system including at least one data processing device an update ratings data structure;

forming at the at least one data processing device a plurality of data structures representing said sparse unary ratings matrix, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

forming in the at least one data processing device a runtime recommendation model from said plurality of data structures and said update ratings data structure;

determining at the recommendation system a recommendation from said runtime recommendation model in response to a request for a recommendation; and

providing said recommendation in response to said request.

10. The method of claim 9 further comprising calculating a unary multiplicity voting recommendation from said runtime recommendation model.

11. The method of claim 9 further comprising calculating a non-unary multiplicity voting recommendation from said runtime recommendation model.

12. The method of claim 10 wherein said calculating a unary multiplicity voting recommendation comprises calculating an anonymous recommendation.

13. The method of claim 10 wherein said calculating a unary multiplicity voting recommendation comprises calculating a personalized recommendation.

14. The method of claim 11 wherein said calculating a non-unary multiplicity voting recommendation comprises calculating an anonymous recommendation.

15. The method of claim 11 wherein said calculating a non-unary multiplicity voting recommendation comprises calculating a personalized recommendation.

16. The method of claim 9, further comprising:

mapping said sparse unary ratings matrix into a plurality of sub-space ratings matrices, said mapping comprising multiplying said unary ratings matrices by a mapping matrix between said unary ratings matrices and a plurality of categories, and each of said sub-space ratings matrices corresponding to one of said plurality of categories.

19. A method of preparing a user recommendation, comprising:

receiving at a first recommendation system, including a data processing device, a runtime recommendation model from a second recommendation system, wherein the runtime model is formed from a plurality of data structures representing a unary array of ratings entries that can be arithmetically manipulated, wherein each unary data entry has a value of either zero or one, wherein a majority of the entries in the array are zero, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

receiving at the first recommendation system a request for a recommendation;

generating in the data processing device of the first recommendation system a recommendation using the received runtime recommendation model; and

transmitting the recommendation.

20. The method of claim 19, wherein said generating a recommendation comprises:

calculating a unary multiplicity voting recommendation from the received runtime recommendation model; and

generating an anonymous recommendation.

21. The method of claim 19, wherein said generating a recommendation comprises:

calculating a unary multiplicity voting recommendation from the received runtime recommendation model; and

generating a personalized recommendation.

22. The method of claim 19, wherein said generating a recommendation comprises:

calculating a non-unary multiplicity voting recommendation from the received runtime recommendation model; and

generating an anonymous recommendation.

23. The method of claim 19, wherein said generating a recommendation comprises:

calculating a non-unary multiplicity voting recommendation from the received runtime recommendation model; and

generating a personalized recommendation.

24. A method for generating a runtime recommendation model comprising:

retrieving at a first recommendation system, including a data processing device, a unary array of ratings entries that can be arithmetically manipulated, wherein data in the unary array of ratings entries is unary data, wherein each unary data entry has a value of either zero or one, and wherein a majority of the entries in the array are zero;

receiving at the first recommendation system an update to the unary array of ratings entries;

generating in the data processing device of the first recommendation system the runtime recommendation model from a plurality of data structures representing the unary array of ratings entries, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix; and

providing the runtime recommendation model from the first recommendation system to a second recommendation system, wherein the second recommendation system generates a recommendation using the runtime recommendation model.

25. A data processing device, comprising:

a processor configured to generate in memory a sparse unary ratings matrix from users'"'"' selected preferences, wherein each user'"'"'s selected preferences are represented as unary data entries in said sparse unary ratings matrix, wherein each unary data entry has a value of either zero or one;

wherein the processor is configured to form a plurality of data structures representing said sparse unary ratings matrix, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

wherein the processor is configured to store said plurality of data structures in the memory;

wherein the processor is configured to form a runtime recommendation model from said plurality of data structures; and

wherein the processor is configured to determine a recommendation from said runtime recommendation model in response to a request for a recommendation.

26. A data processing device comprising:

means for generating in memory a sparse unary ratings matrix from users'"'"' selected preferences, wherein each user'"'"'s selected preferences are represented as unary data entries in said sparse unary ratings matrix, wherein each unary data entry has a value of either zero or one, and wherein a majority of the entries in said sparse unary ratings matrix are zero;

means for forming a plurality of data structures representing said sparse unary ratings matrix, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

means for storing said plurality of data structures in the memory;

means for forming a runtime recommendation model from said plurality of data structures; and

means for determining a recommendation from said runtime recommendation model in response to a request for a recommendation.

27. An article of manufacture including a computer-readable storage medium having stored thereon computer-executable instructions, execution of which by a processing device, causes the processing device to perform operations comprising:

generating in memory a sparse unary ratings matrix from users'"'"' selected preferences, wherein each user'"'"'s selected preferences are represented as unary data entries in said sparse unary ratings matrix, wherein each unary data entry has a value of either zero or one;

forming a plurality of data structures representing said sparse unary ratings matrix, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

forming a runtime recommendation model from said plurality of data structures; and

determining a recommendation from said runtime recommendation model in response to a request for a recommendation.

30. A method of preparing a user recommendation comprising:

generating, in memory, a sparse unary ratings matrix from users'"'"' selected preferences;

forming in at least one data processing device a plurality of data structures representing said sparse unary ratings matrix, wherein the plurality of data structures includes a matrix of co-rates, and wherein the matrix of co-rates includes either a pre-multiplication of the sparse unary ratings matrix by a transpose of the sparse unary ratings matrix or a post-multiplication of the sparse unary ratings matrix by the transpose of the sparse unary ratings matrix;

forming in the at least one data processing device a runtime recommendation model from said plurality of data structures;

determining in the at least one data processing device a recommendation from said runtime recommendation model in response to a request for a recommendation; and

providing the recommendation in response to the request.

31. The method of claim 30, wherein said forming a runtime recommendation model includes using a formulation:

Unary_Multi_Vote(i,j)_k′

(R_u,*,k)=TOP_k′

(<sub>zε

Ru,*</sub>Σ

(_(I-I)M(i,j)^r(k)_z,*)), and

wherein

TOP_k′

returns a maximum of k′

values of its argument,

_(I-I)M=R^tR, wherein

R is the sparse unary ratings matrix, and

R^t is the transpose of the sparse unary ratings matrix,

R_u,* is a row in the sparse unary ratings matrix for client u,

zε

Ru,* indicates performing the formulation over a set of values in the row in the sparse unary ratings matrix for client u, and

k is a number of neighbors.