イントロ
検索は不確実な推測 -> 不確実性のあるものに理にかなった基礎を提供するのが確率論
- 確率論と確率的ランキング付け -> 11.1,2
- バイナリー独立モデル(オリジナルで、最も影響のある確率モデル) -> 11.3
- BM25 -> 11.4
- ベイジアンネットワーク -> 11.4
11.1 基本的な確率論
同時確率の定義
P(A,B) = P(A|B)P(B) = P(B|A)P(A)
ベイズの法則
P(A|B) = P(B|A)P(A) / P(B)
事前確率と事後確率
- 事前確率 -> P(A) (他のどの情報もない時)Aが起こる確率
- 事後確率 -> P(A|B) Bという情報が与えられた時のAの確率
- オッズ -> P(A) / (1-P(A)) 確率がどのくらい変化するか
11.2 確率ランキング原理
11.2.1 1/0の損失の場合
ランク付けされた検索の設定を想定
(文書コレクションが有り、ユーザーがクエリを投げると順序付けられた文書のリストが返される)
R_d,q -> クエリーqに対してdが関連しているかどうかの指標確率変数．文書が関連していれば1してなければ0の2値(以下略してRと記述)
P(R=1|d,q) -> 文書をこの確率によってランキングすることが確率ランキング原理の基礎となる
目標 = top-kに対して最高の結果を返す -> 1/0損失(検索コスト、アクションやエラーへの異なる重み付けを考えない、関連か非関連かだけを考える)の場合、確率で降順
検索の結果集合が順序付けなく返される場合
dが関連する ⇔ P(R=1|d,q) > P(R=0|d,q)
これをベイズ最適決定規則という
定理 : PRP(確率ランキング原理)は1/0損失の下で期待される損失(ベイズリスク)を最小にする意味で最適
11.2.2 検索コスト付きの確率ランキング原理
前節は検索コストがないと仮定した。C_1は関連文書を検索するコスト、C_0は非関連文書を検索するコスト。このとき特定の文書dと未検索のすべての文書d'に関して。
C_1*P(R=1|d)+C_0*P(R=0|d) <= C_1*P(R=1|d')+C_0*P(R=0|d')
ならばdは次に検索される文書である。(つまりすべての未検索の文書よりもコストの期待値が小さいとき)これによりモデリングの段階で偽陽性や偽陰性の差額コストをモデル化できる。
11.3 バイナリ独立モデル
前提
- 文書/クエリー/関連性の論理表現(正解データが必要?)
- 用語独立
- クエリーにない用語は結果に影響を及ぼさない
- 文書の関連性は独立している
これらの全体を元に、文書とクエリーがあたえられたときの関連性の有無を確率的に表現するモデル
文書dのベクトル表現
x=(x_1,x2,….)
x_tは文書dに出現する単語。出現する場合はx_t=1, しない場合はx_t=0をとる。
クエリーqのベクトル表現も同様
(ただしクエリーはもともと語の集合の形を取るため重要ではない)
確率的な戦略
文書内の用語がどのように関連性に貢献しているかを評価。そのために、用語頻度、文書頻度、文書長、その他文書関連性の判断に利用d家いるような統計情報を利用し評価する。
ベイズの定理による、文書とクエリが与えられたときの関連性の有無を確率で表現すると
P(R=1|x,q) = P(x|R=1,q)P(R=1|q) / P(x|q)
P(R=0|x,q) = P(x|R=0,q)P(R=0|q) / P(x|q)
P(R=1|x,q) + P(R=0|x,q) = 1
となる。
11.3.1 クエリー用語のランキング関数を導出
基本的な考え方として、P(R=1|x,q)を降順に順序付けしたものが検索結果である。なので実際の確率を求める必要はなく、順序関係が同一な結果が得られれば良い。共通項として消せるものや、定数項として分離できるものを分離するような式変形を行っていく。
まずはオッズ比を考えると
O(R|x,q) = P(R=1|x,q)/P(R=0|x,q) = (P(R=1|q) / P(R=0|q) * (P(x|R=1,q) / P(x|R=0,q))
となる。ここで第1項はクエリーに対しての定数であるので無視出来る。このため第2項を推定すれば結果が得られる。第2項の推定は困難なので、ここでナイーブベイズの仮定を置くことで単純化する。
(ナイーブベイズの仮定とは文書内の用語は独立しているという仮定。実際はそんなことはないがしばしばこの仮定がうまくいったりする)
P(x|R=1,q) / P(x|R=0,q) = Π(t)(P(x_t|R=1,q) / P(x_t|R=0,q))
以下 p_t = P(x_t|R=1,q), u_t = P(x_t|R=0,q) とする。
ここでも前回と同じ戦略(クエリーに関する定数項を分離)で式変形をする。また仮定として、q_t=0ならばp_t=u_tという仮定をおく。(クエリーに出現しない語は、関連文書と非関連文書に同じ割合で出現する)
O(R|x,q) = O(R|q) * Π(x_t=q_t=1)(p_t(1-p_t) / u_t(1-u_t)) * Π(q_t)((1-p_t) / (1-u_t))
となる。これで第1項,第3項はクエリーに関する定数項なので無視。第2項は積だと扱いにくいためlogをとる。この値を検索状態値(RSV)と呼ぶ。
RSV_d = Σ(x_t=q_t=1) log(p_t(1-u_t) / u_t(1-p_t))
シグマ内の項をc_tとおく
c_t = log(p_t / (1-p_t)) + log((1-u_t) / u_t)
11.3.2 確率の推定の理論
c_tを推定すれば、順序関係は求まる。推定は正解データからの学習により行う。
N,df_t,S,sの関係を
| 文書 | 関連 | 非関連 | 合計 |
|---|---|---|---|
| 用語出現 x_t=1 | s | df_t-s | df_t |
| 用語不出現 x_t=0 | S-s | (N-df_t)-(S-s) | N-df_t |
| 合計 | S | N-S | N |
とする。これらは正解データとしてあたえられている。
実際の推定は
c_t = log((s / (S-s)) / ((df_t-s) / ((N-df_t)-(S-s))))
実際はlog0をさけるためスムージングする。ここでは1/2でスムージングする。
c_t = log(((s+1/2) / (S-s+1/2)) / ((df_t-s+1/2) / ((N-df_t)-(S-s)+1/2)))
上の方法 -> 最尤推定, 下の方法 -> MAP推定の一つ
11.3.3 実際の確率推定
関連文書は文書集合全体に比べて非常に小さな割合であるという仮定がおける。
非関連文書を考える時、以上の仮定から、全体のコレクションの近似と考えても良い。
log((1-u_t) / u_t) = log((N-df_t) / df_t) ≒ log(N/df_t)
N >> df_t
これはidfである。
p_tをもとめるときはこうはいかない。
1. 用語出現の頻度を利用(適合性フィードバックを利用 -> 11.3.4)
2. p_t=0.5と仮定。こうすると最初の項は0になるためランキング付けはidfのみの評価となる
3. p_t = 1/3 + 2/3 * df_t / N
11.3.4 関連性フィードバックへの確率論的アプローチ
p_tのより正確な推定
1. p_tとu_tの初期値を推測
2. p_tとu_tに現在の推定を使用
3. ユーザとの対話。文書Vに対するユーザの関連性への判断を学習(クリックとか?)VはVR(関連性有りと判断)とVNR(関連性なしと判断)の2つの部分集合に別れる。
4. VRを利用し、p_tとu_tを再学習
p_t = |VR_t| / |VR|
スムージングして
p_t = (|VR_t|+1/2) / (|VR|+1)
この場合だとノイズが多いので、ベイズ更新
p_t(k+1) = (|VR_t|+κp_t(k)) / (|VR|+κ)
p_t(k)はk番目の推定値,κは重み
5. ステップ2以降を繰り返し
V=VRと装うこともできる。この場合、重みc_tはtf-idf値のようにみなせる。
c_t ≒ log(((|V_t| + 1/2) / (|V|-|V_t|+1))*(N / df_t))
11.4 評価といくらかの拡張
11.4.1 確率モデルの評価
これらの手法のパフォーマンスは勝ったことがない。
おく前提、制約がきびしすぎる??
11.4.2 用語間の木構造の依存関係
用語間の関係を木構造でもつ
11.4.3 Okapi:BM25:バイナリ独立モデル
適合判定がない場合
RSV_d = Σ_t∈q[log(N / df_t)] * ((k_1+1)tf_td / (k_1((1-b) + b * (L_d / L_ave) + tf_td) + tf_td)) * ((k_3+1)tf_tq / (k_3 + tf_tq))
ある場合 -> より完全な形で記述可能
RSV_d = Σ_t∈q[log[((|VR_t|+1/2) / (|VNR_t|+1/2)) / ((df_t-|VR_t|+1/2) / (N-df_t-|VR|+|VR_t|+1/2))]] * ((k_1+1)tf_td / (k_1((1-b) + b * (L_d / L_ave) + tf_td) + tf_td)) * ((k_3+1)tf_tq / (k_3 + tf_tq))
11.4.4 情報検索のベイジアンネットワークのアプローチ
詳しい解説はなし。文書コレクションネットワークとクエリネットワーク。