厳密最近傍探索（Exact NNS）は、高次元のベクトル空間において、クエリとなるデータ点に最も近いデータを誤差なく正確に見つけ出す技術です。推薦システムや画像検索などの基盤となる技術ですが、データの次元数や件数が増えると計算量が爆発的に増加する「次元の呪い」という課題を抱えています。
厳密最近傍探索とは
厳密最近傍探索とは、多次元ベクトル空間に配置されたデータ群の中から、特定のクエリ（基準点）に対して距離が最も近いデータを100%の精度で（近似することなく）正確に探し出す手法のことです。
詳しく解説
AIや機械学習の分野、特にディープラーニングにおいては、画像やテキストなどのデータを高次元の「埋め込みベクトル」に変換して扱います。これらのベクトル間の類似性を評価する際、最も似ているデータを見つけるために「最近傍探索」が行われます。厳密最近傍探索は、すべてのデータとの距離を計算する「全探索（線形探索）」などをベースとし、一切の妥協や誤差を許さずに真の最確データを特定します。コサイン類似度やユークリッド距離といった距離指標が用いられます。しかし、データ件数が数百万、数千万とスケールしたり、ベクトルの次元数が数百以上に高次元化したりすると、計算コストが指数関数的に増大する「次元の呪い」に直面するため、システム設計において処理効率の向上が極めて重要になります。
具体例・使われ方
例えば、ECサイトの推薦システムにおいて、ユーザーが閲覧した商品の埋め込みベクトルに最も類似する商品を、データベース全体から誤差なく正確に抽出してレコメンドする場面が挙げられます。また、顔認証システムにおいて、カメラで撮影された顔の特徴ベクトルと、登録データベース内のベクトルを厳密に照合し、最も一致する人物を特定する際にも、厳密最近傍探索の考え方が基礎として利用されています。
似た用語との違い
混同されやすい概念に「近似最近傍探索」があります。厳密最近傍探索が100%の精度で正確な最近傍データを特定するのに対し、近似最近傍探索は、多少の精度低下（わずかな誤差）を許容する代わりに、インデックス構造などを工夫して探索速度を劇的に高速化する手法です。大規模な検索システムでは計算時間の制約から近似最近傍探索が好まれますが、絶対に誤りが許されない高度なセキュリティ分野や小規模データでは厳密最近傍探索が適しています。
注意点
厳密最近傍探索の最大の注意点は計算コストです。データの件数をN、次元数をDとしたとき、全探索を行うと計算量はO(ND)となり、大規模データに対してはリアルタイムでの応答が不可能になります。k-dツリーなどの空間分割木を用いた最適化手法もありますが、高次元データにおいては全探索よりも処理が遅くなる「次元の呪い」が発生するため、実用上はデータの規模や要求される速度・精度に応じて近似アルゴリズムとの使い分けを検討する必要があります。