最近、レコメンデーション系のことをやっている関係で色々調べてます。 以前はNGTを使って近傍探索を試していました。
Embeddingとかを使った検索やレコメンデーションには近傍探索ライブラリは非常に重要です。 ちょっと調べてみると、メルカリさんがFaissというライブラリを使っているようでした。
ちょっと興味が出て使ってみたので、、今回はそのメモです。
近傍探索問題
近傍探索問題は、データ量に応じて計算量が急激に増大する古典的な問題で、以下のような用途で使われています。
最近傍探索は、以下のような様々な分野で使われている。
・パターン認識 - 特に光学文字認識
・統計分類- K近傍法参照
・コンピュータビジョン
・データベース - 例えば、内容に基づく画像検索（CBIR）など
・符号理論 - 最尤復号参照
・データ圧縮 - MPEG-2参照
・レコメンデーションシステム
・インターネットマーケティング - コンテンツ連動広告、行動ターゲティング
・DNAシークエンシング
・スペルチェッカ
・盗用検出
https://ja.wikipedia.org/wiki/最近傍探索
Faiss
FaissはFacebook Resarchが提供する近傍探索ライブラリです。
こちらの記事を参考にさせていただいてます。
github はこちら。
インストール
この辺の通りにやっていただければ普通に動きました。
faiss/INSTALL.md at master · facebookresearch/faiss · GitHub
Dockerfileで書いたらこんな感じになりました。
FROM continuumio/anaconda3 RUN conda install faiss-cpu -c pytorch
ハイかんたん。
使ってみる
チュートリアルがあるのでそのへん読んでみます。
Getting started · facebookresearch/faiss Wiki · GitHub
探索しているのは、
D, I = index.search(xq, k)
の部分で、引数のxqのベクトルを近傍の中心として、上位k件とってくるようになっています。 ちなみにxqは複数取れるので、複数の近傍探索を同時に実行できます。
戻り値のIが上位k件のインデックス、Dがその時の近傍点までの距離になっているようです。
感想
この辺見る感じ、近傍探索の中ではかなり早い部類みたいです。
メルカリさんも使っているということで、今後はこれを使う方向で考えたいと思います。
何より簡単ですしね!
