この記事は Elasticsearchで検索を行った際の結果のランク付けのもとになっている、スコアの計算がどのようにおこなわれているのかと、スコア計算のパラメータを調整する方法を調査してまとめたものです。
目次
はじめに
Elasticsearchは全文検索エンジンです。
検索でリクエストされたテキストと、あらかじめ登録されているドキュメントの類似度をスコアとして計算し、類似度の高いドキュメント順にソートしてレスポンスしてくれます。
今回はこのスコア計算がどのように行われているのかと、スコア計算の調整について調査してみました。
前提
Elasticsearch と Kibana（バージョンは 7.6.2）を使用します。
Elasticsearch、Kibana については以下の記事もあわせてお読みください。
blog.linkode.co.jp blog.linkode.co.jp
準備
まず、Kibana を使って、次のように score-confirmation というインデックスへドキュメントを登録します。
POST /score-confirmation/_bulk {"index": {}} {"message": "Linkode Tech"} {"index": {}} {"message": "Linkode Blog"} {"index": {}} {"message": "Linkode Tech Blog"} {"index": {}} {"message": "Linkode Tech Blog Scala"}
これで、以下のドキュメントが登録されました。
| ドキュメント |
|---|
| Linkode Tech |
| Linkode Blog |
| Linkode Tech Blog |
| Linkode Tech Blog Scala |
スコアの確認
次に Linkode Blog というテキストで、作成したインデックス score-confirmation を検索してみます。
GET /score-confirmation/_search { "query": { "match": { "message": "Linkode Blog" } } }
検索結果は次のようになりました。
Elasticsearch からの検索レスポンス
{ "took" : 3, "timed_out" : false, "_shards" : { "total" : 1, "successful" : 1, "skipped" : 0, "failed" : 0 }, "hits" : { "total" : { "value" : 4, "relation" : "eq" }, "max_score" : 0.5200585, "hits" : [ { "_index" : "score-confirmation", "_type" : "_doc", "_id" : "ZQt0oHEBWDDK_RCJ1jAj", "_score" : 0.5200585, "_source" : { "message" : "Linkode Blog" } }, { "_index" : "score-confirmation", "_type" : "_doc", "_id" : "Zgt0oHEBWDDK_RCJ1jAj", "_score" : 0.44546846, "_source" : { "message" : "Linkode Tech Blog" } }, { "_index" : "score-confirmation", "_type" : "_doc", "_id" : "Zwt0oHEBWDDK_RCJ1jAj", "_score" : 0.3895909, "_source" : { "message" : "Linkode Tech Blog Scala" } }, { "_index" : "score-confirmation", "_type" : "_doc", "_id" : "ZAt0oHEBWDDK_RCJ1jAj", "_score" : 0.11859183, "_source" : { "message" : "Linkode Tech" } } ] } }
各ドキュメントのスコアは次の通りです。
| ドキュメント | スコア |
|---|---|
| Linkode Tech | 0.11859183 |
| Linkode Blog | 0.5200585 |
| Linkode Tech Blog | 0.44546846 |
| Linkode Tech Blog Scala | 0.3895909 |
このドキュメントの中では Linkode Blog が最もスコアが高く、検索したテキストに最も類似していることがわかります。
今回の例では検索したテキストと、ドキュメントの内容が完全に一致しているので、期待通りの挙動です。
ドキュメントのスコア計算
ドキュメントのスコア計算ですが、結論から先に書くと、
GET /index-name/_search { "query": { "match": { "value-name": "value" } } }
で検索した際のスコアは、次のように計算されているようです。
| 項 | 説明 |
|---|---|
| q | Query、検索テキスト |
| d | Document、対象のドキュメント |
| t | Term、検索テキスト q に含まれる単語 |
| boost | t に対して恣意的に重み付ける係数 |
| tf | ドキュメントやクエリ内で単語が出現する頻度 |
| idf | インデックス内における単語の稀少価値 |
文章で書いてみると
- 検索テキスト (q) のドキュメント (d) に対する評価 (score) は、検索テキストを単語単位で分解して単語 (t) 毎に、単語に対して恣意的に重み付けられた係数 (boost)、ドキュメントやクエリ内で単語が出現する頻度 (tf) と、インデックス内における単語の希少価値 (idf) を掛け合わせたものの総和
が、スコアになりそうです。
疑似的にPythonで記述するなら次のような処理になるでしょうか。
def get_score(query, document): score = 0 for term in query: score += (boost(term) * tf(term) * idf(term)) return score
boost は検索テキストに含まれる単語（term）をどれだけ重要視するかが任意に設定される係数のようですが、tf、idf がまだよくわかりません。
調べてみると、tf、idf は tf-idf という手法の二つの指標になっているようです。
- tf-idf
Wikipedia からの引用tf-idfは、文書中に含まれる単語の重要度を評価する手法の1つであり、主に情報検索やトピック分析などの分野で用いられている。 tf-idfは、tf（英: Term Frequency、単語の出現頻度）とidf（英: Inverse Document Frequency、逆文書頻度）の二つの指標に基づいて計算される。
さらに Elasticsearch では、この tf-idf を改良した、BM25 (Okapi BM25) という手法が用いられているようです。
※ 厳密には、検索で使用される類似度モジュールのデフォルトがBM25です。
- Okapi BM25
Wikipedia からの引用
Okapi BM25は、情報検索における順位付けの手法である。検索エンジンがクエリとの関連性に応じて、文書を順位付けするのに用いられる。
...<中略>...
ロンドン大学シティ校が1980年代から1990年代にかけて開発したオカピ情報検索システム (Okapi information retrieval system) に最初に実装されたため、 "Okapi BM25" と呼ばれるが、単に、この手法自体の名称であるBM25とも呼ばれる。
それぞれ、tf、idf を求める式は次のようになります。
- tf(t)
| 項 | 説明 |
|---|---|
| freq | ドキュメント内の単語の数 |
| k1 | 単語の出現頻度から計算した重要度(TF-IDF値を指す)の影響の大きさを調整するパラメータ デフォルト値は 1.2 |
| b | 文書の単語数による影響の大きさを調整するパラメータ デフォルト値は 0.75 |
| dl | ドキュメントを構成する単語の数 |
| avgdl | インデックス内の全てのドキュメントを構成する単語の平均値 |
1つのドキュメントの中で検索した単語 (t) の数 (freq) が増えていくほど値は大きくなり、tf は1に近い数字になっていきそうです。
- idf(t)
| 項 | 説明 |
|---|---|
| n | 単語を含むドキュメントの数 |
| N | インデックス内のドキュメントの総数 |
インデックス内のドキュメントの総数 (N) が 100 の時に、単語を含むドキュメントの数が 0~100 で推移したときの上記の式をグラフ化すると次のようになります。
対象単語の出現頻度が少なく 0 に近いほど idf は大きな値になっていて、対象単語が出現するドキュメントが増えていく（インデックス内のドキュメントの総数に近づく）と、idf は限りなく0に近づいていくことがわかります。
このことから、
は、検索対象の単語が、ひとつのドキュメント内で多く出現し、かつインデックス内の全ドキュメント内での出現が少なければ、スコアが高くなる（単語とドキュメントの関連性が高いと判断する）という事がわかります。
スコア計算の過程を確認
それでは、Elasticsearch と Kibana に戻って、スコアの確認 で検索したときと同じテキストで explain パラメータを付加して検索を行い、スコア計算の過程を確認してみます。
GET /score-confirmation/_search?explain=true { "query": { "match": { "message": "Linkode Blog" } } }
計算の過程が詳細にレスポンスされるので、非常に長いのですが、ドキュメント Linkode Blog のスコア 0.5200585 が計算されている過程だけを取り出すと次のようになります。
Elasticsearch からの検索レスポンス（explain パラメータ付き）
{ "_shard" : "[score-confirmation][0]", "_node" : "61hhX0jzQlWWg6WiDvKDWQ", "_index" : "score-confirmation", "_type" : "_doc", "_id" : "ZQt0oHEBWDDK_RCJ1jAj", "_score" : 0.5200585, "_source" : { "message" : "Linkode Blog" }, "_explanation" : { "value" : 0.5200585, "description" : "sum of:", "details" : [ { "value" : 0.11859183, "description" : "weight(message:linkode in 1) [PerFieldSimilarity], result of:", "details" : [ { "value" : 0.11859183, "description" : "score(freq=1.0), computed as boost * idf * tf from:", "details" : [ { "value" : 2.2, "description" : "boost", "details" : [ ] }, { "value" : 0.105360515, "description" : "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5)) from:", "details" : [ { "value" : 4, "description" : "n, number of documents containing term", "details" : [ ] }, { "value" : 4, "description" : "N, total number of documents with field", "details" : [ ] } ] }, { "value" : 0.51162785, "description" : "tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl)) from:", "details" : [ { "value" : 1.0, "description" : "freq, occurrences of term within document", "details" : [ ] }, { "value" : 1.2, "description" : "k1, term saturation parameter", "details" : [ ] }, { "value" : 0.75, "description" : "b, length normalization parameter", "details" : [ ] }, { "value" : 2.0, "description" : "dl, length of field", "details" : [ ] }, { "value" : 2.75, "description" : "avgdl, average length of field", "details" : [ ] } ] } ] } ] }, { "value" : 0.40146667, "description" : "weight(message:blog in 1) [PerFieldSimilarity], result of:", "details" : [ { "value" : 0.40146667, "description" : "score(freq=1.0), computed as boost * idf * tf from:", "details" : [ { "value" : 2.2, "description" : "boost", "details" : [ ] }, { "value" : 0.35667494, "description" : "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5)) from:", "details" : [ { "value" : 3, "description" : "n, number of documents containing term", "details" : [ ] }, { "value" : 4, "description" : "N, total number of documents with field", "details" : [ ] } ] }, { "value" : 0.51162785, "description" : "tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl)) from:", "details" : [ { "value" : 1.0, "description" : "freq, occurrences of term within document", "details" : [ ] }, { "value" : 1.2, "description" : "k1, term saturation parameter", "details" : [ ] }, { "value" : 0.75, "description" : "b, length normalization parameter", "details" : [ ] }, { "value" : 2.0, "description" : "dl, length of field", "details" : [ ] }, { "value" : 2.75, "description" : "avgdl, average length of field", "details" : [ ] } ] } ] } ] } ] } }
_explanation が計算の過程を表した項目になっています。
冒頭のスコア全体の説明（description）として
sum of:
とあり、スコアは以降の配列要素の総和であることがわかります。
詳細を確認していくと、検索したテキスト Linkode Blog が linkode と blog の二つの要素（単語）に分解されています。
それぞれの計算過程の説明（description）を確認すると
score(freq=1.0), computed as boost * idf * tf
idf, computed as log(1 + (N - n + 0.5) / (n + 0.5))
tf, computed as freq / (freq + k1 * (1 - b + b * dl / avgdl))
とあり、boost値 と BM25で求められた単語とドキュメントの関連性が掛け合わされて、各単語のスコアが求められていることがわかります。
スコア計算のカスタマイズ
BM25 の計算式に、k1, b といったパラメータがありました。
Elasticsearch の古いドキュメントで、このパラメータの説明を見つけることができます。
https://www.elastic.co/guide/en/elasticsearch/guide/2.x/pluggable-similarites.html#bm25-tunability
または、日本語のこちらの記事の方がわかりやすいかもしれません。
【技術解説】単語の重要度を測る？TF-IDFとOkapi BM25の計算方法とは
Okapi BM25のパラメータ(k1,b)
◆パラメータk1
k1は主に単語の出現頻度から計算した重要度(TF-IDF値を指す)の影響の大きさを調整するパラメータである．k1=1.2もしくは2.0とし，k1=2.0が一番効果的であることが確認されている．
◆パラメータbについて
bは主に文書の単語数による影響の大きさを調整するパラメータである．0.0から1.0の間で設定し，b=0.75が一番効果的であることが確認されている．なお，b=0.0とした場合，文書の単語数による影響をなくした結果を得ることができる．
この二つのパラメータは Elasticsearch でも調整することができます。
Elasticsearch のリファレンスを参考に、b の値を 0 に設定した例は以下の通りです。
※一旦インデックスを削除して新規に作成する必要があります。
PUT /score-confirmation { "settings": { "index": { "similarity": { "my_similarity": { "type": "BM25", "k1": 1.2, "b": 0.0 } } } }, "mappings": { "properties" : { "message" : { "type" : "text", "similarity" : "my_similarity" } } } }
設定したいパラメータを持った類似モジュールを定義して、モジュールを適応したいドキュメントとマッピングしています。
この状態で、Linkode Blog の検索を行うと、b=0.0とした場合，文書の単語数による影響をなくした結果を得ることができる．という説明の通りのスコアが得られました。
| ドキュメント | スコア |
|---|---|
| Linkode Tech | 0.10536051 |
| Linkode Blog | 0.46203545 |
| Linkode Tech Blog | 0.46203545 |
| Linkode Tech Blog Scala | 0.46203545 |
Elastic社のブログによると、
Practical BM25 - Part 3: Considerations for Picking b and k1 in Elasticsearch
It’s worth noting that picking b and k1 are generally not the first thing to do when your users aren’t finding documents quickly. The default values of b = 0.75 and k1 = 1.2 work pretty well for most corpuses, so you’re likely fine with the defaults.
It’s been fairly well studied that there are no “best” b and k1 values for all data/queries.
とあり、殆どの場合、デフォルト値のままでうまくいくので特に触る必要はなく、また全てのデータ/クエリに「最良の」b および k1 値がないことはかなりよく研究されている、とあります。
ではもっと柔軟に検索をカスタマイズしたい場合はどうするのか？という事も同記事で触れられていて、次のように説明されています。
- Boosting or adding constant scores for things like exact phrase matches in a bool query
- Making use of synonyms to match other terms the user may be interested in
- Adding fuzziness, typeahead, phonetic matching, stemming, and other text/analysis components to help with misspellings, language differences, etc.
- Adding or using a function score to decay the scores of older documents or documents which are further geographically from the end user
特に最後に説明されている function score ですが、日付の古いものや地理的に離れているもののスコアを減少させる…とあるので、ドキュメントのプロパティ次第で
- 時系列で新しいドキュメントを優先する
- 地理的に指定した地域を中心に検索を行う
というような、検索の柔軟なカスタマイズができそうです。
まとめ
Elasticsearch の検索はデフォルトでは
BM25(Okapi BM25)という手法でスコア計算され、ランク付けされていることがわかりました。Elasticsearch でデフォルトで設定されている
BM25(Okapi BM25)のパラメータk1、bは調整可能ですが、特に触る必要はなさそうです。柔軟な検索を行うために
function scoreというスコアの計算方法が提供されていることがわかったので、今度はfunction scoreの調査を行ってみたいと思います。
