Correct feature aggregation for this tricky buying problem

Question

Consider the following problem, which was asked in an interview I was at (but it wasn't directed at me). It seems deceptively simple, but then it turns out to actually be really hard to answer well:

Each week $i$ an online food delivery service has a certain set $P_i$ of selected products among its large assortment that it needs to sell, before they expire.
In order to motivate people to buy those foods, the shop can send out emails at the beginning of the week. But customers get annoyed if they receive such emails, so the number of customers that get an email has to be kept as low as possible. Find only those customer which you think are prone to buy the selected products!
The data you have available:
1) a large purchase history of each customer at each point in time
2) all the past emails that were sent out randomly to a subset of customers
3) some general data about him as a person, find such customers.

What would have been a good solution to this?

I already spent hours thinking about this, but I could only come up with a trivial solution:
Consider it as a binary classification problem without any time component (so just consider the data from all the weeks together as on single large dataset) [this is because I don't know time series]. Thus, given our selected products $P$ we want to find out which kinds of clients will buy it. Separate the data in a training-validation-test set. We then organize the data the following way: Encode all categorical data with a one-hot encoding. Use the following sets features (=columns in the dataframe containing all the data):

• The information available about each customer from 3)
• define a class (=feature=column), that denotes with 1 or 0 if that customer has bought that product in the week after having been sent an email at the beginning of the week (this means that for the same customer we will as many observations (=rows) as there are week). Thus, I don't use any information from they general buying history, only how customers immediate buying changed to due the email.

Finally, use your favourite binary classifier and play around until you maximize prediction accuracy.

---

I think such a model to solve this problem would really have been horrible. Here is a critique of the model by illustrating some of the essential points that I think it would fail to take into account:

a) customers changing how they react to emails in terms of buying behavior with time [is there any way to take care of this without using timeseries? because I don't know almost anything about them]

b) individual customers' buying behavior:
-those customers that never bought what was in the email, should be assigned a low probability of having a buy-response to a´the new email
-I'm not sure that with this model even people that always bought some of the things that were advertised in the email will get a high probability of buying new things. These two points seem essential for me that the model should capture them!
-some customer might have preferences for certain products which would indicate that if the products they generally prefer are in $P$ they should definitely get an email, to motivate them to buy more of that

c) I don't take into consideration any long-term influence of the email: Currently I implicitly I use a cutoff to determine the usefulness of the information that the customer bought one of the products from the email: If he bought some of those products in the week at whose beginning the email was sent out, that information is assumed to be 100% useful (since it is reflected in the feature I construct), if he buys it at any point in time later that information is assumed to be 0% useful (since I ignore it in the features). Rather than using implicitly such a cutoff function I think it would be better if I somehow could make this explicit (but I don't know how) and use some other function that has a lower value the longer the customers took to buy stuff from the mail, in order to model the decaying usefulness of this information with time. This would capture situations where some customers bought that product only, say, 2 weeks after they received the email.

Answer 1

0) and 2) Moving Average Models. Suppose we are given nothing else than the following time series data

     time          y
  1:    0 -12.070657
  2:    1   4.658008
  3:    2  14.604409
  4:    3 -17.835538
  5:    4  11.751944
  ...

which looks like this:

for the purpose of this toy example it is essentially sin(time) + disturbance (you can find the R code below). What do I mean by this weird moving average or most simple time series model? I talk about adding the past values of y as new columns. Lets take $k=3$ for example, then at every time $t$ we add $y_{t-1}, y_{t-2}, y_{t-3}$ as new columns:

    time          y   y_past_1   y_past_2   y_past_3
 1:    0 -12.070657         NA         NA         NA
 2:    1   4.658008 -12.070657         NA         NA
 3:    2  14.604409   4.658008 -12.070657         NA
 4:    3 -17.835538  14.604409   4.658008 -12.070657
 5:    4  11.751944 -17.835538  14.604409   4.658008
 6:    5  14.331069  11.751944 -17.835538  14.604409

consider $t=3$. For this, $t-1 = 2$ and the value of y_past_1 (the value of y in the point in time just before the current $t=3$) is the value $y_{t-1} = y_2 = 14.604409$. Analogously, $t-2=1$ and the value of y_past_2 (the value of y two timesteps before the current $t=3$) is $y_{t-2} = y_1 = 4.658008$.

Now what people do as a first shot is to compute a (linear) model with $y$ as a target variable and `y_past_1, ..., y_past_k$ as input features. These are also called 'lagged' variables because they are the same as the target variable just with a little lag in the time component.

Now let us compute a linear model. What I get is essentially

y ~ 0.4320*y_past_1 + 0.2457*y_past_2 + y_past_3*0.2361 + 0.3070

Huh, how can it be that we computed a linear model but the outcome is not linear? This happens as the function time -> y_time is not linear, i.e. the linear model is applied to the 'non linear pairs of values' (y_past_1, y_past_2, y_past_3) but nevertheless, adds these up linearly.

That is what I mean by simple time series model: Take the past of some variable as input for the prediction of the new state.

NB: We did not discuss the role of $K$. This parameter works as a smoothing factor, i.e. in terms of time series it determines how much the prediction will be a so-called high pass filter (K small, do not filter out sudden movements, i.e. high frequencies, K big then the predictions follows the sin function more smoothly and is not 'fooled' so much by sudden movements of the target variable:

K=1:

K=10: )

1) I mean the following. Let us say that we consider the product PIZZA. We have two users, A and B. During the last year we have sent 20 advertising emails for pizza to each of these users. User A did respond 15 times by buying a pizza and user B did not respond at all. Now let us say that during the current day again we see user A and user B and we have the trigger to send them an ad email. We iterate through all our products and we arrive at the product pizza. Should we send A an ad for pizza? How about B? [of course we should send A the email because it had a high respond rate but we should probably not send B a pizza ad because apparently he/she does simply not like either our advertisement for pizza or pizza or has some other reason not to respond]. In that way for every poiont in time $t$ we should include the past $t-1, ..., t-K$ for each request and each user. That means that we do not have a "single past" for each user but for training but for every request in the training set we have a new unique 'past'... as in the example above: for every $t$, y_past_1 has a unique value, namely $y_{t-1}$. However, in your example, we do not simply take $y_{t-1}, ..., y_{t-K}$ into account but some function of it like so:

For every request given by user $u$ at week $t$ we iterate over every product $p$ and for each product $p$ we go back $K=52$ weeks and check how often we sent the user $u$ an ad email for product $p$ (number sent) and we count how often $u$ responded positively by buying the advertised product within one week after receiving the email (number positiveResponses) and then we compute affinity = positiveResponses/sent and include that as a column for the current request. In that way the model should come up with the rule like 'if affinity for this product is high then I should send an ad for this product'.

In that sense: you do not use a column for each week in the past but for each product you go back 52 weeks.

3) You seemed to be worried that the model could not figure out a certain rule like 'only if the values of column X and of column Y are high then predict TRUE, else predict FALSE'. However, whichever model you choose a model from the "first league of complexity" (i.e. anything other than linear models like neural nets, tree boosting methods like random forest, gradient boosting, geometric methods like SVM, ...) these models can figure out arbitrarily complicated regions if only the data tells them to do so (provably!!!). For example: for NN with just ONE HIDDEN LAYER(!) this [I believe] is the celebrated Stone Weierstrass theorem (https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem, NNs with just one hidden layer form an algebra).

Example: SVM. Navigate your webbrowser to https://www.csie.ntu.edu.tw/~cjlin/libsvm/. Scroll down to the java applet and place two different sets of colored points and play around with the hyperparameter C and g a little bit and you will see results like this:

That means that even (much more complicated!) rules like the ones you formulated above will eventually be captured by the model. That's the reason I would not worry about that too much.

EDIT: R code:

library(data.table)
set.seed(1234)
dt = data.table(time = 0:250)
dt = dt[, y := sin(time/100*2*pi)*30 + rnorm(dt[, .N], mean=0, sd = 10)]
plot(dt$time, dt$y, type="l")



lag = function(x, k, fillUp = NA) {
  if (length(x) > k) {
    fillUpVector = x[1:k]
    fillUpVector[1:k] = fillUp
    return(c(fillUpVector, head(x, length(x)-k)))
  } else {
    if (length(x) > 0) {
      x[1:length(x)] = fillUp
      return(x)
    } else {
      return(x)
    }
  }
}



K = 3
for (k in 1:K) {
  eval(parse(text=paste0("dt = dt[, y_past_", k, " := lag(y, k)]")))
}
train = copy(dt)
train = train[K:dt[, .N]]
train = train[, time := NULL]
model = lm(y ~ ., data = train)
pred = predict.lm(object = model, newdata = train, se.fit = F)
train = train[, PREDICTION := pred]
plot(dt$time, dt$y, type="l")
train = train[, time := K:dt[, .N]]
lines(train$time, train$PREDICTION, col="red", lwd=2)

Regards,

FW