Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Elasticsearch における類似度ベクトル検索のベストプラクティスを求めて/es-ve...

Elasticsearch における類似度ベクトル検索のベストプラクティスを求めて/es-vector-search

Takahiko Ito

July 31, 2019
Tweet

More Decks by Takahiko Ito

Other Decks in Programming

Transcript

  1. 自己紹介 • ソフトウェアエンジニア at クックパッド • 博士(工学) • 12年前に検索エンジンの会社(Fast Search

    & Transfer)に就職した後、検索エン ジンやデータマイニング界隈をフラフラしてます • Twitter アカウント: takahi_i • オープンソース:RedPen、Cookiecutter Docker Science
  2. 準備:関連検索 • テキスト文書の関連検索はメジャーな検索プラットフォーム(Solr、Elasticsearch)で サポートされている • しかし、いろいろ調べたところ画像の類似度検索には決定打となるのが見つからな かった。。。。 • 既存のElasticsearch をベースにした画像の類似度検索

    ◦ https://github.com/EdjoLabs/image-match ◦ https://github.com/kzwang/elasticsearch-image • 問題:ベクトルを古典的な手法(Hashing)で離散化する仕様 • 最新のEmbedding手法で生成したベクトルがそのまま使えない。。。
  3. 準備:Faiss • Facebook によって開発された類似度検索用のパッケージ • URL: https://github.com/facebookresearch/faiss • 感想:よくできている。これで十分では? ◦

    メルカリさんも利用: https://speakerdeck.com/metalunk/merukariniokeru-ai-huo-yong-shi-li-pyc on-jp-2018?slide=21 • ただ、やはり検索プラットフォーム(ElasticsearchやSolr) で実現したい。。。
  4. まとめ:類似ベクトル検索パッケージに望むこと 1. 速度 ◦ 高速に結果が帰ってほしい。検索にかかる時間がO(N)とか┐(´д`)┌ 2. 精度 ◦ 精度が悪いのはNG。できれば最近のEmbedded 手法使いたい

    3. 運用性 ◦ 空間木インデクスだけ与えられてるのはNG。。。。。 ◦ Elasticsaerch とか Solr がインデクスの Replication や Sharding とか提供して くれている時代に。。。 ◦ ほとんどの検索チームは専任一人がいいところ、シュッと構築できないと
  5. 調査 2 • Elasticsaerch で高速に取ってくる手法はないか? • 頑張って探したところ、ブログ記事を発見した • URL:https://www.linkedin.com/pulse/searching-deep-learning-eike-dehling/ •

    処理の流れ(二段階) ◦ KD-木で粗く候補を取ってくるプラグイン ▪ Lucene のKD 木インデクスを ESから利用できるようにした ▪ NOTE: Lucene のKD木は8次元までしか対応していないので、絞り込み 用に低次元ベクトルを別途用意する必要がある。。。 ◦ 候補とクエリに含まれるベクトルのコサイン類似度を計算してランキングし直す プラグイン(全ページで紹介したプラグインを利用する) •
  6. ES のマッピング(スキーマ) ポイント:二種類のベクトルを保持するフィー ルド作る - 低次元ベクトル(8次元) - 高次元ベクトル(200次元) { "mappings":

    { "doc": { "properties": { "name" : {"type": "text"}, "reduced_vector": { "type": "vector", "dimensions": 8 }, "full_vector": { "type": "binary", "doc_values": true } } } } }
  7. インデクス • Python 用ESクライアントでword2vecから算出されたベクトル(8次元、200次元) をESインスタンスにインデクスする。 es.index("full_vectors", "doc", { "name": vocab,

    "reduced_vector": ",".join([str(x) for x in vector8]), "full_vector": base64.b64encode(np.array(vector200). astype(np.dtype('>f8'))).decode("utf-8"), })
  8. 検索クエリ { "query": { "function_score": { "query": { "range": {

    "reduced_vector": { "from": from_vector, "to": to_vector } } }, "functions": [ { "script_score": { "script": { "source": "staysense", "lang" : "fast_cosine", "params": { "field": "full_vector", "cosine": True, "vector" : target_full_vector } } } } ], "boost_mode": "replace" } }} 第一段階の処理:rangeクエリ でターゲットベクトルを含むベク トル部分空間を指定(次ページ で解説) 第二段階の処理:第一段階 の処理で粗く取得された候補 を cosine でリランキング
  9. 絞り込み検索用ベクトルの作成 • KD木で抽出する部分空間(入力ベクトルが内部に存在する部分空間)作 る必要がある。 • 上限ベクトル、下限ベクトルを指定する def generate_ranges(vector): from_vector =

    [element -2.5 for element in vector] to_vector = [element + 2.5 for element in vector] return ",".join([str(x) for x in from_vector]), ",".join([str(x) for x in to_vector]) 下限ベクトル(入 力ベクトルの要 素から定数を引 いたもの) 上限ベクトル(入 力ベクトルの要 素に定数を足し たもの)
  10. 課題 • 絞り込みベクトルの大きさが8次元で固定 ◦ Lucenceを再ビルドすると大きさを変更できるらしい(要検証) ◦ https://github.com/textkernel/vector-search-plugin#intended-use-case に よると ‘by

    default 8, you can re-compile lucene with higher values..’ とは書 いてある。。。 • ベクトルと、超低次元ベクトルの2つを作るのが面倒 ◦ REST API にベクトル入れるとよしなに低次元ベクトルを作ってくれるとより便 利そう ◦ 入力の高次元ベクトルに対して、低次元ベクトル数でmodを取得し足し合わせ るとか
  11. 今回の実験 • 実験で使ったレポジトリ ◦ 関連するプラグインを同梱したもの(KD木による絞り込み、コサイン類似度、イ ンデクス、検索 REST API 経由での文書追加) ◦

    URL: https://github.com/takahi-i/es_embedded_vector_search • 自分では検証、改善する時間が取れないので、そのうち消します