IR本輪読#14
2020/10/27
担当: Sixeight.icon
11 Probabilistic information retrieval
これまでの章では２値モデルやベクトル空間モデルを使って文章の関連度を計算してきた。
この章では文章が情報ニーズにどのくらい関連するかを確率論を使って導く。
11.1 Review of basic probability theory
Chain Rule (連鎖規則)
(11.1) $ P(A, B) = P(A \cap B) = P(A|B)P(B) = P(B|A)P(A)
Partition Rule
(11.3) $ P(B) = P(A,B) + P(\bar{A},B)
Bayes' Rule (ベイズの定理)
(11.4) $ P(A|B) = \frac{P(B|A)P(A)}{P(B)} = \left[ \frac{P(B|A)}{\sum_{X \in \{A,\bar{A}\}}{P(B|X)P(X)}} \right] P(A)
Odds (オッズ)
(11.5) $ O(A) = \frac{P(A)}{P(\bar{A})} = \frac{P(A)}{1-P(A)}
11.2 The Probability Ranking Principle
11.2.1 The 1/0 loss case
順序有りの検索を想定する
$ R_{d,q} はクエリ $ q を与えたときに文章 $ d が適合しているか
$ R_{d,q} = 1 適合している
$ R_{d,q} = 0 適合していない
PRP Probability Ranking Principle
各文章の適合確率を $ P(R=1|d,q) としたとき
この降順で順序付けられた結果を最適とする
全てのパターンの適合確率を知っていればその降順で並べればいい
もっともシンプルな例
各試行に重みを付けない
以下のような失敗を1-0の２値で損失を判定する (1-0損失)
取得できた文章が関連しなかった
関連する文章を取得出来なかった
以下の前提をおき Bayes Optimal Decision Rule によって損失のリスクを最小にする
(11.6) $ d is relevant iff$ P(R=1|d,q) > P(R=0|d,q)
定理 11.1
PRP は1-0損失の下で期待損失（Bayes risk) を最小化するという意味では最適
証明されているが全ての確率を知っている必要があり現実には不可能
IRの確率論モデルを構築する出発点とするには有効
11.2.2 The PRP with retrieval costs
適合確率だったものをコストに入れ替えて考えてみる
(11.7) $ C_0 \cdot P(R=0|d) - C_1 \cdot P(R=1|d) \leq C_0 \cdot P(R=0|d') - C_1 \cdot P(R=1|d')
$ C_0 は適合文書を取得できなかったときのコスト
$ C_1 は非適合文書を取得してしまったときのコスト
$ d は特定のドキュメント
$ d' はまだ取得していない全てのドキュメント
このようなモデルは、偽陽性、偽陰性の差動コスト(？) (differential costs) やパフォーマンスの問題を、評価段階より前にモデル化することができる
この章ではこれ以上は利潤や損失のモデルは扱わない
11.3 The Binary Independence Model
PRPよりも実践的に $ P(R|d,q) を推定するためのシンプルな仮定を置く
Binary (それぞれ2値で表現する)
文章 $ d を $ \vec{x} = (x_1,...,x_M) のようなベクトル $ \vec{x} で表現する
$ x_t=1 単語 $ t が文章 $ d に含まれる
$ x_t = 0 単語 $ t が文章 $ dに含まれない
クエリ $ q も同様のベクトル $ \vec{q} とする
$ q は基本は複数のワードを含むのでこの区別にあまり意味はない
Independence (独立している)
単語の出現は互いの独立していると仮定する
ある文章に「はてな」という単語が出てきて、同じ文章「はてなブックマーク」が出てきても関係ないとみなす
本当は各単語の出現には依存関係があるはずなので現実から乖離している
しかし、実用上はこれでうまくいく
13章で解説される multivariate Bernoulli Naive Bayes と同じになるらしい
その他の仮定
ユーザーは一回の試行のみ行うと仮定する
検索結果からフィードバックを得て情報ニーズを更新しない
各ドキュメントの適合性は互いに独立であるという仮定する
これも本当は正しくない
実用上もシステムが重複した文章を返す場合は特に有害
これらの仮定のもとそれぞれの確率を以下のように定義する
(11.8)
$ P(R=1|\vec{x},\vec{q}) = \frac{P(\vec{x}|R=1,\vec{q})P(R=1|\vec{q})}{P(\vec{x}|\vec{q})}
$ P(R=0|\vec{x},\vec{q}) = \frac{P(\vec{x}|R=0,\vec{q})P(R=0|\vec{q})}{P(\vec{x}|\vec{q})}
どうやってこの確率を推定するのか
全ての確率を知ることはできない
文章コレクションに関する統計情報を利用することができる
全ての文章とクエリに対しては以下が成り立つ
(11.9) $ P(R=1\vec{x},\vec{q})+P(R=1|\vec{x}\vec{q})=1
11.3.1 Deriving a ranking function for query terms
BIMを使って順序ありの場合を考えたい
順序付けられた場合のみ考えたいので直接推定せず別の方法を取る
ここでは適合確率と単調な関すになるオッズを使う
(11.10) $ O(R|\vec{x}\vec{q})=\frac{P(R=1|\vec{x}\vec{q})}{P(R=0|\vec{x}\vec{q})}=\frac{P(R=1|\vec{q})}{P(R=0|\vec{q})}\cdot\frac{P(\vec{x}|R=1,\vec{q})}{P(\vec{x}|R=0,\vec{q})}
(11.5) に (11.8) を代入して分母をはらう
ここで右辺一番右の左の項は定数になっている
Naive Bayes conditional independence assumption を使って全ての単語は独立した事象と仮定すると
(11.12)
$ O(R|\vec{x}\vec{q})=O(R|\vec{q})\cdot\prod_{t=1}^{M}\frac{P(x_t|R=1,\vec{q})}{P(x_t|R=0,\vec{q})}
(11.13) 文章に $ t が出現するかしないかで分離すると以下を得る
$ O(R|\vec{x}\vec{q})=O(R|\vec{q})\cdot\prod_{t:x_t=1}\frac{P(x_t=1|R=1,\vec{q})}{P(x_t=1|R=0,\vec{q})}\cdot\prod_{t:x_t=0}\frac{P(x_t=0|R=1,\vec{q})}{P(x_t=0|R=0,\vec{q})}
ここで以下のように定義する
$ p_t=P(x_t=1|R=1,\vec{q}) (クエリ $ qで適合した文章 $ x_t が単語 $ t を含む確率)
$ u_t=P(x_t=1|R=0,\vec{q}) (クエリ $ qで適合しなかった文章 $ x_t が単語 $ t を含む確率)
(11.14) 表のように整理できる
https://gyazo.com/beac1e058135d9b5892e2b2e4638563c
さらなる仮定を考える
クエリに単語 $ t が含まれない場合は適合確率には影響を与えない
つまり $ q_t = 0 の場合は $ p_t = u_t となる ($ \vec{q} の関数なので)
(11.15)
$ O(R|\vec{q},\vec{x})=O(R|\vec{q})\cdot\prod_{t:x_t=q_t=1}\frac{p_t}{u_t}\cdot\prod_{t:x_t=0,q_t=1}\frac{1-p_t}{1-u_t}
左の総乗はクエリの単語が文章に現れる場合
右の総乗はクエリの単語が文章に現れない場合
(11.16)
$ O(R|\vec{q},\vec{x})=O(R|\vec{q})\cdot\prod_{t:x_t=q_t=1}\frac{p_t(1-u_t)}{u_t(1-p_t)}\cdot\prod_{t:q_t=1}\frac{1-p_t}{1-u_t}
右の総乗に全ての文章を含める
左の総乗からその分を割ってやる
こうすると右の総乗は定数として扱える
全ての文章に関する値なので順序には影響しない
(11.17) Retrieval Status Value (RSV)
$ RSV_d=\log\prod_{t:x_t=q_t=1}\frac{p_t(1-u_t)}{u_t(1-p_t)}=\sum_{t:x_t=q_t=1}\log\frac{p_t(1-u_t)}{u_t(1-p_t)}
単調関数である $ \log を取ってこの値を順序付けに使う
(11.18) 単語の重みの関数
$ c_t=\log\frac{p_t(1-u_t)}{u_t(1-p_t)}=\log\frac{p_t}{1-p_t}+\log\frac{1-u_t}{u_t}
→$ RSV_d=\sum_{x_t=q_t=1}c_t
対数オッズ
この値が0だと適合確率と非適合確率が同じになる
正の数だと適合率が勝る
11.3.2 Probability estimates in theory
(11.19)
https://gyazo.com/57ac4642907d174647a62b8dd35dffc2
文章数を $ N
単語 $ t を含む文章数を $ df_t
適合文章数を $ S
これを使って以下のように置く
$ p_t = s/S
$ u_t = (df_t-s)/(N-S)
(11.20) $ c_t はカーネル関数となり
$ c_t = K(N,df_t,S,s) = \log \frac{s/(S-s)}{(df_t-s)/((N-df_t)-(S-s))}
どこかの辺が0や無限になってしまわないように全ての項に $ \frac{1}{2} を足すと以下のようになる
(11.21)
$ \hat{c_t} = K(N,df_t,S,s) = \log\frac{(s+\frac{1}{2})/(S-s+\frac{1}{2})}{(df_t-s+\frac{1}{2})/(N-df_t-S+s+\frac{1}{2})}
最尤推定 (maximum liklihood estimate / MLE)
今回のような単語の有無を判定するような場合に適合確率を推定する1つの方法
しかし一般的にはデータが少ない時にノイズが多く確率が大きくなりすぎる
平滑化 (smoothing)
今回のように0が混ざるとモデルを壊してしまう場合
試行に現れなかったパターンの確率を上げ、現れたパターンの確率を下げる
簡単な方法は全ての観測した数に $ \alpha を加える
今回は $ \alpha = \frac{1}{2}
ベイズ推定
平滑化で加えた擬似的な数のことを 事前確率 という
今回の場合は一様分布に従っている
Maximum A Posteriori (MAP)
最初に事前確率を想定しておき、あとから実際に観測した事実を加える推定
この辺りは12章でさらに詳しくやる
11.3.3 Probability estimates in practice
ここで関連ドキュメントの数が十分少ないという仮定を置く ($ S = s = 0)
(11.22)
$ c_t = \log \frac{(1-u_t)}{u_t} = \log \frac{(N-df_t)}{df_t} \approx \log \frac{N}{df_t}
これは $ idf に一致する
こういった近似は $ p_t には適用しにくい
$ p_t の推定は以下のような方法が使える
1. 適合文章における$ t_f を使った方法
これは次節で説明する
2. $ p_t を定数としてしまう方法
全ての $ x_t において $ p_t = 0.5 と置く
つまりどの単語でも文章に現れるかは五分五分
結果 $ RSV_d での $ p_t の項は定数となる
$ u_t の近似と同様に $ idf となる
3. 観測から得られた値を使う
定数にするのはひどすぎるということで出てきた値
$ p_t = \frac{1}{3}+\frac{2}{3}df_t/N
11.3.4 Probabilistic approaches to relevance feedback
(擬似的な)適合フィードバックを使ってさらに正確に $ p_t を推定するアプローチ
確率的な適合フィードバックのアルゴリズム
1. 推測で$ p_t と $ u_t 初期推定をする
簡単な方法は前節でみた $ p_t = \frac{1}{2} と使う
2. 初期推定の結果を使って適合文章の集合における最良の推定値を決定する
$ R=\{d: R_{d,q}=1\}
このモデルを使ってユーザーに提示する候補セットを作る
3. ユーザーの評価を使って学習する
ユーザーには文章集合 $ V のサブセットを見せて評価してもらう
評価の結果、$ V は以下のように分類される
$ VR = \{ d \in V, R_{d,q} = 1 \} \subset R
$ VNR = \{ d \in V, R_{d,q} = 0 \}
4. 評価結果から $ p_t と $ u_t を再度推定する
最尤推定
$ VR と $ VNR が十分に多いときは最尤推定ができる
(11.23)$ p_t = |VR_t|/|VR|
これを平滑化すると
(11.24) $ p_t = \frac{|VR_t|+\frac{1}{2}}{(|VR_t|+\frac{1}{2})+(|VR_{\bar{t}}|+\frac{1}{2})} = \frac{|VR_t|+\frac{1}{2}}{|VR|+1}
Bayesian updating
ふつうはそこまで $ V の数を多く出来ない
= 最尤推定ではノイズが多くて信頼性が低い
そこで以下のようにする
(11.25)$ p_t^{(k+1)} = \frac{|VR_t|+kp_t^{(k)}}{|VR|+k}
$ p_t^{(k)} は $ k 回目の $ p_t の推定値
これを次の回の事前確率として利用する
ベータ分布を使う必要があるが結果のこの式はとても簡単
他の事実(evidence)がない場合、かつユーザーが5つ程度のドキュメントを評価しているとすると
$ k=5 くらいがよいとされる
少なすぎるデータに影響されないように重み付けられている
5. ステップ2から繰り返す
ユーザーが満足するまでやる
疑似適合フィードバックに展開したときのアルゴリズム
1. 上で見たのと同様の初期推定をする
2. 適合文章の推定数を決める
不明な場合は保守的に出来るだけ小さくする方がよい
これは高順位の文書集合 $ V のサイズを決めるのに使う
3. $ p_t と $ u_t の推定を改善する
(11.23) か (11.25) を使うか選べる
ここでは $ |V_r| の代わりに $ |V| 使って、$ \frac{1}{2}で平滑している
(11.26) $ p_t = \frac{|V_t|+\frac{1}{2}}{|V|+1}
(11.27) $ u_t=\frac{df_t-|V_t|+\frac{1}{2}}{N-|V|+1}
4. 順位が収束するまでステップ2から繰り返す
実際に推定した $ p_t を使った $ c_t は tf-idf に近くなるらしい
しかし、(11.18) と (11.22) と (11.26) から以下となる
(11.28) $ c_t = \log \left[ \frac{p_t}{1-p_t} \cdot \frac{1-u_t}{u_t} \right] \approx \log \left[ \frac{|V_t|+\frac{1}{2}}{|V|-|V_t|+1} \cdot \frac{N}{df_t} \right]
これは $ tf とは全く関係のない形となる
また対数の性質から以下が得られる
(11.29)$ c_t=\log\frac{|V_t|+\frac{1}{2}}{|V|-|V_t|+1}+\log\frac{N}{df_t}
これより $ tf-idf のような掛け算の形ではなくて、足し算の形なることも分かる
11.4 An appraisal and some extensions
11.4.1 An appraisal of probabilistic models
BIMの仮定
ドキュメント、クエリ、関連について0/1の2値で表現する
単語は互いの独立している
クエリに含まれない単語は結果に影響を与えない
ドキュメントの関連度は互いに独立している
11.4.2 Tree-structured dependencies between terms
依存関係の木構造を用いると単語が互いに独立しているという前提を外す事ができる
Hong と Kong は当然依存していそうみたいなのに対応できる
最初に考案されたときは推定に問題があり実用ではなかった
Tree Augmented Naive Bayes によって実用化された
https://gyazo.com/7e55994406c5994c5d9153a678354b4c
11.4.3 Okapi BM25: a non-binary model
単語の出現頻度とドキュメントの長さの要素を加えた確率モデル
BIMは概要だけの固定長の文章などではうまくいく
これまでの様子をみる
(11.31) $ RSV_d = \sum_{t \in q}\log\frac{N-df_t+\frac{1}{2}}{df_t+\frac{1}{2}}
これだと文章の出現頻度しか考慮出来ていない
また、これだと文書の半分以上に登場する単語があったら負の重みになってしまう
これはストップリストを使うと回避できる
ここに単語の出現頻度とドキュメントの長さの項を加える
(11.32) $ RSV_d=\sum_{t \in q}\log \left[ \frac{N}{df_t} \right] \cdot \frac{(k_1+1)tf_{td}}{k_1((1-b)+b \times (L_d / L_{ave})) + tf_{td}}
ここで
$ k_1 $ (0 \leq k_1) はどのくらい単語の出現頻度を結果に効かせるかの係数
$ k_1 = 0 だと単語の出現頻度は結果に寄与しない
$ b$ (0 \leq b \leq 1) はどのくらい文章の長さを結果に効かせるかの係数
$ b = 0 だと文章の長さは結果に寄与しない
次にクエリの長さが長いときのことを考える
(11.34) (11.32) $ RSV_d=\sum_{t \in q}\log \left[ \frac{N}{df_t} \right] \cdot \frac{(k_1+1)tf_{td}}{k_1((1-b)+b \times (L_d / L_{ave})) + tf_{td}} \times \frac{(k_3+1)tf_{tq}}{k_3+tf_{tq}}
ここで
$ tf_{tq} はクエリの中に単語 $ t が出現する頻度
$ k_3$ (0 \leq k_3) はどのくらいクエリ中の単語出現頻度を結果に効かせるかの係数
$ k_3 = 0 ならクエリ中の単語出現頻度は結果に寄与しない
これらの係数はテストコレクション毎に最適なものを選ぶ必要がある
実際はだいたい以下が効果的と言われている
$ 1.2 \leq k_1 \leq 2
$ 1.2 \leq k_3 \leq 2
$ b=0.75
$ \frac{N}{df_t} を展開すると以下を得る
(11.34)
$ RSV_d=\sum_{t\in q}\log\left[ \left[ \frac{(|VR_t|+\frac{1}{2})/(|VNR+t|+\frac{1}{2})}{(df_t-|VR_t|+\frac{1}{2})/(N-df_t-|VR|+|VR_t|+\frac{1}{2})} \right] \times \frac{(k_1+1)tf_{td}}{k_1((1-b)+b(L_d/L_ave))+tf_{td}} \times \frac{(k_3+1)tf_{tq}}{k_3+tf_{tq}} \right]
単純に単語頻度による重み付け以上の利益が得られる
第一項は適合フィードバックやクエリ拡張の恩恵を得られる
第二項は文章の長さと単語の出現頻度を扱える
第三項はクエリ中の単語の出現頻度を扱える
BM25は広く使われていて成功している
11.4.4 Bayesian network approaches to IR
確率的グラフィカルモデルの一形態であるベイズネットワークも取り入れられている
図11.1のような依存関係の有向グラフの中で、任意の知識に基づいて学習と推論を可能とするアルゴリズム
紙面が足りないのでここでは詳しくは説明しない
2つのネットワークのマッピングで適合確率を推定する
文章ネットワーク
大規模だが事前に構築できる
クエリネットワーク
小規模だがユーザーの入力毎に構築する