Consider the application:

  • We have a set of users and items.
  • Users can perform different action types (think browsing, clicking, upvoting etc.) on different items.
  • Users and items accumulate a "profile" for each action type.
  • For users such profile is a list of items on which they had performed a given action type
  • For items such profile is a list of users who performed a given action type on them
  • We assume that accumulated profiles define future actions.
  • We want to predict the action a user will take using supervised learning (classification with probability estimation)

Consider the following problem:

  • These profiles can be very sparse (millions of items and 100 million users) and it is not feasible to use them directly as features
  • We would like to compute "compressed" profiles (eigenprofiles?:)) with dimensionality < 300 that can then be efficiently stored and fed to different classification algorithms
  • Before you say "Use TruncatedSVD/Collapsed Gibbs Sampling/Random Projections on historical data" bare with me for a second.
  • Enters concept drift.
  • New items and users are being introduced all the time to the system.
  • Old users churn.
  • Old items churn.
  • At some point there are items with most of the users never seen in historical data and users with only fresh items.
  • Before you say "retrain periodically", remember that we have a classifier in the pipeline that was taught on the "historic" decomposition and the new decomposition could assign entirely different "meaning" to cells of output vectors (abs(decompose_v1(sample)[0] - decompose_v2(sample)[0]) >> epsilon) rendering this classifier unusable.

Some requirements:

  • The prediction service has to be available 24/7.
  • The prediction cannot take more than 15ms and should use a maximum of 4 cpu cores (preferably only one)

Some ideas I had so far:

    • We could retrain the classifier on the new decomposition but this would mean that we have to re-run the decomposition on the whole training dataset (with snapshot of profiles at the time of the event we want to predict) and the whole database (all current profiles) plus store it.

    • To make this work we would have to have a second database for storing the decomposed profiles that would be hot-swapped once the new retrained model is ready and all profiles have been decomposed.

    • This approach is quite inefficient in both computational resources and storage resources (this is expensive storage because the retrieval has to be super-fast)

    • We could retrain the classifier as in solution 1. But do the decomposition ad_hoc.
    • This puts a lot of constraints on the speed of the decomposition (has to have sub-millisecond computation times for a single sample).
    • This does a lot of redundant computation (especially for item profiles) unless we add an extra caching layer.
    • This avoids redundant storage and redundant computation of churned users/items at the cost of extra prediction latency and extra caching layer complexity.
  1. <---- Please help me here

    • We could use one of online learning algorithms such as VFT or Mondrian Forests for the classifier - so no more retraining + nice handling of concept drift.
    • We would need an online algorithm for decomposition that satisfies strict requirements: a) at least a part of output vectors should be stable between increments (batches). b) it can introduce new features to account for new variance in the data but should do so at a controllable rate c) should not break if it encounters new users/items

Questions/points of action:

  • Please evaluate my proposed solutions and propose alternatives
  • Please provide algorithms suitable for online learning and online decomposition (if they exist) as described in alternative 3. Preferably with efficient python/scala/java implementations with a sufficient layer of abstraction to use them in a web service (python scripts that take in a text file as dataset would be much less valuable than scikit modules)
  • Please provide links to relevant literature that dealt with similar problems/describes algorithms that could be suitable
  • Please share experiences/caveats/tips that you learned while dealing with similar problems

Some background reading that you may find useful:

Disclaimer: Our application is not strictly ad conversion prediction and some problems such as rarity do not apply. The event we would like to predict has 8 classes and occurs c.a. 0.3%-3% of times a user browses an item.

  • $\begingroup$ Notabene: This is not a recommendation problem because we would like to incorporate data from very different action types and it is very hard to model this as classical recommendation problem and use existing algorithms. But you could prove me wrong on this one:) $\endgroup$
    – JohnnyM
    Sep 7 '15 at 16:16

My take:

  • I agree with the issues raised in 1., so not much to add here - retraining and storage is indeed inefficient
  • Vowpal Wabbit http://hunch.net/~vw/ would be my first choice
  • stability of output between increments is really more of a data than algorithm feature - if you have plenty of variation on input, you won't have that much stability on output (at least not by default)
  • hashing can take care of the variation - you can control by a combination of three parameters: the size of the hashing table and the l1/l2 regularization
  • same for the new features / users (I think - most of the applications i used it had a ercord representing a user clicking or not, so new users / ads were sort of treated "the same")
  • normally I use VW from the command line, but an example approach (not too elegant) for controlling from Python is given here: http://fastml.com/how-to-run-external-programs-from-python-and-capture-their-output/
  • if you prefer sth purely Python, then a version (without decomposition) of an online learner in the Criteo spirit can be found here: https://www.kaggle.com/c/tradeshift-text-classification/forums/t/10537/beat-the-benchmark-with-less-than-400mb-of-memory
  • I am not sure how to handle the concept drift - haven't paid that much attention to it so far beyond rolling statistics: for the relevant variables of interest, keep track of mean / count over recent N periods. It is a crude approach, but does seem to get the job done it terms of capturing lack of "stationarity"
  • helpful trick 1: single pass over data before first run to create per feature dictionary and flag certain values as rare (lump them into a single value)
  • helpful trick 2: ensembling predictions from more than one model (varying interaction order, learning rate)
  • $\begingroup$ Thank you for your input :) VW is an interesting recommendation and I like the python online learner. To extend your answer can you please provide sample code how to feed VW with profiles (I'm assuming dimensionality reduction will be handled in VW) $\endgroup$
    – JohnnyM
    Sep 14 '15 at 18:09
  • $\begingroup$ Assuming each record is a description of an "event" (a user-ad interaction, parametrized by user / ad info, and recording 0/1 target), the best description on VW input is: mlwave.com/… As for dimensionality reduction, you can control via matrix factorization options (rank of the projection) and (implicitly) via the hashing table size. I think LDA can be abused if you care about interpretation, but I am not sure. In general, have a look at: github.com/JohnLangford/vowpal_wabbit/wiki/… $\endgroup$
    – kpb
    Sep 16 '15 at 8:50
  • $\begingroup$ Thanks for the update. However the problem with mlwave and Criteo dataset based tutorials is the fact that categorical features come pre-hashed (some of them might be a "topic" based on user behavior) this does not solve the problem of creating features from user profiles. But I have almost no experience with VW so there might be something obvious I'm missing. Can I feed it directly with something like 1 | [1,2,3]; 2 | [3,6,8,11] ? $\endgroup$
    – JohnnyM
    Sep 16 '15 at 16:39
  • $\begingroup$ I don't have a vowpal installation on the computer I'm typing from, so I can only share a few "offline" thoughts: 1. if you replace {1,2,3} with letters, drop the semicolons and add variable names, this could work 2. you can verify/experiment yourself via hunch.net/~vw/validate.html 3. would it be possible to paste a line or two of your input? i am quite certain that hashing is done internally in VW anyway, so [1,2,3] as a feature value could work. $\endgroup$
    – kpb
    Sep 17 '15 at 8:04
  • $\begingroup$ I got a chance to dig a bit deeper into vw and it seems that it indeed does support online LDA based on Variable Bayes (VB) which is exactly what I was looking for. Thanks for that! papers.nips.cc/paper/… Now I'll have to somehow make this applicable for production use:) $\endgroup$
    – JohnnyM
    Sep 20 '15 at 16:52

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.