技术摘要：通过成对观测实现近渐近最优的主动聚类

问题陈述

本文研究了将 $M$ 个无标签项目划分为未知数量的 $K$ 个不同组别的**主动聚类（Active Clustering）**问题。该设定涉及一个带有噪声的预言机，当查询一对项目 $(i, j)$ 时，返回一个二进制反馈 $Y_{ij} \in \{0, 1\}$。

• 如果项目 $i$ 和 $j$ 属于同一簇，则 $Y_{ij} \sim \text{Ber}(p)$。
• 如果它们属于不同的簇，则 $Y_{ij} \sim \text{Ber}(q)$。
• 参数 $p$ 和 $q$ 是未知的，但满足 $0 \le q < 1/2 < p \le 1$。

与通常分析单次图快照的随机块模型（Stochastic Block Model, SBM）不同，该框架允许对任何项目对进行自适应、重复的查询。目标是设计一个 $\delta$-正确算法，在以至少 $1-\delta$ 的概率识别出真实的聚类，同时在 $\delta \to 0$ 的情景下（固定置信度设定）最小化期望查询次数（样本复杂度）。

方法论

1. 理论下界

作者将该问题表述为一个纯探索型多臂老虎机任务，其中每个“臂”对应于一对项目。利用测度变换技术，他们推导出了期望样本复杂度的实例相关下界 $E_C[\tau_\delta]$：
$$\liminf_{\delta \to 0} \frac{E_C[\tau_\delta]}{\ln(1/\delta)} \ge D^*(C)^{-1}$$
其中 $D^*(C)$ 是一个极大-极小优化问题的解：
$$D^*(C) := \sup_{\lambda \in \mathcal{P}_I} \inf_{C' \in \text{Alt}(C)} \sum_{(i,j) \in I} \lambda_{ij} \text{KL}(v_{ij}, v'_{ij})$$
这里 $\text{Alt}(C)$ 代表替代实例（错误的聚类方式）的集合。一个关键的理论贡献是定理 2，它显著缩小了下确界的搜索空间。该定理证明了“最难”的替代实例 $C'$ 必须是一个简单的合并或拆分（即 $C'$ 具有 $K-1$ 或 $K+1$ 个簇）。这使得搜索范围从超指数级的贝尔数划分缩减到了可控的局部扰动集合。

2. 算法设计：A3CNP

为了逼近该下界，作者提出了 A3CNP（具有噪声成对观测的近渐近最优主动聚类算法）。该算法由三个部分组成：

• 投影子程序 (ProjC)： 由于对实例 $\hat{C}_t$ 的经验估计可能不满足有效聚类所需的传递性，算法将其投影到有效实例集 $\mathcal{C}$ 上，以获得一致的估计 $C_t$。
• 改进的 D-Tracking 采样规则： 算法自适应地采样项目对。它通过使用投影后的实例求解简化的极大-极小问题来计算最优分配 $\lambda^*(\sigma; C_t)$。为了确保探索和收敛，它使用了一个混合分布：
  $$\lambda^*_\epsilon(\sigma; C_t) = (1-\epsilon)\lambda^*(\sigma; C_t) + \epsilon \cdot u$$
  其中 $u$ 是均匀分布。实际查询的项目对是通过使用 D-Tracking 规则选定的，以确保经验采样频率收敛到目标分布。
• 计算可行停止规则： 理论上最优的停止规则依赖于广义似然比（GLR）统计量，该统计量涉及对连续参数的难以计算的下确界。作者提出了一个代理统计量 $\tilde{Z}(t)$，它通过“因子化”所有项目对中的最小查询计数来简化计算。这种修改使得问题具有闭式解并具备计算可行性，同时保留了 $\delta$-正确性属性。

核心贡献

1. 问题表述： 作者将具有噪声成对查询的主动聚类建模为固定置信度的纯探索问题，明确处理了未知的 $p, q$ 和 $K$。
2. 实例相关下界： 他们建立了一个由加权二元 KL 散度表征的基本下界。至关重要的是，他们证明了“最坏情况”替代实例的搜索空间可以限制在具有 $K \pm 1$ 个簇的实例中。
3. 算法创新： 他们开发了 A3CNP，这是一个结合了以下内容的实用算法：
   • 一个用于处理不一致经验估计的投影机制。
   • 一个基于推导出的下界结构的采样规则。
   • 一个计算高效的停止规则，避免了标准 GLR 测试中的不可计算性。
4. 性能保证： 论文证明了 A3CNP 是近渐近最优的。具体而言，其期望样本复杂度随 $\ln(1/\delta)$ 对数增长，且归一化增长率被限制在一个常数倍的理论下界之内。算法性能与下界之间的差距被明确表征，并被证明是可控的。

结果与评估

• 理论边界： 论文推导出了显式边界，表明次优性差距取决于采样分配的离散程度（$\max \lambda / \min \lambda$）和正则化参数。
• 实证验证： 实验针对 $M=6$ 个项目和 $K=3$ 个簇进行，使用了具有挑战性的参数（$p=0.6, q=0.4$）。
  • A3CNP 与 Chen 等人 [24] 的主动聚类算法进行了基准测试。
  • 结果显示，A3CNP 实现的停止时间非常接近理论下界，并且明显快于（小于）基准算法。
  • 算法展示了对超参数 $\epsilon$ 和 $\sigma$ 变化的鲁棒性。
  • 研究表明，一个数据驱动的代理指标能够准确追踪理论上界。

意义与主张

该论文声称为固定置信度领域的主动聚类提供了一个原则性的框架。其主要意义在于弥合了统计最优性与计算可行性之间的鸿沟：

• 它超越了传统的 $M \to \infty$ 极限，转而关注误差概率趋于零（$\delta \to 0$）的情景，这对于实体解析等高可靠性应用至关重要。
• 它证明了通过识别“最难”替代项的结构简单性（合并/拆分操作），可以设计出近乎最优的采样规则，而无需进行难以计算的操作。
• 该工作将主动聚类定位为一个信息获取问题，暗示未来的算法应当动态地将精力集中在最具歧义的结构决策上，而非均匀地精炼所有成对关系。

作者指出，虽然所提出的停止规则在计算上是可行的，但实现完全渐近最优的停止规则仍是一个开放性挑战，目前的方法会产生一个可以进行经验估计但尚未在理论上消除的乘性差距。