Optimal Top-$k$ Identification from Pairwise Comparisons

技術要約：ペア比較からの最適なTop-$k$識別

問題の定式化
本論文は、ノイズを含むペア比較からの固定信頼度（fixed-confidence）top-$k$識別という能動学習の問題を扱う。設定として、$n$個のアイテムがあり、未知の潜在ユーティリティ $\theta = (\theta_1, \dots, \theta_n)$ が存在する。アルゴリズムは、アイテムのペア $(i, j)$ を逐次的に選択して比較を行い、その結果を観測し、誤差確率が最大 $\delta$ 以下となるように、トップ$k$のアイテムの集合 $S^*(\theta)$ を返して停止しなければならない。目的は、期待比較回数（サンプル複雑性）を最小化する $\delta$-正しい手順を設計することである。

著者らは、比較の結果が1パラメータ指数型分布に従う潜在ユーティリティモデルを仮定している。具体的には、ペア $(i, j)$ に対して、出力分布は自然パラメータ $\eta_{ij}(\theta) = \theta_i - \theta_j$ に依存する。このフレームワークは、バイナリの結果（例：ブラッドリー・テリー・モデル）と、基数的な結果（例：ガウス差分）の両方に対応している。本問題は、第$k$位と第$(k+1)$位のアイテムの間に正のギャップ（$\theta_{(k)} > \theta_{(k+1)}$）があることを前提としている。

手法およびアルゴリズム設計
提案される解は、オンラインかつ適応的なアルゴリズム（Algorithm 1）であり、$\delta \to 0$ において漸近的最適性を達成する。その手法は、最適な「オラクル」による比較割り当てを追跡し、統計的な信頼度が十分になった時点で停止するという、Track-and-Stopフレームワークに基づいている。

1. オラクル問題の特性付け:
   著者らは、最大最小（max-min）オラクル問題によって支配される、サンプル複雑性の情報理論的下界を特性付けている。彼らは、真のパラメータ $\theta$ を、トップ$k$の集合が異なる任意の代替パラメータ $\theta'$ と区別するために、境界ペア（boundary pairs）——すなわち、$u$ が真のトップ$k$集合に含まれ、$v$ が含まれないようなペア $(u, v)$ ——のみを考慮すれば十分であることを示している。
   オラクル問題は、以下の2プレイヤー・サドルポイント・ゲームとして定式化される：

   • 設計者（Primal）: すべてのペアに対して比較の重み $w$ を割り当てる。
   • 敵対者（Dual）: 最も困難な代替案を「標的」とするために、境界ペア上の分布 $q$ を選択する。
     このゲームの平衡解 $(w^*, q^*)$ が、漸近的に最適なサンプリング戦略および最適な情報レート $\Gamma^*(\theta)$ を定義する。

2. オンライン・プライマル・デュアル学習:
   真の $\theta$ は未知であるため、アルゴリズムはサドルポイントをオンラインで学習する。各ラウンド $t$ において：

   • 推定: 最大尤度推定（MLE） $\hat{\theta}_t$ と、それに付随する境界集合 $\hat{B}_t$ を計算する。
   • 追跡: プライマルの反復変数 $w_t$（割り当ての重み）と、デュアルの反復変数 $q_t$（境界ペア上の重み）を維持する。
   • 更新: 毎ステップで完全なmax-min問題を解く代わりに、アルゴリズムは、確率的勾配を用いた単一のエントロピー的Follow-The-Regularized-Leader (FTRL) 更新ステップを実行する。
   • 勾配推定: 計算効率を確保するため、アルゴリズムは $\hat{B}_t$ から単一の境界ペア $I_t$ を一様にサンプリングし、KLダイバージェンス投影のための不偏勾配推定値を構築する。これにより、すべての境界ペアに対して投影を計算する $O(n^2)$ のコストを回避する。
   • サンプリング: 次に比較するペアは、C-trackingを通じて選択される。これは、混合スケジュールによる探索を維持しながら、経験的なサンプリング比率が学習された重みの移動平均を追跡することを保証する。

3. 停止ルール:
   アルゴリズムは、尤度比マルチンゲール論に基づく停止ルールを採用している。各境界ペアに対して、現在のMLEと、そのペアの順序を入れ替える最も紛らわしい代替案との間の対数尤度比を表す統計量 $Z_{ij}(t)$ を計算する。アルゴリズムは、これらの統計量の最小値が、自己正規化集中不等式から導出された閾値 $\beta(t, \delta)$ を超えたときに停止する。

主な貢献

• 漸近的最適性: 本論文は、潜在ユーティリティモデルの下での、ペア比較からのトップ$k$識別に関する、初の漸近的に最適なアルゴリズムを確立した。提案手法の期待サンプル複雑性は、$\delta \to 0$ において情報理論的な下界と一致する。
• 構造的特性付け: 著者らは、代替集合を境界ペアを反転させるパラメータへと簡約化することで、下界の構造を特性付けている。この簡約化により、オラクル問題を扱いやすいサドルポイント問題として定式化することが可能になる。
• 計算効率の高い手順: 問題をゲームとして定式化し、確率的プライマル・デュアル更新を用いることで、アルゴリズムは各ステップで「最も紛らわしい」代替案を見つけるという組合せ爆発的な複雑さを回避している。これにより、本手法は中規模な $n$ に対してスケーラブルとなる。
• 汎用性: このフレームワークは、一般的な指数型分布の仮定の下で、バイナリおよび基数的比較結果の両方に適用できる。

結果と性能
著者らは、3つの合成インスタンスを用いてアルゴリズムを評価している：

1. ランダム・ユーティリティ: 一様分布から生成され、中心化されたユーティリティ。
2. 等間隔ユーティリティ: 固定されたギャップを持つユーティリティ。
3. SST選好行列: 強的なる統計的推移性（Strong Stochastic Transitivity; SST）を満たすが、必ずしも潜在ユーティリティによって誘導されるとは限らない行列から生成された結果。

$\delta = 0.01$ のシミュレーションにおいて、提案アルゴリズムは、様々なアイテム数 $n$ およびトップ$k$のサイズ $k$ にわたって、既存のベースライン（SEEEKS, SEEKS-v2, および Active Ranking）を一貫して上回る性能を示した。

• ランダム・ユーティリティの設定では、$n$ および $k$ が増加するにつれて、優れた性能を示す。
• 等間隔の設定では、アルゴリズムの停止時間は真の $\theta$ を知っているオラクル・ベンチマークを密接に追跡しており、中程度の $\delta$ においても近似的に最適な性能を確認している。
• SSTの誤設定下においても、アルゴリズムは競争力を維持しているが、$\|\hat{\theta}_t\|_2^2$ の増大により、中程度の $\delta$ では停止閾値が緩くなることがある。

意義と主張
本論文は、様々な純粋探索（pure exploration）問題において漸近的に最適な手順が存在する一方で、潜在ユーティリティモデルの下でのペア比較からのトップ$k$識別に対する漸近的に最適なアルゴリズムは、本研究まで確立されていなかったと主張している。その意義は、以下の手順を提供することにある：

1. $\delta \to 0$ において、情報理論的な下界（乗法的定数を含む）に正確に一致する。
2. サドルポイントをオンラインで学習することにより、計算効率が高く、実用的な問題サイズにもスケールする。
3. 統一されたフレームワーク内で、バイナリおよび基数的フィードバックの両方を扱う。

著者らは、現在の手法における弱点として、中程度の $\delta$ における停止閾値が、特定の領域（例：ユーティリティのノルムが大きい場合）においてベースラインと比較して劣る場合があることを控えめに述べている。彼らは、漸近的最適性を維持しつつ、中程度の $\delta$ に対してよりタイトな停止閾値を構築することに今後の課題があると考えている。