現代版 TF-IDF である Okapi BM25 の原理について(前半)

Okapi BM25 とは?

Okapi BM25 はオープンソースの検索エンジンとして有名な Elasticsearch やそのエンジンである Apache Lucene で採用されている検索のランキングアルゴリズムです。

ランキング手法としては TF-IDF が有名ですが、BM25 は TF-IDF を改良した物と言えます。また一方で、BM25 は確率論をベースとしたモデルを採用した手法でもあります。多くの検索エンジンでデフォルトのランキングアルゴリズムとして採用されており、BM25 は「現代版 TF-IDF」と言えると思います。

BM25 は以下を主要なアイデアとして採用した手法になります。この記事では二回にわたってこれらを解説していきます。

• 条件付き確率を基礎としたスコアリング
• ロバートソン/スパルクジョーンズ重み付け関数 (IDF に相当)
• Binary Independence Model (BIM)
• Eliteness
• 長さの考慮

なお、この記事は基本的には「情報検索 :検索エンジンの実装と評価」(通称ブッチャー本)の8章の内容を中心に整理(あるいは再解釈)し直した物です。検索に関して非常に充実しているので、興味のある方は購入する事をお勧めします^[1]。

https://www.amazon.co.jp/dp/4627817614/ref=cm_sw_em_r_mt_dp_TWZ2508883X5AGH3D5QV

また、BM25 とそのベースとなる情報検索の確率モデルを作り上げた人達の一人であるステファン・ロバートソン氏による記事も見る事ができます^[2]。こちらも BM25 について詳細に書かれてあります。

検索における課題

解説を始める前に、まずは検索における課題について整理します。

そもそも非常にシンプルなケースに絞れば BM25 や TF-IDF といったランキング手法は不要です。例えば、「検索は1単語しか入れられない、検索対象も長さが一定の俳句」といった場合、単語が出現しているかどうかだけで判断できます(逆にいうと区別しようがない)。

しかし多くの場合は検索単語は複数ですし、ドキュメントの長さも様々です。こういった部分の考慮をしていくと、課題が出てきます。

課題1: 単語の重み

• 「a b」で検索した時、「a だけが出てきた」ドキュメントと「b だけが出てきた」ドキュメントはどちらがより関連しているのか?

課題2: 複数単語でマッチした場合の重み

• 「a b c」で検索した時、「a だけが出てきた」ドキュメントと「b と c だけが出てきた」ドキュメントはどちらがより関連しているのか?

課題3: 出現頻度の考慮

• 「a が 2 回」と「b が 3 回」はどちらの方が関連しているか?

課題4: ドキュメントの長さが色々ある

• 「a の出現数が 2 倍、文章の長さが 4 倍」の場合はより関連していると言えるのか?

その他にもいくつか課題があります。

課題5: キーワードがドキュメントに直接的に現れない

• 「a が主要なテーマだからこそ直接的な明言がされてない」場合がある

課題6: クエリにはない要求がある

• 人気のドキュメントを優先したい場合がある

確率モデルによるスコアリング

上記の課題に関しては、それぞれに対してはヒューリスティックスで優先順位を調整する事が可能です。

• レアな単語が出現したドキュメントを優先する(IDF の考え)
• 単語の出現回数が多いドキュメントを優先する(TF の考え)
• アクセス数の多いドキュメントを優先する

しかしこれらのヒューリスティックスを組み合わせようと思った時に、「ある特性で見た場合はドキュメント A が優れているが、別の面で見た場合はドキュメント B が優れている」といったトレードオフに対応する必要が出てきます。検索システムは「志村けんとカルロスゴーンはどっちがすごいか」みたいな問題に答えなければいけません。

こういった問題に対して無理矢理でも点数をつけて比較するのが TF-IDF のようなスコアリングになります。

確率モデル

スコアリングにより複数の特性を組み合わせて比較する事ができるようになります。しかし今度はスコアの付け方が問題になってきます。

• TF や IDF はログを取ったものを使うべきか
• TF-IDF にドキュメントのアクセス数を組み合わせたい場合、アクセス数を足せばいいのか。掛けていいのか

こういった特性の組み合わせを確率論の枠組みに落とし込んで推定するのが BM25 のアプローチです。スコアを求めたいドキュメントから特性 $d$ を抽出し、それと同じ特性をもつドキュメントがユーザーの検索要求を満たしている(条件付き)確率を求めるというのが出発点になります。

 

$$\LARGE{score(d) = p(r | D=d)}$$

 

$D=d$ および $r$ は以下の通りです。

• 事象 $D=d$ … ランダムで取り出したドキュメントの特性 $D$ が $d$ である
• 事象 $r$ … ランダムで取り出したドキュメントがユーザーの要求を満たす

現時点では $d$ の決め方はなんでもありです。「単語 a を含む」でもいいですし、「単語 b を 2 回含み、長さが1000文字以上」とかでも良いです。

スコア

確率と言ってもこれだけでは計算のしようがないです。そこで幾つかの前提を加えます。

まず、特性 $d$ は特徴量のベクトルとして表現します。最終的には BM25 はドキュメントを「単語→出現回数」のベクトル^[3]として扱いますが、初期は必ずしもそうではないので「ベクトルである」という事だけ前提に入れておくと良いです。

また、スコアとして以下を使います。

 

$$\LARGE{score(d) = logit(p(r | D=d)) - logit(p(r | D=\bold{0}))}$$

 

$logit(p) = log(\dfrac{p}{1 - p})$ は確率 p の「ロジット」と呼ばれ、ロジスティック回帰などの他の確率分野でも活用されます。

https://ja.wikipedia.org/wiki/ロジット

$logit(p(r | D=\bold{0}))$ は特徴量が全くないドキュメント(ゼロベクトル)に対するロジットに相当します。

また、このスコアの式は「対数オッズ比」と呼ばれており、以下の特徴があります。

• $p(r | D=d)$ が高ければ高いほど高い値になる。従ってスコアが高い = 正解の可能性が高い
• $D=\bold{0}$ の場合、スコアは 0 になる

オッズ比

ここで、オッズ比について補足します。

オッズ比は二つのグループの性能比較に使われます。今回のスコアの例で言えば、特性 $d$ と特性 $\bold{0}$ で、$r$ の条件付き確率を比較しています。オッズ比は $r$ だけではなく、$r$ の否定 $\overline{r}$ の条件付き確率も組み合わせて使います。

	$D=d$	$D=\bold{0}$
$r$	$\color{limegreen}p(r | D=d)$	$\color{red}p(r | D=\bold{0})$
$\overline{r}$	$\color{red}p(\overline{r} | D=d)$	$\color{limegreen}p(\overline{r} | D=\bold{0})$

この表の緑の部分に該当するドキュメント数を掛け、赤の部分に該当するドキュメントで割った値がオッズ比になります。

対数オッズ比はこれに log をとったものになります。

一方で、オッズ比は二つのグループの相関にも使われます。ドキュメントをある特性 $t$ のあり/なしのグループに分けると、以下のような表になります。

	$t$	$\overline{t}$
$r$	$\color{limegreen}p(r,t)$	$\color{red}p(r,\overline{t})$
$\overline{r}$	$\color{red}p(\overline{r},t)$	$\color{limegreen}p(\overline{r},\overline{t})$

この場合、「$t$ かつ $r$」および「$\overline{t}$ かつ $\overline{r}$」が、「$t$ かつ $\overline{r}$」および「$\overline{t}$ かつ $r$」より相対的に高いほどオッズ比は高くなります。

最後に、条件付き確率とオッズ比に関する式変形について補足します。事象 $a$ $b$ があった時、対数オッズ比はベイズの定理を使って以下のように式変形できます。

$$\begin{align*} \LARGE{logit}&\LARGE{(p(r | a)) - logit(p(r | b))}\\ &\LARGE{= log(\frac {\color{limegreen} p(a|r)p(b|\overline{r}) }{\color{red} p(b|r)p(a|\overline{r}) }) }\\ &\LARGE{= log(\frac {\color{limegreen} p(a,r)p(b,\overline{r}) }{\color{red} p(b,r)p(a,\overline{r}) }) } \end{align*}$$

証明

それぞれの項に対してベイズの定理を実行します。最初の logit は以下のように変形されます。

$$\begin{align*} logit(p(r | a)) &= log(p(r | a) / p(\overline{r} | a)) \\ &= log( \dfrac{p(a | r) p(r)}{\color{red} p(a)} / \dfrac{p(a | \overline{r})p(\overline{r})}{\color{red} p(a)} ) \\ &= log(\dfrac{p(a | r)p(r)}{p(a | \overline{r})p(\overline{r})})\\ \end{align*}$$

第二項も同様に変形して、対数オッズ比を式変形します。

$$\begin{align*} log(\dfrac{p(a | r)p(r)}{p(a | \overline{r})p(\overline{r})}) - log(\dfrac{p(b | r)p(r)}{p(b | \overline{r})p(\overline{r})}) &= log(\dfrac{ p(a | r) {\color{red} p(r)} p(b | \overline{r}) {\color{red} p(\overline{r})} }{ p(a | \overline{r}) {\color{red} p(\overline{r})} p(b | r) {\color{red} p(r)} })\\ &= log(\dfrac{p(a | r)p(b | \overline{r})}{p(a | \overline{r})p(b | r)})\\ \end{align*}$$

また、ベイズの定理を使う代わりに条件付き確率の定義をそのまま使うと、以下のような変形ができます。

$$\begin{align*} logit(p(r | a)) &= log(p(r | a) / p(\overline{r} | a)) \\ &= log(\dfrac{p(a,r)}{\color{red} p(a)} / \dfrac{p(a,\overline{r})}{\color{red} p(a)})\\ &= log(\dfrac{p(a,r)}{p(a,\overline{r})})\\ \end{align*}$$

$$\begin{align*} log(\dfrac{p(a,r)}{p(a,\overline{r})}) - log(\dfrac{p(b,r)}{p(b,\overline{r})}) = log(\dfrac{ p(a,r) p(b,\overline{r}) }{ p(a,\overline{r}) p(b,r) }) \end{align*}$$

この式変形は後で使用します。

ロバートソン/スパルクジョーンズ重み付け関数

この上で、最初に出てきた課題 1 を考えてみましょう。「a b」で検索した時、「a だけが出てきた」ドキュメントと「b だけが出てきた」ドキュメントはどちらがより正解に近いと言えるのでしょうか?

この問題は、ドキュメントに単語 t が出現した場合のスコアを求めれば解決できます。「t が出現した」事象を $t$ とすると、スコアは t に関する式 $w_t$ になります。

$$score(d) = w_t = logit(p(r | t)) - logit(p(r | \overline{t}))$$

この $w_t$ を式変形すると、以下のようになります。

 

$$\LARGE{\begin{align*} w_t &= log(\dfrac {\color{limegreen} p(t | r)p(\overline{t} | \overline{r})} {\color{red} p(t | \overline{r})p(\overline{t} | r)} )\\ &= log(\dfrac {\color{limegreen} p(t,r)p(\overline{t},\overline{r})} {\color{red} p(t,\overline{r})p(\overline{t},r)} )\\ &= logit(p(t | r)) - logit(p(t | \overline{r})) \end{align*}}$$

 

この $w_t$ は ロバートソン/スパルクジョーンズ重み付け関数と呼ばれます。1行目と2行目は先ほどの対数オッズ比の式変形を活用した式になります。また、3行目のように logit を使った形式にも式変形できます。

$w_t$ は t の出現と正解/不正解との相関を表す関数とも言えます。

例

例を挙げてみます。

	$a$	$\overline{a}$
$r$	$\color{limegreen}5$	$\color{red}10$
$\overline{r}$	$\color{red}5$	$\color{limegreen}980$

	$b$	$\overline{b}$
$r$	$\color{limegreen}10$	$\color{red}200$
$\overline{r}$	$\color{red}10$	$\color{limegreen}780$

今回の場合、a が含むドキュメントも b を含むドキュメントも不正解のドキュメントが半々くらい混じっています。一方で a を含まないドキュメントはほとんど不正解ですが、b を含んでなくても正解のドキュメントがそこそこあるようです。

これに対して $w_t$ を計算します。 $w_t$ は以下のようになります。

$$\begin{align*} w_a &= log(\dfrac{\color{limegreen}5・980}{\color{red}5・10}) = log(98) ≒ 4.58\\ w_b &= log(\dfrac{\color{limegreen}10・780}{\color{red}10・200}) = log(3.9) ≒ 1.36 \end{align*}$$

今回の場合、a の方が高スコアになります。

IDF

さて、現実としては正解のドキュメントが何であるかはユーザーに聞かないとわかりません。そのため、$r$ と $\overline{r}$ がわからない前提で $w_t$ を計算する必要があります。そんな事ができるのでしょうか?

多くの検索システムでは、こういった場合は「レアな(つまりIDFが高い)単語がマッチしたドキュメントの方がスコアが高い」というヒューリスティックスを使います。例えば「サザエさん 苗字」で検索した場合、「サザエさん」だけに関連するドキュメントの方が「苗字」に関連するドキュメントよりも正解である可能性が高いと考えるわけです。

このヒューリスティックスを $w_t$ に当てはめましょう。参考のためここで一度上の表を見てみます。なんとなく以下の傾向がある事がわかります。

1. $r$ のドキュメントは全体からすると少ない
2. t を含むドキュメントは全体からすると少ない
3. $r$ の段の二つの比は、$\overline{r}$ の段の二つの比と比べてとても小さい

ドキュメントが少なかったり絞り込む需要がないのでなければ検索機能を使う必要もないので、1. は妥当だと思われます。また 2. は結構苦しい理屈になりますが、適切に絞り込むためにユーザーがキーワードを考えるので、ドキュメント数は全体と比べて少ないようには見えます。

3. はどうでしょう? あまり根拠がないように思われますが、一旦これを前提に考えてみます。

表にしてみると以下のようになります。この時事象 $a$ を満たすドキュメント数として $n_a$ という式を取り入れます。全てのドキュメントの数を $N$ とします。

	$t$	$\overline{t}$	合計
$r$	$\color{limegreen}n_{r,t}$	$\color{red}n_{r,\overline{t}}$	$n_r$
$\overline{r}$	$\color{red}n_{\overline{r},t}$	$\color{limegreen}n_{\overline{r},\overline{t}}$	$N-n_r$
	$n_t$	$N - n_t$	$N$

この場合の $w_t$ を考えます。

$$w_t = log( \frac{n_{r,t}}{n_{\overline{r},t}} \frac{n_{\overline{r},\overline{t}}}{n_{r,\overline{t}}} )$$

ここで、3. を前提とすると、 $n_{r,t}$ と $n_{r,\overline{t}}$ の比は無視できます。一方で 1. が前提にあると、

$$\begin{align*} n_{\overline{r},t} &\fallingdotseq n_t\\ n_{\overline{r},\overline{t}} &\fallingdotseq n_{\overline{t}} = N - n_t \end{align*}$$

と近似できます。その上で $w_t$ を考えると、

$$w_t ≒ log( \frac{n_{\overline{r},\overline{t}}}{n_{\overline{r},t}} ) ≒ log(\dfrac{N - n_t}{n_t})$$

となります。さらに 2. を前提とすると、$log(N/n_t)$ が得られます。これは一般的な IDF と同じものです。

 

$$\LARGE{w_t = log(\dfrac{N}{n_t}) = IDF}$$

 

若干強引ではあるものの、これで IDF と確率論が結び付けられました。正解のドキュメントに関する統計情報が得られない場合、多くの場合 $w_t$ としてこの IDF 値が使われます。

$w_t$ として IDF を使う事に関しては ^[4] で考察されています。

Binary Independence Model

今度は課題 2 について考えてみます。複数単語にマッチした場合はスコアはどうなるでしょう。それに対する答えが Binary Independence Model (BIM) です。

BIM は以下の前提としたモデルです。

1. ドキュメントは「ある/なし」の二値(binary)の特徴量をもつベクトルである
2. 各特徴量の間に相関はなく、(条件付き)独立(independent)である
3. クエリに出現しない単語の特徴量は無視できる

全てのドキュメントに含むあらゆる単語に1からIDを振ったとして、ドキュメントの特徴ベクトル $d$ は $(d_1,d_2,…)$ という要素を持つベクトルであると考えられます。例えば、

レモン一個に含まれるビタミンCはレモン一個分

だと、「レモン」「一個」「に」「含まれる」「ビタミンC」「は」「分」を含むので、これらの単語のID番目の要素には1、それ以外の要素には0が入る事になります。

さて、この場合のスコアを考えましょう。前述の対数オッズ比の式変形を行うと、以下の式になります。

$$\begin{align*} score(d) &= logit(p(r | D=d)) - logit(p(r | D=\bold{0}))\\ &= log(\dfrac{ p(D=d | r) p(D=\bold{0} | \overline{r}) }{ p(D=d | \overline{r}) p(D=\bold{0} | r) })\\ \end{align*}$$

ここで、$d$ は二値のベクトルであるという仮定 1. と、各特徴量は独立^[5]であるという仮定 2. を思い出します。$d_i$ を $d$ の $i$ 番目の要素、$D_i$ を $D$ の $i$ 番目の要素だとすると、

$$\begin{align*} score(d) &=log(\dfrac{ p(D=(d_1,d_2,…) | r) p(D=(0,0,…) | \overline{r}) }{ p(D=(d_1,d_2,…) | \overline{r}) p(D=(0,0,…) | r) })\\ &=log(\dfrac{ p(D_1=d_1 | r)p(D_2=d_2 | r)… p(D_1=0 | \overline{r})p(D_2=0 | \overline{r})… }{ p(D_1=d_1 | \overline{r})p(D_2=d_2 | \overline{r})… p(D_1=0 | r)p(D_2=0 | r)… })\\ &=log(\prod_i \dfrac{ p(D_i=d_i | r)p(D_i=0 | \overline{r}) }{ p(D_i=d_i | \overline{r})p(D_i=0 | r) })\\ &=\sum_i log(\dfrac{ p(D_i=d_i | r)p(D_i=0 | \overline{r}) }{ p(D_i=d_i | \overline{r})p(D_i=0 | r) })\\ \end{align*}$$

となります。この総和の要素は、$d_i = 1$ の場合ロバートソン/スパルクジョーンズ重み付け関数そのものです。$d_i = 0$ の場合 1 になります。つまり、BIM を前提とした場合のスコアは以下のようになります。

$$score(d) = \sum_{i ∈ d} w_i$$

最後に、クエリに存在しない単語の特徴量は無視できるという仮定 3. を考えます。クエリを $q$ とすると、BIM を前提としたスコアは以下になります。

 

$$\LARGE{score(d) = \sum_{i ∈ q \cap d} w_i}$$

まとめ

まとめると、BIM を前提とした時のスコアは以下のようにすれば良い事になります。

1. 各特徴量の重み $w_t$ を合計したものをスコアとすれば良い
2. 特徴量 t の重みは「tあり/なし」を比較した正解率の対数オッズ比を使う
3. 対数オッズ比がわからない場合は推測する。一般的には IDF を使う

後半は出現回数の考慮など、残りの課題に対して BM25 が行っている手法の解説をしていきます。

脚注

1. 専門書らしく、一般的なエンジニア向け技術書と比べると激高ですが。

2. The Probabilistic Relevance Framework: BM25 and Beyond

3. ここでいうベクトルは非常に大きな次元のベクトルを指します。連想配列といった方がイメージしやすいかもしれないです。

4. On relevance weights with little relevance information

5. これは厳密には単純な独立ではなく、条件付き独立と呼ばれるものです。条件付き独立である事に関しては、スコアの関数をシンプルにするためとの事です。詳細は脚注2のドキュメントに書かれてあります。