技術要約：不確実性を考慮したリトリーバル（検索）のための分布近似最近傍探索 (dinosaur)

1. 問題提起

現代の大規模なレコメンダーシステムは、候補生成段階において、数百万のアイテムをランク付け可能なセットへと絞り込むために、近似最近傍 (Approximate Nearest Neighbour: ANN) 探索に依存しています。標準的な実装では、ユーザーとアイテムの表現を、共有された潜在空間における決定論的な点推定値（単一のベクトル）として扱います。

本論文は、このパラダイムにおける根本的な欠陥を指摘しています：

• 固有の不確実性: 疎なインタラクション・データから学習された埋め込み（エンベディング）は、本質的に不確実です。この不確実性は二種類あります：
  • エピステミック（認識論的）不確実性: インタラクション・データの不足による、ロングテール・アイテムの高分散。
  • アレトリック（偶然的）不確実性: 低ランク潜在因子モデルに内在する情報の損失。
• 系統的なバイアス: 決定論的なANNリトリーバルは、硬直した幾何学的境界を作り出します。真の関連性が高い可能性があるものの、点推定の平均値がわずかに外れている不確実性の高いアイテム（通常はニッチな、あるいはロングテールのコンテンツ）は、トップ-$k$の候補から永久に排除されてしまいます。
• 結果: これは人気バイアスと「富める者はさらに富む」というフィードバックループを引き起こします。ヘッドアイテム（人気アイテム）が露出を独占する一方で、ロングテールのクリエイターや多様なコンテンツは、システム的にインプレッションを奪われ、枯渇することになります。既存の救済策（例：事後的な再ランキングや多様性目標）は、多くの場合、ヒューリスティックであり、根本的な原因であるリトリーバル段階とは切り離されています。

2. 手法：dinosaur フレームワーク

著者らは、既存のANNインフラストラクチャやスコアリングモデルを変更することなく、埋め込みの不確実性を候補生成プロセスに直接組み込むフレームワークである dinosaur (Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval) を提案しています。

コアメカニズム

各アイテム $i$ に対して単一の点推定値 $\mu_i$ をインデックス化する代わりに、dinosaur はアイテムを（平均 $\mu_i$ と共分散 $\Sigma_i$ によって特徴付けられる）分布 $P(v_i)$ として扱います。

1. インデックス構築 (オフライン): 各アイテム $i$ について、システムはアイテムの埋め込み分布 $P(v_i)$ から $S_i$ 個の独立したサンプル $v_i^{(j)} \sim P(v_i)$ を抽出します。ANNインデックスは、この拡張されたベクトル集合に対して構築されます。
2. クエリ実行 (オンライン): サービング時には、ユーザーの分布 $P(v_u)$ からユーザーの埋め込み $v_u$ がサンプリングされます。ANNインデックスは、このサンプリングされたベクトルに対する最近傍探索を行います。
3. 重複排除: 取得されたベクトルは元のアイテム識別子へとマッピングされ、正確に $k$ 個の異なるアイテムが返されるまで重複が削除されます。

主な特性

• インフラストラクチャとの互換性: この手法は、ANNインデックスのアルゴリズム（FAISS、HNSW、ScaNNなど）やスコアリングモデルを変更する必要がありません。単に、より多くのベクトルを扱うことができるインデックスを必要とするだけです。
• 両方向 vs 片方向: 本フレームワークはユーザーとアイテムの両方のサンプリングをサポートしていますが、本論文では探索を促進するためにアイテム側の不確実性に焦点を当てています。これは、リアルタイムのユーザーサンプリングがレイテンシの制約に抵触する可能性がある動的なマーケットプレイスにおいて特に有用です。
• 適応型サンプリング (Adaptive Sampling): メモリコスト（インデックスの肥大化）を管理するために、論文ではサンプル予算 $S_i$ をアイテムの不確実性に依存させる適応型サンプリングを提案しています。信頼度の高いヘッドアイテムには $S_i=1$ を割り当て、不確実なロングテールアイテムには $S_i > 1$ を割り当てます。

理論的根拠

論文は、本フレームワークに関する理論的な保証を提供しています：

• 収束性: 埋め込みの分散が消失する場合 ($\sigma^2 \to 0$)、dinosaur は標準的な決定論的点推定リトリーバルに収束します。
• 単調なカバレッジ拡大: 決定論的なトップ-$k$の外にある任意のアイテムについて、そのアイテムがリトリーバルされる確率は、埋め込みの分散とともに厳密に増加します。これは、ランダムなノイズ注入なしに、不確実なアイテムに対して「リトリーバル段階の探索ボーナス」を与え、構造的にロングテールコンテンツを優遇することを数学的に保証します。
• Thompson Samplingとの関連性: このメカニズムは、サンプリングから事後分布を抽出することで探索と活用（Exploration and Exploitation）のバランスを取るThompson Samplingと形式的に結びついています。

3. 実験設定

著者らは、MovieLens-32M データセット（32Mのインタラクション、約20万ユーザー、約8.4万アイテム）を用いて dinosaur を評価しました。

• ベースライン: 正確な内積探索 (Flat) および近似探索 (IVFFlat)。
• 不確実性のプロキシ: ベースモデル (iALS) は決定論的であるため、著者らは、標準偏差 $\sigma_i$ がアイテムのインタラクション数 $n_i$ に反比例する合成的なエピステミック事後分布を構築しました：$\sigma_i = \alpha / (1 + n_i)^\gamma$。
• 指標:
  • Recall@K: 標準的なオフライン・ユーティリティ指標。
  • Catalogue Coverage@K: 少なくとも一つのユーザーのトップ-$K$リストに現れる全アイテムカタログの割合。
  • 層別カバレッジ (Stratified Coverage): 人気度五分位（B0 = 最も人気、B4 = 最も低人気）による分析。

4. 主な結果

• 大幅なカバレッジ向上: サンプル予算を $S=1$ (ベースライン) から $S=5$ に増やすことで、グローバルなカタログカバレッジがほぼ3倍になりました（$K=1000$ において 23.52% から 62.97% へ）。
• 無視できるほどのRecall低下: このカバレッジの拡大は、オフラインのRecallに対して極めて小さなコスト、すなわち 0.0041 の減少のみで実現されました。
• ロングテールの露出:
  • 標準的な IVFFlat は、最も人気のないアイテム（バケット B4）に対して 0.00% のカバレッジしか達成できませんでした。
  • dinosaur ($S=5$) は、バケット B4 に対して 81.88% のカバレッジを達成し、ユーザーの13%以上が最も無名のアイテムからの推薦を受けられるようにしました。
• パレート優位性: $\epsilon$-greedy ヒューリスティックと比較して、dinosaur は様々なリトリーバルの深さ ($K \in \{100, 500, 1000\}$) において、探索的な推薦の割合に対してより高いRecallを達成し、ベースラインを厳密に上回りました。

5. 意義と主張

本論文は、dinosaur が、リトリーバルにおける探索と活用のトレードオフに対する原則に基づいた、インフラ互換性のあるソリューションを提供すると主張しています。

• パラダイムの転換: 不確実性を扱う負担を、事後的な再ランキングやヒューリスティックな多様化から、リトリーバル段階そのものへと移行させます。
• フィードバックループの打破: 不確実なアイテムが候補セットに入れることを可能にすることで、決定論的なポリシーによってロングテールアイテムが露出できず、学習すらできないというアルゴリズムのフィードバックループを打破します。
• 実用性: この手法は、サンプル数以外の新しいハイパーパラメータを必要とせず、既存のプロダクショングレードのANNライブラリと動作します。
• 限界の承認: 著者らは、使用した不確実性のプロキシが学習された分布ではなくインタラクション数に基づいていること、およびオフライン指標 (Recall) が MNAR (Missing Not At Random) データによってバイアスされていることを認めています。彼らは、真のマーケットプレイスへの影響を測定するために、プロペンシティ（傾向）を考慮したオフライン評価とオンラインA/Bテストを組み合わせるべきであると示唆しています。

要約すると、dinerosaur は、埋め込みを点ではなく分布として扱うことが、標準的なリトリーバルの有用性をほとんど損なうことなく、カタログの多様性とロングテールの露出を大幅に改善できることを示しています。