Enhanced matching through explore/exploit schemes

• US 8,244,517 B2
• Filed: 11/07/2008
• Issued: 08/14/2012
• 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: Roy, H. Scott, Ramakrishnan, Raghunath, Elango, Pradheep, Motgi, Nitin, Agarwal, Deepak K., Chu, Wei, Chen, Bee-Chung
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US12/267,534
• Publication Number:
  US 20100121624A1
• Time in Patent Office: 1,376 Days
• Field of Search: 703/6, 703/22, 703/13, 705/7, 705/8, 705/10, 705/1, 706/45, 706/46, 706/12, 717/136, 707/4, 707/5, 707/3, 725/146, 709/246
• US Class Current: 703/22
• 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:

conducting one or more experiments using a computer simulation simulating a specified future time period, the one or more experiments comprising;

hypothetically serving content items to hypothetical users assumed to visit a page during the specified future time period;

simulating hypothetical user behavior during the specified future time period based on observed historical user behavior data;

recording, in a set of simulated data, one or more values for a performance metric for each item hypothetically served for the specified future time period;

selecting a particular item of a plurality of items for presentation based, at least in part, on the set of simulated data; and

presenting the particular item to a user during an actual page visit.

2. The computer-implemented method of claim 1, wherein the observed historical user behavior data comprises a number of times each item of the plurality of items has been viewed by a plurality of users and a 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 hypothetical user behavior further comprises;

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

selecting the first item based on the probability;

the step of recording, in the set of simulated data, one or more values for the performance metric further comprises;

recording a hypothetical view of the first item as first simulated data; and

recording a value based on a probability that a hypothetical user of the hypothetical users would click on the first item as second simulated data.

4. The computer-implemented method of claim 3, wherein the probability that the first item will maximize performance metric is based on at least a subset of the observed historical user behavior data and at least a subset of the set of simulated data.

5. The computer-implemented method of claim 3, wherein the value based on the probability that a hypothetical user would click on the first item comprises:

a division of a total number of clicks observed for the first item by a total number of times the first item was selected for presentation to users;

wherein the total number of times the first item was selected for presentation to users is based on the first simulated data and at least a subset of the observed historical user behavior data.

6. The computer-implemented method of claim 1, wherein selecting the particular item of for presentation further comprises selecting the particular item based on a percentage of times that the particular item was hypothetically served to hypothetical users during the one or more experiments.

7. The computer-implemented method of claim 1, wherein the performance metric comprises one of:

a click-through rate, a total number of page views over time, revenue of an associated portal, or a measure of overall user experience.

10. The computer-implemented method of claim 1, wherein the step of presenting is performed after the computer simulation simulating the specified future time period.

11. The computer-implemented method of claim 1, wherein the step of presenting is performed during the computer simulation simulating 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;

wherein the method is performed by one or more computing devices.

9. The computer-implemented method of claim 8, wherein the performance metric comprises one of:

a click-through rate, a total number of page views over time, revenue of an associated portal, or a measure of overall user experience.

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

13. The computer-implemented method of claim 8, wherein the simulation of user behavior is based, at least in part, on a Bayesian explore/exploit problem.

14. The computer-implemented method of claim 8, further comprising initializing a value for a click-through rate for the item based, at least in part, on observed historical user behavior data.

15. The computer-implemented method of claim 8, further comprising estimating a value for a click-through rate for the item based, at least in part, on at least one of:

a Beta-Binomial (EWBB) model, and a Gamma-Poisson (EWGP) model.

16. The computer-implemented method of claim 8, wherein the simulation further comprises satisfying a lifetime constraint of the item.

17. The computer-implemented method of claim 8, wherein a constraint on a time interval of the function is relaxed using a Lagrange relaxation technique.

18. The computer-implemented method of claim 8, further comprising assigning a normal distribution to a function representing the performance metric.

19. A non-transitory machine-readable medium storing one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors cause:

conducting one or more experiments using a computer simulation simulating a specified future time period, the one or more experiments comprising;

hypothetically serving content items to hypothetical users assumed to visit a page during the specified future time period;

simulating hypothetical user behavior during the specified future time period based on observed historical user behavior data;

recording, in a set of simulated data, one or more values for a performance metric for each item hypothetically served for the specified future time period;

selecting a particular item of a plurality of items for presentation based, at least in part, on the set of simulated data; and

presenting the particular item to a user during an actual page visit.

20. The non-transitory machine-readable medium of claim 19, wherein the observed historical user behavior data comprises a number of times each item of the plurality of items has been viewed by a plurality of users and a number of times each item of the plurality of items has been clicked.

21. The non-transitory machine-readable medium of claim 19, wherein:

simulating hypothetical user behavior further comprises;

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

selecting the first item based on the probability;

recording, in the set of simulated data, one or more values for the performance metric further comprises;

recording a hypothetical view of the first item as first simulated data; and

recording a value based on a probability that a hypothetical user of the hypothetical users would click on the first item as second simulated data.

22. The non-transitory machine-readable medium of claim 21, wherein the probability that the first item will maximize the performance metric is based on at least a subset of the observed historical user behavior and at least a subset of the set of simulated data.

23. The non-transitory machine-readable medium of claim 21, wherein the value based on the probability that a hypothetical user would click on the first item comprises:

a division of a total number of clicks observed for the first item by a total number of times the first item was selected for presentation to users;

wherein the total number of times the first item was selected for presentation to users is based on the first simulated data and at least a subset of the observed historical user behavior data.

24. The non-transitory machine-readable medium of claim 21, wherein selecting the particular item of for presentation further comprises selecting the particular item based on a percentage of items that the particular item was hypothetically served to hypothetical users during the one or more experiments.

25. The non-transitory machine-readable medium of claim 19, wherein the presenting is performed after the computer simulation simulating the specified future time period.

26. The non-transitory machine-readable medium of claim 19, wherein the presenting is performed during the computer simulation simulating the specified future time period.

27. The non-transitory machine-readable medium of claim 19, wherein the performance metric comprises one of:

a click-through rate, a total number of page views over time, revenue of an associated portal, or a measure of overall user experience.

28. A non-transitory machine-readable medium storing one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors cause:

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.

29. The non-transitory machine-readable medium of claim 28, wherein the performance metric comprises one of:

a click-through rate, a total number of page views over time, revenue of an associated portal, or a measure of overall user experience.

30. The non-transitory machine-readable medium of claim 28, wherein the simulation of user behavior pertains to users of a portal page on the internet.

31. The non-transitory machine-readable medium of claim 28, wherein the simulation of user behavior is based, at least in part, on a Bayesian explore/exploit problem.

32. The non-transitory machine-readable medium of claim 28, further comprising sequences of instructions which, when executed cause initializing a value for a click-through rate for the item based, at least in part, on observed historical user behavior data.

33. The non-transitory machine-readable medium of claim 28, further comprising sequences of instructions which, when executed cause estimating a value for a click-through rate for the item based, at least in part, on at least one of:

a Beta-Binomial (EWBB) model, and a Gamma-Poisson (EWGP) model.

34. The non-transitory machine-readable medium of claim 28, wherein the simulation further comprises satisfying a lifetime constraint of the item.

35. The non-transitory machine-readable medium of claim 28, wherein a constraint on a time interval of the function is relaxed using a Lagrange relaxation technique.

36. The non-transitory machine-readable medium of claim 28, further comprising sequences of instructions which, when executed cause assigning a normal distribution to a function representing the performance metric.