読者です 読者をやめる 読者になる 読者になる

sonickun.log

備忘録

確率的情報検索 Okapi BM25 についてまとめた

 ひょんなことで情報検索の知識が必要になったので,勉強したことを簡単にまとめておきます.

 情報検索とは,コンピュータを用いて大量のデータ群から目的に合致した物を取り出すことです.
 Okapi BM25は情報検索における文章中の単語の重み付けの手法の一つであり,他にもTF-IDFと言ったアルゴリズムがあります.

 Okapi BM25 - Wikipedia, the free encyclopedia

 一般的にはTF-IDFよりも良い結果が得られると言われ,比較手法としてのベースラインになっています.
 
 

Term Frequency (TF)

 文書中において出現頻度の高い単語は重要であるという考え方です.
 ある単語Tiの文書Dj中における重みを考えると

TF(i,j) = (文書Djにおける単語Tiの出現回数) / (文書Djのの総単語数)

 となります.
 
 

Inverse Document Frequency (IDF)

 多くの文書において出現頻度の高い単語は重要ではないという考え方です.

n = 単語Tiが出現する文書数
N = 文書の総数
としたとき
IDF(i) = log(N) - log(n) = log(N/n)

 となります.
 ちなみに,TFとIDFをかけ合わせるとTF-IDFの式となり,文書とクエリの特徴ベクトルの内積から類似度を評価することができます.BM25はこのTF-IDFをさらに改良したものとなります.
 
 

Document Length (DL)

 これがDM25のミソとなってきます.
 ある単語の出現回数が同じ2つの文書について,総単語数の少ない文書と多い文書では,前者のほうがより価値があると考えます.

DL(j) = 文書Djの総単語数
としたとき
NDL(j) = DL(j) / (すべての文書の平均DL)

 となります.
 
 

Okapi BM25b (Combined Weight)

 これまでの3つの重み付けをインプットとして,BM25のCombined Weight(CW)を作ります.

CW(i,j) = [ TF(i,j) * IDF(i) * (K1 + 1) ] / [ K1 * (1 - b + (b * NDL(j)) + TF(i,j) ]

 となります.定数K1とbについて以下に説明します.これらはどちらもチューニングの役割を果たします.

 K1は単語の出現頻度による影響を調節します.1 < k1 < 2 で,K1 = 2が最も効果的と言われています.
 bは文書の長さによる影響を調節します.0 < b < 1で,b = 0.75が効果的と言われています.

 まとめると,この式でより大きく重み付けされるのは

  • 文書における単語の出現頻度の高いもの
  • 多くの文書における単語の出現頻度が低いもの
  • より短い文書において出現回数が大きいもの

 となります.