FARGO: グローバル・マルチ・プロービングによる高速最大内積探索

01/01/2023

最大内積探索を理解する：理論から実践へ

機械学習と人工知能の進歩に伴い、高次元のベクトル空間を効率的に探索する能力がますます重要になってきている。この領域における基本的な課題の1つが最大内積探索（MIPS）問題であり、与えられたクエリーベクトルとの内積を最大にするベクトルをデータセットから見つけることを含む。この演算は、推薦システム、多クラスラベル予測、類似項目検索、構造SVM、ディープラーニングなど、数多くのアプリケーションの中心となっている。

空間分割木を用いた従来のMIPSへのアプローチは、次元が増加するにつれて指数関数的に遅くなり、数百、数千の次元を扱うことが多い最新のアプリケーションには実用的でない。近似最近傍探索にはLocality-Sensitive Hashing（LSH）が有効であることが証明されているが、内積類似度のユニークな特性のため、MIPSに直接適用することはできない。MIPSに対する効率的でスケーラブルなソリューションの必要性は、組織がますます大規模で高次元のデータセットを処理するようになるにつれて、かつてないほど高まっている。

本稿では、MIPS問題へのアプローチ方法に革命をもたらす新しいフレームワーク、FARGOを紹介する。現在のMIPSソリューションの包括的な分析とその限界、そしてFARGOがグローバルマルチプロービングとランダムXBOX変換を含む革新的な技術によってどのようにこれらの課題を克服したかを紹介します。我々のフレームワークは、既存の手法と比較して優れた精度と効率を達成するだけでなく、大規模な高次元データを扱う実世界のアプリケーションに実用的なソリューションを提供する。

Get the Whitepaper