通过主动询问成对物品，实现接近最优的聚类，误差可控。
Almost Asymptotically Optimal Active Clustering Through Pairwise Observations
- 主动查询物品对，用二元反馈判断是否同属一类
- 提出理论下界，算法性能逼近该下界，误差在常数倍内
- 适合需要高效聚类且可主动获取反馈的应用场景
我们提出一种新分析框架，通过主动收集噪声反馈，将 M 个物品聚类到未知数量的 K 个不同组中。每个时间步，智能体可查询一对物品，并观察二元带索反馈：若两者属于同一簇，反馈为 1 的概率为 $p > 1/2$；若属于不同簇，则反馈为 1 的概率为 $q < 1/2$。借助普遍的测度变换技术，我们建立了达到目标置信度所需查询次数的理论下界，形式为一个上确界-下确界优化问题。基于此理论基础，我们设计了一种渐近最优算法，其停止条件涉及经验版本的内部下确界——广义似然比（GLR）统计量与阈值比较。我们提出了一个计算可行的 GLR 变体，并证明其性能与下界的差距可被准确估计，且始终在常数倍之内。
原文摘要 · Abstract (English)
We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses. At each time step, an agent is allowed to query pairs of items and observe bandit binary feedback. If the pair of items belongs to the same (resp.\ different) cluster, the observed feedback is $1$ with probability $p>1/2$ (resp.\ $q<1/2$). Leveraging the ubiquitous change-of-measure technique, we establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the clustering accuracy, formulated as a sup-inf optimization problem. Building on this theoretical foundation, we design an asymptotically optimal algorithm in which the stopping criterion involves an empirical version of the inner infimum -- the Generalized Likelihood Ratio (GLR) statistic -- being compared to a threshold. We develop a computationally feasible variant of the GLR statistic and show that its performance gap to the lower bound can be accurately empirically estimated and remains within a constant multiple of the lower bound.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。