Markov Determinantal Point Processes

Raja Hafiz Affandi, Alex Kulesza, Emily B. Fox

Abstract

Determinantal Point Processes (DPPs) are powerful tools for selecting diverse subsets of items. However, they are traditionally static, failing to ensure diversity across sequential time steps. This paper introduces Markov Determinantal Point Processes (M-DPPs), a framework that models temporal diversity by ensuring that consecutive subsets are diverse both internally and relative to each other. M-DPPs are mathematically tractable, allow for efficient sampling in polynomial time, and demonstrate superior performance in applications such as news recommendation and exploration-exploitation tasks.

Introduction

Subset selection is a fundamental challenge in machine learning, appearing in tasks ranging from document summarization to product recommendation. While DPPs provide an elegant probabilistic framework to model "repulsion" (diversity) within a single set, many real-world applications require a continuous stream of diverse sets. For example, a news aggregator should provide a diverse set of headlines today that is also distinct from yesterday's headlines to avoid boring the user with repetitions.

Standard DPPs, when applied independently at each time step, often repeat the same high-quality items, failing to capture this temporal dimension of diversity. The authors seek to extend the tractable mathematics of DPPs into a time-series setting where repulsion exists both within a time step and across time steps.

Methodology

The authors construct the M-DPP framework using several key innovations:

1. The Union Property

The core theoretical insight is ensuring that the union of two consecutive sets ($Z_t = Y_t \cup Y_{t-1}$) is itself a DPP. By defining the joint distribution this way, the model naturally enforces that $Y_t$ is diverse relative to $Y_{t-1}$. If the union is diverse, the individual sets must, by definition, be different from each other.

2. L-Ensemble and Transition Distributions

They define a transition distribution $P(Y_t \mid Y_{t-1})$ that functions as a conditional DPP. This allows the model to remain stationary—meaning its statistical properties do not drift over time—while maintaining the "DPP-ness" of each individual marginal set. This is achieved through the construction of a marginal kernel $\hat{K}$.

3. Efficient Sampling and Learning

Unlike other repulsive processes that require slow Markov Chain Monte Carlo (MCMC) simulations, M-DPPs allow for exact sampling in polynomial time (Algorithms 2 and 4). Furthermore, the authors propose a log-linear model to learn item "quality" scores from user feedback (e.g., clicks). This transforms the M-DPP into an exploration-exploitation engine: the inherent diversity forces the system to explore new topics, while learned quality scores ensure it exploits known user preferences.

Experimental Evaluation

The researchers evaluated M-DPPs using the Gigaword Corpus, specifically a subset of ~35,000 New York Times articles. They simulated a task of displaying 10 articles per day from a weekly pool of roughly 1,400 articles.

Comparison of temporal diversity between standard DPP (left) and M-DPP (right). Note the vertical gaps and clusters in the standard DPP versus the more uniform distribution over time in the M-DPP.

Key Results

  • Superior Temporal Diversity: In fixed-quality tests, the M-DPP showed a marked increase in 1-step and 2-step diversity compared to standard k-DPPs. As illustrated in the figure above, the M-DPP successfully avoids the temporal "clumping" where the same high-quality articles are shown day after day.
  • Faster Learning: In user preference simulations, the M-DPP's diversity-driven exploration discovered user interests much faster than weighted random sampling or standard DPPs. It achieved nearly 70% recall of preferred articles within 100 days.
  • Balanced Utility: Using a metric for diminishing returns (where repeated items lose value), the M-DPP consistently outscored all baselines, proving it effectively balances quality, internal diversity, and temporal freshness.

Conclusion

M-DPPs provide a robust and tractable solution for sequential subset selection. By extending the repulsion property of DPPs into the temporal domain, they solve the problem of redundancy in streaming applications. While the current model is limited to first-order Markov dependencies, it sets the stage for more complex temporal modeling and formal regret bounds in diversity-aware learning.

Summary updated

BibTeX
@inproceedings{affandi2012markov,
  author = {Raja Hafiz Affandi and Alex Kulesza and Emily B. Fox},
  title = {{Markov Determinantal Point Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
}
Figure