RankFromSets: Scalable set recommendation with optimal recall

We study a variant of user-item recommendation where each item has a set of attributes, such as tags on an image, user reactions to a post or foods in a meal. We focus on the latter example, with the goal of building a meal recommender for a diet tracking app. Meal recommendation is challenging: (i) each item (meal) is rarely logged by more than a handful of users, (ii) the database of attributes (foods) is large, and (iii) each item is tagged with only a handful of attributes. We propose RankFromSets (RFS), a flexible and scalable class of models for recommending items with attributes. RFS treats item attributes as set-valued side information and learns embeddings to discriminate items a user will consume from items a user is unlikely to consume. We develop theory connecting the RFS objective to optimal recall and show that the learnable class of models for RFS is a superset of several previously proposed models. We then develop a stochastic optimization method for RFS that uses negative sampling to scale to massive problems like meal recommendation. In experiments on a real dataset of 55k users logging 16M meals, the new method outperforms competing approaches while learning embeddings that reveal interpretable structure in user behavior. Code is available on GitHub (https://github.com/altosaar/rankfromsets).