arXiv:2601.10901cs.DScs.IR2026-01NeurIPS被引 1

动态新闻推荐中,用单次遍历算法最大化主题覆盖率。

Streaming Stochastic Submodular Maximization with On-Demand User Requests

  • 将用户访问建模为在线流,基于拟凹函数优化内容选择
  • 在有限内存下实现1/(8δ)的竞争力比,优于已有方法
  • 适合实时推荐系统,尤其资源受限场景

我们研究一种新型的流式子模最大化问题,灵感来自新闻推荐平台的动态特性。用户可随时访问新闻网站,每次访问需展示最多k条新闻。用户行为具有随机性:每条新闻被用户接受的概率不同,且覆盖特定主题。目标是设计一个流式算法,以最大化期望总主题覆盖率。我们建立该问题与带拟阵约束的子模最大化之间的联系。当用户访问次数已知或可使用线性大小内存时,可有效应用已有方法。但在更现实的场景中,仅知访问次数上界且内存为亚线性时,现有算法无法保证性能。为此,我们提出一种新在线流算法,达到1/(8δ)的竞争比,仅需一次遍历数据流,且内存与流长无关。实验表明,本算法始终优于基线方法。

原文摘要 · Abstract (English)

We explore a novel problem in streaming submodular maximization, inspired by the dynamics of news-recommendation platforms. We consider a setting where users can visit a news website at any time, and upon each visit, the website must display up to $k$ news items. User interactions are inherently stochastic: each news item presented to the user is consumed with a certain acceptance probability by the user, and each news item covers certain topics. Our goal is to design a streaming algorithm that maximizes the expected total topic coverage. To address this problem, we establish a connection to submodular maximization subject to a matroid constraint. We show that we can effectively adapt previous methods to address our problem when the number of user visits is known in advance or linear-size memory in the stream length is available. However, in more realistic scenarios where only an upper bound on the visits and sublinear memory is available, the algorithms fail to guarantee any bounded performance. To overcome these limitations, we introduce a new online streaming algorithm that achieves a competitive ratio of $1/(8δ)$, where $δ$ controls the approximation quality. Moreover, it requires only a single pass over the stream, and uses memory independent of the stream length. Empirically, our algorithms consistently outperform the baselines.

流式优化新闻推荐子模最大化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。