从大量特征中选出关键特征，用最少观察完成物品聚类
Clustering Items through Bandit Feedback: Finding the Right Feature out of Many
- 通过自适应选择特征和物品，利用序列减半算法筛选有效特征
- 在1-δ概率下实现正确聚类，所需观察次数有理论上限
- 适用于特征多但只需少数关键特征的聚类场景
我们研究基于带奖反馈的物品聚类问题。共有n个物品，每个由特征向量表征，维度d可能很大。物品被未知地划分为两组，同组内物品特征向量相同。在序贯自适应设置中，每轮学习者选择一个物品和一个特征，观测该物品在该特征上的噪声评价。目标是尽可能少的观察次数下恢复正确划分。我们提出一种算法，通过寻找对聚类任务有效的特征，借助序列减半算法实现。以至少1-δ的概率，获得准确的划分，并给出预算的上界。此外，我们推导了实例相关的下界，在某些情况下是紧的。
原文摘要 · Abstract (English)
We study the problem of clustering a set of items based on bandit feedback. Each of the $n$ items is characterized by a feature vector, with a possibly large dimension $d$. The items are partitioned into two unknown groups such that items within the same group share the same feature vector. We consider a sequential and adaptive setting in which, at each round, the learner selects one item and one feature, then observes a noisy evaluation of the item's feature. The learner's objective is to recover the correct partition of the items, while keeping the number of observations as small as possible. We provide an algorithm which relies on finding a relevant feature for the clustering task, leveraging the Sequential Halving algorithm. With probability at least $1-δ$, we obtain an accurate recovery of the partition and derive an upper bound on the budget required. Furthermore, we derive an instance-dependent lower bound, which is tight in some relevant cases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。