Implicit Feedback Factorization Machines : Format of Input and Recommendations

Question

I am looking at methods for making product recommendations to customers based on attributes of the customer (e.g. demographics) and past product interactions (e.g. did or did not buy). There are ~250 products to recommend. This is of course an implicit feedback recommendation engine setup.

I have two questions as it pertains to the use of Factorization Machines.

1) Is the only way to structure the data for this algorithm to create 1 row per customer / product interaction with columns for the customer attributes and a one-hot encoded matrix for which product is being considered? A 1/0 included for the target column. This would be a pretty sparse matrix and in libsvm format for example. All positive interactions (the customer bought) and a sample of negative examples for each customer would be included if each combination of customer and product is not feasible.

2) Once a model is built....how to serve recommendations? Does one have to iterate through all the products (variants) for each customer? This seems prohibitive.

While this is described as a product recommendation, a click through model in adtech would be the other common situation. Wondering how people deal with this in the real world?

Answer 1

Your intuition is correct, unless we have a few tens of thousand items it can quickly become too expensive to generate hundred of thousands of rankings and then sort them. What is done is commonly referred as "candidate items selection"; estimates are generated for a subset of the available items. We aim to avoid unnecessarily evaluating items that have extremely small probability to be in the final top-$k$ ranking. To that extent, there is no difference due to Implicit or Explicit feedback mechanisms.

Simplistically, the above mentioned "pruning" can be achieved by simply evaluating items $I_U$ such that these are the items that were ranked by a group of users $U$ who themselves are clustered together the candidate user $U_c$. That are far more rigorous approaches: A prototypical algorithm for this task is Weighted AND (WAND) as this was proposed by Broder et al. (2003) in Efficient query evaluation using a two-level retrieval process. It creates what could be considered an "approximate" ranking based on the presence or absence of certain high-impact features and then if that approximate ranking is above a certain threshold then a full ranking is estimated. Asadi & Lin's (2013) Effectiveness/Efficiency Tradeoffs for Candidate Generation in Multi-Stage Retrieval Architecture give a nice overview of different candidate generation approaches. Recent develops build on WAND (e.g. Borisyuk et al. (2016) CaSMoS: A Framework for Learning Candidate Selection Models over Structured Queries and Documents) as well as circumvent altogether (e.g. Wang X. et al. (2016) Skype: top-k spatial-keyword publish/subscribe over sliding window). For the sake of completeness: the actual indexing system used by each algorithm is crucial. Without getting into any gory details, WAND and other algorithms like BMW, are what we call DaaT - Document-at-a-time approaches, documents are evaluated in an iterative manner and we have document-ordered indices. There are other approaches like Term-at-a-time (TaaT), where we have frequency-order indices and Score-at-a-Tie (SaaT) where we have impact-order indices. Crane et al. (2017) A Comparison of Document-at-a-Time and Score-at-a-Time Query Evaluation offer a comprehensive look into this comparison.

Final caveat: As one might correctly recognise the approaches previously mentioned exaggerate the problem of the "rich-getting-richer" issue, i.e. popular items getting consistently recommended more often. While this phenomenon is well-known for some years (e.g. Celma & Cano (2008) From hits to niches? or how popular artists can bias music recommendation and discovery) it is still an extremely active field of study (e.g. see Wang Y. et al. (2015) Peacock: Learning Long-Tail Topic Features for Industrial Applications or Antikacioglu & Ravi (2017) Post Processing Recommender Systems for Diversity) and if indeed we need to rank only a subset of the available candidate it would be good to keep it in mind.

To succinctly address the initial question of input formats: Encoding negative examples (or absence of inforation) can indeed lead to extremely large datasets of sparse data. One of the first ML formats to address this was the LibSVM format for sparse data. LibSVM is still generally accepted as a semi-reasonable standard especially when it comes to ranking (i.e. recommender systems) applications. For example, both XGBoost and Tensorflow offers way to read LibSVM data (see respectively the links here and here for more details). Nevertheless a lot of things are case specific and particular to algorithm used; the old Netflix Prize used per movie ratings in .txt files while the latest 2019 RecSys challenge reports session information in .csv files. Ultimately we do need "some sparse matrix" functionality and whether or not that is going to be provided by the format we use (e.g. LibSVM) or we just going to build it up as we read the data in (e.g. in the RecSys challenges) are up to us. Familiarising oneself with the particulars of the algorithms input format (e.g. the DMatrix in the case of XGBoost) is crucial when data size is an important factor.