6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Side note: You know simple linear regression, right? Well, then you essentially know time series because the most simple models in TSA go like this: Assume you have same target values $y_1, ..., y_n$ then at each point in time t use the 'lagged' variables $y_{t-1}, y_{t-2}, ..., y_{t-k}$ as you $k$-dimensional input feature vector and then do a linear regression. In that sense you can cleverly mix the TSA with your 'surfing on the wave of NOW'-model by just incooperating 'usual' or 'lagged' features. Examples: ... $\endgroup$ – Fabian Werner Jun 13 '18 at 6:09
  • 1
    $\begingroup$ In the last X weeks, how often did the customer buy the product? In the last X weeks, how often did the customer react to an ad email advertising this product? Here, X is some kind of hyperparameter that you need to play around with... However, in your scenario I guess that you can probably select X to be very high because a general affinity to pizza or to tunafish will not come and go but will stay for the rest of your life: either you love it or you don't :-) $\endgroup$ – Fabian Werner Jun 13 '18 at 6:10
  • $\begingroup$ @FabianWerner Thanks, this is good info!! What is the name of these simple TSA models that are just linear regression in disguise? I will update my model in the next days (unless someone offers an answer beforehand) after I read up a bit on those models. Also, by "play around with" I assume you mean "use cross-validation (or something similar) until you find its minimum"? $\endgroup$ – l7ll7 Jun 13 '18 at 6:40
  • $\begingroup$ The name is MA (moving average). It is a part of the very first standard TSA model AR(I)MA. Play around is not formulated very well, but yes, just test a few values to get a feeling which values are “good”. Also I would not worry too much about b: once you select a mode that is “complicated” enough to cut out “banana shapes” etc. (like SVM, NN, RF, Gradient Boosting, ...) the Mode will figure out whether or not there are these patterns. What you could to to support the model in its decisions is to encode (supposedly) “high” probs for buying using certain ranges of values, I.e. ... $\endgroup$ – Fabian Werner Jun 13 '18 at 7:37
  • $\begingroup$ you could use something like $e^{-\text{time difference between ad email and product buy}}$ in the last week(s). In that way the value of the feature is very big if the points in time where the ad email was sent and when the customer bought the product are close and it is very little if the difference is big. Should there be some assertion like 'if the customer bought the product withing a short time after the ad email' then you make it easy for the model to spot this pattern because it simply needs to select 'featureValue > threshold' where threshold=$e^{-7}$ or so. $\endgroup$ – Fabian Werner Jun 13 '18 at 7:43
3
$\begingroup$

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:

enter image description here

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

enter image description here

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: enter image description here

K=10: enter image description here )

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:

enter image description here

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

$\endgroup$
  • $\begingroup$ I can just say "wow"! Such a great answer! I think this was the most deserving +1 I ever gave. (It will take me a bit of time dig through it -since I've got a different deadline coming soon- so please bear with me that it will take me a bit of time until I will accept it. $\endgroup$ – temo Jun 19 '18 at 6:09
  • $\begingroup$ I knew about the Stone-Weierstrass theorem. Never would I have imagined that it would come up in a use case like this! (* blown away *). May I ask where you learned all this stuff? At the university, in books, some websites? It seems that in most books (e.g. ISLR by Hastie and Tibshirani - but others too) don't teach any of these more practical aspects... $\endgroup$ – temo Jun 19 '18 at 6:24
  • $\begingroup$ @temo: To be honest: Although I hold a Dr (german equivalent of phd) in math I did not learn any of those things at university. I hardly read books because they are mostly clumsy and I am mostly interested in a very small portion of what is written. That's the reason I am reading so much on stats.se.com and watch youtube videos and so on. On the other hand: the whole TSA stuff is just very basic and I learned it from experience: We wanted to predict the arrival times of certain train connections and one useful feature was 'how long did the train take usually?'. It also did hit me when I... $\endgroup$ – Fabian Werner Jun 19 '18 at 11:24
  • $\begingroup$ realized that this complicated ARIMA stuff is just (or, to be more precisely: even weaker than) 'take any regression algorithm and apply it to lagged features'... I thought that this TSA stuff is more complicated. It offers more depth though: The decomposition into periodical, trend and error part, the (high/low pass) filters, the frequency space and autocorrelation and related things. I just did not use them because the problems were of the same nature as given above: mixing 'surfing on the wave of now' with the past in a clever way and then hit it with Gradient Boosting :-D $\endgroup$ – Fabian Werner Jun 19 '18 at 11:26
  • $\begingroup$ @FabianWerner Sorry for taking a long time to accept this (really great!) answer; I had been away on conferences and I'm back only now. $\endgroup$ – l7ll7 Jul 6 '18 at 10:07

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.