Presenting a diversity of recommendations

• US 8,374,985 B1
• Filed: 11/21/2011
• Issued: 02/12/2013
• Est. Priority Date: 02/19/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Garg, Ashutosh, Datar, Mayur
• Primary Examiner(s): Vincent, David R
• Assistant Examiner(s): BUSS, BENJAMIN J
• Application Number:
  US13/300,987
• Time in Patent Office: 449 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, the 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, wherein the score is based in part on a measure of similarity between the first result and the second result, and wherein the score decreases as the measure of similarity increases; and

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

2. The method of claim 1 wherein the maximum conditional interest likelihood score that the user will select the second result assumes that the user does not select the first result.

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 method of claim 1 wherein the measure of similarity between the first result and the second result is based on a history of past user click behavior.

5. The method of claim 4 wherein the history of past user click behavior takes into account user selections of the first result and the second result when the first result is selected within a same time period as the second result.

6. The method of claim 4 wherein the history of past user click behavior takes into account user selections of the first result and the second result when the first result is selected within a same time session as the second result.

7. 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.

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

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2(R1 . . . RK-1, RK)</sup>,

where α

is a value learned from training, β

₀, β

₁ and β

₂ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, and S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1.

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

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)−

β

3Link(R1 . . . RK-1, RK),</sup>

where α

is a value learned from training, β

₀, β

₁, β

₂, and β

₃ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1, and Link(R₁ . . . R_K-1, R_K) is a value based on whether R_K directly links to or is directly linked to by any of R₁ . . . R_K-1.

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

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)−

β

3Link(R1 . . . RK-1, RK)−

β

4Vector(R1 . . . RK-1, RK),</sup>

where α

is a value learned from training, β

₀, β

₁, β

₂, β

₃, and β

₄ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1, Link(R₁ . . . R_K-1, R_K) is a value based on whether R_K directly links to or is directly linked to by any of R₁ . . . R_K-1, and Vector(R₁-R_K-1, R_K) is a value based on whether R_K and any of R₁ . . . R_K-1 are indirectly linked to each other.

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

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

13. A system comprising:

data processing apparatus 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 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, wherein the score is based in part on a measure of similarity between the first result and the second result, and wherein the score decreases as the measure of similarity increases; and

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

14. The system of claim 13 wherein the maximum conditional interest likelihood score that the user will select the second result assumes that the user does not select the first result.

15. The system of claim 14, 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.

16. The system of claim 13 wherein the measure of similarity between the first result and the second result is based on a history of past user click behavior.

17. The system of claim 16 wherein the history of past user click behavior takes into account user selections of the first result and the second result when the first result is selected within a same time period as the second result.

18. The system of claim 16 wherein the history of past user click behavior takes into account user selections of the first result and the second result when the first result is selected within a same time session as the second result.

19. The system of claim 13, 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.

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

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)</sup>,

where α

is a value learned from training, β

₀, β

₁ and β

₂ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, and S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1.

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

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)−

β

3Link(R1 . . . RK-1, RK),</sup>

where α

is a value learned from training, β

₀, β

₁, β

₂, and β

₃ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1, and Link(R₁ . . . R_K-1, R_K) is a value based on whether R_K directly links to or is directly linked to by any of R₁ . . . R_K-1.

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

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)−

β

3Link(R1 . . . RK-1, RK)−

β

4Vector(R1 . . . RK-1, RK),</sup>

where α

is a value learned from training, β

₀, β

₁, β

₂, β

₃, and β

₄ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1, Link(R₁ . . . R_K-1, R_K) is a value based on whether R_K directly links to or is directly linked to by any of R₁ . . . R_K-1, and Vector(R₁-R_K-1, R_K) is a value based on whether R_K and any of R₁ . . . R_K-1 are indirectly linked to each other.

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

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

25. A non-transitory computer-readable storage medium having instructions stored thereon that, when executed by data processing apparatus, cause the data processing apparatus 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 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, wherein the score is based in part on a measure of similarity between the first result and the second result, and wherein the score decreases as the measure of similarity increases; and

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

26. The non-transitory computer-readable storage medium of claim 25 wherein the maximum conditional interest likelihood score that the user will select the second result assumes that the user does not select the first result.

27. The non-transitory computer-readable storage medium of claim 26, 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.

28. The non-transitory computer-readable storage medium of claim 25 wherein the measure of similarity between the first result and the second result is based on a history of past user click behavior.

29. The non-transitory computer-readable storage medium of claim 28 wherein the history of past user click behavior takes into account user selections of the first result and the second result when the first result is selected within a same time period as the second result.

30. The non-transitory computer-readable storage medium of claim 28 wherein the history of past user click behavior takes into account user selections of the first result and the second result when the first result is selected within a same time session as the second result.

31. The non-transitory computer-readable storage medium of claim 25, 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.

32. The non-transitory computer-readable storage medium of claim 25, wherein each conditional interest-likelihood score is calculated according to the formula

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)</sup>,

where α

is a value learned from training, β

₀, β

₁ and β

₂ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, and S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1.

33. The non-transitory computer-readable storage medium of claim 25, wherein each conditional interest-likelihood score is calculated according to the formula

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)−

β

3Link(R1 . . . RK-1, RK),</sup>

where α

is a value learned from training, β

₀, β

₁, β

₂, and β

₃ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1, and Link(R₁ . . . R_K-1, R_K) is a value based on whether R_K directly links to or is directly linked to by any of R₁ . . . R_K-1.

34. The non-transitory computer-readable storage medium of claim 25, wherein each conditional interest-likelihood score is calculated according to the formula

I(R_K|Not(R₁ . . . R_K-1))=α

e<sup>−

β

0−

β

1δ

(RK)−

β

2S(R1 . . . RK-1, RK)−

β

3Link(R1 . . . RK-1, RK)−

β

4Vector(R1 . . . RK-1, RK),</sup>

where α

is a value learned from training, β

₀, β

₁, β

₂, β

₃, and β

₄ are learned bias values, δ

(R_K) is a measure of the inverse likelihood of a user selecting R_K considered in isolation, S(R₁ . . . R_K-1, R_K) is a measure of the similarity between R_K and R₁ through R_K-1, Link(R₁ . . . R_K-1, R_K) is a value based on whether R_K directly links to or is directly linked to by any of R₁ . . . R_K-1, and Vector(R₁-R_K-1, R_K) is a value based on whether R_K and any of R₁ . . . R_K-1 are indirectly linked to each other.

35. The non-transitory computer-readable storage medium of claim 25, wherein the first result has a maximum marginal interest-likelihood score among the set of data objects.

36. The non-transitory computer-readable storage medium of claim 25, wherein the conditional interest-likelihood score is calculated as an empirically determined probability.