属性間の多様性を達成するための NNS における功利主義的定式化

arXiv:2602.08742v1 Announce Type: cross 近傍検索（Nearest Neighbor Search: NNS）は、データ構造の基盤となる問題であり、ウェブ検索、推薦システム、そして最近では検索增强生成（RAG）など幅広い応用領域で利用されています。このような最近の応用においては、返された近傍の関連性（類似度）に加えて、近傍間の多様性が中心的な要件となっています。本論文では、属性間の多様性を実現するために、功利主義に基づく原則的な NNS 定式化を開発します。我々の定式化は、数学経済学から導かれた功利関数に基づいており、中心的多様性（公平性）と関連性（経済的効率）の公理を満たします。特に、ナッシュ社会功利に焦点を当てて、我々の功利主義に基づく定式化は、クエリ依存の形で関連性と多様性を適応的にバランスさせる目的関数を提供することを示します。著しく、従来の制約に基づくアプローチは固定されたレベルの多様性を強要し関連性を最適化していましたが、そのようなバランスは存在していませんでした。さらに、我々の定式化は関連性と多様性のトレードオフを制御するためのパラメトリックな手法を提供し、実務家は特定のタスクの要件に合わせて検索結果を調整する柔軟性を得ます。我々は、功利主義的目的に対して証明された保証を持つ効率的な近傍検索アルゴリズムを開発しました。著しく、我々のアルゴリズムは、標準的な ANN メソッドの上に適用できる（すなわち、標準的な ANN メソッドをサブルチンとして使用）ことが可能であり、我々の功利主義に基づく目的関数を実質的に最大化する近傍を効率的に見つけることができます。実験結果は、我々のアプローチが実用的であることを示しており、返された近傍の高い関連性を維持しながら多様性を著しく向上させることを示しています。

arXiv:2602.08742v1 Announce Type: cross Abstract: Nearest Neighbor Search (NNS) is a fundamental problem in data structures with wide-ranging applications, such as web search, recommendation systems, and, more recently, retrieval-augmented generations (RAG). In such recent applications, in addition to the relevance (similarity) of the returned neighbors, diversity among the neighbors is a central requirement. In this paper, we develop principled welfare-based formulations in NNS for realizing diversity across attributes. Our formulations are based on welfare functions -- from mathematical economics -- that satisfy central diversity (fairness) and relevance (economic efficiency) axioms. With a particular focus on Nash social welfare, we note that our welfare-based formulations provide objective functions that adaptively balance relevance and diversity in a query-dependent manner. Notably, such a balance was not present in the prior constraint-based approach, which forced a fixed level of diversity and optimized for relevance. In addition, our formulation provides a parametric way to control the trade-off between relevance and diversity, providing practitioners with flexibility to tailor search results to task-specific requirements. We develop efficient nearest neighbor algorithms with provable guarantees for the welfare-based objectives. Notably, our algorithm can be applied on top of any standard ANN method (i.e., use standard ANN method as a subroutine) to efficiently find neighbors that approximately maximize our welfare-based objectives. Experimental results demonstrate that our approach is practical and substantially improves diversity while maintaining high relevance of the retrieved neighbors.