I am struggling with the following problem: Suppose we fit a machine learning model to model advertisers click rates. I used a Logistic Regression approach using a one-hot/dummy encoding.

We have two advertisers A and B with a click rate of 10% and 9% respectively. Hence, we would rank A before B and would show users ads from A more often, say 90% of all times. Hence our overall click rate would be close to 10%.

Now we introduce a new feature which says a user either clicked on the advertiser before or not. For advertiser A, we observe a click rate of 8% for users that have not clicked before and a rate of 30% for users that have at least clicked once on an ad of the advertiser. For advertiser B we see no difference in the click rate for this feature.

So when it now comes to ranking the ads and we get a "fresh" user that has not clicked on both advertisers, we would rank B above A. Since fresh users are obviously more often, we would mostly show users ads from B, say 90%.

As a consequence, our overall click rate would drop from almost 10% to a little over 9%. The machine learning model does everything correct since we did not introduce any information that the two states of this new features are timely dependent.

From an intuitive approach I would still rank advertiser A over B for these fresh users since it's not clear if they're going to click.

Any ideas how to tackle this problem to get a ranking that in the end maximizes the click rate?

  • Let $X$ represent the event "a user clicks an ad" with advertiser X,
  • Let event $Y$ represent a new user ($\neg Y$ a returning user),

for any advertiser $X$ the probability of a user clicking an ad is:

$p(X) = p(X\wedge Y) + p(X\wedge \neg Y)$

$p(X) = p(X|Y)p(Y) + p(X| \neg Y)p(\neg Y)$

$p(X) = p(X|Y)p(Y) + p(X| \neg Y)(1 - p(Y))$

If it's possible to obtain the information "new user" (event $Y$) in the system, then obviously there should be two distinct rankings, one for $Y$ and one for $\neg Y$. Phrased in a ML context: $Y$ is a binary feature and the predicted best advertiser depends on it. In this scenario a different advertiser would be selected depending on whether the user is new or not, here A for returning users and B for new users.

If not possible, then the advertisers should be ranked according to their overall probability $p(X)$, which depends on the probability of a new user $Y$. Based only on your initial values 10% vs. 9%, this means selecting advertiser $A$ is optimal overall.

To illustrate how this works we can calculate the detail based on the values provided. First we calculate $p(Y)$:

$p(X) = p(X|Y)p(Y) + p(X| \neg Y) - p(X| \neg Y)p(Y)$

$p(X)-p(X| \neg Y) = (p(X|Y)- p(X| \neg Y))p(Y) $

$(p(X)-p(X| \neg Y)) / (p(X|Y)- p(X| \neg Y)) = p(Y) $

We have $p(A)=0.1$, $p(A|Y) = 0.08$ and $p(A| \neg Y) = 0.3$, so we can derive $p(Y)=0.91$.

What happens in this example is that the high value $p(A| \neg Y) = 0.3$ makes up for the low $p(A|Y) = 0.08$ despite $p(Y)=0.91$:

  • A: $0.91*0.08+0.09*0.3 = 0.1$
  • B: $0.91*0.09+0.09*0.09 = 0.09$

Of course this would be different if $p(A| \neg Y)$ was 0.15 instead of 0.3 or if $p(A| Y)$ was 0.11 instead of 0.09, etc.

[edit based on comments by OP]

Indeed it seems that a more accurate representation of the problem would take into account the probability that a user clicks again (and again, and again...) on an ad.

This reminds me of classical probability exercises such as the Russian roulette game, the tree of possible outcomes is somewhat similar:

  • user doesn't click on the ad at all: $n=0$
  • user clicks on the ad at least once
    • user never clicks again: $n=1$
    • user clicks on the ad at least twice
      • user never clicks again: $n=2$
      • user clicks on the ad at least 3 times
        • user never clicks again: $n=3$
        • .......

So the goal would be to represent as accurately as possible the random variable $n$ which represents how many times a user clicks on an ad, and to use the expected value of $n$ (that is, how many times a user clicks on average) to rank the advertisers.

I'm guessing that this can get pretty sophisticated depending on how we choose to represent the problem. I'm probably not able to do anything sophisticated so I'll stick to a simple representation where I assume that there are two probabilities involved:

  • initial probability $F=p(n\geq 1)$ for a new user to click
  • probability for a user to click again after having clicked $m$ times: $G=p(n\geq m+1|n\geq m)$ for $m>0$.

This representation has the advantage to be very close to the original probabilities in the question: new user clicks and returning user clicks. Notice that the model assumes that the probability to click again is a constant, which is unlikely in reality. Also the model doesn't take into account any other features, such as for how long a user hasn't clicked. I'll just assume that one estimate these probabilities from a training set for the sake of simplicity.

Now let's calculate the expected value [fair warning, I might get it wrong!]

  • $p(n=0) = 1 - F$
  • $p(n=1) = F \times (1-G)$
  • $p(n=2) = F \times G \times (1-G)$
  • $p(n=3) = F \times G \times G \times (1-G)$
  • ...
  • $p(n=i) = F \times G^{i-1} \times (1-G)$

Therefore the expected value is:

$\sum_{i\geq 0} (p(n=i) \times i) = \sum_{i\geq 1} (F \times G^{i-1} \times (1-G) \times i)$

[Ok so normally now we can plug in the values for advertisers A and B. The problem is that I just calculated the result for the first few values and it doesn't really work... I probably made a mistake somewhere, or maybe the values don't represent the same thing... Anyway I hope this gives you the idea, maybe I'll give it another try later]

  • $\begingroup$ Thank you for your answer. I am little confused whether event Y and C are the same, but nevertheless it think all you equations are correct. But there was a minor misunderstanding that might change everything. There is a difference between clicking on ads of A and B. So there are actually two events: Y, clicking on on A, and Z, clicking on B. Still the probabilitiee would tell us to rank B before A for new users. But over time, A wouldn't get any users at all since he is never shown to new users... $\endgroup$ – user1488793 Jul 21 '19 at 20:43
  • $\begingroup$ So if we known that Y holds, a new user. I think ranking the ads by P(X|Y) might not be a wise choice. Shouldn't we take into account, that these users might click later on and hence might later increase the overall click rate. So. Something like P(X|Y) + P(X|Y) * P(X|notY)? $\endgroup$ – user1488793 Jul 21 '19 at 20:51
  • $\begingroup$ @user1488793 sorry for the Ys and Cs, I changed the letters midway through and forgot to replace some, it's fixed now. About your other points I'm confused: first, it's a different purpose to maximize the click rate and to collect data about the click rate: if you need to do both then probabilities don't really help, you would have to show them both from time to time independently from new users or not. I don't completely understand the last point but it seems to be about the fact the probability can change with time isn't it? $\endgroup$ – Erwan Jul 21 '19 at 22:40
  • $\begingroup$ Yes that is my point. Collecting the data and maximization are now somehow connected and the probability estimate somehow ignores this. In reality probabilities might change, but lets ignore this for now. Lets set up an experiment, were we selected data and observed the probabilites above. Now we apply our learning for new incoming data, where the same probabilities hold. The ML model would now see only fresh users and will only display advertiser B to the users. And since A does is never shown to the users, no user will end up with clicks of A. So I am thinking whether its $\endgroup$ – user1488793 Jul 22 '19 at 7:44
  • $\begingroup$ best to assume 0.1 as initial probabilty for new incoming users. Simply because it would now be optimal to show only adveriser A for the new incoming data since we would end up with a click rate of 0.1. Do you see where am I going? $\endgroup$ – user1488793 Jul 22 '19 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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