Events

Mr. Lin An
Ph.D. Candidate in Algorithms, Combinatorics, and Optimization
Tepper School of Business
Carnegie Mellon University

Real-time personalization has advanced significantly in recent years, with platforms utilizing machine learning models to predict user preferences based on rich behavioral data on each individual user. Traditional approaches usually rely on embedding-based machine learning models to capture user preferences, and then reduce the final real-time optimization task to one of nearest-neighbors, which can be performed extremely fast both theoretically and practically. However, these models struggle to capture some complex user behaviors, which are essential for making accurate recommendations. Transformer-based models, on the other hand, are known for their practical ability to model sequential behaviors, and hence have been intensively used in personalization recently to overcome these limitations. However, optimizing recommendations under transformer-based models is challenging due to their complicated architectures. In this paper, we address this challenge by considering a specific class of transformers, showing its ability to represent complex user preferences, and developing efficient algorithms for real-time personalization.

We focus on a particular set of transformers, called simple transformers, which contain a single self-attention layer. We show that simple transformers are capable of capturing complex user preferences, such as variety effects, complementarity and substitution effects, and irrational choice behaviors, which traditional embedding-based models cannot capture. We then develop an efficient algorithm for real-time personalization under simple transformer models. Our algorithm achieves near-optimal performance with sub-linear runtime with respect to the size of the item pool. Finally, we demonstrate the effectiveness of our approach through an empirical study on large datasets from Spotify and Trivago. Our experiment results show that (1) simple transformers predict user preferences substantially more accurately than non-transformer baselines and nearly as accurately as deeper transformer models, and (2) our algorithm completes personalized recommendation tasks both quickly and effectively. Specifically, under a fixed candidate budget, our method achieves objective values that are, on average, 20.86% higher than those obtained using k-Nearest Neighbor and 20.56% higher than those from Beam Search.