Zenn
Closed9

Elasticsearch による近似最近傍探索

fujimotoshinjifujimotoshinji

本文ざっくりまとめ

  • 機械学習の一般化によりベクトルによる検索の利用が増えてきた
  • ベクトルによる検索は単語の検索、スコア付けでなく、文章の意味による検索、スコア付けができる
  • Elasticsearch は 7.6 でリリースした dense_vector フィールドを利用することでベクトルの保存とそれを用いたスコア算出ができる
    • 8.0 より前は script でのみ利用できた？
  • Elasticsearch 8.0 から高速な近似最近傍探索（ANN）を提供
    • 今までは性能的に小さいデータセット、低次元ベクトル用途がメインだったが、大規模データセット、高次元ベクトルでも性能が出るようになった
    • Elasticsearch 8.0 は ANN のアルゴリズムに HNSW（Hierarchical Navigable Small World graphs）を利用
  • 従来の kNN と比較して精度は若干落ちるが性能はかなり上がっている
    • 計測例
      • script: 再現率 1.0、5.257qps
      • HNSW: 再現率 0.945、849.286qps
  • ベースは Lucene の機能
  • _knn_search というエンドポイントで 8.0 から提供開始
    • テクニカルプレビューの位置づけ
    • いずれは _search で利用可能になる

Mapping 定義例

PUT index
{
 "mappings": {
   "properties": {
     "image-vector": {
       "type": "dense_vector",
       "dims": 128,
       "index": true,
       "similarity": "l2_norm"
     }
   }
 }
}

検索例

GET index/_knn_search
{
 "knn": {
   "field": "image-vector",
   "query_vector": [-0.5, 9.4, ...],
   "k": 10,
   "num_candidates": 100
 }
}
fujimotoshinjifujimotoshinji

近似最近傍探索（ANN: approximate nearest neighbor）

最近傍探索（NNS: Nearest neighbor search）の派生。

最近傍探索って？

https://ja.wikipedia.org/wiki/最近傍探索

距離空間における最も近い点を探す最適化問題やその解法。
最も簡単なアルゴリズムは線形探索。すべての点との距離を計算して最も近い点を探し出す。
データ量や次元が増えると計算量が増え、遅くなる。

最近は最近傍探索でも faiss のように GPU 使ったり、アルゴリズムを改善することで高性能になってきている。

近似最近傍探索（ANN）って？

https://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor

近似最近傍探索は厳密に最近傍じゃなくていいので、高速化した最近傍探索。
大規模データセット、高次元になっても性能が落ちづらい。

Elasticsearch が採用した HNSW: Hierarchical Navigable Small World や他にも Locality-sensitive hashing、k-d tree といった様々な手法がある。

HNSW

グラフ型の ANN。ベクトルからグラフを生成して、グラフを辿って近似最近傍を見つける。
Elasticsearch の kNN search もこのアルゴリズムを使っている。

HSNWイメージ

https://www.pinecone.io/learn/hnsw/ から転載

fujimotoshinjifujimotoshinji

Elasticsearch のドキュメントページ

https://www.elastic.co/guide/en/elasticsearch/reference/8.0/knn-search.html

Elasticsearch がサポートする kNN 検索

  • HNSW を用いた kNN search API
  • script_score で painless の関数

このブログの内容は前者。後者は 7.6 から利用可能。
検索性能優先なら前者、精度、インデックス性能優先なら後者。

Approximate kNN

マッピング設定

フィールドは dense_vector 型を利用する。 dense_vector はこちらを参照。

パラメータ 説明
dims ベクトルの次元数
index kNN search API に使うなら true に設定
similarity 類似度の指標
l2_norm dot_product cosine のいずれかをサポート

例

      "field": {
        "type": "dense_vector",
        "dims": 5,
        "index": true,
        "similarity": "l2_norm"
      },

検索

https://www.elastic.co/guide/en/elasticsearch/reference/8.0/knn-search-api.html

パラメータ 説明
knn.field dense_vector のフィールド名
knn.query_vector 検索ベクトル
knn.k 取得件数
knn.num_candidates シャードから取得する件数（よくわかっていない） 
GET my-approx-knn-index/_knn_search
{
  "knn": {
    "field": "my-image-vector",
    "query_vector": [-0.5, 90.0, -10, 14.8, -156.0],
    "k": 10,
    "num_candidates": 100
  },
  "fields": [
    "my-image-vector",
    "my-tag"
  ]
}
fujimotoshinjifujimotoshinji

まとめ

  • Elasticsearch 8.0 から kNN search API を利用可能（GA ではない）
  • kNN search API は ANN によるベクトルの近似最近傍探索が可能
  • kNN search API により単語ベースの検索よりもっと高度な文章の意味による検索、画像検索などが可能になる
  • ただしベクトル化する必要があるので今までのようにデータをそのまま Elasticsearch に登録するのではなく、ベクトル化しなければいけない
    • さらにいうとどうベクトル化するかが重要になる
  • 現状はベクトル単体の検索、スコア付けしかできない
    • 他のフィルターを組み合わせたりできない
fujimotoshinjifujimotoshinji

Appendix. テキストのベクトル化

テキストをベクトル検索するためにはテキストをベクトルに変換してインデックスして、検索キーワードをベクトルに変換して検索する必要がある。
「テキストをベクトルに変換する」とはなんだろうか？

Bag of words

「テキスト ベクトル」で検索すると大体最初に Bag of words が出てくる。Bag of words は転置インデックスの考え方にかなり近い。すべてのテキストに含まれる単語と各テキストの出現回数をカウントしてものである。というか TF-IDF の TF に相当する。

https://en.wikipedia.org/wiki/Bag-of-words_model

たとえば「今日は天気がいい」「明日の天気は雨らしい」という 2つのテキストがあったとすると。

単語 前者出現回数 後者出現回数
今日 1 0
は 1 1
天気 1 1
が 1 0
いい 1 0
明日 0 1
の 0 1
雨 0 1
らしい 0 1

※ 形態素解析は適当

となり、
前者のベクトルは [ 1, 1, 1, 1, 1, 0, 0, 0 ]、後者のベクトルは [ 0, 1, 1, 0, 0, 1, 1, 1 ] となる。

TF-IDF

Elasticsearch おなじみ TF-IDF（今は BM25）。Bag of words では特徴を識別できないので IDF を乗算することで特徴を踏まえたベクトルに変換できる。
たとえば、上記例では 2つの文書に含まれる「は」「天気」は特徴的ではないので 0になる。

前者のベクトルは [ 1, 0, 0, 1, 1, 0, 0, 0 ]、後者のベクトルは [ 0, 0, 0, 0, 0, 1, 1, 1 ] となる。

Bag of words、TF-IDF は固定長ベクトルではないので kNN には利用できません。

fujimotoshinjifujimotoshinji

Doc2Vec

Bag of words のような単語のカウンティングではなく、文書を分散表現する技術です。
任意の長さのテキストを固定長のベクトルに変換できます。
固定長のベクトルに合わせることで機械学習モデルの入力に利用できるところが大きい。
また単語の出現順序や単語間の距離など文書の意味をデータとして処理することができる。

Doc2Vec で変換したベクトルを利用することでレコメンド、感情分析、スパムフィルタリングなどの用途に活用できる。

Doc2Vec のアルゴリズムに PV-DM と PV-DBOW があるらしいが色々と調べてみたけど説明できる理解にいたらなかった。
ベクトル化するためのアプローチが逆のような印象を持ったが、実際にどういうアルゴリズムでベクトルになるのかわからなかった。
PV-DM は周辺の単語から推測する単語を導きながらベクトルを作成する。PV-DBOW は単語から推測する周辺の単語を導きながらベクトルを作成する。みたいに読み取れたけど、、、

詳細は別途学習する。

参考

https://pesuchin.hatenablog.com/entry/2017/12/24/201534
https://qiita.com/g-k/items/5ea94c13281f675302ca

fujimotoshinjifujimotoshinji

Universal Sentence Encoder

Doc2Vec が有名だが、Elasticsearch のベクトル検索のブログを読んでたら Universal Sentence Encoder を使ってベクトル変換して試してみたとあった。

https://www.elastic.co/jp/blog/text-similarity-search-with-vectors-in-elasticsearch

Universal Sentence Encoder は Google が発表したベクトル変換するモデル。
大規模なコーパスで転移学習済み？

TensorFlow Hub にアップロードされているので簡単に利用できる（英語で学習済み？）

https://tfhub.dev/google/universal-sentence-encoder/

参考

https://qiita.com/kenta1984/items/9613da23766a2578a27a
https://recruit.gmo.jp/engineer/jisedai/blog/universal-sentence-encoder/

fujimotoshinjifujimotoshinji

Universal Sentence Encoder（以後 USE）で ANN によるソートしてみた

まずは簡単にできそうだった Universal Sentence Encoder で試してみた。
TensorFlow を実行するのに Google Colaboratory（以後、colab）が簡単そうだったので colab で USE を使って生成したベクトルを Elasticsearch に登録、検索して、ソート順が想定どおりか試してみる。

  1. 登録する単語、検索キーワードをベクトル化
  2. Elasticsearch のインデックスを作成
  3. 単語とベクトルを Elasticsearch に登録
  4. _knn_search で出力順を確認

登録する単語

a. strawberry
b. lemon
c. iron

検索キーワード

a. sweet red
b. sour yellow
c. hard metal

1. 登録する単語、検索キーワードをベクトル化

colab にアクセスして、ノートブックを作成する

https://colab.research.google.com/

USE を使ってベクトル化して CSV ファイルでダウンロードする

import tensorflow_hub as hub
from google.colab import files
import numpy

embed = hub.load("https://tfhub.dev/google/universal-sentence-encoder/4")

embeddings = embed([
    "strawberry",
    "lemon",
    "iron",
    "red sweet",
    "sour yellow",
    "hard metal",
])

numpy.savetxt('vector.csv', embeddings.numpy(), delimiter=',', fmt='%f')

files.download('vector.csv')

2. Elasticsearch のインデックスを作成

Elasticsearch は適当に起動します。ローカルで docker で起動するには以下を参考に。

https://zenn.dev/link/comments/c80c95cfe94eab

単語とベクトルを持つインデックスを作成します。

PUT item
{
  "mappings": {
    "properties": {
      "name": {
        "type": "text"
      },
      "name_vector": {
        "type": "dense_vector",
        "dims": 512,
        "index": true,
        "similarity": "l2_norm"
      }
    }
  }
}

3. 単語とベクトルを Elasticsearch に登録

1 でダウンロードしたファイルを開いて、1〜3 行目のベクトルを登録する

PUT item/_doc/1
{
  "name": "strawberry",
  "item_vector": [0.021565, ..., -0.068993]
}

PUT item/_doc/2
{
  "name": "lemon",
  "item_vector": [-0.014715, ..., -0.031529]
}

PUT item/_doc/3
{
  "name": "iron",
  "item_vector": [-0.010550, ..., -0.026417]
}

4. _knn_search で出力順を確認

4〜6行目のベクトルで検索する

# red sweet
GET item/_knn_search
{
  "_source": "name",
  "knn": {
    "field": "item_vector",
    "query_vector": [0.023232, ..., -0.012324],
    "k": 10,
    "num_candidates": 100
  }
}

# response
{
  "took" : 2,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 3,
      "relation" : "eq"
    },
    "max_score" : 0.4523797,
    "hits" : [
      {
        "_index" : "item",
        "_id" : "1",
        "_score" : 0.4523797,
        "_source" : {
          "name" : "strawberry"
        }
      },
      {
        "_index" : "item",
        "_id" : "2",
        "_score" : 0.43282026,
        "_source" : {
          "name" : "lemon"
        }
      },
      {
        "_index" : "item",
        "_id" : "3",
        "_score" : 0.39016128,
        "_source" : {
          "name" : "iron"
        }
      }
    ]
  }
}

strawberry が一番なので想定通り。データが 3つだけだからかスコアに大きな差はない

# sour yellow
GET item/_knn_search
{
  "_source": "name",
  "knn": {
    "field": "item_vector",
    "query_vector": [0.036190, ..., -0.030133],
    "k": 10,
    "num_candidates": 100
  }
}

# response
{
  "took" : 3,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 3,
      "relation" : "eq"
    },
    "max_score" : 0.5030037,
    "hits" : [
      {
        "_index" : "item",
        "_id" : "2",
        "_score" : 0.5030037,
        "_source" : {
          "name" : "lemon"
        }
      },
      {
        "_index" : "item",
        "_id" : "1",
        "_score" : 0.4327205,
        "_source" : {
          "name" : "strawberry"
        }
      },
      {
        "_index" : "item",
        "_id" : "3",
        "_score" : 0.41674447,
        "_source" : {
          "name" : "iron"
        }
      }
    ]
  }
}

lemon が一番なので想定通り。

# hard metal
GET item/_knn_search
{
  "_source": "name",
  "knn": {
    "field": "item_vector",
    "query_vector": [-0.050342, ..., -0.031056],
    "k": 10,
    "num_candidates": 100
  }
}

# response
{
  "took" : 2,
  "timed_out" : false,
  "_shards" : {
    "total" : 1,
    "successful" : 1,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : {
      "value" : 3,
      "relation" : "eq"
    },
    "max_score" : 0.46831155,
    "hits" : [
      {
        "_index" : "item",
        "_id" : "3",
        "_score" : 0.46831155,
        "_source" : {
          "name" : "iron"
        }
      },
      {
        "_index" : "item",
        "_id" : "2",
        "_score" : 0.38828826,
        "_source" : {
          "name" : "lemon"
        }
      },
      {
        "_index" : "item",
        "_id" : "1",
        "_score" : 0.38251448,
        "_source" : {
          "name" : "strawberry"
        }
      }
    ]
  }
}

iron が一番なので想定通り。

データ数、ケース数が少ないけど特にチューニングとか必要なくベクトル化してインデキシングして検索するだけで想定通りの結果を確認することができた。

このスクラップは2022/03/09にクローズされました