1. はじめに

このブログではElasticsearchについて時々思い出したように書きなぐっております。

そしてこの記事では、Elasticsearchのデフォルトのスコアリング方式であるBM25について、数式が苦手でも、なんとなく分かった気になる（かもしれない）解説を試みてみます。

邪道に徹しておりますので、(私自身もそうですが）できれば数式を見たく無い人向けに「デフォルメ」した言い方をしているところもあります。この点をご容赦いただくとともに、デフォルメを超えて間違っているじゃんというところがあればこっそり教えてください。

正攻法や、数学的・情報科学的に正確な手法としての説明をお求めの方は、末尾の参考リンク先などをあたってください。

2. BM25やTF-IDFのアイディア

BM25やそのある種前身であるTF-IDFについて、使う側の立場としてこれらの手法を理解するには、どのようなドキュメントおよび検索語の場合に評価（スコア）が高くなるか/高評価とするかを掴むのが早道だと思います。

ということで、どんな時に評価が高いの？というところの3大要素を以下にあげてみます。

検索語の出現数が多いと高評価。
ここで、レアな検索語であれば、出現数評価の重みをさらにUPする。
ここで、検索語の出現割合が高い文書であれば、さらに出現数評価の重みをUPする。

f:id:azotar:20200103163310p:plain

ひとつめは、比較的感覚にそったものになっていると思います。ふたつめ、みっつめは、ひとつめの弱点をカバーする、あるいはスコアにメリハリをもたらすものです。

以下に分かった気になるかもしれない、ひとことウンチク入りのイメージ図をはりつけてみます。 (上記の3点を、検索語の出現数、レアな検索語、密度が高い... のようにキャッチコピー的に言い換えています。）

1. 検索語の出現数

検索語の出現数が多いと高評価というのは（何か弱点はあるかもしれないですが）特に反対する理由はないと思います。これはBag of Wordsという、より古典的な考え方そのものらしいです。

f:id:azotar:20200103163349p:plain

2. レアな検索語

こちらは「レア度」の評価がポイントになりますが、全ドキュメント数のうち、そのワード（検索語）を含むドキュメント数の比率を使います。ドキュメント検索の例ではありませんが、山田さんは名簿の中に5%もいるが、綾小路さんは一人だけ...という具合です。なお、分かった気になるには「レア度」のように希少価値に目を向けた方が良いと思いこのように説明していますが、英語でいうところの「a」や「the」など数を数えてもそれほど意味をなさない（ただしこれらは検索に使われることもまれですが）ようなワードを除外する効果もあります。

f:id:azotar:20200103163420p:plain

3. 密度が高い

こちらは、長い文章になんどかそのワードが出てくるという例よりも、（相対的に）短めの文章の中で繰り返しそのワードが出てくるような例の方がそのワードについて詳しく述べているというアイディアになります。実際には、全ドキュメントの平均ワード数に対してスコア評価対象となるドキュメントのワード数の比率から、そのドキュメントではあるワードに対して集中的・専門的に述べているのかを見出します。 (TF-IDFに対するBM25の最大の改善ポイントはこの観点によるものです。）

f:id:azotar:20200103163535p:plain

3. スコア値の傾向を見てみる

BM25の定義

数式の説明はボロが出るのでここでは行いませんが、パワポで数式エディタを使ってみたかったのでひとまず下記に引用します。

f:id:azotar:20200103163856p:plain

利用シーンを仮定してできるだけ具体的な数値におきかえする

数式での厳密な定義はともかく、BM25のパラメータは以下の6つ（6個目は2つ分なのでそうとらえると7つ）です。

f:id:azotar:20200103163937p:plain

ここで、まともに考えると、ある検索語とそれにマッチしたドキュメントのそれぞれのBM25によるスコアは、検索語とドキュメントのその都度の関係です。

よって、本来であれば、その都度の計算にはなります。

一方、肌感覚をつかむという意味では、実際は定数と思っても良さそうな変数については、いっそ定数だと思って値を当てはめて計算することにしましょう、グラフを書いてみましょうというところが良いでしょう。

BM25やTF-IDFの評価はパラメータも多く動的なものになりますが、ご自身が検索サービスとして対象としているドキュメント群や想定検索シナリオを例にとると、大半のパラメータは定数とみなして値を当てはめてしまっても良さそうです。

例えば、次のように考えてみます。

f:id:azotar:20200105103026p:plain

評価(score)の計算式について、変数が2つだけの式に変形できました。変数を減らしたことで、この時点でグラフの形が想像しやすくなっています。

具体的には、左のlogの項はdが大きくなるほど0に近くづきます*1ことと、右の項も2.2に近くことが予想できます。

BM25のスコア値のグラフ

実際にグラフをえがいてみます。

検索語Wで、あるドキュメントDのスコアを計算しました、というグラフです。

3つグラフがあります。タイトルにあるように、全ドキュメント数を1,000,000、100,000、10,000と変えてみたグラフで、それ以外は同じ条件です。
縦軸は、あるドキュメントDのBM25のスコアです。
各系列はtf=●●、dl/avgdl=▲▲とあります。tfはスコアを計算したいドキュメントDに対して、この検索語Wが何回出現したかです。 dl/avgdlは、このドキュメントDのワード数と全ドキュメントの平均ワード数との比です。平均の2倍のワード数なら2となります。
横軸はその検索語Wが、全ドキュメント中、何件のドキュメントに出現するようなワードであったかを示します。つまり横軸の右にいけばいくほど、Wはありふれた単語に該当するということになります。

f:id:azotar:20200103165227p:plain

f:id:azotar:20200103165220p:plain

f:id:azotar:20200103165213p:plain

縦軸と横軸のスケールは揃えています！！！

グラフの形を見ると（見なくても数式に強い人だったら想像がつく範囲ですが、対数(log)のグラフなので）、全ドキュメントの多寡によらず、スコアの傾向は似た形状を辿りそうです。

気づき

前述の3つのポイントはそれはそれで見て取れるのですが、実際に値を当てはめてみた上で、私見ではここでの見どころは次のように捉えています。

グラフがひらがなの「し」の字のようになっている*2。　→ (あくまでこの例の範囲から他の場合も想像したにすぎませんが、)相当レアな検索語でなければ、思ったほどスコアの差が付かない。3つのグラフで、全ドキュメント数の多い少ないはありますが、横軸の20あたりにスコアの変曲点のようなものがあり、20件を超える出現数の検索語だとそれ以上の出現数と大差ないスコアが付く傾向が見て取れます。
各グラフは、TF(グラフ図中はtfと表記)の値が同じものごとに同じ色で点線か実線をかえて描画しています。TFの値が大きいもの（グラフ中だと赤いラインのグラフ）はTFの値が小さいもの（青のラインのグラフ）より、「dl/avgdlの値の大きさ（そのドキュメントがワードが多いテキストか少ないテキストか）」によるスコアの差が出にくくなっていることが見て取れます。
検索語の出現数が極めて少ない（グラフでいうと横軸が0に近く）としても、この定義の範囲では、最大でも40程度の値の範囲である。

まとめと所感

邪道と大きくでたものの、実のところ値を固定してBM25のグラフを描いただけ？となってしまいましたが、グラフを描いてみることでなんとなくわかった気になれていることを目指してみました。

いずれも、もともと定義がそういうものであり、加えてこの記事でそういう係数にしているというところもより後押ししている面もありますが、コンセプトどおりに、評価がなされていることが実感できました(?)。

また、そのようになるように定義・調整したから当たり前といえば当たり前ですが、対数(log)を数式に入れることで、なだらかなグラフになるとともに、過剰に評価が高くなることもないことが実感できました(?)。

それと当時に、ありふれたワードの検索の場合は、コンマいくつの値レベルで評価の差は出るにはでるものの、大きな差にはならないという当たり前のことも分かりました。

いうまでもなくあくまで個人の意見ですが、実際の検索利用シーンに置き換えると、また誤解をおそれずにいうと、BM25などのRelevance Scoringは、あくまで味付けなんだなと思いました。

いまさらですが、少ない検索ワードや曖昧なコンテキストにおいて、利用者の探している情報を検索させるというところの難しさを実感します。

レストラン検索サイトでただただ「ラーメン」で検索させてもどんぐりの背比べになってしまうので、2つめの検索条件としてどのようなものをユーザーに入れてもらえるようにするか選択させるか、およびそもそも各レストランのウリや特徴を捉えたドキュメンテーションやライティングを行うかというところなんだろうなと思う次第です。

そのためには、(利用者（ペルソナ）を決めたもの以外は締め出すなど限定する必要はないものの、)ターゲットとする利用者イメージや利用シーンをいかに高解像度で描けるかが改めて重要だと感じます。幸い、先人やトップランナーがテクニカルな選択肢を広げてくれているので、それにのっかることでもっともっと先が見れるようになってきている期待がもてますので、自分のような凡人もエンジニアリングをより楽しめいければと令和2年の初頭に思いました...謎の締めでこの記事を終わります。

付録

グラフのプロットに用いたプログラム例

import math
import matplotlib.pyplot as plt
import sys
import matplotlib as mpl
mpl.rcParams['font.family'] = 'Hiragino Maru Gothic Pro'


#DOC_COUNT = 10000
DOC_COUNT = int(sys.argv[1])
#v_docFreq = [i + 1 for i in range(DOC_COUNT)]
v_docFreq = [i + 1 for i in range(1000)]
x = v_docFreq


k1 = 1.25
b = 0.75

def score(tf, x, dl_avgdl):
  # https://www.elastic.co/jp/blog/practical-bm25-part-2-the-bm25-algorithm-and-its-variables
  return [math.log(DOC_COUNT/(0.5 + n)) * tf * (k1 +1) / (tf + k1*(1-b + b*(dl_avgdl)))  for n in x]

plt.title('BM25スコア値分布イメージ確認： ドキュメント件数' + '{:,}'.format(DOC_COUNT) + '件,' + 'k1=' + str(k1) + ',b=' + str(b))
plt.xlabel('docFreq:検索語を含むドキュメント数')
plt.ylabel('スコア')
tf = [1, 2, 10, 100]
color = ['blue','green','orange','red']
dl_avgdl = [0.1, 1, 2,10]
linestyle = ['dotted','dashdot','dashed','solid']
pp = []

for i, tf_item in enumerate(tf):
  for j,dl_avgdl_item in enumerate(dl_avgdl):
    linewidth = i + 1
    alpha = (i + 1) * 0.1
    s = score(tf_item, x, dl_avgdl_item)
    p, = plt.plot(x ,s, linestyle=linestyle[j], color=color[i], label='tf=' + str(tf_item) + ', dl/avgdl=' + str(dl_avgdl_item).rjust(3,' ')) 
    pp.append(p)
  

plt.ylim(0,40)
plt.legend(handles=pp,bbox_to_anchor=(0.2, 0.95), loc='upper left', borderaxespad=0,ncol=len(tf))
plt.show()