ENHANCED MATCHING THROUGH EXPLORE/EXPLOIT SCHEMES

• US 20100121624A1
• Filed: 11/07/2008
• Published: 05/13/2010
• Est. Priority Date: 11/07/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Ramakrishnan, Raghunath, Agarwal, Deepak K., Roy, H. Scott, Chen, Bee-Chung, Elango, Pradheep, Chu, Wei, Motgi, Nitin
• Granted Patent: US 8,244,517 B2
• Time in Patent Office: Days
• US Class Current: 703/6
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

Content items are selected to be displayed on a portal page in such a way as to maximize a performance metric such as click-through rate. Problems relating to content selection are addressed, such as changing content pool, variable performance metric, and delay in receiving feedback on an item once the item has been displayed to a user. An adaptation of priority-based schemes for the multi-armed bandit problem are used to project future trends of data. The adaptation introduces experiments concerning a future time period into the calculation, which increases the set of data on which to solve the multi-armed bandit problem. Also, a Bayesian explore/exploit method is formulated as an optimization problem that addresses all of the issues of content item selection for a portal page. This optimization problem is modified by Lagrange relaxation and normal approximation, which allow computation of the optimization problem in real time.

Claims

1. A computer-implemented method comprising:

simulating user behavior pertaining to a specified future time period,

wherein the simulating is based on an observed user behavior, and

wherein the simulating produces first simulated data;

selecting an item of a plurality of items during the specified future time period based on the first simulated data; and

presenting the item to a user.

2. The computer-implemented method of claim 1, wherein the observed user behavior comprises a number of times the plurality of items have been viewed by a plurality of users and the number of times each item of the plurality of items has been clicked.

3. The computer-implemented method of claim 1, wherein the step of simulating user behavior further comprises:

calculating a probability that a particular item of the plurality of items will maximize a performance metric;

selecting the particular item based on the probability;

recording, in connection with the particular item at the first simulated data, a hypothetical view; and

recording, in connection with the particular item at second simulated data, a value based on a probability that a user of the plurality of users would click on the particular item.

4. The computer-implemented method of claim 3, wherein the probability is based on the observed user behavior and the first and second simulated data.

5. The computer-implemented method of claim 2, wherein the value based on a probability that a user of the plurality of users would click on the particular item comprises:

a division of a total number of clicks observed for the particular item by a total number of times the particular item has been selected;

wherein the total number of times the particular item has been selected is based on the first simulated data and the observed user behavior.

6. The computer-implemented method of claim 1, wherein the first simulated data comprises percentages of times each item of the plurality of items was selected in the step of simulating user behavior.

7. The computer-implemented method of claim 6, wherein the percentages comprise the probability that each item of the plurality of items will be presented to the user during the specified future time period.

8. A computer-implemented method comprising:

generating a plan for presenting an item from a plurality of items to a user;

wherein the plan is based on a simulation of user behavior pertaining to a specified future time period;

wherein the simulation comprises a function measuring a potential that presenting the item will maximize a performance metric; and

presenting, to the user, the item selected from the plurality of items according to the plan.

9. The computer-implemented method of claim 8, wherein the performance metric comprises a click-through rate, a total number of page views over time, or a measure of overall user experience.

10. The computer-implemented method of claim 8,

wherein the function measuring a potential that presenting the item will maximize a performance metric further comprises calculating a priority corresponding to the item;

and

wherein the priority comprises a measure of a current estimated click rate pertaining to the item and a measure of the probability that the current estimated click rate will improve.

11. The computer-implemented method of claim 8, further comprising the steps of:

presenting, to the user, the item selected according to the plan after the simulation of user behavior pertaining to a specified future time period.

12. The computer-implemented method of claim 8, further comprising the steps of:

presenting, to the user, the item selected according to the plan during the simulation of user behavior pertaining to a specified future time period.

13. The computer-implemented method of claim 8, wherein the simulation of user behavior pertains to users of a portal page on the internet.

14. The computer-implemented method of claim 8, wherein the simulation of user behavior is based on a solution to the Bayesian multi-armed bandit problem.

15. A machine-readable volatile or non-volatile medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

simulating user behavior pertaining to a specified future time period,

wherein the simulating is based on an observed user behavior, and

wherein the simulating produces first simulated data;

selecting an item of a plurality of items during the specified future time period based on the first simulated data; and

presenting the item to a user.

16. The machine-readable volatile or non-volatile medium of claim 15, wherein the observed user behavior comprises a number of times the plurality of items have been viewed by a plurality of users and the number of times each item of the plurality of items has been clicked.

17. The machine-readable volatile or non-volatile medium of claim 15, wherein the step of simulating user behavior further comprises:

calculating a probability that a particular item of the plurality of items will maximize a performance metric;

selecting the particular item based on the probability;

recording, in connection with the particular item at the first simulated data, a hypothetical view; and

recording, in connection with the particular item at second simulated data, a value based on a probability that a user of the plurality of users would click on the particular item.

18. The machine-readable volatile or non-volatile medium of claim 17, wherein the probability is based on the observed user behavior and the first and second simulated data.

19. The machine-readable volatile or non-volatile medium of claim 16, wherein the value based on a probability that a user of the plurality of users would click on the particular item comprises:

a division of a total number of clicks observed for the particular item by a total number of times the particular item has been selected;

wherein the total number of times the particular item has been selected is based on the first simulated data and the observed user behavior.

20. The machine-readable volatile or non-volatile medium of claim 15, wherein the first simulated data comprises percentages of times each item of the plurality of items was selected in the step of simulating user behavior.

21. The machine-readable volatile or non-volatile medium of claim 20, wherein the percentages comprise the probability that each item of the plurality of items will be presented to the user during the specified future time period.

22. A machine-readable volatile or non-volatile medium carrying one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

generating a plan for presenting an item from a plurality of items to a user;

wherein the plan is based on a simulation of user behavior pertaining to a specified future time period;

wherein the simulation comprises a function measuring a potential that presenting the item will maximize a performance metric; and

presenting, to the user, the item selected from the plurality of items according to the plan.

23. The machine-readable volatile or non-volatile medium of claim 22, wherein the performance metric comprises a click-through rate, a total number of page views over time, or a measure of overall user experience.

24. The machine-readable volatile or non-volatile medium of claim 22,

wherein the function measuring a potential that presenting the item will maximize a performance metric further comprises calculating a priority corresponding to the item;

and

wherein the priority comprises a measure of a current estimated click rate pertaining to the item and a measure of the probability that the current estimated click rate will improve.

25. The machine-readable volatile or non-volatile medium of claim 22, further comprising the steps of:

presenting, to the user, the item selected according to the plan after the simulation of user behavior pertaining to a specified future time period.

26. The machine-readable volatile or non-volatile medium of claim 22, further comprising the steps of:

presenting, to the user, the item selected according to the plan during the simulation of user behavior pertaining to a specified future time period.

27. The machine-readable volatile or non-volatile medium of claim 22, wherein the simulation of user behavior pertains to users of a portal page on the internet.

28. The machine-readable volatile or non-volatile medium of claim 22, wherein the simulation of user behavior is based on a solution to the Bayesian multi-armed bandit problem.