On-line recommender system

• US 20040158497A1
• Filed: 02/06/2003
• Published: 08/12/2004
• Est. Priority Date: 02/06/2003
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Brand, Matthew E.
• Granted Patent: US 7,475,027 B2
• Time in Patent Office: Days
• US Class Current: 705/26
• 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/0253 During e-commerce, i.e. online transactions
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

A method and system recommends items such as products and services to consumers. Rating on items are received from consumers as a sequential stream of data. A thin singular value decomposition is updated, one rating at the time, while receiving the ratings. A prediction of a recommendations of particular items for a particular consumer is based on the updated singular value decomposition while receiving the ratings and updating the singular value decomposition. The ratings are discarded after the updating so that a size, structure, and content of an underlying preference matrix is unknown.

Claims

1. A method for recommending items to consumers in a recommender system, comprising:

receiving a stream of rating on items from consumers;

updating sequentially a singular value decomposition, one rating at the time, while receiving the ratings; and

predicting recommendations of particular items for a particular consumer based on the updated singular value decomposition while receiving the ratings and updating the singular value decomposition.

2. The method of claim 1 further comprising:

receiving the stream of ratings asynchronously in a random order.

3. The method of claim 1 wherein the updating further comprises:

adding, changing, and retracting the ratings from the singular value decomposition.

4. The method of claim 1 further comprising:

discarding the ratings after the updating so that a size, structure, and content of an underlying preference matrix is unknown.

5. The method of claim 1 wherein the updating is a sequential rank-1 update of the singular value decomposition to produce a thin SVD.

6. The method of claim 5 wherein the singular value decomposition factors a matrix X into two orthogonal matrices U and V, and a diagonal matrix S≐

diag(s), such that USV^T=X, and U^TXV=S, where ^T represents the SVD transform, the elements of s are singular values and columns of U and V are left and right singular vectors, respectively, and further comprising;

arranging non-negative elements on the diagonal of S in descending order, and a first non-zero element in each column of U is positive so that the thin SVD is unique.

7. The method of claim 6 further comprising:

discarding all but a predetermined number of the r largest singular values and the corresponding singular vectors so that a product of the resulting thinned matrices, U′

S′

V′

=X, is a best rank-r approximation of X in a least-squares sense, and a matrix U′

^TX=S′

V′

^T.

8. The method of claim 7 wherein a projection of X onto r orthogonal axes, specified by the columns of U′

is a reduced-dimension representation of the ratings.

9. The method of claim 8 wherein X represents a tabulation of the ratings, an a subspace spanned by the columns of U′

is interpreted as an r-dimensional consumer taste space.

10. The method of claim 9 wherein individual consumers are located in the taste space according to a similarity of their ratings, and a relationship between the ratings of the particular consumer is represented as a column vector c, and a corresponding taste-space location p is c=U′

p, and p=U′

^Tc.

11. The method of claim 9 wherein a product taste space is the vector V′

, and the taste space contains items arranged according to the consumers.

12. The method of claim 1 further comprising:

translating the ratings to center the ratings on an origin of the singular value decomposition.

13. The method of claim 12 further comprising:

interpreting singular value decomposition as a Gaussian covariance model of the ratings that express correlations between the ratings of the consumers.

14. The method of claim 7 where for column vectors a and b, and the thin SVD USV^T=X, the updating determines the singular value decomposition of X+ab^T, where column b is a binary vector indicating which columns are updated, and column a is derived from the ratings.

16. The method of claim 1 further comprising:

displaying the recommendation in real-time while receiving and updating.

17. The method of claim 1 wherein the receiving, updating, and predicting are executed in a client computer.

18. The method of claim 17 further comprising:

executing the receiving, updating, and predicting in a plurality of client computers connected via a network to enable a distributed and decentralized recommender system.

19. The method of claim 1 wherein the receiving, updating and predicting are all performed on-line, and in real-time.

15. The method of claim wherein all truncated singular values have a small predetermined threshold value ε

.

20. A system for recommending items to consumers in a recommender system, comprising:

means for receiving a stream of rating on items from consumers;

means for updating sequentially a singular value decomposition, one rating at the time, while receiving the ratings; and

means for predicting recommendations of particular items for a particular consumer based on the updated singular value decomposition while receiving the ratings and updating the singular value decomposition.