近似最近傍探索のサーベイ

ANN_survey1.md

近似最近傍探索のサーベイ

入口となる研究

まずググってトップにでてくるやつ

近似最近傍探索の最前線

2019年の資料。読み切れてないが概観するにはとても良かった。 特に気になったのは以下の点

• PythonおすすめANN手法選択フローチャート
  • 10^9までなら nmslib (hnsw)が良いらしい
  • それ以上なら faiss-cpu になる。参考:近傍探索ライブラリFaissを使ってみた
• ANNの問題
  • 数学的背景が無く、実データで実測で速ければ良いとなってる
  • 評価手段が無い(データ依存で偶然良いのか、実装が良いのかわからない)

現在までの3年にアップデートがあるかは気になる。

Elasticsearch 8系

• Elasticsearch 8 が 近似近傍探索 をサポートした
  • kNNなので、あらかじめクラス分けできていることが前提で、ちょっと欲しいものと違う(そのままで使えるかわかんない)かも kNNとは近傍k個の取得なので大丈夫そう
  • Elasticsearch 8.0.0は 2022-02-11 リリース。比較的最近の機能。結構頻繁にリリースされており、現在の最新は 8.5.2
• ベースになってる Lucene が対応したことによるらしい

Lucene周り

https://www.rondhuit.com/soleami-comparison-classifier.html (2014/2/25初出の記事) より

LuceneとMahoutの文書分類機能比較

• Mahout は懐かしの Hadoop で動く機械学習アルゴリズム。バッチ処理には使えそう

Lucene は 4.2 から文書分類ツールが提供されるようになりました

Lucene には、単純ベイズと k-NN 法による分類器が実装されています

• https://avinton.com/academy/naive-bayes/

Mahout は同じく単純ベイズと、さらにランダムフォレストで文書分類を行ってみましょう

lucene-classification パッケージ

Lucene 自身は k-NN までで、ANNまではサポートしてなさそう。 2019年にLuceneでANNする論文が出てる
Lucene for Approximate Nearest-Neighbors Search on Arbitrary Dense Vectors

9.0にAN Vector検索を実装したらしいissueがあった apache/lucene#10047

Release Node 9.0 よりそれっぽい記述

Support for indexing high-dimensionality numeric vectors to perform nearest-neighbor search, using the Hierarchical Navigable Small World graph algorithm

HSNWを使ってる: 参考Javadoc

ElasticsearchのANN Searchを試す:
LuceneとANNの経緯から説明してる記事。

ここまでのまとめ

• JavaというくくりならLuceneのHSNWでANNすれば良いのでは?
  • もっと広く構えるならPython使ってANNに慣れたほうが良い
• いずれにせよデータがいる
  • データの下処理も問題になりそう
  • データ次第でパラメーターも変わる恐れがある

その他の資料

• Hierarchical Navigable Small Worlds (HNSW)

ANN_survey2.md

サーベイの続き

HNSWLIBとLuceneを試してANNを試してみた。 sqlite-vssが出てきたので、それも試すことになった。

sqlite-vss

FAISSをSQLiteから使えるようにする拡張。 vector0拡張を前提にvss0を用いる。 仮想テーブルをFAISSのインデックスにマッピングしている。

ベクトルはいったん生データをテーブルに入れたのちに仮想(インデックス)テーブルに移す。

インデックスにはFAISSのfactoryを指定できる。 factoryの種類次第ではtrainingが要る。結構時間がかかる。

HNSWを使うには、このIndexの選択で正しく指定する必要がありそうだ。 つまりFAISSに詳しくなる必要がある。

近似最近傍探索の最前線 にもどる

そういえばこのスライドにFAISSでHNSWの記述があった。

faiss-cpu: hnsw + ivfadc (IndexHNSWFlat + IndexIVFPQ)

いろいろ寄り道をしたあげく、大回りでスタート地点にもどってきた印象。