The traditional ofline approaches are no longer suficient for building modern recommender systems in domains such as online news services, mainly due to the high dynamics of environment changes and necessity to operate on a large scale with high data sparsity. The ability to balance exploration with exploitation makes the multi-armed bandits an eficient alternative to the conventional methods, and a robust user segmentation plays a crucial role in providing the context for such online recommendation algorithms. In this work, we present an unsupervised and trend-responsive method for segmenting users according to their semantic interests, which has been integrated with a real-world system for large-scale news recommendations. The results of an online A/B test show significant improvements compared to a global-optimization algorithm on several services with diferent characteristics. Based on the experimental results as well as the exploration of segments descriptions and trend dynamics, we propose extensions to this approach that address particular real-world challenges for diferent use-cases. Moreover, we describe a method of generating traceable publishing insights facilitating the creation of content that serves the diversity of all users needs.
Why user segmentation? In order to understand why user segmentation is a crucial component of a modern real-world recommender system, it is essential to review the context of the recommendation problem as a whole. It could be argued that it is not necessary to consider any user segmentation in a recommender system, and such an approach is applied in many traditional recommendation methods. However, this claim may not hold Copyright ' 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). for current real-world systems for several reasons discussed below.
For instance, as observed by [
Another critical issue which is not addressed by the
standard techniques is data sparsity. Online services provide a
vast number of items, but only a few are read by particular
visitors. Hence, generating recommendation lists for users
with a short or, in a cold-start scenario, no browsing history
becomes a critical problem. Having noticed the insuficiency
of ofline collaborative filtering approaches, one could
consider popularity-based social recommender systems. They
are designed to address the trend-responsiveness requirement
and are capable of generating recommendations for less
active users by making use of the crowd wisdom. However, as
noted by [
Another approach which has recently attracted much
attention is based on the multi-armed bandit algorithm. Chiefly,
the ability to balance exploration with exploitation makes
multi-armed bandits a promising solution for this type of
problems — they provide stable recommendation quality due
to the exploitation component while responding to changing
popularity trends in the exploration phase. Due to their high
eficiency and scalability, the bandit algorithms have been
successfully applied to large-scale real-world recommender
scenarios ([
The long-term objective of our research is to build a
scalable recommender system that can be applied in a dynamic
domain such as a news service. Towards this goal, we focus
here on presenting an unsupervised method for clustering
users based on their semantic interests (Section 3) which
was successfully integrated with a real-time
recommendation system described in Section 2. The proposed solution
has been used to personalize the largest Polish news service
Onet1, with over 10 million real users2 and nearly 500 million
pageviews on the main page monthly [
To prove the relevance of our method, the evaluation of proposed solution is performed with online A/B tests on several news sections with diferent characteristics as described in Section 4.1. Based on experimental results (Section 4.3) as well as exploration of segments descriptions and trends dynamics, in Section 5 we propose extensions to this approach that address particular real-world challenges. Most notably, we explain how our solution is used to generate traceable and actionable publishing insights for enhancing article diversity. We compare our solution to the current state of the art in Section 6 and discuss how this approach may be extended to further improve the service quality in Section 7.
2Real users are different from cookies (which are often used to estimate a number of users) as each user may have several cookies. 2. Resolve segments
Segments
API Periodically updates assignment of users to the segments stored on Hadoop
Hadoop
1. Request (with placement & user ID)
Recommendations API
3. Resolve reward function value
4. Resolve recommendation Performance
API
Combines simple measures (often based on browser events) to calculate reward value based on business' KPIs
Algorithm
Service
Selected recommendation
algorithm implementation (for instance e-Greedy bandit) ∙ First, the user segments, stored on Hadoop, are fetched by a dedicated service that provides an online view of the user-segment assignments (Figure 1,2.). This information, combined with the recommendation placement provided in the request, constitutes a complete recommendation context for the bandit algorithm. ∙ Next, the reward for each item is calculated according to a business-defined Key Performance Indicator (KPI) formula (Figure 1,3.) processed in real-time and updated with sub-second latency. The reward function calculation is context-aware so that the item rewards are computed for each segment and placement independently. ∙ Finally, the recommendation algorithm configuration is determined for a given context, and a final list of recommendations is generated (Figure 1,4.). The conifguration may define the appropriate algorithm as well as other parameters such as exploration-exploitation ratio, as described in Section 2.3.
For simplicity, we focus here on the most important stages of the recommendation generation process and omit some additional engineering challenges which had to be considered in the real-world system implementation. 2.2
To reduce latency, the flow presented in Section 2.1 is executed only as often as necessary and the generated recommendations are cached for a short period of time for every recommendation context. The cache is refreshed asynchronously so that the system is resilient to temporal break-downs. To achieve minimal latency, fresh recommendations populate the cache in the background (in the meantime stale recommendations are returned).
Since the recommendations are served from an in-memory cache, extremely low latency is guaranteed (retrieval from cache takes less than ten milliseconds) and scalability is achieved as recommendations are generated only once per context, each of which is shared by thousands of users. 2.3
The goal of a multi-armed bandit algorithm [
In the context of news recommendation, the item pool in trial is represented by the set of available articles. The algorithm aims at providing a list of articles which is the most suitable for a given context, in order to maximize the reward . Since the item pool changes dynamically, the knowledge also needs to be constantly updated in order to estimate the rewards for new items. Moreover, we adapt the trend-sensitivity of the algorithm by adjusting the knowledge window . 3
As described in Section 2.3, we use a contextual multi-armed bandit approach in which the context is represented by the recommendation placement as well as the user segment. In this section, we describe the algorithm for building clusters of users for which the recommendations are generated.
Our solution is based on the machine learning pipeline concept, by extending PySpark ML python API3, that enables chaining multiple data transforming operations into one. Such a modular system may be easily extended with different encapsulated components within a common interface and combined with other processes. We build data processing and modeling pipelines by incorporating available ML transformers and custom data preparation steps for filtering user events and processing article texts. Since our solution is integrated with a distributed environment of Hadoop cluster and due to large-scale computations, we use Apache Spark for data processing. The main stages of the proposed solution are described below. 3.1
We are primarily interested in retrieving universal user
interest profiles that are independent of website structure and
language characteristics, considering latent semantic interest
features. Hence in the first stage, we aim at discovering
abstract topics within the collection of all articles texts from
the database. We apply Latent Dirichlet Allocation (LDA) [
As a preprocessing step, stopwords based on a predefined list as well as words that appear in less than 10 texts or more than 10% of all documents are removed (the thresholds are selected arbitrarily). Next, the text is normalized to lowercase and words shorter than three characters and with non-alphabetic characters are filtered out. We preprocess and lemmatize tokens with SpaCy Python library extended to 3https://spark.apache.org/docs/latest/ml-pipeline.html support Polish language 4. For words with ambiguous base forms, the first form in alphabetic order is returned. 3.2
We construct user behavioral profiles by averaging the vectors of the articles in their browsing history. Thus, the resulting user profile describes the user’s average interest in each of the latent topics from the LDA representation: = ( ), ∈ , where are indices of articles in the user’s history. We used the average of the vectors rather than the sum, as it provides feature normalization in the context of user activity (the vectors represent user interests independently of how many articles they read). To avoid dominance of popular topics in the user profile representation and to extract their unique interest characteristics, we additionally apply vector standardization to ensure unit standard deviation and zero mean. 3.3
In order to produce user segments in an unsupervised way,
we apply the bisecting k-Means algorithm to their profiles
described in Section 3.2. The algorithm is a hierarchical
variant of the popular k-Means clustering [
One of the advantages of using topic modeling technique is the ability to generate interpretable topics descriptions (as described in Section 3.1). For each segment , ∈ {1, . . . , }, we define its representation as the average topic distribution of included users: = ( ), ∈ . We further use this distribution to provide characteristics of resulting user segments by retrieving the descriptions of topics above global average for each cluster center: () = {(, )}, > 0. 4
In this section, we describe the process of online experiments involving a real-world recommendation system. We have decided to perform online A/B tests which are capable of representing the dynamic nature of news recommendation scenarios (such as trend-responsiveness). We believe that this method is more appropriate than oiflne tests for an end-toend system evaluation. The goal of this test is to evaluate the general approach to user interests segmentation and indicate further improvement directions based on particular use-case analysis.
For building the user segments, we use a private database of articles and events from multiple publisher sites of Ringier
Axel Springer Polska, including the news service Onet and other websites, from anonymous users who accepted our cookie policy and terms of use. The data is stored on a Hadoop cluster. Each record in the history table represents an interaction between a user (represented by a cookie) and an item (when an article was viewed by a user). The user profiles are calculated daily from 14-day browsing histories to represent medium-length user interests. Only users who viewed at least two articles during this period are considered, resulting in approximately 13 million users scored daily and over 30 000 items in their browsing history. Article texts are in Polish and cover a wide range of topics (such as news, sports, business, and entertainment) and content types (such as long texts, videos, and gallery descriptions). 4.1
To perform A/B testing, the trafic is randomly split between experiment variants. Each variant is defined by a tuple (, , ), where is the destination section, is the set of user segments, and is the recommendation algorithm configuration. In this experiment, we compare the following recommendation configurations: (1) Destination section is one of the 6 selected website thematic sections: general, news, sports, travel, automotive and entertainment. (2) Recommendation algorithm is one of the following: ∙ Random—a baseline variant that returns items in a random order, ∙ − —contextual multi-armed bandit algorithm described in Section 2.3. The context of the bandit algorithm is defined by the tuple ( , ), where is the destination section and , ∈ {1, . . . , } is the user segment. Additionally, since segments are assigned only for users who were active recently, we define an extra segment 0 for new users without known history. (3) Segments set is a set of user segments , ∈ {0, . . . , } for the general segmentation (described in Section 3) or an empty set (global optimization for all users). Thus, we aim to compare the performance of contextual − , a non-contextualized − (which is a global popularity-based baseline), and a referential random algorithm on the six sections mentioned above. In the following section we describe the parameter choice for recommendation algorithms and segmentation . 4.2
We perform a two-fold parameter selection procedure by selecting the configuration for the contextual multi-armed bandit as well as the user segmentation algorithm. 4.2.1 Recommendation algorithm configuration. We use an ofline experiment simulation to eficiently select the contextual multi-armed bandit algorithm (described in Section 2.3) hyperparameters for diferent recommendation scenarios. 7,9 7,85 10 20 30 40 70 80 90
100 50 60 Number of topics
First, we estimate the initial parameters for calculating the algorithm payofs in given recommendation scenario, including trafic size (estimated number of views of items in given time slot), item pool size (number of items available in each trial), article lifetime (number of trials in which it is available in the pool) and a distribution of the reward function .
Next, the simulation procedure is performed by running
multiple iterations for diferent algorithm configurations. As
a result, the optimal configuration for each of the
recommendation settings is returned, including the knowledge window
and the value for the − bandit algorithm.
4.2.2 Segmentation algorithm configuration . For congfiuring
the segmentation algorithm, first, we need to select an optimal
number of topics for the LDA algorithm. We use perplexity
to measure how well the word probability distribution of
LDA model predicts a sample of held-out documents [
However as shown by [
To avoid the information bubble efect and to provide suficient statistics for per-segment contextual bandits (Section 2.3) in real time, we selected a relatively small number of = 10 clusters which provides a satisfactory level of interest consistency within segments while ensuring eficient training of the real-time recommendation algorithm. Moreover, larger segments support recommendation diversity (which reduces risk of information bubble) as the optimization is performed for a wider interest group. The distribution of users in these segments is shown in Figure 3. 4.3
The results of a 30-day online experiment for six diferent sections of Onet home page are presented in Table 1. We compare the performance of analyzed algorithms to the random baseline. Each of the experiments uses a custom businessdefined KPI based on user engagement metrics (incorporating pageviews, time spent on the website and bounce rate penalization), the details of which cannot be disclosed as it concerns business secrets.
The experiment results show that − recommendations consistently outperform randomly generated lists for all the experimental settings during the whole test period. We observed some fluctuations in the performance of all the variants that may be caused by publishing trends afecting user behavior (as shown in Figure 4). Additionally, for all the experiments the contextual bandit approach substantially outperforms the globally optimized version. The most considerable diference is achieved for the general thematic section (+15.2 pp. vs. global optimization, measured as a relative improvement over the random baseline) as well as for domain-specific sections with longer article lifetime (entertainment, travel, automotive). The semantic context has the smallest impact on highly time-sensitive sections (+1.9pp. diference to global optimization for news section and +6.2pp. for sports). Additionally, further analysis of segment performance showed that groups of users whose interests were underrepresented in the articles pool for a given section, on average performed worse than others. We also noted that the trafic size has a significant impact on algorithm performance. 0,6 0,4 0,2 0 -0,2 0,8 0,6 0,4 0,2 0 -0,2 0,8 0,6 0,4 0,2 0 -0,2 -0,4 air smog pollution particulates norm movie role Oscar prize love goal minute penalty ball This may be caused by the fact that for a larger sample, the exploration may be performed faster and the algorithm converges more quickly.
To summarize, the analysis of the experiment results leads us to the following observations: (1) Need for diversity: The general user segmentation gives the highest improvement for recommendations within a wide thematic range (as shown in the experiment results for the general section). Moreover, diversity of the item pool has an impact on the performance of particular segments — our analysis has revealed that users who cannot find articles relevant to their preferences become less active than others. (2) Need for time-sensitivity: Semantic interests have a lower impact on dynamical and time-sensitive sections such as news or sports feeds (as shown in Table 1). User behavior in such services may be influenced by shortterm interest patterns caused by popularity trends and hot topics (as shown in Figure 4) more than individual preferences. (3) Need for fine-grained interests representation: Interests in domain-specific thematic sections such as sports or technology do not necessarily match general user preference groups. Based on the analysis of the general segment descriptions (Table 2 left), we observe that for instance all users interested in entertainment are in the same segment, hence their more fine-grained interests in this domain cannot be recognized. 5
As observed in Section 4.3, due to the variety of recommendation scenarios, a general-purpose user segmentation cannot serve the diversity of all business cases. Hence, in the following sections, we propose some extensions to our method that are designed for particular use cases and address these realworld challenges. First, we present two alternative variants of the segmentation algorithm which are aimed at representing domain-specific and time-sensitive user interests. Next, we propose an approach to address the lack of diversity in the item pool by indicating missing thematic areas. 5.1
As discussed, in order to obtain a more satisfying level of performance for some of the challenging sections, we had to adopt diferent algorithms depending on the use-case. This could be achieved by leveraging the modular, extendable architecture described in Section 3 and resulted in three general types of user segmentation which are shown in Figure 5 and described below.
Topic modeling
Segmentation
Join Save (a)
Join Topic modeling Segmentation
Save (b)
Article data
Filter Topic modeling
Segmentation
Join Save (c) Article data
Event data
Article data
Event data Event data
The interchangeability of these algorithms enables us to easily adjust the segmentation to diferent circumstances, e.g. by employing the general approach when launching personalization on the entire page and the site-specific method for a small, thematic section. 5.1.1 General long-term users interests (Figure 5a). This algorithm is described in Section 3 and tested in the first experiment. Its idea is the following: create topics for the entire set of articles but cluster the users in the topic vector space according to their activity in a recent limited period. This, on the one hand, ensures that the topics obtained are general (such as sports, politics, news, and others) but on the other hand produces clusters which “follow” a user’s interests as they change with time. The balance between newsresponsiveness and general topic representation is achieved by adjusting the period to which user activity is limited. 5.1.2 Hot topics interests (Figure 5b). In our analyses we have discovered that sudden, popular events tend to attract the attention of users regardless of their general interests (see Figure 4). This seems to be confirmed by the insignificant improvement in performance for the news section seen in Table 1. In order to measure this phenomenon more closely and quantify its impact on the quality of recommendations as well as enable more meaningful segment descriptions, we have created an alternative version of the segmentation. Its main diference to the first, general approach is that the topics are computed only after the articles are joined with (and efectively filtered by) the user activity data. This in efect produces a topic vector space which more accurately captures these transient trends (see Table 2) and is capable of representing short-term user interests. Additionally, this method is more eficient due to a much smaller set of articles for which the topic space is computed. 5.1.3 Domain-specific recommendations (Figure 5c). As shown in Table 1, besides the long and short-term topics, for some sections, there is also a need to accurately represent subcategories in readers’ interests. The idea is to consider only the trafic and articles on a specific section of the page which leads the reader to a set of topically related articles. To achieve this, we applied a slight modification to the original, general-topic architecture, which filters the articles based on a section in which they appeared. This leads to a topic space and segments that capture the smaller sub-topics within a broader category. An example of this variant for the sports section is shown in Table 3. 5.2
Recommendation algorithms tend to improve user satisfaction by providing the most suitable items according to their interests. However, to provide personalized recommendations lists, the diversity of the item pool should be suficient to match particular user needs. Since for the news domain the article freshness is required, it is essential to provide meaningful and traceable insights about the types of content that are currently missing, so that these shortages may be addressed by the content provider. In the simplest scenario, we assume that if a group of users becomes less active, it may be caused by an insuficient number of articles relevant to their interests. Hence we address this issue by indicating segments that perform worse than the global average during each day and providing their descriptions as the topics that are missing in the available article set along with titles of articles that they liked in the past. First, we calculate the average performance (regarding the objective metric ) for each of the user segments : = ∑︀=1 , ∈ , ∈ {1, . . . , }, ∈ {1, . . . , }.
Next, we calculate the average = ∑︀=1 , ∈ and season, footballer, club, player — Legia6, goal, coach, footballer Entertainmentstar, actress, picture, look — role, musician, record, song Automotive car, auto, engine, model — company, customer, shop, price Other photo, do, look, al — water, eat, product, coal child, woman, family, home — man, perc, publish, photo star, love, beautiful, album — star, dance, Joanna5, journalist Oscar, role, actress, award — Oscar, Biedronka3, nominate breast, photo, Fabia2, Skoda2 — match, coach, player, team hair, skin, color, face — organism, disease, vitamin, contain Warsaw, network, arrange, TV set — perc, retirement, bank, amount 1 Jan Olszewski, Jaroslaw Kaczyn´ski - Polish politicians; 2 Skoda Fabia - car model; 3 Biedronka - Polish supermarket; 4 Kubica, Williams - Formula One competitors; 5 Joanna Mazur - runner, participant of the Polish edition of Dancing with the Stars; 6 Legia - Polish football club 4 penalty kick, Borussia, host — Legia, Lech, Jagiellonia, Warsaw 6 5
Barcelona, Real Madrid — Manchester, United, City, League the standard deviation () of the performance for all segments and we define that a segment is “unsatisfied” if < − (). Finally, we retrieve the articles that were particularly interesting for this segment in the past by calculating a performance metric , of each article in a given segment and we standardize this metric for all segments. The titles of articles with the highest score for each “unsatisfied” segment along with the segment descriptions and their cardinalities are presented in the form of textual insights (as shown in Figure 6).
As noticed by [
To fully exploit the potential of contextual bandits, it is
essential to apply a suitable method for user segmentation.
In [
A summary of approaches to user modeling in Internet
applications has been presented by Gauch et al. [
We described a universal method for segmenting users according to their semantic interests. Our solution is based on an unsupervised bisecting k-means clustering algorithm and is therefore capable of representing changing popularity trends. Moreover, using the topic modeling technique enables us to generate high-quality textual descriptions of users segments characteristics, which can provide traceable publishing insights for enhancing article diversity. This solution has been integrated with a large-scale news recommender system for personalizing the largest Polish news service Onet. The eficacy of our proposed system was evaluated in an online A/B test on several news sections with diferent characteristics. Based on the analysis of the results for particular use cases as well as qualitative analysis of segment descriptions and trend dynamics, we proposed further extensions of the segmentation algorithm that address these real-world issues.
In future work, we plan to incorporate into the model other types of behavioral features and content metadata. Moreover, we aim to improve the recommendation quality by exploring diferent segmentation and recommendation techniques to address other real-world challenges such as the user cold-start problem.