3
$\begingroup$

My goal is to estimate the click-ability (the percentage of viewers who clicked) of a specific advertisement in a new web-page based on historical data. The nature of my data is such that each web page is categorized by two parameters - The site the page is in (e.g. stackoverflow.com), and type of the page (sports, entertainment, etc..). I know the clickability of my ad in many pages from my historical data, and would like to predict it for a new page which I don't have enough data on.

Since each web page is characterized by two parameters, I can summarize my data in a two dimensional sample matrix M'(X,Y), where each data point in the matrix is the click-ability of the ad in the specific combination of website and page type. For example if I know that the average of the click-rates in pages of type Programming in Stackoverflow.com is 0.5, when I get a new page which fits those parameters I will "guess" 0.5 as the click-rate of my ad in that page. When I look at the distribution of click-rates in a specific combination of site and page type, it is distributed normally in a nice bell shape - So in fact my guess is the mean estimator of the normal distribution that is specific to those parameters.

My problem arises when I don't have enough information in a specific coordinate in the matrix M'(X,Y) to get a robust estimate of the mean estimator - For example when I have historical data only for 2 web pages of type entertainment in stackoverflow. In that case, and assuming that I have new page in Stackoverflow that is an entertainment page - I can estimate the normal distribution of that advertisement in stackoverflow and independently estimate the distribution in pages of type entertainment in all websites (Not just stackoverflow). The question is how to combine the two normal mean estimators?

Here is a concrete example: enter image description here

Each number in the matrix represents what is the click-rate of my advertisement in a specific webpage, base on previous data in which I counted views and clicks in that specific webpage. Each coordinate in the matrix represents the click rates in all the web pages in the specific combination of site and page type. For simplicity I made the number of web pages in each combination of parameters small, but usually it is of size between 0 and 1000. My goal is to obtain the mean and variance parameters that best describes a specific coordinate, even for coordinates with little or no data (such as stackoverflow/entertainment or cnn/programming). For example the mean estimation for stackoverflow and programming would be ~0.5 with a standard deviation of around 0.1.

How might this be achieved? Is there a "correct way" to combine the the estimators for each dimension? Most solutions I found on the internet related on how to combine two samples of the same normal distribution - for example the inverse variance method. This doesn't seem quite right in my case - since each normal distribution describes a separate dimension of 2-dimensional data.

Another possible solution which doesn't seem right is Combination of two Gaussians. If one dimension has data for 1 million web pages and the other has 1000 - The first one would dominate the combined result, despite the fact that 1000 web pages is enough to get a robust statistic and thus should get the same weight as the other dimension when combining them.

Is there any sound solution to this problem?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ I'm afraid I just cannot connect the dots between the start and end of this question in any meaningful way. Could you be more specific--perhaps with an example--about what it means, precisely, for data that are "generated by an underlying Gaussian distribution" to have "categorical dimensions"? $\endgroup$
    – whuber ♦
    Dec 22, 2014 at 17:54
  • $\begingroup$ I editten the question with a more concrete example to make it clearer. What I meant by categorical dimensions was that the indexes of the matrix define a different subset of webpages (sports pages, travel pages, etc.. ) which don't have any numerical connection between them. Hope this makes this clear $\endgroup$
    – dan12345
    Dec 23, 2014 at 10:06
  • $\begingroup$ "Clicks" are not continuous, it is a count data. Did you consider that Normal distribution would be a just an approximation in here..? $\endgroup$
    – Tim ♦
    Dec 23, 2014 at 10:43
  • $\begingroup$ But the "click-through-rate" - I.e. clicks/views is continuous, right? So it does stand to reason that it will be distributed normally, I think. My assumption is that the distribution of click-through-rates among webpages which share the same father website and category is normal. When looking empirically this is not exactly true, it is a bit more heavy tailed (perhaps distributed log-normally). Anyway my question is more general, About how to combine distributions in multidimensional data: I would be interested in an answer even it was referring to other non-normal distributions $\endgroup$
    – dan12345
    Dec 23, 2014 at 11:26
  • 2
    $\begingroup$ The nature of your data is becoming clearer, but the question itself remains murky. The problem is that you seem to be using technical terms like "normal" and "Gaussian" in ways that seemingly have little relevance to these data. Do you think you could make some more edits that explain your objectives in plain, non-technical terms? What are you trying to learn about these Web pages and the click-through rates? $\endgroup$
    – whuber ♦
    Dec 23, 2014 at 14:09

2 Answers 2

Reset to default
2
+100
$\begingroup$

This is not really a full answer but maybe is easier to read than stuffing into comments

Problem Set up:

a) So your raw data is of form 

----------
Top-level Site | Theme| Page id | #Clicks| #Impressions
----------

and you collect all the pages for that (top-level site,theme) together ( disregarding the number of impressions on each page)

b) the data is gathered rather than from a proper experiment - so you suffer from issues of unbalanced design. This is especially severe because you are dealing with website data (eg certain themes/top level sites will have many orders more pages than others )

Problem Question: How to find an estimate for click through rate (CTR) for those combinations of (Top level site , theme) that have few pages - namely by combining an estimate based on theme with an estimate based on top level site in particular dealing with the unbalanced design.

Problem Answer:

You should use a regression model - in particular logistic regression would be the natural choice to estimate a probability. A logistic regression model written (in R formula notation) as CTR ~ top level site + theme will provide you with just such an estimate. You might be able to get away with a single model of the form CTR ~ top level site + theme + top level site x theme this will use the interactions when there is enough data and the individual dimensions additively if not.

I am not sure whether the regression model will have any issues with the unbalanced design - maybe more experienced members can pipe in.

Predicting clicks: Estimating the click-through rate for new ads

Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine

the second paper aims to address more specifically your issue of developing a general model to fill in the gaps where you have missing data points. however a logistic regression model of CTR~ site + theme + site x theme might work OK (ie the model tries to predict CTR with site and theme separately )

Some remarks

a standard assumption for click data is that it follows a binomial distribution with parameters (N =number of trials ie impressions, p =theoretical proportion of successes ie clicks ), so make sure you are comfortable with this.

even if your data is generated by the same theoretical process (equal p) your estimate (from data) of p will vary - with amount of variation dependent on number of samples ( and value of p) (see eg binomial proportion confidence interval). You might want to review your different samples of click through rate based on this ( ie for each combination of site/theme eg {0.3,0.25} is the variation in sample ctr just due to statistical variation ( too few impressions).

If you really do want to model the CTR as random then the beta distribution is a better choice than the normal distribution (Normal distribution for CTR doesn't take account variability due to different sample sizes, and that ctr must be between zero and 1)

you could then create a linear regression model ( or other statistical model) for each parameter (eg mu ~ site + theme +site x theme) see eg Bid Landscape Forecasting in Online Ad Exchange Marketplace

as I hope is clear from the linked papers, this is a pretty standard approach for web advertising companies - so its definitely 'web scale'.

Overfitting with 1000 x 1000 dummy variables over fitting is not a problem, precisely because most of the inputs are zero. you control over fitting with say L2 regularisation (which puts a penalty on the coefficients - with the effect that the a coefficient will be nonzero only if it reduces the overall error sufficiently: by playing with this regularisation you can ensure combinations with few impressions are ignored.

the high dimensional (but sparse) representation of dummy variables does require you to pass your input to logistic regression in a sparse format ( as a sparse matrix) or as a dictionary - otherwise you run out of memory.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the comments, they were very interesting. A few thoughts regarding logistic regression - I thought that in order to have logistic regression, I need to have the data in form of Theme | Top-level site -> 0/1 where 1 represents a click. The problem is that my data is already in aggregated form (#clicks vs #of impressions). Is the logistic regression model still valid? I could theoretically create 0/1 data from my aggregated data... Or am I wrong in understanding that logistic regression requires a 0/1 output varible? $\endgroup$
    – dan12345
    Jan 3, 2015 at 8:26
  • $\begingroup$ My second thought - in practice it is probably not feasible for me to try to learn regression model online, for running time reasons (my data is of a nature that would require learning millions of regression models per hour). I will definitely try to think if and how regression models might work, but if we go back to the formulation of my question - I can directly infer the normal distributions of both the theme dimension and Top-level site dimension. It seems to me probable that there is SOME statistical sound way to combine them... Don't you think? Any suggestions if we stick to that? $\endgroup$
    – dan12345
    Jan 3, 2015 at 8:42
  • $\begingroup$ Logistic regression will work fine with aggregated data (just depends on implementation.. Eg r glmnet Supports it). And I am afraid logistic regression is exactly the method to combine two feature probabilities. I think you need to step back and explain what is the problem - why do you need to perform 1 million separate regressions? Why not add extra variables to the logistic regression model, and have only a single (or handful of models). $\endgroup$
    – seanv507
    Jan 3, 2015 at 10:20
  • $\begingroup$ Naive Bayes methods would be a quicker way... But they are not likely to give you accurate prediction (may still be sufficient if you are just doing ranking of sites?). $\endgroup$
    – seanv507
    Jan 3, 2015 at 10:26
  • $\begingroup$ Interesting stuff. By the way - Since my features (websites, themes) are discrete and not numeric - Would you have a feature vector which is a binary 0/1 for each possible combination of site + theme? This would be quite a large feature vector as it will be of size O(n^2) - which makes me worry about problems of over-fitting, especially since most combinations will be almost always a constant 0. We are talking about ~ 1000 sites, and ~1000 themes. $\endgroup$
    – dan12345
    Jan 3, 2015 at 16:01
1
$\begingroup$

Unless I completely misunderstood your question, it seems to me that you could approach this as a problem of missing values (incomplete data). If this is the case, the problem can be solved by using corresponding methods, such as multiple imputation. Depending on whether your data is normal or non-normal, you could use an R package to impute missing data, such as Amelia / Amelia II (http://cran.r-project.org/web/packages/Amelia) or mice (http://cran.r-project.org/web/packages/mice). Both packages are very flexible and support a variety of data types and imputation/regression models. If your data is normal, but you're not comfortable with programming in R, Amelia has an interactive GUI version, which might be sufficient for your purposes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.