基于图平滑性设计高效推荐算法，小有效维度下可快速学习用户偏好。
Spectral bandits
- 利用图上函数的平滑性建模推荐系统，邻居节点相似度高
- 仅需数十次评估就能在数千项中学习用户偏好，误差低
- 提出有效维度概念，算法复杂度随其线性/次线性增长，适合真实图数据
图上的光滑函数在流形学习和半监督学习中有广泛应用。本文研究一种带权问题，其中各选项的收益在无向图上是光滑的。该框架适用于涉及图结构的在线学习任务，如基于内容的推荐。每个可推荐项目对应图的一个节点，其期望评分与邻近节点相似。目标是推荐具有高期望评分的项目。我们希望算法的累积后悔值不会随节点数量过多增长。为此，我们引入有效维度这一概念，在真实图数据中通常较小，并提出三种算法，其性能在该维度上呈线性或次线性增长。在内容推荐任务上的实验表明，仅通过数十次节点评估，即可对数千个项目的用户偏好进行良好估计。
原文摘要 · Abstract (English)
Smooth functions on graphs have wide applications in manifold and semi-supervised learning. In this work, we study a bandit problem where the payoffs of arms are smooth on a graph. This framework is suitable for solving online learning problems that involve graphs, such as content-based recommendation. In this problem, each item we can recommend is a node of an undirected graph and its expected rating is similar to the one of its neighbors. The goal is to recommend items that have high expected ratings. We aim for the algorithms where the cumulative regret with respect to the optimal policy would not scale poorly with the number of nodes. In particular, we introduce the notion of an effective dimension, which is small in real-world graphs, and propose three algorithms for solving our problem that scale linearly and sublinearly in this dimension. Our experiments on content recommendation problem show that a good estimator of user preferences for thousands of items can be learned from just tens of node evaluations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。