はじめに
BM25は特に検索アルゴリズムに使われる自然言語処理の一つで、tf-idfの進化系である。具体的には単語の出現頻度に基づいて、文章の順位付けを行う。tf-idfとの違いはドキュメントが短いほど順位が高くつき、長いほど順位が低くつく傾向があるというところである。この記事では数式を紐どいて、BM25の性質を説明する。
数式
BM25の数式についてまず説明する。$D$を文章全体の集合(以下全文章と呼ぶ)、$d$は文章であり$D$の要素、$q$を検索クエリ($q_i\in q$)とした時のBM25の数式は以下のようなものである。
$$
score(q, d) = \sum_i idf(q_i)\times\frac{(k_1+1)f(q_i, d)}{f(q_i, d)+k_1(1-b+b\frac{|d|}{avg(dl)})}
$$
$idf(q_i)$は単語$q_i$のidf、$f(q_i, D)$は文章$d$中での単語$q_i$の出現頻度、$|d|$は文章$d$の単語数、$avg(dl)$は全文章の平均単語数を表している(dlはdocument lengthの略)。また、$k_1$は0以上の実数、$b$は0から１の実数をとるパラメーターであり$k_1\in[1.2, 2.0]$、$b=0.75$とされることが多い。
tf-idfとの類似
式をtf-idfのものと比較するとtfの部分を
$$
\frac{(k_1+1)f(q_i, d)}{f(q_i, d)+k_1(1-b+b\frac{|d|}{avg(dl)})}
$$
で置き換わったものとなっている。tf-idfでtfとidfを分けて考えるようにここでも分けて考える。
idf
先に既知であるidfについて簡単に説明する。idfは文章中に単語$q_i$があるという事象の情報量であり、数式では$idf(q_i) = \log_2(\frac{N}{n(q_i)})$のように書く。$N$は全文章数、$n(q_i)$は全文章のうち単語$q_i$を含む文章の総数である。idfはシグマの各項に対する重み付けと考えられ、単語$q_i$が頻出であるほど小さくなり、珍しいほど大きくなる。
tfに当たる部分
次にtf-idfでtfに当たる部分
$$
\frac{(k_1+1)f(q_i, d)}{f(q_i, d)+k_1(1-b+b\frac{|d|}{avg(dl)})}
$$
を細かく見る。$\frac{|d|}{avg(dl)}$は全文章$D$の単語数の平均を文章$d$の単語数で割ったものとなっている。つまりこれは全文章$D$中の文章に対する文章$d$の相対的な長さを表している。$f(q_i, d)$は文章$d$中での単語の出現頻度を表している。厳密な意味での単語の出現頻度ではなく、この関数は色々な実装が可能である。tfが使われたり、単語$q_i$の出現数が使われたり、単語$q_i$の出現数のルートが使われたりする。ElasticsearchのLucene's Practical Scoring Functionでは単語$q_i$の出現数のルートが使われている。結局のところこれは文書$d$中に含まれる単語$q_i$の数に依存している。これで式中の各関数の説明は済んだので次は式の振る舞いを考察する。
初めに簡単のため、$|d| = avg(dl)$と仮定して考える($1-b+b\frac{|d|}{avg(dl)}=1$)。この場合今考えている関数は以下のようになる。
$$
\frac{(k_1+1)f(q_i, d)}{f(q_i, d)+k_1}
$$
$f(q_i, d)$は、文章$d$中の単語$q_i$の数とする。単語が含まれていないときは$f=0$となり、考えている関数は0となる。このことは文章$d$中に単語$q_i$が含まれていない場合はスコアに影響しないということを示している。また単語が一つ含まれているとき、二つ含まれているときと考えていくと以下のようなグラフが得られる。
$k_1=1.2$とした。グラフを見ると単語数(f)が増えるにつれ考えている式(y)の増加が小さくなっている。数式からもこの傾向は読み取ることができ、考えている式は上限が$k_1+1$で単語数が増えれば増えるほと増加するが増加率は小さくなる関数であることがわかる。これの意味するところは含まれる単語数が多ければ多いほどスコアも大きくなるが、上限があってそれに近づくにつれ増えるスコアが小さくなるということだ。これは$f(q_i, d)$が文章$d$に含まれる単語$q_i$の数ではなくても同じ傾向である(tfやルートを取っても)。
次に簡単のために$１$と仮定した部分$1-b+b\frac{|d|}{avg(dl)}$について考える。これをグラフによって表すと以下のようになる。
xを$\frac{|d|}{avg(dl)}$とした。このグラフから文章の長さが相対的に長ければ長いほど値が大きくなる、パラメーター$b$が大きければ大きいほど違いが顕著に現れることがわかる。これを念頭に置いて最初の取り出した式に代入してみると以下のようなグラフが現れる。
$b=0.75$として、文章の長さが平均の2倍と等倍、半分の条件で出力した。グラフから読み取れることは文章$d$中に出現する単語$q_i$の数(f)が同じでも、文章$d$の単語数が多いとスコアが小さくなり、少ないと大きくなることである。文章$d$の単語数が多ければそこに単語$q_i$が含まれる期待値が大きいことは直感的にもわかる、文章$d$の長さによる影響を小さくするために、$1-b+b\frac{|d|}{avg(dl)}$を罰則項として実装している。
まとめ
まとめると式
$$
score(q, d) = \sum_i idf(q_i)\times\frac{(k_1+1)f(q_i, d)}{f(q_i, d)+k_1(1-b+b\frac{|d|}{avg(dl)})}
$$
は検索クエリ$q$と文章$d$のスコアを表していて、検索クエリを分解した単語$q_i$のスコアの和によって求められる。単語$q_i$のスコアは文章$d$中の単語$q_i$の数と、文章$d$の相対的な長さによって決まる値であり、それぞれ単語$q_i$のidfで重み付けしてある。振る舞いとしては、文章$d$中に単語$q_i$が含まれるほどスコアは大きくなり、文章が長いほど小さくなる。また、全文章$D$に多く出現する単語は小さくなる。