Predictive Client-side Profiles for Personalized Advertising Mikhail Bilenko Microsoft Research Redmond, WA 98052 [email protected] Matthew Richardson Microsoft Research Redmond, WA 98052 [email protected] ABSTRACT Personalization is ubiquitous in modern online applications as it provides significant improvements in user experience by adapting it to inferred user preferences. However, there are increasing concerns related to issues of privacy and control of the user data that is aggregated by online systems to power personalized expe-riences. These concerns are particularly significant for user pro-file aggregation in online advertising. This paper describes a practical, learning-driven client-side perso-nalization approach for keyword advertising platforms, an emerg-ing application previously not addressed in literature. Our ap-proach relies on storing user-specific information entirely within the user’s control (in a browser cookie or browser local storage), thus allowing the user to view, edit or purge it at any time (e.g., via a dedicated webpage). We develop a principled, utility-based formulation for the problem of iteratively updating user profiles stored client-side, which relies on calibrated prediction of future user activity. While optimal profile construction is NP-hard for pay-per-click advertising with bid increments, it can be efficiently solved via a greedy approximation algorithm guaranteed to pro-vide a near-optimal solution due to the fact that keyword profile utility is submodular: it exhibits the property of diminishing re-turns with increasing profile size. We empirically evaluate client-side keyword profiles for keyword advertising on a large-scale dataset from a major search engine. Experiments demonstrate that predictive client-side personaliza-tion allows ad platforms to retain almost all of the revenue gains from personalization even if they give users the freedom to opt out of behavior tracking backed by server-side storage. Addition-ally, we show that advertisers can potentially increase their return on investment significantly by utilizing bid increments for key-word profiles in their ad campaigns. Categories and Subject Descriptors H.2.8 [Database Applications]: Data Mining; H.3.4 [Systems and Software]: User profiles and alert services. General Terms Algorithms, Human Factors, Experimentation, Measurement Keywords Online advertising, client-side personalization. 1. INTRODUCTION Personalization is a core component of many web applications, where its uses vary from re-ranking search engine results to re-commending items in domains such as news or online shopping. Traditional uses of personalization center on customizing the out-put of an information system for a given user based on attributes composing their profile. Profile attributes may be explicitly or implicitly obtained, where explicit attributes are provided by the user or computed deterministically (e.g., user-submitted demo-graphics or IP-based location). Implicit user attributes are in-ferred based on the logs of the user’s prior behavior, e.g., past searching, browsing, reviews or shopping transactions. A wide variety of personalization approaches have been proposed in re-cent years; notable examples include algorithms that leverage preference correlations across users (i.e., collaborative filtering), and methods that use past behavior to assign users to one or more pre-defined categories (i.e., “targeting segments” in online adver-tising). Raw behavior logs used to infer implicit user attributes are typi-cally stored in the online service’s datacenter (server-side), where they are processed to compute each user profile in a compact re-presentation chosen for the application at hand. Examples of such representations include advertiser-defined categories for beha-vioral targeting in display advertising [3][37] and low-dimensional latent topics in collaborative filtering methods based on matrix decomposition [24]. The resulting profiles are used in subsequent interactions with the user to adjust the output of the application to user preferences. Server-side aggregation is being increasingly challenged by con-sumer and privacy advocates due to the fact that it limits users’ ability to view and control data associated with their behavior, raising the need for privacy-enhanced personalization methods. In the context of personalized search, methods have been pro-posed for constructing category-based profiles on a user’s ma-chine (client-side), where they are employed to re-rank search results [34][36]. In online advertising, several alternative ad deli-very architectures have been proposed based on client-side cate-gory-based profiles used to perform ad selection locally [13][10][35]. The previous approaches’ reliance on broad catego-ries for representing user interests is a significant barrier for their use in search and contextual advertising, where campaigns target highly specific intents via bids on individual keywords (short phrases that match the query or webpage exactly or approximate-ly). Furthermore, these approaches require significant architec-tural changes to ad delivery pipelines and installation of additional components client-side both present significant barriers to adop-tion. In this paper, we describe a novel approach to keyword-based personalization for search advertising that is practical, principled, and privacy-friendly. Based on keyword bid increments that allow differentiating between users with casual and long-term topical interests, the approach naturally integrates with existing ad deli- Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. KDD’11, August 21–24, 2011, San Diego, California, USA. Copyright 2011 ACM 978-1-4503-0813-7/11/08...$10.00. 413very platforms, campaigns, and bid optimization frameworks, allowing advertisers to experiment with highly-granular ad perso-nalization without significant infrastructure investments. While highly practical, the described approach for keyword pro-file construction is derived from a principled utility-based frame-work.