System and method for using noisy collaborative filtering to rank and present items

• US 6,321,179 B1
• Filed: 06/29/1999
• Issued: 11/20/2001
• Est. Priority Date: 06/29/1999
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Glance, Natalie S., Dardenne, Manfred
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Pretlow, Demetrius
• Application Number:
  US09/343,118
• Time in Patent Office: 875 Days
• Field of Search: 702/81-84, 702/108, 702/122, 702/123, 702/179, 702/181, 702/182, 702/183, 702/188, 702/190, 702/193, 702/196, 702/197, 709/223, 709/224, 709/225, 708/300, 708/301, 708/303, 708/432, 705/2, 705/7, 705/14, 705/10, 705/26
• US Class Current: 702/189
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04N 21/252 Processing of multiple end-users' preferences to derive collaborative data

Abstract

A system and method of providing predicted user ratings includes calculating the accuracy of predictions based on the variance of distribution of the predicted user'"'"'s rating. The system and method present and rank the results by treating the variance as a source of noise. The decision to present or not to present an item is made by sampling the probability distribution of the predicted rating and comparing the result to some user-set threshold (e.g., “show me all results that the system predicts I will score 3 or higher”) or a system default value.

Claims

1. A collaborative filtering system for predicting a user'"'"'s rating for an item, comprising:

a memory storing;

a set of correlation coefficients, wherein each correlation coefficient is a measure of similarity in ratings between pairs of users in the system who have rated a particular item; and

ratings for the item made by other users in the system; and

a processor, responsive to a request for a predicted user'"'"'s rating for the item, for calculating the predicted user'"'"'s rating, wherein predicted user'"'"'s rating is the sum of the product of a rating and its respective correlation coefficient divided by the sum of the correlation coefficients, and for calculating the variance of the predicted user'"'"'s rating, wherein the variance of the predicted user'"'"'s rating is a function of the variance of the correlation coefficients and the variance of the ratings.

2. The system of claim 1, wherein the processor calculates the predicted user'"'"'s rating of an item i for a user X, Pⁱ_x in accordance with the relationship:

$P_x^i=P_0+\frac{\underset{y<br><br>\text{\hspace{1em}<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{raters}}{\sum <br><br>}<br><br>\left(S_y^i-P_0\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}}{\underset{y}{\sum <br><br>}<br><br><br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>},$

where Sⁱ_y is the rating of each user Y who has rated the item i, P₀ is a predetermined value and α

_xy is the correlation coefficient between the user X and user Y.

3. The system of claim 2, wherein the processor calculates the variance of the predicted user'"'"'s rating, Var(Pⁱ_x), in accordance with the relationship:

$\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\underset{y}{\sum <br><br>}<br><br>{\left(\frac{\partial <br><br>P_x^i}{\partial <br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}}\right)}^2<br><br>\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}})+\underset{y}{\sum <br><br>}<br><br>{\left(\frac{\partial <br><br>P_x^i}{\partial <br><br>S_y^i}\right)}^2<br><br>\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>S_y^i).$

4. The system of claim 2, wherein the processor calculates the variance of the predicted user'"'"'s rating, Var(Pⁱ_x), in accordance with the relationship:

$\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\frac{\underset{y}{\sum <br><br>}<br><br>K_y^2/N_{\mathrm{xy}}}{(\underset{y}{\sum <br><br>}<br><br>{<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>}^2}+\frac{\underset{y}{\sum <br><br>}<br><br>{\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2<br><br>{\mathrm{\sigma <br><br>}}_y^2}{\underset{y}{\sum <br><br>}<br><br>{<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>}^2},$

where the range of ratings varies from 0 to 2S_A, K_y=(S_yⁱ−

S_A)−

sign(α

_xy)×

(P_xⁱ−

S_A) and is bounded by [6S_A,2S_A].

5. The system of claim 4, wherein the processor provides the predicted user'"'"'s rating when the predicted user'"'"'s rating calculation exceeds a predetermined threshold value and provides the variance as a range about the predicted user'"'"'s rating.

6. The system of claim 1, wherein the processor, responsive to a user set threshold rating value, provides the predicted user rating and variance to the user when the predicted user rating is greater than the threshold rating value.

7. The system of claim 1, wherein the processor ranks and presents items to the user by estimating the distribution of the prediction rating as a normal distribution with expected value given by the calculated predicted user'"'"'s rating and variance by the calculated variance of the predicted user'"'"'s rating.

8. The system of claim 1, wherein the processor ranks and presents items to the user by estimating the distribution of the prediction rating from empirically determined usage data and using the observed distribution with expected value given by the calculated predicted user'"'"'s rating and variance by the calculated variance of the predicted user'"'"'s rating.

9. The system of claim 1, wherein the processor ranks and presents items to the user by sampling the probability distribution of the predicted user'"'"'s rating and presents the predicted user'"'"'s rating when the probability distribution is greater than a user set threshold value.

10. The system of claim 9, wherein the probability that the predicted score is greater than the user set threshold value r₀ is given by the probability that the expected user'"'"'s predicted rating is greater than r₀:

$\mathrm{\rho <br><br>}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\frac{1}{2}<br><br>\left\{1+\mathrm{erf}<br><br>\text{\hspace{1em}<br><br>}\left[\frac{P_x^i-r_0}{\sqrt{2<br><br>\text{\hspace{1em}<br><br>}}<br><br>\mathrm{\sigma <br><br>}}\right]\right\}.$

11. The system of claim 1, wherein the set of correlation coefficients comprises a set of initial correlation coefficients α

_xy(0), wherein each initial correlation coefficient is an assumed measure of similarity between pairs of users in the system; and

wherein the processor, responsive to a rating for an item, uses the received rating to update the user'"'"'s correlation coefficients with the other users.

12. A method of predicting a user'"'"'s rating for an item in a collaborative filtering system, comprising:

providing a set of correlation coefficients, wherein each correlation coefficient is a measure of the similarity in ratings between pairs of users who have rated a particular item;

providing ratings for the item made by other users in the system;

calculating a predicted user rating for the item, wherein the predicted rating comprises the sum of the product of a rating and its respective correlation coefficient divided by the sum of the correlation coefficients; and

calculating a variance of the predicted rating, wherein the variance of the predicted rating is a function of the variance of the correlation coefficients and the variance of the ratings.

13. The method of claim 12, wherein the predicted user'"'"'s rating of an item i for a user X, Pⁱ_x, is calculated in accordance with the relationship:

$P_x^i=P_0+\frac{\underset{y<br><br>\text{\hspace{1em}<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{raters}}{\sum <br><br>}<br><br>\left(S_y^i-P_0\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}}{\underset{y}{\sum <br><br>}<br><br><br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>},$

where Sⁱ_y is the rating of each user Y who has rated the item i, P₀ is a predetermined value and α

_xy is the correlation coefficient between the user X and user Y.

14. The method of claim 13, wherein the variance of the predicted user'"'"'s rating, Var(Pⁱ_x), is calculated in accordance with the relationship:

$\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\underset{y}{\sum <br><br>}<br><br>{\left(\frac{\partial <br><br>P_x^i}{\partial <br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}}\right)}^2<br><br>\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}})+\underset{y}{\sum <br><br>}<br><br>{\left(\frac{\partial <br><br>P_x^i}{\partial <br><br>S_y^i}\right)}^2<br><br>\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>S_y^i).$

15. The method of claim 13, wherein the variance of the predicted user'"'"'s rating, Var(Pⁱ_x), is calculated in accordance with the relationship:

$\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\frac{\underset{y}{\sum <br><br>}<br><br>K_y^2/N_{\mathrm{xy}}}{(\underset{y}{\sum <br><br>}<br><br>{<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>}^2}+\frac{\underset{y}{\sum <br><br>}<br><br>{\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2<br><br>{\mathrm{\sigma <br><br>}}_y^2}{\underset{y}{\sum <br><br>}<br><br>{<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>}^2},$

where the range of ratings varies from 0 to 2S_A, K_y=(S_yⁱ−

S_A)−

sign(α

_xy)×

(P_xⁱ−

S_A) and is bounded by [6S_A,2S_A].

16. The method of claim 15, further comprising:

providing the predicted user'"'"'s rating when the predicted user'"'"'s rating calculation exceeds a predetermined threshold value; and

providing the variance as a range about the predicted user'"'"'s rating.

17. The method of claim 12, further comprising:

providing a user set threshold rating value; and

providing the predicted user rating and variance to the user when the predicted user rating is greater than the threshold rating value.

18. The method of claim 12, further comprising:

providing a set of initial correlation coefficients α

_xy(0), wherein each initial correlation coefficient is an assumed measure of similarity between pairs of users in the system; and

responsive to receipt of a rating for an item, using the received rating to update the user'"'"'s correlation coefficients with the other users.

19. A method of ranking items to be presented to a user in a collaborative filtering system, comprising:

providing a set of correlation coefficients, wherein each correlation coefficient is a measure of the similarity in ratings between pairs of users who have rated a particular item;

providing ratings for the item made by other users in the system;

calculating a predicted user rating for the item, wherein the predicted rating comprises the sum of the product of a rating and its respective correlation coefficient divided by the sum of the correlation coefficients;

calculating a variance of the predicted rating, wherein the variance of the predicted rating is a function of the variance of the correlation coefficients and the variance of the ratings;

sampling the probability distribution of the predicted user'"'"'s rating; and

presenting the predicted user'"'"'s rating when the value sampled from the probability distribution is greater than a predetermined threshold value.

20. The method of claim 19, wherein the predicted user'"'"'s rating of an item i for a user X, Pⁱ_x, is calculated in accordance with the relationship:

$P_x^i=P_0+\frac{\underset{y<br><br>\text{\hspace{1em}<br><br>}\in <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{raters}}{\sum <br><br>}<br><br>\left(S_y^i-P_0\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}}{\underset{y}{\sum <br><br>}<br><br><br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>},$

where Sⁱ_y is the rating of each user Y who has rated the item i, P₀ is a predetermined value and α

_xy is the correlation coefficient between the user X and user Y.

21. The method of claim 20, wherein the variance of the predicted user'"'"'s rating, Var(Pⁱ_x), is calculated in accordance with the relationship:

$\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\underset{y}{\sum <br><br>}<br><br>{\left(\frac{\partial <br><br>P_x^i}{\partial <br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}}\right)}^2<br><br>\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}})+\underset{y}{\sum <br><br>}<br><br>{\left(\frac{\partial <br><br>P_x^i}{\partial <br><br>S_y^i}\right)}^2<br><br>\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>S_y^i).$

22. The method of claim 20, wherein the variance of the predicted user'"'"'s rating, Var(Pⁱ_x), is calculated in accordance with the relationship:

$\mathrm{Var}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\frac{\underset{y}{\sum <br><br>}<br><br>K_y^2/N_{\mathrm{xy}}}{(\underset{y}{\sum <br><br>}<br><br>{<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>}^2}+\frac{\underset{y}{\sum <br><br>}<br><br>{\mathrm{\sigma <br><br>}}_{\mathrm{xy}}^2<br><br>{\mathrm{\sigma <br><br>}}_y^2}{\underset{y}{\sum <br><br>}<br><br>{<br><br>{\mathrm{\alpha <br><br>}}_{\mathrm{xy}}<br><br>}^2},$

where the range of ratings varies from 0 to 2S_A, K_y=(S_yⁱ−

S_A)−

sign(α

_xy)×

(P_xⁱ−

S_A) and is bounded by [6S_A,2S_A].

23. The method of claim 19, wherein the probability that the predicted score is greater than a user set threshold value r₀ is given by the probability that the expected predicted user'"'"'s rating is greater than r₀:

$\mathrm{\rho <br><br>}(\text{\hspace{1em}<br><br>}<br><br>P_x^i)=\frac{1}{2}<br><br>\left\{1+\mathrm{erf}<br><br>\text{\hspace{1em}<br><br>}\left[\frac{P_x^i-r_0}{\sqrt{2<br><br>\text{\hspace{1em}<br><br>}}<br><br>\mathrm{\sigma <br><br>}}\right]\right\}.$