# How can I estimate a score for my users, on if they will match ad campaign criteria?

I have ad campaigns that I want to display to users. Each one has criteria a user must meet in order for them to be valid for the campaign. For example, "User must be in the USA", or "User must like the albums by at least one of the artists [The Beatles, Michael Jackson], AND user must be in USA".

Right now I just let the user see all of the ads as they browse though my site, but I want to optimize for certain scenarios where I have scarcity (only show one ad on the home page, or one featured ad in search results). I want to be able to pick the best ad to display. At least half the ads have such custom requirements that I can't apply the criteria to see if they are valid to target. After the user clicks the ad placement, they are asked to fill out more data, at that point we have enough info to know if they are valid, and we match the user with the advertiser or product. We then collect revenue.

I am a software developer, and I don't know much about stats or machine learning. I want to know if there is some kind of machine learning or statistical model that I can use to help optimize this process. I'm imagining some kind of system where I run our ad targeting criteria against our entire user base's data (we have over 5 million users), and generate a set of tuples:

{user: John Doe, ad_campaign: Coca-Cola, valid_to_target: Yes/No/Maybe(but not enough info)}


Then, I would feed that set of tuples as a training set into some kind of ML model (not sure if I'm using the right terminology). That process would result in a model, a piece of code I can execute in my ad service, that would be able to take as input a brand new user, and output a set of tuples similar to the training data tuple above, except these tuples would also have a score indicating how likely that user is to be valid/targetable. I guess a Yes/No/Maybe could also work, but sometimes the criteria involve several user data properties, so I would want the model to be able to give a higher score for users who look like they might be able to be valid, maybe have data for 5 fields out of 6 that are part of the ad targeting criteria, and the 5 fields they have data for don't rule them out for that campaign. So that user would see that ad over one where they have maybe 1 field out of 4.

Then, I could apply the ad revenue/costs with the scores to know know exactly what to show the user.

I'd like to know if this is possible, and if so, what are some canonical references that would help me learn to accomplish it. I see that there are libraries like Infer.NET (I'm a .NET developer mostly) that might be able to help.

• @jonsca, thank you for all the edits! They are a vast improvement on what I originally wrote. – DarkwingDev Mar 7 '13 at 13:48
• I would also appreciate if anyone could recommend approaches that can deal with the types of data I have. I would like if we could use an algorithm that can distinguish between the different types of data in a user's record. E.g., 1-N: Country/State can be any value from a specific set, and N-N: the user can select one or more values from a set for the "Musical Genre Preferences" field. Other fields are numeric, or bucket ranged. – DarkwingDev Mar 7 '13 at 16:12
• No problem! Pay it forward :) – jonsca Mar 7 '13 at 23:17

Cold start problem can be partly solved by considering the observed features about a user. This information can then be considered together with user preferences in a probabilistic collaborative filtering model. The Infer.NET has a number of (advanced) examples where it shown how to use the features (as priors for a parameter). As @psycharo has pointed out, this requires quite substantial expertise with Bayesian approaches to learning to leverage the Infer.NET to its full potential. It is not too complicated but will take some time.

Let's say each user u is represented by a (sparse) vector of features f[u]; each campaign c is also represented by a vector features in the same space f[c]. You could simply find a nearest neighbour (or several of those) by using kNN e.g. with Manhattan distance, or some other measure that suits your features better. Of course, this will not work nicely for a user for which you do not have data at all.

Another approach is to use collaborative filtering i.e. showing a user stuff that similar users liked/viewed/clicked. In your settings you might prefer this one if you have at least some data about a user after registration.

Both these approaches have a scalable implementation e.g. in Apache Mahout.

I think the problem that you are referring to (a brand new user) is a so-called cold start problem, and I do not know whether it has an ultimate solution. Though there are methods that can tackle it, take a look at the survey (Methods and metrics for cold-start recommendations, Schein et al, 2002).

P.S. As for Infer.Net, it is a very cool toolbox which possibly can also solve your problem - authors created an opponent recommender system for XBox with it, called TrueSkill. But it actually would require some knowledge in Bayesian learning.

update

If the number of campaigns is not too big, you could use naive bayes classification. Each campaign is a separate class c_i. The training phase boils down to computing likelihoods for separate features (e.g. p(country=usa|campaign=c_i) - probability that the country is usa given that his campaign is c_i), each can be a frequency of a certain value of a feature. One should also compute priors p(campaign=c_i) - which shows how frequent campaign c_i is.

Then in production for each c_i you compute posterior probability p(campaign=c|country=usa,viewed_item1=True,), which is simply a product of prior and likelihoods. The campaign with the highest probability is assigned to the user. I would assume that one could use sparsity and do computations efficiently. Note that this approach assumes that all the features are independent.

• Thanks for the reply. How does it work in terms of training a model, and then uploading a "trained model" into my production environment so that the model can analyze user data and assign scores or provide recommendations? What would you have to actually upload, I'm assuming it would be some kind of metadata, right? – DarkwingDev Mar 7 '13 at 16:07
• It precomputes a set of campaigns for the user, so the output is a (ranked) list. – psycharo Mar 7 '13 at 17:01
• OK, so I would be precomputing offline, and upload the result into production so they can be used to choose which ads to display? But even if I am doing this offline, once I train the model, isn't there some kind of state that needs to be retained so that when I run it to do the precomputation it knows how to score the tuples? – DarkwingDev Mar 7 '13 at 17:51
• Yes, the # of campaigns isn't that large, in the 100 - 500 range at any given time. – DarkwingDev Mar 7 '13 at 17:51
• Thanks again! Your latest update helps. I'll be looking into Naive Bayes. – DarkwingDev Mar 7 '13 at 17:53