Re:ゼロから始めるML生活

ミスよりグズを嫌え

近傍探索ライブラリFaissを使ってみた

f:id:nogawanogawa:20191020155537p:plain

最近、レコメンデーション系のことをやっている関係で色々調べてます。 以前はNGTを使って近傍探索を試していました。

www.nogawanogawa.com

Embeddingとかを使った検索やレコメンデーションには近傍探索ライブラリは非常に重要です。 ちょっと調べてみると、メルカリさんがFaissというライブラリを使っているようでした。

tech.mercari.com

ちょっと興味が出て使ってみたので、、今回はそのメモです。

近傍探索問題

近傍探索問題は、データ量に応じて計算量が急激に増大する古典的な問題で、以下のような用途で使われています。

最近傍探索は、以下のような様々な分野で使われている。
・パターン認識 - 特に光学文字認識
・統計分類- K近傍法参照
・コンピュータビジョン
・データベース - 例えば、内容に基づく画像検索(CBIR)など
・符号理論 - 最尤復号参照
・データ圧縮 - MPEG-2参照
・レコメンデーションシステム
・インターネットマーケティング - コンテンツ連動広告、行動ターゲティング
・DNAシークエンシング
・スペルチェッカ
・盗用検出
https://ja.wikipedia.org/wiki/最近傍探索

Faiss

FaissはFacebook Resarchが提供する近傍探索ライブラリです。

こちらの記事を参考にさせていただいてます。

qiita.com

qiita.com

github はこちら。

github.com

インストール

この辺の通りにやっていただければ普通に動きました。

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がその時の近傍点までの距離になっているようです。

感想

この辺見る感じ、近傍探索の中ではかなり早い部類みたいです。

qiita.com

メルカリさんも使っているということで、今後はこれを使う方向で考えたいと思います。

何より簡単ですしね!