To be more general here in the introduction, the situation is that we have a user-item preference matrix which is also evolving over time. Essentially, we have a collection of user-item preference matrices, one for each time point. The preference matrix can be, for example, user’s preference on a collection of books, popularity of movies among people, effectiveness of a set keywords on a collection of campaigns. The prediction task is really to forecast a user-item preference matrix of the next time point.

From another angle, we really have a 3D preference matrix of with axes being users, items, and time. Given the matrix, the task is to predict a future slice of the matrix along the time axis.

The problem is very interesting and makes a lot sense in the real world. For example, the cinema can predict which movies will be popular next day/week/month, and make arrangements according to the predictions to maximize the profit.

Table of content

Link to the code

Coding

I would use Python for coding on top of Spark environment. Some Python packages involved and worth of mentioning are listed as follows.

  • numpy for array and matrix operation.
  • pandas for data preprocessing and transformation
  • sklearn for machine learning model, e.g., random forest regression running on a single cpu core.
  • mllib, Spark machine learning library for machine learning models e.g., collaborative filtering running parallel on Spark environment.
  • matplotlib for plotting.
  • pyspark Spark python context enabling python on Spark.
  • statsmodels for autoregressive-moving-average ARMAR model on time series prediction.

The reasons are

  • It is essentially log data generated possibly from some streaming system e.g., Kafka.
  • The example data file is small compared to the real situation. The preprocessing and learning should be able to scale on very large dataset. Therefore, the given task naturally requires framework like Spark or Hadoop.
  • During the data preprocessing and exploration, a lot of operations are done based on key/value pairs. MapReduce heuristics will naturally optimize these key/value operations.
  • Machine learning is also expected to be scalable on large scale data. Spark has a machine learning library with parallelized learning algorithms.

Complete code for customer A and results are in my Github.

Complete code for customer B and results are in my Github.

Code can be run in Spark with the following command (in my case)

$../../spark-1.4.1-bin-hadoop2.6/bin/spark-submit solution.py

Question 1: Modeling

I would use collaborative filtering to impute missing values then random forest regression trained locally for each individual keyword.

Data exploration

Overview

  • There are 93 days. Logs are available for each day.

    First dayLast day
    Actual date2015-08-172015-11-17
    Index092

  • About 1.19% criterions are not unique to ad group meaning that keyword can be defined as adgroup_id+criterion_id. On the hand, 57.04% keywords are not unique to campaign meaning that I cannot combine keyword_id and campaign_id. Different campaigns share keywords.

  • The histogram of the number of logs for campaign, keyword and date are shown in the following figure.

    photo

  • The availability of logs in campaign/keyword/date is shown in the following figure. The figure demonstrates

    • The date can be seen as a preference matrix of keywords on campaigns over time (time series preference matrices).
    • Different campaigns share keywords.
    • Data are very sparse.

    photo

  • Ideally, I would model the data with all dimensions (campaign, keyword, time). However, due to the sparseness, I will collapse the campaign-keyword-time matrix to a keyword-time matrix by summing along the campaign dimension.

  • In particular, I will work with the keyword-time matrix in the following part of the analysis.

Behavior of an average keyword over time

  • The following plot shows the global behavior (mean keyword) over time, shown separately for different match_type and the number of click for individual log.

    photo

  • There is a heart beat/periodical pattern in the plot above. However, the different between different match_type is quite small. Again, I would ideally model the data with different match_type. However, I would average over match_type due to the sparseness.

  • The following plot shows the global behavior over time, without making difference on match_type.

    photo

Behavior of individual keyword over time

  • Looking at the behavior of individual keyword, I also observe the periodical pattern of having high click typically on Monday and Sunday and low click during the working days. However, the patterns are quite different from one keyword to another as shown in the following plot.

    photo

  • If there is a pattern base on weekdays, how about average over weekdays? The following plot shows the behavior of individual keyword averaged over weekdays. The pattern is somehow more clear that people did more searches at the beginning or towards the end of the week while did fewer searches during the week.

    photo

  • The observations suggest that it might be a good idea to build a regression model based on weekdays. For example, use data from previous Monday to Sunday to predict current Monday, and use data from previous Tuesday to this Monday to predict this Tuesday.

Missing data

For now the practical problem is really how much data I actually have or can use. The following plots show all available data points in keyword-time matrix in terms of different match type. The plot demonstrates that

  • Different matching type generates different entries in the data matrix since the individual percentages sum up to the all.

  • Interesting! This actually says that different match type did not generate overlapped data.

  • In addition, I only have about 10% data available in the matrix by putting together data generated from different match type.

  • It actually suggests that to deal with sparseness I should really pool data together other than model them in high resolution.

    photo

Learning and prediction

So far, the hints from basic analysis are

  • I should pool keyword data from different campaigns and match types to tackle the sparseness.
  • The data is still very sparse even pooling logs from different dimensions. We still need to work out the missing values in the matrix.
  • There is a heart beat / weekday pattern for different keywords across time which essentially goes up at the beginning or towards the end of the week and goes down during the week. The periodical pattern suggests that the preference of different keywords are somehow correlated because of the human behaviour. In machine learning, it allows collaborative analysis e.g., collaborative filtering.
  • Another patten shown in the data besides periodical pattern is that the number of clicks/conversions decay over weeks.
  • Behavior of individual keywords are quite different which means that local regression model built based on individual keyword might be a good idea. However, with additional/external data, one can group keywords into different keyword groups and build a regression model for each group.
  • I should focus on predicting click and conversion data, as the ratio is the conversion rate.

Missing value imputation

  • As already mentioned, the first problem is that I need to compute the missing values in the keyword-time matrix of click data and conversion data.

  • This can be tackled by collaborative filtering. The technique is well-known for recommender system and is implemented in Spark machine learning library. The actual algorithm running in the backend is alternating least square ALS.

  • In particular, I will be working on a keyword-time matrix

    ItemValue
    Missing entry443835
    All entry490947
    Missing at90.40 %
    Keywords5279
    Time93

  • For now, I only divide all data into training and test where test data is just to make prediction on the last day. Parameter tuning is done on training data. Then model is trained with the best parameters.

  • Parameter selection result is listed as in the following table.

    RankLambdaNumIterRMSE
    300.100101.64
    300.100151.62
    300.100201.60
    300.010101.50
    300.010151.45
    300.010201.42
    300.001101.50
    300.001151.44
    300.001201.44
    200.100102.27
    200.100152.24
    200.100202.22
    200.010102.16
    200.010152.13
    200.010202.14
    200.001102.20
    200.001152.10
    200.001202.14
    100.100103.40
    100.100153.44
    100.100203.45
    100.010103.37
    100.010153.36
    100.010203.33
    100.001103.43
    100.001153.30
    100.001203.34

  • Compare collaborative filtering approach with mean imputation approach on click data.

    MethodRMSE
    CF1.42
    Mean imputation93.47

  • The following figure shows the results of imputation on click data for 4 keywords. Each subplot shows the click number of the keyword along time. Vertical lines correspond to non-missing data.

    photo

  • Similarly, parameter selection on conversion data is shown in the following table.

    RankLambdaNumIterRMSE
    300.100101.63
    300.100151.62
    300.100201.60
    300.010101.50
    300.010151.45
    300.010201.43
    300.001101.51
    300.001151.45
    300.001201.42
    200.100102.27
    200.100152.22
    200.100202.22
    200.010102.15
    200.010152.13
    200.010202.13
    200.001102.17
    200.001152.13
    200.001202.13
    100.100103.55
    100.100153.41
    100.100203.42
    100.010103.35
    100.010153.30
    100.010203.29
    100.001103.37
    100.001153.34
    100.001203.29

  • Compare collaborative filtering approach with mean imputation approach on conversion data.

    MethodRMSE
    CF1.42
    Mean imputation93.47

  • The following figure shows the results of imputation on conversion data of 4 keywords. Each subplot shows the conversion number of keyword along time. Vertical lines correspond to non-missing data.

    photo

Localized regression model

  • The idea is to build a regression model locally for each keyword in order to capture the weekday pattern of clicks and conversions.

  • At the same time, the weekday regression model will not collapse for some keywords in which clicks/conversion decays over weeks.

  • In particular, I have for each keyword data from day 0 to day 92. The the final task is predict the value for day 93.

  • As training data x and y, I construct from historical data

    X(Feature)Y(Label)
    day 0, day 1, …, day 67
    day 1, day 2, …, day 78
    ……
    day 85, day 86, …, day 9192
    day 86, day 87, …, day 92?

  • We use random forest regression model from scikit-learn. The training rooted mean square error RMSE are shown in the following plot.

    photo

Other possibilities

  • The approach described here is collaborative filtering for missing value imputation + local regression model based on weekday pattern for individual keyword.

    • Some improvement on current implementation:
      • Log transformation of the click and conversion data to make them more like Gaussian distributed. So that regression can be better trained.
      • Add parameter selection procedure on training local random forest regression model.
      • Make training/validation/test partitions for parameter selection scheme.

  • Other possibilities base on current data

    • Missing value imputation + global regression for all keyword. The only difference here is to train a global regression model with all keyword data instead of having one regression model for individual keyword.

      • Pro: Consider more information when making a prediction. More flexible for distributed computation.
      • Con: Not sure whether other keywords are actually related to the current one.

    • Missing value imputation + group regression. Divide keywords into groups according to campaign information, then build a regression model for each keyword group.

      • Pro: Consider other keyword in the same group. Model is trained with more information.
      • Con: Sparse data which is difficult to find the keyword group.

    • Missing value imputation + time series prediction model e.g., autoregression model, autoregressive–moving-average model. Previous regression models are built based on the observation that there is a weekday pattern on the number of click or conversions. However, data here is essentially time series of the preference over keywords. Therefore, the time series regression can be applied here.

      • Pro: Data is essentially time series.
      • Con: Local model on individual keyword. Neglect weekday pattern.

    • Gaussian process locally for each keyword. The observation for each keyword can be taken as a collection (21) of time series curves from Monday to Sunday. Gaussian process essentially assume observations on different day (e.g., Monday) follows a Gaussian distribution and the correlation between different days (e.g., Monday and Tuesday) follows a covariance structure.

      • Pro: Advanced model for time series modeling. Training is still feasible on the data of this size. Prediction comes with confidence interview (variance).
      • Cons GP is for finding patterns not for making prediction which means that the variance of prediction might be very high. Neglect the fact that the popularity of keywords decay over weeks.

    • Ensemble models combining multiple local/global regression models.

  • Given more data, it is really to make regression model on fine-tuned groups

    • When click/conversion can be segmented on devices, it makes sense to predict click, conversion, conversion rate for each device.
    • When more information about keywords is available, it is then realistic to put keywords into different groups and run regression/missing value imputation on different group.

Question 2: Pitfall

The assumption in regression $$y=wx+b$$ is the output variable $$y$$ is Gaussian distributed if input features are Gaussians which is true in most of cases. Therefore, if the number of conversions is few or zero, when learning the regression model, the distribution of $$y$$ is skewed.

  • When the number of conversions is few, it might make sense to have a log transformation of the number of conversions. As a results, the distribution of the number of conversion is more like Gaussian.
  • When the number of conversion is zero and there are many of it, it might be a good idea to have a two stage model. In the first stage, having a binary classifier/outlier detector to predict if the conversion of a keyword is zero or non-zero. In the second stage, building a regression model to predict the actual conversions for keyword predicted to have conversions in the first stage.

Question 3: Measure the performance

In order to compare the performance of two models (model A and model B) in term of predicting conversion rate, one can work on

  • Historical data
    • by comparing rooted mean square error (RMSE) computed from all available test data points.
  • Future data
    • by comparing rooted mean square error (RMSE) computed from all available test data points.
    • by performing an A/B test in order to claim that updating keywords by deploying model A significantly (statistically) boots the conversion rate compared to deploying model B.

On historical data

RMSE as measure of success

Conversion rate ($$R_{j}$$) of a keyword $$j$$ is defined as the ratio between the number of conversions and the number of clicks during a fixed sample period as

$$ ConversionRate = \frac{Conversion}{Click} $$

The sample period can be 1 day or a few hours. Essentially, the number of clicks and the number of conversions during the period are collected and assigned to the sample point at the end of the sample period. The conversion rate for the period is computed accordingly and also assigned to the sample point. The measure of success is the rooted mean square error (RMSE) between the true conversion rate $$R$$ and the predicted conversion rate $$\hat{R}$$ defined as

$$RMSE = \sqrt{\sum_{j=1}^{M}\sum_{i=1}^{N}(R_{ij}-\hat{R}_{ij})^2}$$

assuming there are $$M$$ keywords and $$N$$ time points.

The test procedure can be described as follows.

  • Assume we have historical data of conversion rate of $$M$$ keywords on N time points (e.g., N days)

    $${{R_{ij}}{i=1}^{N}}{j=1}^{M}$$

  • With model A we are able to predict the conversion rate of $$M$$ keywords on N time points

    $${{\hat{R}^A_{ij}}{i=1}^{N}}{j=1}^{M}$$

  • With model B we are able to predict the conversion rate of $$M$$ keywords on N time points

    $${{\hat{R}^B_{ij}}{i=1}^{N}}{j=1}^{M}$$

  • Rooted mean square error of two models are computed according to

    $$RMSE_A = \sqrt{\sum_{i=1}^{N}\sum_{j=1}^{M}(R_{ij}-\hat{R}^A_{ij})^2}$$

    $$RMSE_B = \sqrt{\sum_{i=1}^{N}\sum_{j=1}^{M}(R_{ij}-\hat{R}^B_{ij})^2}$$

  • We say model A outperforms model B in predicting conversion rate if RMSE of A is smaller than RMSE of B.

  • Pro:

    • The test is fast and cheap.

  • Con:

    • The problem is that the difference between two RMSEs might be very small or due to some randomness. Therefore, the claim based on RMSE might not be very well justified.
    • Overfit training data if the test is not conducted in a proper way.

On future data

In stead of testing the model on historical data, one can perform the test on line. For example, if the sample period is 1 day, one can predict the conversion rate of tomorrow using all data available upto today; then repeat on the following days.

RMSE as measure of success

In stead of testing the model on historical data, one can perform the test in a online fashion. For example, if the sample period is 1 day, one can predict the conversion rate of tomorrow using all data available upto today; then repeat on the following days.

The test procedure is described as follows.

  • Assume we have some data available for training which allow us to predict (with model A and model B) the conversion rate of of $$M$$ keywords for tomorrow (day 1)

    $${\hat{R}^B_{j1}}{j=1}^{M} , {\hat{R}^B{j1}}_{j=1}^{M}$$

  • The next day we will collect the real conversion rates for $$M$$ keywords

    $${R^B_{j1}}_{j=1}^{M}$$

  • The procedure can be repeated for $$N$$ days in the future. In the end we will collect the true conversion rates of $$M$$ keywords

    $${{R_{ij}}{i=1}^{N}}{j=1}^{M}$$

    conversion rates of $$M$$ keywords predicted by model A

    $${{\hat{R}^A_{ij}}{i=1}^{N}}{j=1}^{M}$$

    conversion rates of $$M$$ keywords predicted by model B

    $${{\hat{R}^B_{ij}}{i=1}^{N}}{j=1}^{M}$$

  • Rooted mean square error of two models are computed according to

    $$RMSE_A = \sqrt{\sum_{i=1}^{N}\sum_{j=1}^{M}(R_{ij}-\hat{R}^A_{ij})^2}$$

    $$RMSE_B = \sqrt{\sum_{i=1}^{N}\sum_{j=1}^{M}(R_{ij}-\hat{R}^B_{ij})^2}$$

  • We say model A outperforms model B in predicting conversion rate if RMSE of A is smaller than RMSE of B.

    • Pro:
      • Less likely to overfit training data compared to testing on historical data
    • Con:
      • The problem is that the difference between two RMSEs might be very small or due to some randomness. Therefore, the claim based on RMSE might not be very well justified.
      • Take time and money to perform the test.
      • Two models predict on a fix collection of keywords over time which does not make much sense and gain addition profits.

Conversion rate as measure of success (A/B test)

The model developed for predicting conversion rates of keywords is eventually applied to picking keywords during the campaign. Therefore, to compare model A and model B, it also make sense to measure the conversion rate over a collection of clicks from keywords suggested by model A and a collection clicks from keywords by model B over a certain time period.

The idea behind: if model A outperforms model B in predicting conversion rate of keywords, it will pick/update to a better collection of keywords and during the campaign period and such generate more conversions given a same amount of clicks.

  • The first problem is how many clicks are needed for the experiment. Assume the conversion rate in the group where model A is applied is $$p=60%$$. In order to say, with statistical power of $$\beta = 90%$$ and confident level of $$\alpha = 99%$$, that I can detect the conversion rate of q in group where model B is applied that is significantly different from p in A, I need $$M$$ clicks (samples). $$M$$ can be computed from

    $$M = 2(t_{\frac{\alpha}{2}} + t_{\beta})^2\frac{p(1-p)}{|q-p|^2}$$

    where $$t_{\frac{\alpha}{2}} = 2.58$$ and $$t_{\beta} = 1.29$$ are from the standard norm distribution table.

    In particular, the sample size $$M$$ is shown in the following table when conversion rate from model A is $$60%$$

    Conversion rate q in B is detected with statistical powerNumber of clicks
    0.6171889
    0.6217972
    0.637988
    0.644493
    0.652876

  • The next thing is to collect click data. One has to make sure there is no bias towards special dates, people, products, regions, etc. For example, model A and model B will both work for similar campaigns from a same company on similar product in same regions over one week.

  • After sample collection, we have the number of clicks collected from group A and group B. We also know how many conversions are from each group. I would use standard G test to test wether conversion rate in A is different from conversion rate in B.

Custom B data

Overview

  • The following plot shows the availability of data in the space of keyword-campaign-time.

    photo

  • Collapse data by summing along the campaign dimension. The following figures shows the keywords-time matrices for different match types.

    photo

  • This is not too bad as half of the entries are missing.

Collaborative filtering

  • The first thing to do is to impute missing values by collaborative filtering.

  • The following table shows the statistics of the matrix I will be working with.

    ItemValue
    Missing entry18916
    All entry33222
    Missing at56.94 %
    Keywords5537
    Time6

  • The following matrix shows the parameter selection of collaborative filtering on click data.

    RankLambdaNumIterRMSE
    20.01054.77
    20.010104.73
    20.010154.71
    20.05054.84
    20.050104.74
    20.050154.74
    20.10054.97
    20.100104.80
    20.100154.75
    30.01053.72
    30.010103.74
    30.010153.67
    30.05053.91
    30.050103.70
    30.050153.72
    30.10054.05
    30.100103.75
    30.100153.71
    40.01052.48
    40.010102.45
    40.010152.45
    40.05052.69
    40.050102.50
    40.050152.45
    40.10052.64
    40.100102.55
    40.100152.49

  • I compute the rooted mean square error RMSE on training data and compared with mean imputation approach for click data. The result is shown in the following table.

    MethodRMSE
    CF2.45
    Mean imputation20.58

  • The following matrix shows the parameter selection of collaborative filtering on conversion data.

    RankLambdaNumIterRMSE
    20.01054.75
    20.010104.73
    20.010154.75
    20.05054.80
    20.050104.73
    20.050154.74
    20.10055.02
    20.100104.77
    20.100154.74
    30.01053.76
    30.010103.74
    30.010153.70
    30.05053.84
    30.050103.72
    30.050153.69
    30.10054.06
    30.100103.75
    30.100153.71
    40.01052.51
    40.010102.46
    40.010152.45
    40.05052.75
    40.050102.48
    40.050152.49
    40.10052.58
    40.100102.58
    40.100152.49

  • I compute the rooted mean square error RMSE on training data and compared with mean imputation approach for conversion data. The result is shown in the following table.

    MethodRMSE
    CF2.45
    Mean imputation20.58

  • The following figure shows the results of imputation on conversion data of 6 keywords. Each subplot shows the conversion number of keyword along time. Vertical lines correspond to non-missing data.

    photo

Learning and prediction

  • There are only information available for click and conversion data during the first 6 days and the task is to predict the click and conversion on 7 days.

  • It is somehow difficult to use the same regression approach as built for custom A.

  • For each keyword, the clicks/conversions in the first 6 day can be taken as a time series and the task can be translated into predict the click/conversion number on the 7 day.

  • Therefore, for each keyword, I build a autoregressive-moving-average ARMAR model trained on the time series of clicks and conversions.

  • Model tuning (parameter selection) is performed locally for each keyword.

  • The training rooted mean square error RMSE are shown in the following plot.

    photo

side note

  • Learning can be improved by applying parameter selection on a training/validation/test partition other than current training/test partition.
  • Parameter selection should be added to local random forest regression. For now, I only have parameter selection on collaborative filtering not for random forest regression.
  • Paper on proper statistical test So you want to run an experiment …
  • Parameter selection should be added to selecting rank parameter in autoregressive-moving-average ARMAR model.