本notebookは情報検索・検索技術 Advent Calendar 2022の17日目の記事です。
はじめまして、nadareと申します。普段はMLエンジニアとしてレコメンドエンジン等を作っています。
今回は緯度経度の距離計算に用いられるhaversine関数を用いた近傍探索を、近似近傍探索(ANN)により高速化したのでその実装とコードを公開します。
記事本体となるNotebookはこちらになります。
https://www.kaggle.com/code/nadare/ivfxl2rrflat-for-haversine
おまけ(ポエム)
近似近傍探索、個人的に好きな分野ですが割と使いどころが難しいです。
近似近傍探索が有効なのは大量の画像のembeddingに対してコサイン類似度で探したいみたいなケースだと思います。ユークリッド距離のような条件ではK-D TreeやBall Treeといったアルゴリズムが使えますが、コサイン類似度は全探索で探す必要があります。(scikit learnのNearest Neighborの項に詳しいです。)
ANNはこのようなケースで有効ですが、faissやnmslib等の実装はprefilterによる部分検索ができないので検索対象のメタ情報との組み合わせが難しいです。具体的にはxxのタグがついた類似画像の検索みたいなことをしたい場合は、ANNを使うのであれば多めに近傍を取得したうえでフィルターをかける、ただし件数の保証はされない、みたいなことが起こります。タグがない場合でもレコメンドシステム等でembeddingによる検索を行う場合、全アイテムを探索するのではなくランキング上位N件に絞ったほうが精度良くてANNの効果が薄い(KNNの方が精度よく速度も十分)みたいなことも起こります。
ElasticsearchやOpensearchにANNの機能が追加されてきています。(前者はnmslibのHNSW、後者はさらにfaissに対応)
とはいえそのままでは全体集合に対する近似近傍探索しかできないので、自前でANNを実装できると活用の幅は広がるとおもいます。
例えばKMeans + 転置インデックスによる粗量子化は比較的簡単に実装できますし、最近だとBigQueryによる最大内積検索の実装の記事の「ベクトルの離散化による候補削減」では4次元のLSHによる候補削減を行っていて感動しました。
近似近傍探索はGCPでVertex Matching Engineが使えるようになったり、windowsでも使えるfaissにFastScanが実装されたりと近年ホットな分野です。ぜひ活用していきましょう。