Localizing Embeddings for Recommendation Systems using Binary Pairwise Comparisons

Abstract

Recommendation systems predict the preferences of users (who may be, for example, customers of an online shopping website or moviegoers), to various items (for example, consumer products or movies). One way this information is modeled is the ideal point model of preference, in which items and users live in an n-dimensional Euclidean space where each dimension represents an attribute and a small distance between an item and user indicates the user has a preference for that item. We seek to determine an embedding of many items and users given only binary pairwise comparisons of the form "user x prefers item q_i to item q_j." First, we present an optimization-based framework for localizing new items and users given an existing embedding. We demonstrate that user localization can be formulated as a simple constrained quadratic program. Further, we show that although item localization produces a quadratically-constrained quadratic program which is difficult to solve, we can make the problem more computationally tractable by strategically combining comparisons to make the quadratic constraints into linear constraints. Finally, we show that by iteratively applying this localization method to every item and user, we can recover an embedding that agrees with almost every comparison, allowing us to iteratively improve the accuracy of a noisy embedding or even create an embedding using no a priori knowledge apart from the list of pairwise comparisons. Throughout, we present implementation details and optimization algorithms which make the recommendation system computationally efficient even with large datasets and dimensionalities.