Using linear and log-linear model combinations for estimating probabilities of events

• US 8,484,077 B2
• Filed: 09/29/2010
• Issued: 07/09/2013
• Est. Priority Date: 07/21/2010
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Cetin, Ozgur, Manavoglu, Eren, Achan, Kannan, Cantu-Paz, Erick, Iyer, Rukmini
• Primary Examiner(s): Lastra, Daniel
• Application Number:
  US12/893,939
• Publication Number:
  US 20120022952A1
• Time in Patent Office: 1,014 Days
• Field of Search: 705/14.1
• US Class Current: 705/14.1
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

A method for combining multiple probability of click models in an online advertising system into a combined predictive model, the method commencing by receiving a feature set slice (e.g. corresponding to demographics or taxonomies or clusters), and using the sliced data for training multiple slice-wise predictive models. The trained slice-wise predictive models are combined by overlaying a weighted distribution model over the trained slice-wise predictive models. The combined predictive model then is used in predicting the probability of a click given a query-advertisement pair in online advertising. The method can flexibly receive slice specifications, and can overlay any one or more of a variety of distribution models, such as a linear combination or a log-linear combination. Using an appropriate weighted distribution model, the combined predictive model reliably yields predictive estimates of occurrence of click events that are at least as good as the best predictive model in the slice-wise predictive model set.

Claims

1. A computer-implemented method for combining probability of click models in an online advertising system, said method comprising:

receiving, at a computer, at least one feature set slice;

training, in a computer, a plurality of slice predictive models, the slice predictive models corresponding to at least a portion of the features in the at least one feature set slice;

assigning weights, in a computer, to at least two of the plurality of slice predictive models by overlaying a weighted distribution model over the plurality of slice predictive models; and

calculating, in a computer, a combined predictive model based on the at least two of the plurality of slice predictive models and their assigned weights.

2. The method of claim 1, further comprising receiving a model and slice specification.

3. The method as set forth in claim 1, wherein the weighted distribution model is a linear combination using a uniform average weighting.

4. The method of claim 1, wherein the combined predictive model p(c|x) is calculated using the formula:

5. The method as set forth in claim 1, wherein the weighted distribution model is a log-linear combination using a maximum-entropy weighting.

6. The method of claim 1, wherein the combined predictive model p(c|x) is calculated using the formula:

7. The method as set forth in claim 1, wherein said training comprises training a predictive model using a flat weighting.

8. The method as set forth in claim 1, wherein said training a plurality of slice predictive models comprises partitioning said training data set into a plurality of slices by generating a plurality of clusters from said training data.

9. The method as set forth in claim 1, wherein said plurality of slice predictive models is partitioned by categories of subject matter corresponding to selected query-advertisement pairs.

10. A computer readable medium comprising a set of instructions which, when executed by a computer, cause the computer to combine probability of click models in an online advertising system, said instructions for:

receiving, at a computer, at least one feature set slice;

training, in a computer, a plurality of slice predictive models, the slice predictive models corresponding to at least a portion of the features in the at least one feature set slice;

assigning weights, in a computer, to at least two of the plurality of slice predictive models by overlaying a weighted distribution model over the plurality of slice predictive models; and

calculating, in a computer, a combined predictive model based on the at least two of the plurality of slice predictive models and their assigned weights.

11. The computer readable medium of claim 10, further comprising receiving a model and slice specification.

12. The computer readable medium as set forth in claim 10, wherein the weighted distribution model is a linear combination using a uniform average weighting.

13. The computer readable medium of claim 10, wherein the combined predictive model p(c|x) is calculated using the formula:

14. The computer readable medium as set forth in claim 10, wherein the weighted distribution model is a log-linear combination using a maximum-entropy weighting.

15. The computer readable medium of claim 10, wherein the combined predictive model p(c|x) is calculated using the formula:

16. The computer readable medium as set forth in claim 10, wherein said training comprises training a predictive model using a flat weighting.

17. The computer readable medium as set forth in claim 10, wherein said training a plurality of slice predictive models comprises partitioning said training data set into a plurality of slices by generating a plurality of clusters from said training data.

18. The computer readable medium as set forth in claim 10, wherein said plurality of slice predictive models is partitioned by categories of subject matter corresponding to selected query-advertisement pairs.

19. An advertising network for combining probability of click models in an online advertising system, comprising:

a module for receiving at least one feature set slice;

a module for training a plurality of slice predictive models, the slice predictive models corresponding to at least a portion of the features in the at least one feature set slice;

a module for assigning weights to at least two of the plurality of slice predictive models by overlaying a weighted distribution model over the plurality of slice predictive models; and

a module for calculating a combined predictive model based on the at least two of the plurality of slice predictive models and their assigned weights.

20. The advertising network of claim 19, further comprising a module for receiving a model and slice specification.