技術要約：ペアワイズ観測を通じた、ほぼ漸近的に最適な能動的クラスタリング

問題設定

本論文は、$M$ 個のラベルなしアイテムを未知の $K$ 個の異なるグループに分類する**能動的クラスタリング（active clustering）**の問題を扱う。設定としては、ノイズを含むオラクルに対し、アイテムのペア $(i, j)$ をクエリとして投げると、バイナリのフィードバック $Y_{ij} \in \{0, 1\}$ が返される。

• アイテム $i$ と $j$ が同じクラスターに属する場合、$Y_{ij} \sim \text{Ber}(p)$ となる。
• アイテム $i$ と $j$ が異なるクラスターに属する場合、$Y_{ij} \sim \text{Ber}(q)$ となる。
• パラメータ $p$ および $q$ は未知であるが、$0 \le q < 1/2 < p \le 1$ を満たす。

単一のスナップショットのグラフを通常解析するストカスティック・ブロックモデル（SBM）とは異なり、このフレームワークでは、任意のアイテムのペアに対して適応的かつ反復的なクエリを行うことが可能である。目標は、$\delta \to 0$ のレジーム（固定信頼度設定）において、期待クエリ数（サンプル複雑性）を最小化しつつ、少なくとも確率 $1-\delta$ で真のクラスタリングを特定する$\delta$-正しいアルゴリズムを設計することである。

手法

1. 理論的下界

著者らは、各「腕（arm）」がアイテムのペアに対応する純粋探索型バンディット問題として問題を定式化した。チェンジ・オブ・メジャー（測度変換）の手法を用いて、期待サンプル複雑性 $E_C[\tau_\delta]$ に関するインスタンス依存の下界を導出した：
$$\liminf_{\delta \to 0} \frac{E_C[\tau_\delta]}{\ln(1/\delta)} \ge D^*(C)^{-1}$$
ここで、$D^*(C)$ は以下のsup-inf 最適化問題の解である：
$$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であり、これは下限（infimum）の探索空間を大幅に削減するものである。これは、「最も困難な」代替インスタンス $C'$ は、真のクラスターの単純なマージ（結合）またはスプリット（分割）（すなわち、$C'$ は $K-1$ または $K+1$ 個のクラスターを持つ）でなければならないことを証明している。これにより、探索範囲を超指数関数的なベル数（分割数）から、管理可能な局所的摂動へと削減している。

2. アルゴリズム設計：A3CNP

下界に近づくために、著者らは A3CNP (Almost Asymptotically Optimal Active Clustering with Noisy Pairwise Observations) を提案している。このアルゴリズムは、以下の3つのコンポーネントで構成される：

• 投影サブルーチン (ProjC)： 実験的なインスタンスの推定値 $\hat{C}_t$ は、有効なクラスタリングに求められる推移性を満たさない可能性があるため、アルゴリズムは $\hat{C}_t$ を有効なインスタンスの集合 $\mathcal{C}$ に投影して、一貫した推定値 $C_t$ を得る。
• 修正された D-Tracking サンプリング則： アルゴリズムは適応的にペアをサンプリングする。投影されたインスタンスを用いて簡略化された sup-inf 問題を解くことで、最適な割り当て $\lambda^*(\sigma; C_t)$ を計算する。探索と収束を確実にするため、混合分布を使用する：
  $$\lambda^*_\epsilon(\sigma; C_t) = (1-\epsilon)\lambda^*(\sigma; C_t) + \epsilon \cdot u$$
  ここで、$u$ は一様分布である。実際にクエリするペアは、実験的なサンプリング頻度がターゲットとなる分布に収束することを保証するために、D-Tracking ルールを用いて選択される。
• 計算可能な停止則： 理論的に最適な停止則は、連続パラメータに対する計算不可能な下限（infimum）を伴う一般化尤度比（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$）レジームに焦点を当てている。これは、エンティティ・レゾリューション（実体識別）のような高信頼性が求められるアプリケーションにおいて極めて重要である。
• 「最も困難な」代替の構造的な単純さ（マージ/スプリット操作）を特定することで、計算不可能な計算を必要とせずに、ほぼ最適なサンプリング則を設計できることを示している。
• 本研究は、能動的クラスタリングを情報獲得問題として位置づけており、将来のアルゴリズムは、すべてのペアの関係を一様に精緻化するのではなく、最も曖昧な構造的決定に動的に注力すべきであることを示唆している。

著者らは、提案された停止則は計算上は実行可能であるが、完全な漸近的最適停止則を実現することは依然として未解決の課題であり、現在の手法は、理論的に排除はできるものの、経験的に推定可能な乗法的ギャップを伴うことを述べている。