確率的情報検索について

概要

情報検索の分野でBüttcher本と呼ばれるInformation Retrieval: Implementing and Evaluating Search Engines*1という本がある。確率的な情報検索モデルについて知りたくなったためこの本の8章と9章を読んだのだが、これが想像以上に素晴らしかったのでScrapboxのメモを編集しながら久々にブログを書くことにした。

内容的にはProbability Ranking Principleと呼ばれる原理から始まり(TF)IDF, BM25, 適合性フィードバック, クエリ拡張(Query Expansion)へと綺麗に繋がっていく。この分野は歴史があってやや強引な仮定も所々あるのだけど、その論理の展開が工学的な視点という意味で現代でもとても参考になる。以下その詳細と最後に感想を述べておく。

確率ランキング原理について

Probability Ranking Principle

（クエリに対して）関連度が高い文書をランキング(降順)で返すことがユーザの満足度を最も高めることに繋がるというもの

この原理に従って議論を進めていく。まず問題となるのは、あるクエリに対して対象の文書がどのくらい関連しているかをどのように確率で示すかということである。

この問題を解くため準備も兼ねて以下を考える。

準備

文書とクエリを表す確率変数として $D, Q$ , 関連度を示す2値を取る確率変数として $R$ を導入して $p(R=1|D=d,Q=q)$ を考える。
以下 $D=d,Q=q$ を $DとQ$ として、 $R=1$ を $r, R=0$ を $\bar{r}$ で簡約する。

ベイズの定理を使うと

$\displaystyle p(r|D,Q)= \frac{p(D,Q|r)p(r)}{p(D,Q)}$ , $\displaystyle p(\bar{r}|D,Q)= \frac{p(D,Q|\bar{r})p(\bar{r})}{p(D,Q)}$

とできる。ここで $logit(p)=\log(\frac{p}{1-p})$ を導入する。

ここがまず一つ目のポイントだろう。 $logit$ は順序を維持した写像(Rank-equivalent transformations)なので以下はこの値を考える。

ある文書とクエリが与えられたときの $r$ と $\bar{r}$ の $logit$ は、 $p(\bar{r}|D,Q) = 1 - p(r|D,Q)$ とすると

$\displaystyle \log{\frac{p(r|D,Q)}{p(\bar{r}|D,Q)}} = \log{ \frac{p(D,Q|r)p(r)}{p(D,Q|\bar{r})p(\bar{r})}}$

となり、ここで $p(D,Q|r) = p(D|Q,r)p(Q|r)$ とできるから、さらに式変形すると

$\displaystyle \log{\frac{p(r|D,Q)}{p(\bar{r}|D,Q)}} = \log{\frac{p(D|Q,r)p(Q|r)p(r)}{p(D|Q,\bar{r})p(Q|\bar{r})p(\bar{r})}} = \log{\frac{p(D|Q,r)p(r|Q)}{p(D|Q,\bar{r})p(\bar{r}|Q)}}$

で表せる。展開すると

$\displaystyle \log{\frac{p(D|Q,r)}{p(D|Q,\bar{r})}} + \log{\frac{p(r|Q)}{p(\bar{r}|Q)}}$

になるが、第二項目の値は文書Dに関連しないので無視できる。

以上からPRPの元では各文書に対して

$\displaystyle \log{\frac{p(D|Q,r)}{p(D|Q,\bar{r})}}$ ...(1)

この値を求めてランキングにして並べればよいことになった!

$p(D|Q,r)$ のまま考えるのでなくlogitにすることで考えやすくなるというのは参考になる。

Binary Independence Modelの導出

ここで文書Dの再定義を行う。 $D = (D_1, D_2..)$ というベクトルで表現し、各要素は語彙となる単語が出現したら1, そうでないときに0をとる確率変数とする。

文書Dは構成する単語で表現できると考えている

ここで強い仮定が2つ出てくる。

仮定1

Assuption T: Given relevance, terms are statically independent.

文書に出現する単語(term)は互いに独立しているというもの。BoWでお馴染み。
この仮定により(1)は簡単になる。

さてこの仮定のもとで(1)の $p(D|Q,r)$ は

$\displaystyle p(D|Q,r) = \prod_{i=1}^{|V|}p(D_i|Q,r)$

となり、同様に $\bar{r}$ も同じ処理をできるので結局

$\displaystyle \log{\frac{p(D|Q,r)}{p(D|Q,\bar{r})}} = \sum_{i=1}^{|V|} \log{\frac{p(D_i|Q,r)}{p(D_i|Q,\bar{r})}}$

となる。だいぶ簡単になってきた。

仮定2

Assuption Q: The presence of a term in a document depends on relevance only when that term is present in the query.

ユーザのニーズと関連文書を紐づけるのはクエリのみである
要はクエリに対応した単語によって関連性が決められるということ

この仮定を取り入れることで先ほどの式を計算することがかなり容易くなる。全ての語彙に対して計算するのでなく、クエリの単語だけを対象に計算すれば良くなったため。

具体的にクエリQをみると $Q = q_i$ が $q_i=0$ となる場合は上記の仮定で考慮しなくて済むわけだから、その場合は $\log{\frac{p(D_i|Q,r)}{p(D_i|Q,\bar{r})}} = 0$ でよい。

結局Queryとして出現しているtermだけが対象になるので $q_i=1$ を簡略して

$\displaystyle \sum_{t \in q}^{} \log{\frac{p(D_t|r)}{p(D_t|\bar{r})}}$

と書ける。

次に文書Dについて個別にみていくと、文書の中にはクエリとなるtermを含まないものもあるので

$\displaystyle \sum_{t \in q}^{} \log{\frac{p(D_t=d_t|r)}{p(D_t=d_t|\bar{r})}} - \sum_{t \in q}^{} \log{\frac{p(D_t=0|r)}{p(D_t=0|\bar{r})}}$

としたい。そして第二項は仮定2から定数とみなせる(関連性はクエリから決定されるので)

ここでクエリを含む文書とそうでない文書で分けて考える。なおかつ第二項目を0にするために両方の項に工夫を加えると。。

$\displaystyle \sum_{t \in (q \cap d)}^{} \log{\frac{p(D_t=1|r)p(D_t=0|\bar{r})}{p(D_t=1|\bar{r})p(D_t=0|r)}} - \sum_{t \in q \backslash d}^{} \log{\frac{p(D_t=0|r)p(D_t=0|\bar{r})}{p(D_t=0|\bar{r})p(D_t=0|r)}}$

となり第二項は0なので結局

$\displaystyle \sum_{t \in (q \cap d)}^{} \log{\frac{p(D_t=1|r)p(D_t=0|\bar{r})}{p(D_t=1|\bar{r})p(D_t=0|r)}}$ ...(2)

となる！これがBinary Independet Modelとして知られるモデルである。

IDFが導かれるまで

(2)を $\sum_{t \in (q \cap d)}^{} w_t$ とおいて、 $p(D_t=1|r)$ を $p_t, p(D_t=1|\bar{r})$ を $\bar{p_t}$ と置くと

$\displaystyle w_t = \log{\frac{p_t(1-\bar{p_t})}{\bar{p_t}(1-p_t)}} (= \log\frac{p_t}{1-p_t} + \log\frac{1-\bar{p_t}}{\bar{p_t}})$

と変形できる。この方程式はRobertson/Sparck Jones formulaと呼ばれる。

ここで全文書の数を $N$ , tを含む文書の数を $N_t$ , 関連文書の数を $N_r$ , 関連文書かつtを含むものを $N_{t,r}$ として、 $p_t, \bar{p_t}$ に最尤推定を使うと

$\displaystyle w_t = log \frac{N_{t,r}}{N_r - N_{t,r}} + \log\frac{N - N_r - N_t + N_{t,r}}{N_t - N_{t,r}}$

が成り立つが、ここで $N$ と $N_t, N_r$ と $N_{t,r}$ の関係を考えると前者は後者に比べてかなり大きい値を取ると想定できる。すなわち

$\displaystyle w_t = logit(p_t) + \log\frac{N-N_t}{N_t}$

とみなしてもよいだろう。

CroftとHarper(1979)は $p_t = \frac{1}{2}$ かつ $N_t$ が $N$ に比べてかなり小さいと仮定できることから $w_t = \log\frac{N}{N_t}$ を導いた。これは標準的なIDFである。

メモ: $p_t$ は $p(D_t=1|r)$ だったわけだから、 $p_t = \frac{1}{2}$ というのは関連文書にクエリが出現する確率は半々ということ。必ずしも関連文書にクエリが出現するわけではないからこれは妥当な仮定とされているが、適合性フィードバックによってこの確率をもっと正確に見積もることはできる。これが適合性フィードバックのベースの一つとなる。

TF(単語頻度)の扱い方

Binary Independence Modelの導出のところまで戻ると文書Dは各単語が2値の確率変数を持つベクトルとして表現されていたのだった。単語の頻度を考慮するために各単語の頻度 $F_t$ を確率変数として $D=(F_1,F_2...)$ というようにさらに再定義する。

Binary Independet Modelの式は

$\displaystyle \sum_{t \in q }^{} \log{\frac{p(F_t=f_t|r)p(D_t=0|\bar{r})}{p(F_t=f_t|\bar{r})p(D_t=0|r)}}$

となる。さて関連文書と非関連文書の単語頻度を確率変数として扱いたいわけだが、どのようなモデルを考えればよいか。

ここで以下のようにElitenessを新しい概念として導入する。

Elitenessの導入

$p(F_t=f_t|r)$ と $p(F_t=f_t|\bar{r})$ を考えたいわけだが、ここでeliteという概念を導入する。

文書があるトピックについて論じているときそれはelitenessを持つと考える
そしてelitenessは単語頻度に影響を与えると考える

すなわち関連文書の単語頻度はelitenessを導入することで、それぞれ別の確率モデルから単語頻度が決まるとみなすことができる。そして単語頻度を決める分布としてポアソン分布を仮定する。

簡易的なTwo-Poisson Model

Two-Poisson Modelの詳細については本書を参考にしてほしいが、RobertsonとWalker(1994)がTwo-Poisson Modelに期待される性質を満たした簡易的な重み付けとして

$\displaystyle \sum_{t \in q }^{} \frac{f_{t,d}(k_1+1)}{k_1+f_{t,d}} w_t$ ...(3)

を提案している。kはパラメータで通常1から2の間の値が用いられ、k=1.2が論文ではよく採用される。

Q. なぜ対数オッズである $w_t$ に重みを掛けて良いの？
Q. ポアソン分布の導入がなぜ最終的に↑の式になるの？
- A. Two-Poisson Modelが直接簡易式になるわけではなく、Two-Poisson Modelが $w_t$ に対して及ぼす影響と同じ性質を持つ式を代わりに取り入れたということ。こういう技もあるんですね。

$f_{t,d}$ は単語の頻度を示すがこれがとても大きくなっても重みは $(k_1 +1)w_t$ に留まる。要は単語頻度が増えるに従い重みがsaturateするような関数となる。

関数の特徴を調べて簡単なもので置き換えるのはなるほどという感じ。

ちなみにBM11の頃の論文だと $\sum_{t \in q }^{} \frac{f_{t,d}}{k_1+f_{t,d}} w_t$ となっていてサチることがわかりやすい。(k+1)の項は定数になるのでランキングに影響は及ぼさないが $f_{t,d}$ の値と対応づけやすいようにするための工夫だそうだ。

以下の論文にこの辺りの事情が書いてある(p.361あたり)

The Probabilistic Relevance Framework: BM25 and Beyond
- http://www.staff.city.ac.uk/~sb317/papers/foundations_bm25_review.pdf

BM25について

前述した(3)は文書の長さを加味していなかった(ポアソン分布を導入したときに全文書は同じ長さだと仮定していた)。
文書の平均長を使って以下のようにスケーリングさせる。

$\displaystyle f'_{t,d} = f_{t,d} * (l_{avg}/l_d)$

しかし長い文書の方が質の高い文書である可能性が高いと想定することもあるだろう。パラメータbを導入してスケーリングの影響度合いを調節できるようにする。

(3)と上記をまとめると以下の重み付けの式が導出できる。

$\displaystyle \sum_{t \in q }^{} \frac{f_{t,d}(k_1+1)}{k_1 ( (1-b) + b(l_{avg}/l_d) )+f_{t,d}} w_t$

これはBM25として知られている。パラメータとなるbは0.75がよく使われるらしい。

$(l_{avg}/l_d)$ がbにかかっているのは $f_{t,d}$ に元々かかっていたものが約分されてるから。

適合性フィードバックによる拡張

最後に確率的検索モデルが適合性フィードバックについてどのように方針と理論的土台を与えるかを簡単にメモ。

これまで検索モデルは以下の2点で改善の余地がある

(2)式での $p_t$ に対する見積もり
ユーザが潜在的に想定しているクエリの追加(Query Expansion)
- Assuption Qによって適切なクエリ拡張は関連性に対して良い影響を及ぼすだろう

Term Selectionによる明示的な適合性フィードバックも解説されているが、擬似的な適合性フィードバック(Pseudo-Relevance Feedback)についての記述が秀逸だったのでメモする。

擬似的な適合性フィードバック(Pseudo-Relevance Feedback)について

適合性フィードバックはユーザによる明示的なインタラクションを必要とするが、ユーザはこのような作業を好まないとされている。
Pseudo-Relevance Feedbackは、上位k(=20)件の文書を関連文書と仮定しm(=10)個程度の特徴語を抽出し、元々のクエリに追加するというものである。

ポイントになるのは以下の考え。

k=20とすると擬似的適合性フィードバックの仮定から $n_{r} = 20$ とできるから、各単語の $n_{t,r}$ をカウントすることで $p_t$ を推定することができる。さらに $N, N_t$ はわかっているわけだから、Robertson/Sparck Jones formulaがこの手法で拡張できることがわかる!

具体的には拡張するクエリ(元々のクエリも含む)の $p_t$ を求められることと、ユーザの入力したクエリを関連文書の単語で拡張できる。なお拡張クエリの重みは1/3程度にすると実証的に良いようだ。

Pseudo-Relevance Feedbackは再現率と精度に良い影響を与えることが知られており、本書ではBM25にPRFを組み合わせた形式が有効であることが示されていた。

感想など

冒頭で述べたように仮定や導入しているモデルにナイーブさがあるが、どうしてもヒューマンファクターが絡みがちな情報検索という分野に確率的な視点を導入することで、不確かさについての議論がしやすくなる点は評価したい。個人的にIIR本よりも例が豊富で記述もわかりやすいので好み(といってもIIR本は日本語訳版しか読んだことはないんだけど)。

あとメモを書き上げてから他のひとが同じ章の記事を書いてる*2ことに気づきました。自分のメモと見比べてみると視点の違いとかが垣間みえて面白いですね。

*1:http://www.ir.uwaterloo.ca/book/

*2:https://sleepy-yoshi.hatenablog.com/entry/20120504/p1