Presenting a diversity of recommendations

• US 8,065,254 B1
• Filed: 02/19/2008
• Issued: 11/22/2011
• Est. Priority Date: 02/19/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Datar, Mayur, Garg, Ashutosh
• Primary Examiner(s): Gaffin; Jeffrey A
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US12/033,540
• Time in Patent Office: 1,372 Days
• Field of Search: 706/12, 706/46
• US Class Current: 706/46
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

Methods, systems and apparatus, including computer program products, for providing a diversity of recommendations. According to one method, results are identified so as to increase the likelihood that at least one result will be of interest to a user. Following the identification of a first result, second and later results are identified based on an assumption that the previously identified results are not of interest to the user. The identification of diverse results can be based on formulas that approximate the probability or provide a likelihood score of a user selecting a given result, where a measured similarity between a given object and previously identified results tends to decrease the calculated probability approximation or likelihood score for that object.

Claims

1. A computer-implemented method, comprising:

identifying K results from among a set of data objects, K being an integer greater than 2, wherein identifying K results comprises;

identifying from among the data objects in the set of objects a first result of the K results and first remaining data objects, the first result being one data object of the set of data objects and the first remaining data objects being the set of data objects excluding the first result; and

then

identifying from among the first remaining data objects a second result of the K results having a maximum conditional interest-likelihood score that a user will select the second result given that the user does not select the first result; and

providing the K results as recommendations to the user including the first result and the second result.

2. The computer-implemented method of claim 1, wherein K is at least 3, and wherein identifying K results further comprises:

identifying second remaining data objects, the second remaining data objects being the first remaining data objects excluding the second result; and

identifying from among the second remaining data objects a third result having a maximum conditional interest-likelihood score that the user will select the third result given that the first result and the second result are not selected.

3. The computer-implemented method of claim 2, wherein K is greater than 3, and wherein identifying K results further comprises:

identifying (K−

1)st remaining data objects, the (K−

1)st remaining data objects being the first remaining data objects excluding the second through the (K−

1)st results; and

identifying from among the (K−

1)st remaining data objects a Kth result having a maximum conditional interest-likelihood score that the user will select the Kth result given that the first result through the (K−

1)st results are not selected.

4. The computer-implemented method of claim 1, wherein each conditional interest-likelihood score is calculated according to the formula

5. The computer-implemented method of claim 1, wherein each conditional interest-likelihood score is calculated according to the formula

6. The computer-implemented method of claim 1, wherein each conditional interest-likelihood score is calculated according to the formula

7. The computer-implemented method of claim 1, wherein each conditional interest-likelihood score is calculated according to the formula

8. The computer-implemented method of claim 1, wherein the first result has a maximum marginal interest-likelihood score among the set of data objects.

9. The computer-implemented method of claim 1, wherein the conditional interest-likelihood score is calculated based on a measure of similarity between the respective remaining data objects and the first result.

10. The computer-implemented method of claim 1, wherein the conditional interest-likelihood score is calculated as an empirically determined probability.

11. A computer-implemented method, for identifying K results from among a set of data objects, where K is an integer greater than 2, the method comprising:

determining K results from among the set of data objects that give the expression

I_TOTAL=I(select R₁)+I(select R₂ given no selection of R₁)+ . . . +I(select R_K given no selection of any of R₁ . . . R_K-1)

a maximum value, wherein each R_i is a distinct result in the set of data objects, I(select R₁) is a calculated interest-likelihood score representing a likelihood that a user will select R₁ from a list of presented results, I(select R₂ given no selection of R₁) is a calculated interest-likelihood score representing a likelihood that the user will select R₂ given that the user does not select R₁, and I(select R_K given no selection of any of R₁ . . . R_K-1) is a calculated interest-likelihood score representing a likelihood that the user will select R_K given that the user does not select R₁ through R_K-1; and

providing the K results as recommendations to the user.

12. The computer-implemented method of claim 11, wherein the term I(select R₁) is an empirically determined marginal selection probability.

13. The computer-implemented method of claim 12, wherein the term I(select R₁) is calculated according to the equation

14. The computer-implemented method of claim 13, wherein the term I(select R₂ given no selection of R₁) is an empirically-determined conditional selection probability.

15. The computer-implemented method of claim 14, wherein the term I(interest in R₂ given no selection of R₁ is calculated according to the equation

16. The computer-implemented method of claim 12, wherein the term I(select R_K given no selection of any of R₁ . . . R_K-1) is an empirically determined conditional selection probability.

17. The computer-implemented method of claim 16, wherein the term I(select R_K given no selection of any of R₁ . . . R_K-1) is calculated according to the equation

18. The computer-implemented method of claim 11, wherein user selections comprise user clicks.

19. A system comprising:

one or more computers programmed to perform operations comprising;

identifying K results from among a set of data objects, K being an integer greater than 2, wherein identifying K results comprises;

identifying from among the data objects in the set of data objects a first result of the K results and first remaining data objects, the first result being one data object of the set of data objects and the first remaining data objects being the set of data objects excluding the first result; and

then

identifying from among the first remaining data objects a second result of the K results having a maximum conditional interest-likelihood score that a user will select the second result given that the user does not select the first result; and

providing the K results as recommendations to the user including the first result and the second result.

20. The system of claim 19, wherein K is at least 3, and wherein identifying K results further comprises:

identifying second remaining data objects, the second remaining data objects being the first remaining data objects excluding the second result; and

identifying from among the second remaining data objects a third result having a maximum conditional interest-likelihood score that a user will select the third result given that the first result and the second result are not selected.

21. The system of claim 20, wherein K is greater than 3, and wherein identifying K results further comprises:

identifying (K−

1)st remaining data objects, the (K−

1)st remaining data objects being the first remaining data objects excluding the second through the (K−

1)st results; and

identifying from among the (K−

1)st remaining data objects a Kth result having a maximum conditional interest-likelihood score that a user will select the Kth result given that the first result through the (K−

1)st results are not selected.

22. The system of claim 19, wherein the conditional interest-likelihood score is calculated according to the formula

23. The system of claim 19, wherein the conditional interest-likelihood score is calculated according to the formula

24. The system of claim 19, wherein the interest-likelihood score is calculated as an empirically determined probability.

25. The system of claim 19, wherein each conditional interest-likelihood score is calculated according to the formula

26. The system of claim 19, wherein each conditional interest-likelihood score is calculated according to the formula

27. The system of claim 19, wherein the first result has a maximum marginal interest-likelihood score among the set of data objects.

28. The system of claim 19, wherein the conditional interest-likelihood score is calculated based on a measure of similarity between the respective remaining data objects and the first result.

29. A computer program product, encoded on a computer readable medium, operable to cause data processing apparatus to perform operations to identify K results from among a set of data objects, where K is an integer greater than 2, the operations comprising:

determining K results from among the set of data objects that give the expression

I_TOTAL=I(select R₁)+I(select R₂ given no selection of R₁)+ . . . +I(select R_K given no selection of any of R₁ . . . R_K-1)

a maximum value, wherein each R_i is a distinct result in the set of data objects, I(select R₁) is a calculated interest-likelihood score representing a likelihood that a user will select R₁ from a list of presented results, I(select R₂ given no selection of R₁) is a calculated interest-likelihood score representing a likelihood that the user will select R₂ given that the user does not select R₁, and I(select R_K given no selection of any of R₁ . . . R_K-1) is a calculated interest-likelihood score representing a likelihood that the user will select R_K given that the user does not select R₁ through R_K-1; and

providing the K results as recommendations to the user.

30. The computer program product of claim 29, wherein the term I(select R₁) is an empirically determined marginal selection probability.

31. The computer program product of claim 30, wherein the term I(select R₁) is calculated according to the equation

32. The computer program product of claim 31, wherein the term I(select R₂ given no selection of R₁) is an empirically-determined conditional selection probability.

33. The computer program product of claim 32, wherein the term I(interest in R₂ given no selection of R₁) is calculated according to the equation

34. The computer program product of claim 30, wherein the term I(select R_K given no selection of any of R₁ . . . R_K-1) is an empirically determined conditional selection probability.

35. The computer program product of claim 34, wherein the term I(select R_K given no selection of any of R₁ . . . R_K-1) is calculated according to the equation

36. The computer program product of claim 29, wherein user selections comprise user clicks.

37. A system comprising:

one or more computers programmed to perform operations to identify K results from among a set of data objects, where K is an integer greater than 2, the operations comprising;

determining K results from among the set of data objects that give the expression

I_TOTAL=I(select R₁)+I(select R₂ given no selection of R₁)+ . . . +I(select R_K given no selection of any of R₁ . . . R_K−

)

a maximum value, wherein each R_i is a distinct result in the set of data objects, I(select R₁) is a calculated interest-likelihood score representing a likelihood that a user will select R₁ from a list of presented results, I(select R₂ given no selection of R₁) is a calculated interest-likelihood score representing a likelihood that the user will select R₂ given that the user does not select R₁, and I(select R_K given no selection of any of R₁ . . . R_K-1) is a calculated interest-likelihood score representing a likelihood that the user will select R_K given that the user does not select R₁ through R_K-1; and

providing the K results as recommendations to the user.

38. The system of claim 37, wherein the term I(select R₁) is an empirically determined marginal selection probability.

39. The system of claim 38, wherein the term I(select R₁) is calculated according to the equation

40. The system of claim 39, wherein the term I(select R₂ given no selection of R₁) is an empirically-determined conditional selection probability.

41. The system of claim 40, wherein the term I(interest in R₂ given no selection of R₁) is calculated according to the equation

42. The system of claim 38, wherein the term I(select R_K given no selection of any of R₁ . . . R_K-1) is an empirically determined conditional selection probability.

43. The system of claim 42, wherein the term I(select R_K given no selection of any of R₁ . . . R_K-1) is calculated according to the equation

44. The system of claim 37, wherein user selections comprise user clicks.