Source-linked AI summary
Personalized News Recommendation with Context Trees
Florent Garcin, Christos Dimitrakakis, Boi Faltings
TL;DR
News recommendation must serve anonymous, casually visiting readers despite rapidly changing stories, topics, and preferences. The paper introduces incrementally updated context-tree recommenders that combine contextual expert models, achieving strong accuracy and novelty while adapting to current trends and reader preferences.
Problem
Anonymous news visitors often provide only ephemeral browsing histories, while stories and topics evolve rapidly and recommendations should add value beyond already popular front-page articles.
Method
The paper proposes online context-tree recommender algorithms that incrementally learn from complete browsing histories, selecting and combining experts over contexts to score fresh and popular candidate stories.
Results
Context-tree recommenders achieve state-of-the-art performance in prediction accuracy and recommendation novelty under unbiased testing, with personalized-item accuracy outperforming current techniques.
Takeaways & Limitations
Context trees flexibly model news sequences, topics, and topic distributions while continuously adapting to changing trends and reader preferences.
Takeaways & Limitations
Dirichlet priors can cause predictions to be made mainly by only one expert model.
Abstract
from arXiv · showhide
The profusion of online news articles makes it difficult to find interesting articles, a problem that can be assuaged by using a recommender system to bring the most relevant news stories to readers. However, news recommendation is challenging because the most relevant articles are often new content seen by few users. In addition, they are subject to trends and preference changes over time, and in many cases we do not have sufficient information to profile the reader. In this paper, we introduce a class of news recommendation systems based on context trees. They can provide high-quality news recommendation to anonymous visitors based on present browsing behaviour. We show that context-tree recommender systems provide good prediction accuracy and recommendation novelty, and they are sufficiently flexible to capture the unique properties of news articles.
1. INTRODUCTION
News recommendation must handle rapidly changing stories, limited knowledge of casual visitors, and browsing histories that are richer than the last article read. The paper proposes incrementally updated context-tree recommenders that account for context, popularity, and freshness, achieving strong accuracy and novelty.
- Casual visitors often provide only ephemeral browsing histories, limiting the information available for personalization.
- Manual recommendations typically address many users and consider only the last article, motivating automatic use of complete browsing histories.
- News recommenders must accommodate rapidly appearing and disappearing stories while providing value beyond already-seen popular articles.
- Context-tree algorithms provide incrementally updated, context-dependent recommendations using progressively finer-grained partitions of article sequences or topic representations.
- Experts combine predictions while modeling news popularity and freshness, allowing recommendations to reflect article-specific dynamics.
- Unbiased testing found state-of-the-art performance in both prediction accuracy and recommendation novelty.
2. RELATED WORK
Prior news recommenders include collaborative, content-based, hybrid, and Markov-based approaches. The paper focuses on context trees partly because existing sequential models can be difficult to scale and unsuitable for online learning.
- Collaborative filtering uses similar users’ preferences, whereas content-based systems use similarity between news items.
- News aggregation systems combine clustering, covisitation, and other scores to recommend stories.
- Content-based systems have been more common for news personalization, with several systems extending the approach beyond newsgroups.
- Hybrid systems combine user click behavior, group trends, and personalized recommendation models.
- Context trees are commonly used to estimate variable-order Markov models, which represent sequences through contexts and symbol statistics.
- Markov and hidden Markov approaches can suffer from high state complexity, requiring multiple maintained models that are not scalable or suitable for online learning.
- Sequential recommender proposals include fixed-history decision-tree forests and finite mixtures of Markov models with fixed weights.
3. PRELIMINARIES
The paper uses context trees to represent browsing contexts at varying levels of specificity and assigns local prediction experts to those contexts. This supports recommendations based on increasingly precise user histories or topic representations.
- A k-order Markov model summarizes a user’s state by the last k visited items, but selecting k is unclear; variable-order models use context-dependent order.
- Context trees organize increasingly precise partitions of sequences, topic sequences, or topic distributions into a hierarchy.
- Each context receives a local prediction expert whose recommendations apply to users matching that context.
- The framework describes prediction models, their association with contexts, and their combination into recommendations.
3.1 Sequence Context Tree
A sequence context tree represents article histories through suffix-defined contexts arranged in a refining partition tree. As the article pool changes, the tree creates branches for new articles and removes branches for disappearing ones.
- The system tracks the sequence of articles read by each user.
- A sequence is an ordered list of articles read by a user, and topic sequences can be treated similarly.
- The context tree is built from sequences and their suffixes, where a suffix contains the final elements of a sequence.
- A context contains all sequences ending with a specified suffix.
- At each depth, contexts form a partition, and each child context is a subset of its parent.
- When a new article is read, the active leaf is split into subsets, producing a variable-order Markov model.
- The tree evolves with the article pool by creating branches for new articles and removing nodes for articles that disappear.
3.2 Topic Distribution Context Tree
The topic-distribution context tree partitions topic-distribution space into progressively smaller regions, enabling recommendations based on similarity to the user's recent topic context.
- Motivation: Topic-based contexts can recommend stories that no one has read by exploiting similarity among topic distributions.This addresses the large number of news items relative to available topics.
- Topic-distribution tree: Topic-distribution contexts are modeled as regions in a k-dimensional space and represented with a k-d tree.Each node corresponds to a hyper-rectangle, and the topic space is [0, 1]^k.
- Topic-distribution tree: The tree recursively splits each region through its center along a principal axis, cycling through axes by depth.The two child regions are disjoint and together cover their parent region.
- Topic-distribution tree: When a new topic distribution is observed, it is added to the tree and may cause the tree to expand.The observed distribution is assigned according to the relevant hyperplane partition.
3.3 Experts
Experts are local prediction models attached to contexts in the tree, and the experts along the path matching a user's browsing history jointly produce recommendations.
- Expert definition: Each context node receives an expert that estimates the probability of the user's next article given that context.The expert is formally defined as a function associated with a specific context.
- Active experts: The browsing history is matched to the context tree to identify a path of nodes and their active experts.These active experts are responsible for generating the recommendation.
- Active experts: Active experts correspond to contexts whose suffixes match the user's browsing history.The active set is defined using the suffix relation between node contexts and the browsing history.
3.4 Combining Experts into Predictions
The system combines predictions from active experts along the matched context path, weighting more specific and more general contexts according to their usefulness and updating those weights after observed clicks.
- Prediction mixture: The predictions of all active experts are combined by marginalizing their weighted probabilities.The mixture uses each expert's context-relevance probability as its combination weight.
- Prediction mixture: The stopping weights determine whether prediction uses a specific expert or continues toward more general contexts.Experts are considered from the most specific node toward the root, with each weight representing the probability of stopping.
- Recursive combination: The combined prediction can be computed recursively as q_k = w_kP_k(nt+1 = x|st) + (1 − w_k)q_{k−1}.The root prediction is q_0, while q_4 is the complete prediction in the illustrated path.
- Online updates: After a user reads article x, the weights of active experts are updated using the sequential prediction probability q_k(x) and Bayes' theorem.Only weights for active experts corresponding to relevant suffixes are updated; local active-expert models are also updated.
3.5 Expert Models
Each context expert combines models for standard item frequencies, popularity, and freshness so recommendations reflect both browsing patterns and the changing dynamics of news.
- Model decomposition: The expert is decomposed into local models for ordinary item probabilities, popular news, and fresh breaking news.These models represent different assumptions about what users may read next.
- Standard model: The standard model estimates an item's probability from its active-context click count using a Dirichlet-multinomial prior.The prior contributes an initial count α0 to the estimate.
- Motivation: The popularity and freshness extensions address news dynamics involving new content, trends, and changing preferences.These dynamics make a simple frequency-only model insufficient.
- Popularity model: Popular items are defined by recent readership, with the candidate-pool size |P| controlling how many recent items the popularity expert considers.When |P| is small, the expert focuses on the most recently read news.
- Freshness model: Fresh items are unread breaking news among the next |F| items scheduled for publication, and |F| influences their prediction probability.The fresh-item model assigns separate probabilities to items inside and outside the fresh set.
- Mixing models: The three expert models are combined into a mixture whose expert probabilities can be set by a Dirichlet prior or adapted through Bayesian updating based on expert accuracy.The mixture is designed to avoid relying exclusively on a single expert when Dirichlet priors concentrate predictions.
4. CONTEXT-TREE RECOMMENDERS
Context-tree recommenders organize browsing contexts into increasingly specific nodes and combine context-linked expert predictions to recommend timely news. The paper instantiates this framework with several sequence-, topic-, and topic-distribution-based variants.
- Variants: The paper describes three VMM-based recommenders and one k-d context-tree recommender for the news domain.The variants use news-item sequences, topic sequences, hybrid topic/item representations, or complete topic distributions.
- General algorithm: The general CT algorithm learns and recommends online after each read article, using a changing candidate pool of popular and fresh stories.It estimates each candidate’s probability and returns the highest-probability items.
- Variants: The standard VMM predicts the next news item from sequences of previously read news items, whereas topic variants predict from topic representations.The topic-based construction assigns topics to stories and performs predictions on those topics.
- Variants: The k-d context tree models complete topic distributions instead of only sequences of most probable topics.This represents the last article in the space of topic distributions.
5. EVALUATION AND COMPARISON
The evaluation tests context-tree recommenders on anonymous browsing data using accuracy, personalized accuracy, novelty, and an accuracy–novelty utility. Results show robustness to candidate-pool changes and distinct strengths across model variants.
- Evaluation design: The study asks whether context trees outperform standard methods and which partition and expert-model combination works best.It evaluates both accuracy and novelty because popular recommendations can be accurate yet add little value.
- Datasets: The evaluation uses filtered anonymous-user visits and news stories from two Swiss-French newspaper websites spanning November 2008 to May 2009.A second dataset supports an unbiased comparison after hyperparameters are selected on the first dataset.
- Metrics: The metrics include Success@5, personalized Success@5 after removing popular items, and novelty measured as unseen recommended items divided by recommended items.Personalized Success@5 filters bias from websites’ default popular-item recommendations.
- Sensitivity evaluation: As the candidate pool grows, popularity-based recommendations become less effective, while Bayesian expert updating is more robust and CT performance improves slightly with more fresh items.Dirichlet-prior updating can become dominated by the popularity model as the candidate pool increases.
- Sensitivity evaluation: CT systems have accuracy close to existing techniques overall but outperform them for personalized items.The result indicates that model order matters when popular items are excluded.
- Comparison: The expected-performance comparison finds poor accuracy and novelty for CVMM, significantly better performance for HVMM, and much higher novelty for kCT.VMM and Z have similar accuracy, but only VMM has reasonable novelty.
- Comparison: For lower accuracy weights, kCT is preferred, whereas VMM is preferred for higher accuracy weights.This selection follows tuning on one dataset and evaluation on the other using the accuracy–novelty utility.
6. CONCLUSION
The paper develops context-tree recommenders for dynamically changing news domains and anonymous, one-time sessions. Its evaluation finds that different context-tree variants favor accuracy or novelty, while leaving online validation on a real news website for future work.
- Context-tree recommenders adapt continuously to changing news topics, reader preferences, current trends, and one-time sessions without logged-in users.The approach uses a single context tree and updates models incrementally, supporting scalability in a dynamic domain.
- The study considers context trees over news sequences, topic sequences, and topic distributions.It combines expert models based on news popularity and freshness into a single model.
- Static-dataset accuracy favors a variable-order Markov context tree, whereas novelty is best served by a k-d tree over topics.These conclusions come from expected performance curves using parametrized utility metrics.
- Large context order matters mainly when recommendations should avoid highly popular items.
- Whether these static-trace findings remain qualitatively similar in an actual recommender system remains an open question.The authors identify online testing on a real news website as future work.