stop-the-world

takuya-a のブログ

Information Retrieval and Web Search まとめ(12): 確率的情報検索(1) 確率ランキング原理とバイナリ独立モデル

前回は、TF-IDF とコサイン類似度による文書のスコアリングについて解説した。今回からは確率的モデルを取り入れた情報検索である、確率論的情報検索について紹介する。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の12日目の記事です。

adventar.org

確率的情報検索の必要性

  • ランク付き検索において、通常のブーリアン検索 (クエリを AND, OR, NOT で組み立てる検索) には、検索結果がしばしば非常に少なくなる（= 0）か、非常に多くなる（> 1000）という問題があった
    • 前回は、各文書とクエリ間の類似度を計算してランク付けする（一種の "soft AND"）という解決策を示した
  • しかし、ユーザが入力したクエリ表現も、それと文書との適合性も、いずれも不確かなものである
    • 古典的な情報検索システムでは、タームを使ってクエリと各文書とをマッチさせているが、それらの適合性は不正確な予測によるものである
  • 確率論は、不確かな推論に関する基礎を提供する
    • 上で述べた検索の不正確さを定量化するために確率論を使う

確率ランキング原理

  • 文書のランキングは、現代的な情報検索システムのコアである
  • 確率論的情報検索のアイデア：情報ニーズを考慮した適合確率によって文書をランキングする
    • p\left(R=1 \mid d,q \right)
      • クエリ q に対して文書 d が適合している確率
      • R は、文書がクエリに適合しているかどうかを示す確率変数
      • まずは確率変数 R が 1/0 の2値のどちらかをとる場合について考える
  • 確率論的情報検索は、以下の 確率ランキング原理 (probability ranking principle; PRP) を出発点にしている

If a reference retrieval system’s response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data.

[1960s/1970s] S. Robertson, W.S. Cooper, M.E. Maron; van Rijsbergen (1979:113); Manning & Schütze (1999:538)

  • 「検索システムが、ユーザのリクエストに対して、データに基づいて文書の適合度の確率を可能な限り正確に推定し、その確率の降順で文書をランキングするなら、システム全体の有効性は、これらのデータに基づいて得られる最高のものとなるだろう」

確率的情報検索の戦略

  • 各タームが適合度にどのくらい寄与するかを推定
    • 他の要素、例えばターム頻度 (TF) や文書長は文書の適合性にどのくらい影響するか？
      • BIM（後述）ではまったく関係ない
      • BM25 （後述）で議論
  • 文書の適合確率を結合（？）
  • 適合確率の降順で並べ替え
  • 「1/0 の損失のもとで損失（ベイズリスク）を最小化するには、確率的ランキング定理 (PRP) を使用するのが最適」という定理がある [Ripley 1996]

バイナリ独立モデル

  • バイナリ独立モデル (Binary Independence Model; BIM) は、古典的に PRP と併用されているモデル
  • バイナリ (binary) = ブーリアン (bolean)
    • 文書はタームの2値生起ベクトル (binary incidence vector) として表現される (参考：IIR chapter 1):
    • \vec{x} = (x_1,...,x_M)
    • x_i = 1 iff ターム i が文書 x に存在するとき
  • 独立 (independence)
    • タームは文書中に独立に生起する
  • 異なる文書でも同じベクトルとして表現されることがある
  • クエリも2値生起ベクトルとして表現する
  • 与えられたクエリ q に対して、各文書 d に対して p\left(R \mid d,q \right) を計算したい
    • d を2値生起ベクトルで表現した x で d を置き換えた p\left(R \mid x,q \right) の計算で代替する
      • ランキングのみに興味がある
  • ベイズの定理を使えば、 p\left(R=1 \mid x,q \right) は以下のように変形できる
    • p\left(R=1 \mid q \right) は、クエリ q に対して適合している文書の事前確率
    • p\left( x \mid R=1, q \right) は、クエリ q に対する適合文書が取得されたときに、それが x である確率
 p\left(R=1 \mid x,q \right) = \dfrac{ p\left( x \mid R=1, q \right) p\left( R=1 \mid q \right) }{ p\left( x \mid q \right)}
  • 文書が適合しているオッズ (odds) は以下の通り 
\begin{eqnarray}
O\left(R \mid q,x \right)

&=&
\dfrac{
  p\left(R=1 \mid x,q \right)
}{
  p\left(R=0 \mid x,q \right)
} \\

&=&
\dfrac{
  \frac{
    p\left(R=1 \mid q \right) p\left(x \mid R=1, q \right)
  }{
    p\left( x \mid q \right)
  }
}{
  \frac{
    p\left(R=0 \mid q \right) p\left(x \mid R=0, q \right)
  }{
    p\left( x \mid q \right)
  }
} \\

&=&
\dfrac{
  p\left(R=1 \mid q \right)
}{
  p\left(R=0 \mid q \right)
}
\cdot
\dfrac{
  p\left(x \mid R=1, q \right)
}{
  p\left(x \mid R=0, q \right)
}
\end{eqnarray}
  • 最後の式の左の項は、与えられたクエリ q に対しては定数になる
    • いまはランキングにのみ興味があるので、推定しなくてよい（計算しない）
  • 右の項は推定しなければならないが、難しい
    • そこで、上述した独立性の仮定を使う
  • 最終的に以下の形になる（途中の計算は省略: IIR pp.224-225 を参照）
    • p_i = p \left( x_i = 1 \mid R=1, q \right)
    • r_i = p \left( x_i = 1 \mid R=0, q \right)
    • i はタームのインデックス

O\left(R \mid x,q \right) =

O\left(R \mid q \right)
\cdot
\displaystyle\prod_{x_i = q_i = 1}
  \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) }
\cdot
\displaystyle\prod_{q_i = 1}
  \frac{ 1 - p_i }{ 1 - r_i }
  • 第1項と第3項はクエリに対しては定数になる
    • ランキングのためには第2項のみを推定すればよい
  • この第2項の対数をとったものを Retrieval Status Value (RSV) と呼ぶ
\begin{eqnarray}
RSV

&=&
\log \displaystyle\prod_{x_i = q_i = 1}
  \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) }

=
\displaystyle\sum_{x_i = q_i = 1}
  \log \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) } \\

&=&
\displaystyle\sum_{x_i = q_i = 1} c_i; \;
c_i = \log \frac{ p_i \left( 1 - r_i \right) }{ r_i \left( 1 - p_i \right) }
\end{eqnarray}
  • \sum の中身を c_i と置いた

講義資料

参考資料