Implicit Feedback Factorization Machines : Format of Input and Recommendations

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?

• What papers have you already read? Almost all collaborative filtering papers would be answering these queries. And ~250 are not that much; most applications are looking into $p$ in the thousands if not tens of thousands... – usεr11852 Apr 16 at 8:16
• What papers do you recommend, especially for number 2? – B_Miner Apr 16 at 10:55
• I remember a paper from Karypis on this but I can't quickly locate it now. Check the link here: towardsdatascience.com/… it is quite good. In general the term you want to look at is "candidate items strategies". – usεr11852 Apr 16 at 12:25
• Nothing in that link about it that I can see....good overview of many types of recommender systems though. – B_Miner Apr 16 at 16:38
• Also consider: do customers buy the same thing again and again, or are there time gaps/will a single customer typically only buy a single one (e.g. I am shocked by how many adds tried to sell me another car after buying a car - ask me again in a few years! - instead of extra stuff that would be useful with the car). For that retaining some information on timing may be useful at some stage of the process. – Björn Apr 18 at 9:44

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.
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.