Modern Information Retrieval Chapter 12

Information Retrieval
情報検索の概要と代表的手法
近山・田浦研究室
B4 末包昌司
2003/5/15
本発表の流れ
Richard B. Yates “Modern Information Retrieval”
に基づき、「情報検索」に関して
1. 歴史的背景
2. 現代の情報検索の概要
3. 情報検索の代表的手法
4. 本書籍の今後の流れの紹介
の順で発表
background
abstract
classic models
What’s follows?
1
情報検索の背景と概要
情報検索の背景
•
WWWの発達に伴い安価・場所に依らない・簡単に情報
発信できるという好環境が整ったが…
•
現在の論点
1. どのような方法が高品質な検索結果を返すか？
2. どのような方法が高速な（早い索引付けと短時間でのクエ
リー）検索を行えるか？
3. どうすればユーザの行動をうまく導くことができるか？（品
質に大きく影響を与える）
background
abstract
classic models
What’s follows?
2
情報検索の流れ
background
abstract
classic models
What’s follows?
情報検索モデルの関係
文書構造は気にしない
文書構造を気にする
background
abstract
classic models
What’s follows?
3
伝統的な3つの検索モデル
情報検索の主要な伝統的モデル
古典的な3つの情報検索モデル；文書構造は気にしない∼
1. Boolean model
クエリーはインデックスを含むか含まないかで表現（集合理論的）
2. Vector model
クエリー・インデックスはt-次元空間ベクトルとして表現される（代数的）
3. Probabilistic model
クエリーとインデックスの関係を確率論に従って表現（確率論的）
definitions
K = (k i ) (1 ≤ i ≤ t ) : index terms
d j : documents
wi , j : weight associated with ( k i , d j )(assume mutually indep.)
r
d j = ( w1, j , w2, j , L , wt , j )
r
Gi ( d j ) ≡ wi , j
background
abstract
classic models
What’s follows?
4
1. Boolean Model ~概要~
• query結果はindexが「含まれている」「いない」の2値
のみ(下参照）
• 各indexの重みも2値 i.e. wi , j ∈ {0,1}
• queryはand, or, notで接続
r
qdnf : disjunctive normal form for the query q
r
r
qcc : conjunctive components of qdnf
similarity of a document d j to the query q :
r
r r r
r
 1 : if ∃qcc (qcc ∈qdnf ) ∧ (∀ki , g i (d j ) = g i ( qcc ))
sim (d j , q ) = 
0 : otherwise

background
abstract
classic models
What’s follows?
1. Boolean Model ~例~
q = k a ∧ ( k b ∨ ¬k c )
r
∴ qdcf = (1,1,1) ∨ (1,1,0) ∨ (1,0,0)
の場合、
r
qdcf
r
r
r
if d1 = (0,1,0) then g1 (d1 ) ≠ g1 (qcc )
となり、文書１は非適合に分類されるが・・・
一致する要素があるにもかかわらず、
クエリー結果が2値であるために非適合に分類されている
background
abstract
classic models
What’s follows?
5
1. Boolean Model ~特徴~
長所
– 直感的に理解しやすくIRの枠組をつかみやすい
– ブール代数表現を用いるので正確な意味付けが可能である
短所
– 「関連あり」「なし」の2値判断しかできない
(正確なマッチングを求めると非常に多いか非常に少ない結果が出てくる）
– ブール論理で表すのが大変なときがよくある
以上のような特徴のもと、
– 商用の文書検索システムには多く使用されている
– 古典的ながら、初学者に対して良いモデルである
– インデックス重み付けが改良策である(c.f. Vector Model)
といわれている
background
classic models
abstract
What’s follows?
2. Vector Model ~概要~
Vector Model発案の動機
=Boolean Modelの二値性の不便さの解消
i.e. インデックスの重み・クエリー結果（類似性）の段階を2値から複数に増やす
例えば「類似性」を以下のように定義することでクエリー結果は複数値とる
r
r
dj •q
sim(d j , q ) ≡ cosθ = r
r
dj × q
t
=
∑w
i, j
i =1
t
∑w
i =1
i, j
2
⋅
r
dj
⋅ wi , q
θ
t
∑w
j =1
2
j,q
r
q
t - dimentional vector space
ではインデックスに対してはどのように重み付けすればよいのか？
background
abstract
classic models
What’s follows?
6
2. Vector Model ~概要2~
重み付けの方法？
• 同じ文書内に多く出てくる語は重みを増やす（内部類似性）
• より少ない文書に出てくる言は重みを増やす（外部類似性）
• 代表的な算出式はSaltonのアイディア
– インデックスの要素に対しての重み付けには
wi , j =
freqi , j
max l freql , j
内部類似性
⋅ log
N
(tf - idf scheme)
ni
外部類似性
– クエリーの要素に対しての重み付けには

0.5 freqi ,q 
 ⋅ log N
wi ,q =  0.5 +

max l freql ,q 
ni

background
abstract
classic models
What’s follows?
2. Vector Model ~特徴~
長所
– 「言葉の重み付け」による改善された検索品質
– 「部分一致の判定」により検索結果をクエリー条件に近づける
– コサイン順位付けの手法はクエリーに対する類似性からソートする
短所
– 各インデックスが互いに独立だと仮定している（しかし、非独立としたと
きと比較して全体的なパフォーマンスは勝ると言われている）
以上のような特徴のもと、
– Vector Modelの枠組では品質改善は「クエリーの拡張」・「関連度
フィードバック」（５章）しかない
– 簡潔＆高速な上に、他のモデルと同じかそれ以上の品質
– 現在でもよく使用される情報検索モデル
といわれている
background
abstract
classic models
What’s follows?
7
3. Probabilistic Model ~概要~
•
•
クエリーのインデックスの重み変数はすべて2値
基本的アイディアは
1. ユーザクエリーqを得る wi , j ∈ {0,1}, wi ,q ∈ {0,1}
2. 完全一致する文書を抽出（理想集合として保持）
R : relevent documents set
3. ユーザのフィードバックをもとに類似性を判定する確率論
の式を用いて再帰的に理想集合Rを改善
どのように改善すればよいのか？
background
abstract
classic models
What’s follows?
3. Probabilistic Model ~概要2~
理想集合Rの改善方法
• 類似性は以下のように算出する
r
r
P( R d j ) P(d j R) ⋅ P( R)
r =
sim(d j , q ) ≡
(Q Bayes' Rule)
r
P( R d j ) P(d j R ) ⋅ P( R )
r
P(d j R)
(Q P( R ), P( R ) : const )
~
r
P(d j R )
t

1 − P ( ki R ) 
P(ki R)

~ L = ∑ wi , q ⋅ wi , j ⋅  log
+ log
P(ki R ) 
i =1
 1 − P ( ki R )
• よって、 P(ki R), P(ki R ) を改善すればよい
V
n −V
→いくつかの仮定により P(ki R) = i , P(ki R ) = i i
V
とかけ、これを再帰的に改善する。
background
abstract
classic models
N −V
What’s follows?
8
3. Probabilistic Model ~特徴~
長所
– 文書が互いの類似確率を基にランク付けされるという点
短所
– 類似文書と非類似文書の分類で初期推測が必要である点
– クエリーの各インデックスの重みは2値であるため、文書中のインデッ
クス頻度を考慮しない点
– インデックス同士の独立性の仮定（ほぼ問題なし）
以上のような特徴のもと、
– Boolean Modelよりも高品質である
といわれている
background
abstract
classic models
What’s follows?
伝統的モデルの比較
• Boolean Modelは「部分一致の認識不可能性」により3モデル
の中では最低のパフォーマンス
• Probabilistic ModelとVector Modelの比較ではどちらのパ
フォーマンスがよいかさまざまな意見がある
• 現在の議論では
Vector > Probabilistic >> Boolean
という意見が中心的である
background
abstract
classic models
What’s follows?
9
伝統的モデルからの発展
より発展した情報検索モデル
• Boolean modelの発展
¾
¾
Fuzzy set model
Extended Boolean model
• Vector modelの発展
¾
¾
¾
Generalized vector model
Latent semantic indexing model
Neural network model
• Probabilistic modelの発展
¾
¾
Inference network model
Belief network model
background
abstract
classic models
What’
What’s follows?
10
Information Retrieval
情報検索の概要と代表的手法
近山・田浦研究室
B4 末包昌司
2003/5/15
11

Download Report