Large-Scale Behavioral Targeting for Advertising over a Network

• US 20100179855A1
• Filed: 01/09/2009
• Published: 07/15/2010
• Est. Priority Date: 01/09/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chen, Ye, Pavlov, Dmitry, Canny, John, Berkhin, Pavel
• Granted Patent: US 8,150,723 B2
• Time in Patent Office: Days
• US Class Current: 705/10
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06Q 10/0637 Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals
• CPC Class Codes: G06Q 10/0639 Performance analysis of employees; Performance analysis of enterprise or organisation operations
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0206 Price or cost determination based on market factors

Abstract

A method and a system are provided for large-scale behavioral targeting for advertising over a network, such as the Internet. In one example, the system receives training data that is processed raw data of user behavior. The system generates selected features by performing feature selection on the training data. The system generates feature vectors from the selected features. The system initializes weights of a behavioral targeting model by scanning the feature vectors once. The system then updates the weights of the behavioral targeting model by scanning iteratively the feature vectors using a multiplicative recurrence.

Claims

1. A method for large-scale behavioral targeting, the method comprising:

receiving training data that is processed raw data of user behavior;

generating selected features by performing feature selection on the training data;

generating feature vectors from the selected features;

initializing weights of a behavioral targeting model by scanning the feature vectors once; and

updating the weights of the behavioral targeting model by scanning iteratively the feature vectors using a multiplicative recurrence.

2. The method of claim 1, wherein the training data includes at least one of:

reduced data from raw data of user behavior;

aggregated data from raw data of user behavior; and

merged data from raw data of user behavior.

3. The method of claim 1, further comprising storing one or more behavioral targeting models in a Hadoop Distributed File System.

4. The method of claim 1, wherein the performing feature selection on the training data comprises at least one of:

counting frequencies of entities in terms of touching cookies; and

selecting most frequent entities of the entities in a given feature space.

5. The method of claim 1, wherein the generating feature vectors comprises at least one of:

configuring the feature vectors to represent the selected features;

optimizing the feature vectors for sequential access along both a user dimension and a feature dimension; and

materializing any data reduction and pre-computing opportunities.

6. The method of claim 5, wherein the generating feature vectors comprises at least one of:

configuring each of the feature vectors to be a sparse data structure;

referencing an original feature by an index of an inverted index; and

configuring the features vectors using binary representation and data compression.

7. The method of claim 1, wherein the initializing weights of the behavioral targeting model comprises using a data-driven approach and not randomly assigning weights to all parameters present in the weights, and wherein the data-driven approach includes counting bigrams, and wherein a bigram is one co-occurrence of a target and a feature.

8. The method of claim 7, further comprising at least one of:

distributing a computation of counting bigrams by a composite key; and

caching in-memory an output the computation, wherein a size of an in-memory cache is configurable.

9. The method of claim 1, wherein the multiplicative recurrence comprises at least one of:

using an update formula that has a substantially identical form as an update formula for the initializing the weights of the behavioral targeting model;

configuring a normalizer to become an expected target counts and not a total feature unigram counts, wherein the expected target counts is a Poisson mean as the normalizer.

10. The method of claim 1, wherein the multiplicative recurrence comprises at least one of:

representing a model weight matrix as K dense weight vectors of length J, where K is a number of targets and J is a number of features;

caching features vectors to generate cached feature vectors; and

maintaining a hash map that records all relevant pages for the cached feature vectors.

11. A system for large-scale behavioral targeting, wherein the system is configured for:

receiving training data that is processed raw data of user behavior;

generating selected features by performing feature selection on the training data;

generating feature vectors from the selected features;

initializing weights of a behavioral targeting model by scanning the feature vectors once; and

updating the weights of the behavioral targeting model by scanning iteratively the feature vectors using a multiplicative recurrence.

12. The system of claim 11, wherein the training data includes at least one of:

reduced data from raw data of user behavior;

aggregated data from raw data of user behavior; and

merged data from raw data of user behavior.

13. The system of claim 11, wherein the system is further configured for storing one or more behavioral targeting models in a Hadoop Distributed File System.

14. The system of claim 11, wherein the performing feature selection on the training data comprises at least one of:

counting frequencies of entities in terms of touching cookies; and

selecting most frequent entities of the entities in a given feature space.

15. The system of claim 11, wherein the generating feature vectors comprises at least one of:

configuring the feature vectors to represent the selected features;

optimizing the feature vectors for sequential access along both a user dimension and a feature dimension; and

materializing any data reduction and pre-computing opportunities.

16. The system of claim 15, wherein the generating feature vectors comprises at least one of:

configuring each of the feature vectors to be a sparse data structure;

referencing an original feature by an index of an inverted index; and

configuring the features vectors using binary representation and data compression.

17. The system of claim 11, wherein the initializing weights of the behavioral targeting model comprises using a data-driven approach and not randomly assigning weights to all parameters present in the weights, and wherein the data-driven approach includes counting bigrams, and wherein a bigram is one co-occurrence of a target and a feature.

18. The system of claim 17, wherein the system is further configured for at least one of:

distributing a computation of counting bigrams by a composite key; and

caching in-memory an output the computation, wherein a size of an in-memory cache is configurable.

19. The system of claim 11, wherein the multiplicative recurrence comprises at least one of:

using an update formula that has a substantially identical form as an update formula for the initializing the weights of the behavioral targeting model;

configuring a normalizer to become an expected target counts and not a total feature unigram counts, wherein the expected target counts is a Poisson mean as the normalizer.

20. The system of claim 11, wherein the multiplicative recurrence comprises at least one of:

representing a model weight matrix as K dense weight vectors of length J, where K is a number of targets and J is a number of features;

caching features vectors to generate cached feature vectors; and

maintaining a hash map that records all relevant pages for the cached feature vectors.

21. A computer readable medium carrying one or more instructions for large-scale behavioral targeting, wherein the one or more instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:

receiving training data;

generating selected features by performing feature selection on the training data;

generating feature vectors from the selected features;

initializing weights of a behavioral targeting model by scanning the feature vectors once; and

updating the weights of the behavioral targeting model by scanning iteratively the feature vectors using a multiplicative recurrence.