Click prediction using bin counting

• US 9,104,960 B2
• Filed: 06/20/2011
• Issued: 08/11/2015
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Bottou, Leon, Chellapilla, Kumar, Simard, Patrice Y., Chickering, David Max
• Primary Examiner(s): Sittner, Matthew T
• Application Number:
  US13/163,857
• Publication Number:
  US 20120323677A1
• Time in Patent Office: 1,513 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/0242 Determining effectiveness of advertisements

Abstract

Methods, systems, and computer-storage media having computer-usable instructions embodied thereon for calculating event probabilities are provided. The event may be a click probability. Event probabilities are calculated using a system optimized for runtime model accuracy with an operable learning algorithm. Bin counting techniques are used to calculate event probabilities based on a count of event occurrences and non-event occurrences. Linear parameters, such and counts of clicks and non-clicks, may also be used in the system to allow for runtime adjustments.

Claims

1. One or more computer storage media devices storing computer-useable instructions that, when used by one or more computing devices cause the one or more computing devices to perform a method for calculating event probabilities using linear trainable parameters that capture relationships and concepts that are regularly updatable for a quick incorporation of new data, the method comprising:

identifying a request to calculate an event probability, wherein the event probability indicates an expected number of times the event will occur;

associating information from the request with a set of feature groups, wherein the set of feature groups comprises a first subset of feature groups comprising linear trainable parameters characterized by consecutive integers, and a second subset of feature groups comprising non-linear trainable parameters, wherein a feature group is a classification of the information from the request, and wherein each of the first subset of feature groups includes a plurality of bins;

associating a bin of the plurality of bins with the information from the request;

identifying, by the one or more computing devices, counter information from at least an event counter and a non-event counter associated with the bin, wherein the event counter counts a number of event occurrences for the request and the non-event counter counts a number of non-event occurrences for the request;

training, by the one or more computing devices, the event counter and the non-event counter using a linear-training algorithm;

calculating, utilizing the counter information, the event probability;

identifying and removing at least one non-billable traffic attribute;

updating the counter information based on the removal of the at least one non-billable traffic attribute; and

calculating, utilizing the updated counter information less the non-billable traffic, an updated event probability.

2. The one or more computer storage media devices of claim 1, wherein the event is a click probability.

3. The one or more computer storage media devices of claim 2, wherein the information from the request comprises one or more of a query identifier identifying the query, an advertisement identifier identifying the advertisement, an internet protocol address, and a match type, wherein the match type indicates that the query:

ad pair is one of an exact match, a phrase match, a broad match, or a smart match.

4. The one or more computer storage media devices of claim 1, wherein each feature group in the first subset of feature groups is one of a simple feature, a dictionary feature, a semantic feature, or a cross feature.

5. The one or more computer storage media devices of claim 4, wherein at least one feature group in the second subset of feature groups is a function feature, wherein the function feature does not include linear trainable parameters.

6. The one or more computer storage media devices of claim 1, wherein associating the bin with the information from the request includes:

determining whether the information from the request has been previously identified, wherein the information from the request has been previously identified if it is associated with an existing bin;

based on a determination that the information from the request has been previously identified, associating the information from the request with the existing bin.

7. The one or more computer storage media devices of claim 1, wherein associating the bin with the information from the request includes:

determining whether information from the request has been previously identified, wherein the information from the request has been previously identified if it is associated with an existing bin; and

based on a determination that the information from the request has not been previously identified, associating the information from the request with one of a new bin or a garbage bin.

8. The one or more computer storage media devices of claim 1, further comprising assigning a weight to the counter information.

9. The one or more computer storage media devices of claim 1, wherein the event counter is a click counter that counts a number of clicks of an advertisement and wherein the non-event counter is a non-click counts that counts a number of times the advertisement is presented that does not result in a click of the advertisement.

10. The one or more computer storage media devices of claim 1, wherein the counter information used to calculate the event probability is one of raw counts indicating event occurrences and non-event occurrences or regularized counter information, wherein regularized counter information includes a log of each of the event occurrence counts and non-event occurrence counts.

11. A method for calculating event probabilities using linear trainable parameters that capture relationships and concepts that are regularly updatable for a quick incorporation of new data, the method comprising:

identifying a request to calculate an event probability, wherein the event probability indicates an expected number of times the event will occur;

associating information from the request with a set of feature groups, wherein the set of feature groups comprises a first subset of feature groups comprising linear trainable parameters characterized by consecutive integers, and a second subset of feature groups comprising non-linear trainable parameters, wherein a feature group is a classification of the information from the request, and wherein each of the first subset of feature groups includes a plurality of bins;

associating a bin of the plurality of bins with the information from the request;

identifying, by the one or more computing devices, counter information from at least an event counter and a non-event counter associated with the bin, wherein the event counter counts a number of event occurrences for the request and the non-event counter counts a number of non-event occurrences for the request;

training, by the one or more computing devices, the event counter and the non-event counter using a linear-training algorithm;

calculating, utilizing the counter information, the event probability;

identifying and removing at least one non-billable traffic attribute;

updating the counter information based on the removal of the at least one non-billable traffic attribute; and

calculating, utilizing the updated counter information less the non-billable traffic, an updated event probability.

12. The method of claim 11, wherein the event is a click probability.

13. The method of claim 12, wherein the information from the request comprises one or more of a query identifier identifying the query, an advertisement identifier identifying the advertisement, an internet protocol address, and a match type, wherein the match type indicates that the query:

ad pair is one of an exact match, a phrase match, a broad match, or a smart match.

14. The method of claim 11, wherein each feature group in the first subset of feature groups is one of a simple feature, a dictionary feature, a semantic feature, or a cross feature.

15. The method of claim 14, wherein at least one feature group in the second subset of feature groups is a function feature, wherein the function feature does not include linear trainable parameters.

16. The method of claim 11, wherein associating the bin with the information from the request includes:

determining whether the information from the request has been previously identified, wherein the information from the request has been previously identified if it is associated with an existing bin;

based on a determination that the information from the request has been previously identified, associating the information from the request with the existing bin.

17. The method of claim 11, wherein associating the bin with the information from the request includes:

determining whether information from the request has been previously identified, wherein the information from the request has been previously identified if it is associated with an existing bin; and

based on a determination that the information from the request has not been previously identified, associating the information from the request with one of a new bin or a garbage bin.

18. The method of claim 11, further comprising assigning a weight to the counter information.

19. The method of claim 11, wherein the event counter is a click counter that counts a number of clicks of an advertisement and wherein the non-event counter is a non-click counts that counts a number of times the advertisement is presented that does not result in a click of the advertisement.

20. A computer system for calculating event probabilities using linear trainable parameters that capture relationships and concepts that are regularly updatable for a quick incorporation of new data, the system comprising:

a computing device associated with one or more processors and one or more computer storage media;

a data store coupled with the computing device; and

a predicting engine that identifies a request to calculate an event probability, wherein the event probability indicates an expected number of times the event will occur;

(1) associates information from the request with a set of feature groups, wherein the set of feature groups comprises a first subset of feature groups comprising linear trainable parameters characterized by consecutive integers, and a second subset of feature groups comprising non-linear trainable parameters, wherein a feature group is a classification of the information from the request, and wherein each of the first subset of feature groups includes a plurality of bins;

(2) associates a bin of the plurality of bins with the information from the request;

(3) identifies, by the one or more computing devices, counter information from at least an event counter and a non-event counter associated with the bin, wherein the event counter counts a number of event occurrences for the request and the non-event counter counts a number of non-event occurrences for the request;

(4) trains, by the one or more computing devices, the event counter and the non-event counter using a linear-training algorithm;

(5) calculates, utilizing the counter information, the event probability;

(6) identifies and removes at least one non-billable traffic attribute;

(7) updates the counter information based on the removal of the at least one non-billable traffic attribute; and

(8) calculates, utilizing the updated counter information less the non-billable traffic, an updated event probability.