Elasticsearchの全文検索スコア(BM25)は、ざっとこう計算される

Elasticsearchなどの検索エンジンではOkapi BM25というスコア付けアルゴリズムを使って検索結果の候補を順位づけします。今回は主にElasticsearchなどの検索エンジンを使おうとしているエンジニアを想定読者として、BM25について解説していきます。

またこの記事では具体的なスコアの目安も載せていきます。思ったように検索結果が出ない場合やスコアリングの最適化が必要になった時に助けになるのではと思います。

参考までに、BM25の確率論的な解釈などのより理論的な解説が知りたい方のために以前書いたBM25の記事を紹介しておきます。とはいえ読まなくても特に問題なくこの記事を読み進める事はできるはずです。

https://zenn.dev/wm3/articles/233dccc6e54dab

単語毎のスコアの総合点

クエリ $query$ (単語$q$の集合)に対するドキュメント $doc$ のスコアは以下の通りです。
 

$$\Large{\sum_{q ∈ query} score(doc, q)} \quad\normalsize{(0 ≤ score(doc,q) < \textit{IDF}_q)}$$

BM25は検索キーワードの単語毎にスコアを計算し、その総合点が高いドキュメントを採択する方式です。

単語毎のスコアはIDFと呼ばれる計算値が上限になります。

例えば「ダンボール ごみ 捨て 方」でWikipediaの記事をBM25でスコアリングする事を考えてみると、以下のような配点になります。

キーワード	スコア(0〜IDF)
ダンボール	0 〜 6.732
ごみ	0 〜 5.809
捨て	0 〜 4.078
方	0 〜 1.799
(総合点)	0 〜 18.418

ダンボールやごみの配点が捨てや方よりも高い事がわかると思います。これは割と直感に合う配点ではないでしょうか?

補足: 形態素解析による単語の分割

ElasticsearchやBM25を使った一般的な検索エンジンに日本語で検索する場合、検索キーワードを形態素解析で分割します。

例えば「ダンボールごみ 捨て方」で検索した場合、形態素解析エンジンが「ダンボールごみ」を「ダンボール ごみ」に、「捨て方」を「捨て 方」に変換してからBM25のスコアリング処理を開始します。

形態素解析についての詳細は今回の範囲を超えてしまうのでここでは解説しませんが、BM25はこの形態素解析の性能の影響を受けやすいです。

では次にこの上限値であるIDFを見てみましょう。

IDF(Inverse Document Frequency)

単語 $q$ のIDFは以下の通りです^[1]。
 

$$\Large{\textit{IDF}_q = \log( 1 + \dfrac{\footnotesize{qを含まないドキュメント数}\normalsize{+0.5}}{\footnotesize{qを含むドキュメント数}\normalsize{+0.5}} )}$$

IDFは各単語のレア度です。

IDF値の目安

割り算やlogが出てきてピンと来ないと思いますので、グラフにしてみます。

以下を覚えておくと良いと思います。

• 理論上最小のIDFはおよそ0(=単語が全てのドキュメントに出現した場合)
• 単語の出現数が10分の1になればIDFは 2.3程度(=log(10)) 上がる(Elasticsearchの場合)

また検索対象のドキュメントの量にもよりますが、大雑把な目安としては以下のようになります。

• IDF = 0〜2 → 大体のドキュメントに出てくる単語。このキーワードでは十分には絞り込めない
• IDF = 5〜15 → そのキーワードでそこそこ絞り込める単語
• IDF = 10〜20 → 大量のドキュメント量の中に数件にしか存在しない単語

2024年7月現在のWikipediaを使ってIDFの例を挙げます。Wikipediaの日本語記事は142万程度あり、その中のIDFは以下のようになります。

単語	件数	出現確率	IDF
ダンボール	1,692	0.12%	6.732
ごみ	4,260	0.30%	5.809
捨て	24,062	1.69%	4.078
方	145,366	10.2%	1.799

次は実際のスコアについて見てみましょう。

各単語のスコア(IDF * TF成分)

ドキュメント $doc$ の各単語 $q$ のスコアは以下の通りです。
 

$$\Large{score(doc,q) = \textit{IDF}_q ・ \dfrac{\textit{TF}_{doc,q}}{\textit{TF}_{doc,q} + s_{doc}}}$$

単語のスコアはIDFに0〜1の値となる式を掛けたものになります。

TF(Term Frequency)というのは、ドキュメントでの単語の出現回数^[2]です。

$s_{doc}$ はドキュメントの長さ調整のための値です。後述しますが平均的な長さのドキュメントであれば1.2程度だと考えて良いです。

単語の出現回数と飽和曲線

イメージしにくい式が出てきました。右の$\footnotesize{\dfrac{\textit{TF}_{doc,q}}{\textit{TF}_{doc,q} + s_{doc}}}$という式は$\textit{TF}_{doc,q}$の値に対して飽和曲線という曲線を描きます。この式の値は0〜1になります。

この曲線の特徴はTFが$s_{doc}$くらいまでは順調に上昇するものの、それ以上になると急速にスコアが頭打ちになります。TFが$9s_{doc}$くらいになるとそれ以上なかなか上がりません。

TF成分の目安

スコアのTF成分の例を挙げましょう。平均的な長さのドキュメントでは$s_{doc}$は1.2になるので、それを前提とすると以下の表のようになります。

ケース	式	値
$q$が1回出現した平均的な長さの記事	$\footnotesize{\dfrac{1}{1+1.2}}\normalsize{\textit{IDF}}$	$45.5\%*\textit{IDF}$
$q$が5回出現した平均的な長さの記事	$\footnotesize{\dfrac{5}{5+1.2}}\normalsize{\textit{IDF}}$	$80.6\%*\textit{IDF}$
$q$が10回出現した平均的な長さの記事	$\footnotesize{\dfrac{10}{10+1.2}}\normalsize{\textit{IDF}}$	$89.3\%*\textit{IDF}$
$q$が20回出現した平均的な長さの記事	$\footnotesize{\dfrac{20}{20+1.2}}\normalsize{\textit{IDF}}$	$94.3\%*\textit{IDF}$

平均的な長さでは出現回数10回程度で頭打ちになってくる事がなんとなくイメージできるのではないでしょうか。IDFと同様、検索結果のデバッグや改善をする際にざっくり覚えておくと便利だと思います。

ドキュメントの長さによる影響

これでBM25で説明していないのは謎の値$s_{doc}$になります。この値の式は以下のようになります。
 

$$\Large{s_{doc} = k(1 - b + b ・ \dfrac{\textit{length}_{doc}}{\textit{length}_{avg}})}$$

何やら複雑な式となっています。各変数の意味は以下の通りになります。

• $\textit{length}_{doc}$ … $doc$の長さ
• $\textit{length}_{avg}$ … 全ドキュメント平均の長さ
• $k$、$b$ … BM25をカスタマイズするための設定値
  • Elasticsearchのデフォルトでは$k=1.2$、$b=0.75$^[3]。

一旦は「ドキュメントの長さによる影響を調整する値だ」という事がわかってもらえれば良いと思います。特徴は以下のようになります。

• 平均的な長さの場合は$k(=1.2)$になる
  • 上の式に$\textit{length}_{doc}$に$\textit{length}_{avg}$を代入してみると良いでしょう
• ドキュメントが長いと$s_{doc}$が大きくなる
  • スコアを上げるために必要な単語の出現回数が多くなります

TF成分の目安(長さ考慮)

最後にスコアの値をイメージしやすくするため、スコアのTF成分の例を挙げましょう。

ケース	式	値
$q$が1回出現した平均的な長さの記事	$\footnotesize{\dfrac{1}{1+1.2}}\normalsize{\textit{IDF}}$	$45.5\%*\textit{IDF}$
$q$が10回出現した平均的な長さの記事	$\footnotesize{\dfrac{10}{10+1.2}}\normalsize{\textit{IDF}}$	$89.3\%*\textit{IDF}$
$q$が10回出現した平均の10倍の長さの記事	$\footnotesize{\dfrac{10}{10+9.3}}\normalsize{\textit{IDF}}$	$51.8\%*\textit{IDF}$
$q$が100回出現した平均の10倍の長さの記事	$\footnotesize{\dfrac{100}{100+9.3}}\normalsize{\textit{IDF}}$	$91.5\%*\textit{IDF}$
$q$が1回出現した平均の10分の1の長さの記事	$\footnotesize{\dfrac{1}{1+0.39}}\normalsize{\textit{IDF}}$	$71.9\%*\textit{IDF}$

• 長い文章ではその分だけ出現回数が増えないとスコアが下がる事
• 短い文章では少ない出現回数でもスコアが高い事
• 単語の出現頻度が同じ場合、文章が長い方が少しスコアが高い事

がなんとなくイメージできるのではないでしょうか。

おまけ： ElasticsearchでBM25の値を確認する方法

おまけとして、ElasticsearchでBM25のスコアを確認する方法を記載しておきます。

スコアは/_searchAPIのパラメーターに"explain": trueを渡すと確認ができます。

GET /jawiki/_search
{
  "explain": true, 
  "query": {
    "match": { "content": { "query": "ダンボールごみ 捨て方" } }
  }
}

結果が 死ぬほど読みにくい 長くなるので抜粋しますが、"weight(〜)"というテキストが表示されている箇所にBM25のスコアが表示されます。

なお、Elasticsearchでは歴史的な事情によりBM25のスコアは$k+1$倍されるようです^[4]。

まとめ

この記事ではBM25のスコアリングの解説をしました。BM25のポイントをまとめると以下のようになります。

• 単語毎のスコアの総合点形式
• 各単語のスコアの上限はIDFであり、その値は単語がレアなほど高い
• 単語の出現回数(TF)が多いほどスコア上限に近づくが、上昇幅は頭打ちになる
• 単語の出現回数が同じなら短い文章の方がスコアが高い。出現頻度が同じなら長い文章の方がスコアが高い

次回

BM25を使ってわかった特性やクセについて紹介し、スコアを調整する際に役立つTipsを紹介しようと思います。
BM25の意味について、「求めていなそうなドキュメントにスコアを与えない」という視点で解説します。

https://zenn.dev/wm3/articles/715981c7f33a51

脚注

1. 実はIDFはいくつかバリエーションがあります。例えばシンプルなIDFはlogの中で+1や+0.5をしないなど、より簡単な式になっています。しかし$q$を含むドキュメント数が極端なケースを除くと、上記の式とほぼ同じ値になります。

2. term frequencyなら出現頻度なのでは?と思うのですが、BM25の資料では出現回数をTFと呼んでいるように読めます。

3. $k$や$b$の値は昔からこの値が良いとされているようです。

4. この$k+1$倍処理は元々のBM25にあったのが、その後の論文で削除されたようです。そのためElasticsearchのコアエンジンであるLuceneではこの処理は削除されています。Elasticsearchも追従する動きはあるようですが、互換性のためにこの処理を維持しているようです。