Real-time adaptive probabilistic selection of messages

• US 8,219,447 B1
• Filed: 06/06/2007
• Issued: 07/10/2012
• Est. Priority Date: 06/06/2007
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Wolniewicz, Richard Hansen, Ieong, Ion T., Barkley, Christopher R., Anderson, Matthew O.
• Primary Examiner(s): Tarae, C. M.
• Application Number:
  US11/758,932
• Time in Patent Office: 1,861 Days
• Field of Search: 705/14
• US Class Current: 705/14.43
• CPC Class Codes: G06Q 30/0244 Optimization

Abstract

A facility selects a unit of content to include in an instance of a content container. For each of a plurality of units of content, across a plurality of other instances of the content container distributed during a foregoing period of time that included the unit of content, the facility determines both an average level of success achieved by including the unit of content, and a measure of the level of variability of the level of success achieved by including the unit of content. The facility scores each unit of content by selecting a value from a probability distribution that is based on the determined average level of success and measure of the level of variability of the level of success. The facility selects one of the units of content to include in the instance of the content container based on the determined scores.

Claims

1. A method for selecting an advertising message to include at a distinguished location in a distinguished instance of a web page, comprising:

identifying a plurality of candidate advertising messages that are eligible to be included at a distinguished location in a distinguished instance of the web page;

for each identified advertising message;

determining, across a plurality of instances of the web page served during a foregoing period of time that included the identified advertising message in the distinguished location (a) a set of values associated with the inclusion of the identified advertising message in each of the plurality of instances of the web page;

(b) an average of the values associated with the inclusion of the identified advertising message in the plurality of instances of the web page, and (c) a measure of the level of variability of the values associated with the inclusion of the identified advertising message;

determining a score by performing a weighted random selection of a value from a normal probability distribution centered on the determined average value, wherein the breadth of the normal probability distribution is based on the determined measure of the level of variability of the values; and

selecting the identified advertising message having the highest score to include at the distinguished location in the distinguished instance of the web page,

wherein the method is implemented in a computing system having a processor and a memory.

2. The method of claim 1 wherein the identification is based on an identifier associated with a user who requested the distinguished instance of the web page.

3. The method of claim 1, further comprising:

performing a test associated with the selected advertising message to determine whether the selected advertising message is suitable for inclusion at the distinguished location in the distinguished instance of the web page;

if the performed test succeeds, including the selected advertising message at the distinguished location in the distinguished instance of the web page; and

if the performed test fails, deselecting the selected advertising message in favor of the identified advertising message having the next-highest score.

4. A method for selecting a message to include at a distinguished location in an instance of a dynamically-published document, comprising:

identifying a plurality of candidate messages;

for each identified candidate message;

determining, across a plurality of instances of documents published during a foregoing period of time that included the identified candidate message in the distinguished location (a) a measure of success associated with the inclusion of the identified candidate message in a single instance of document published (b) an average of the measure of success associated with the inclusion of the identified candidate message in the plurality of instances of documents published, and (c) a measure of a level of variability of the measure of success achieved by including the identified candidate message;

determining a score by performing a weighted random selection of a value from a probability distribution based on (a) the determined average measure of success and (b) the determined measure of the level of variability of the measure of success; and

selecting at least one of the identified candidate messages to include at the distinguished location in the instance of the document based on the scores determined for the identified candidate messages,

wherein the method is implemented in a computing system having a processor and a memory.

5. The method of claim 4 wherein an exposure guarantee is associated with one of the identified candidate messages, and wherein, before the determined measure of the level of variability of the level of success is used as a basis for the probability distribution for the candidate message with the associated exposure guarantee, the determined average measure of success of the candidate message with the associated exposure guarantee is augmented by a guarantee bonus value.

6. The method of claim 5, further comprising dynamically determining the guarantee bonus value by which the average measure of success of the candidate message with the associated exposure guarantee is augmented based on an estimate of the average measure of success of the candidate message with the associated exposure guarantee needed to ensure satisfaction of the exposure guarantee.

7. The method of claim 4 wherein a plurality of the identified candidate messages are each the subject of an exposure guarantee, and wherein, at a time when at least one of the exposure guarantees is not satisfied, the selection of any identified candidate messages that are not the subject of an exposure guarantee is precluded.

8. The method of claim 4 wherein the plurality of candidate messages are identified from a pool of messages associated with the distinguished location, the method further comprising, for each of the messages of the pool, decaying information on which (a) the determined average level of success and (b) the determined measure of the level of variability of the measure of success of the message is based on older such information is given less weight than newer such information.

9. The method of claim 8, further comprising dynamically determining a rate of decay used to decay the determined average measure of success and the determined measure of the level of variability of the level of success of the messages.

10. The method of claim 9 wherein the rate of decay is determined by:

for each of a plurality of different posited rates of decay, simulating the selection of messages using determined average levels of success and determined measures of the level of variability of the measure of success decayed at the posited rate of decay; and

selecting the posited decay rate whose simulation produces a highest total level of success.

11. The method of claim 4 wherein a distinguished one of the identified candidate messages has been included at the distinguished location in less than a threshold number of instances of the document,

and wherein the average measure of success determined for the distinguished identified candidate message is a constructive average level of success based on an aggregate average level of success of all messages included at the distinguished location in the document during a preceding period of time,

and wherein the measure of the level of variability of the level of success determined for the distinguished identified candidate message is a constructive measure of the level of variability of the level of success based on an average measure of the level of variability of the level of success of all messages included at the distinguished location in the document during the preceding period of time.

12. The method of claim 4 wherein a distinguished one of the identified candidate messages has been available for inclusion at the distinguished location in the document for less than a length of time,

and wherein the average measure of success determined for the distinguished identified candidate message is a constructive average level of success based on an aggregate average level of success of all messages included at the distinguished location in the document during a preceding period of time,

and wherein the measure of the level of variability of the measure of success determined for the distinguished identified candidate message is a constructive measure of the level of variability of the measure of success based on an average measure of the level of variability of the measure of success of all messages included at the distinguished location in the document during the preceding period of time.

13. The method of claim 4 wherein a distinguished one of the identified candidate messages has been available for inclusion at the distinguished location in the document for less than a length of time,

and wherein the average measure of success determined for the distinguished identified candidate message is a constructive average level of success based on an aggregate average measure of success of all messages included at the distinguished location in the document at least a threshold number of times during a preceding period of time,

and wherein the measure of the level of variability of the measure of success determined for the distinguished identified candidate message is a constructive measure of the level of variability of the measure of success based on an average measure of the level of variability of the measure of success of all messages included at the distinguished location in the document at least a threshold number of times during the preceding period of time.

14. A system for selecting a unit of content to include in a distinguished instance of a content container, comprising:

a computing system having a processor and memory for implementing an analysis subsystem that determines, for each of a plurality of units of content, across a plurality of instances of the content container distributed during a foregoing period of time that included the unit of content (a) a measure of success achieved by including the unit of content in one instance of the content container (b) an average of the measure of success achieved by including the unit of content across the plurality of instances of the content container, and (c) a measure of the level of variability of the levels of success achieved by including the unit of content;

a computing system having a processor and memory for implementing a scoring subsystem that determines a score for each of a plurality of units of content by performing a weighted random selection of a value from a probability distribution based on (a) the determined average measure of success and (b) the determined measure of the level of variability of the measure of success; and

a selection subsystem that selects at least one of the units of content to include in the distinguished instance of the content container based on the scores determined for units of content.

15. The system of claim 14 wherein the content container is a portion of a web page.

16. The system of claim 14 wherein the selected unit of content is an advertising message.

17. The system of claim 14, further comprising a guarantee subsystem that, for a unit of content having an exposure guarantee, augments by a guarantee bonus value the average measure of success determined for the unit of content by the analysis subsystem before its use by the scoring subsystem to determine a score for the unit of content.

18. The system of claim 14 wherein the selection subsystem selects the unit of content having the highest determined score.

19. The system of claim 14 when the selection system selects a unit of content to include in the distinguished instance of the content container by, for each of the plurality of units of content in decreasing order of their scores, until a unit of content is selected:

applying a suitability test associated with the unit of content; and

selecting the unit of content if the applied suitability test is satisfied.

20. The system of claim 14 wherein the analysis subsystem maintains (a) the determined average measure of success and (b) the determined measure of the level of variability of the level of success for the plurality of units of content over time to take into account the inclusion of units of content of the plurality in the additional instances of the content container and associated measure of success.

21. The system of claim 14 wherein the analysis subsystem determines, for at least one the plurality of units of content, across a plurality of instances of both the content container and an alternate content container distinct from the content container distributed during a foregoing period of time that included the unit of content, both (a) an average of a measure of success achieved by including the unit of content, and (b) a measure of the level of variability of the level of success achieved by including the unit of content.