ベクトル空間法 - Top Page | 中川研究室

ベクトル空間法
• 最良優先検索
• タームの重み付けと類似度
• パッセージ検索
各タームを次元にし、質問と文書をベク
トルで表現するベクトル空間
質問ｑ：「人工知能
と知識の関係について
の論文」
人工知能＝１．０
知識＝１．０
論理プログラム＝０
ターム：知識
文書D：「第５世代の失敗」
ターム：知識＝０．７
１．０
：人工知能＝０
：論理プログラム
０．７
＝２．５
Dとｑのなす角＝類似度
１．０
２．５
ターム：人工知能
ターム：論理プログラム
タームの重みその１ターム頻度
• ターム頻度(Term Frequency: tf )
tf ji  freq(i, j)
• freq(i; j) = 文書Dj におけるタームt i の出現頻度。
• 変形版ｔｆ
freq(i,j)
tf ji  K (1 K )
max(freq(i,j))
i, j
log(freq(i, j) 1)
tf ji 
log(文書ｊ中の総ターム種類数）
タームの重みその２文書頻度
dfi  Dfreq(i)
• 文書頻度 Document frequency
• ただし、Dfreq(i)はタームtiが出現する文書数
• 実際はその逆数
を使う
idfi
• 文書総数Nによる正規化
idfi  log
N
1
Dfreq(i,j)
IDF
ベクトル空間モデルではidf をヒューリ
スィックとして導入したが、ターム分布から
理論的に導くこともできる。ある文書D が
関連性があるR かない¬R かの対数尤度
比L(D) を考える。
P( R | D )
L( D )  log
P( R | D )
P( R | D)
L( D)  log
P(R | D)
ベイズの定理により
L( D )  log P( D | R )  log P( D | R )
 log P( R )  log(R )
3 、4 項は、関連性のある文書とない文書の比なので
文書集合における定数であるから考慮しなくてよいの
で無視する。
質問Qに関連する文書としてD があるとし、Q はターム
wi(i = 1,2,..) からなるとする。さらにXi = 1 ならD 中にwi
が出現し、Xi = 0なら出現しないとすると次式になる。
L( D ) 

(log P( X i | R )  log( X i | R ))
i
P(Xi|R)=pi, P(Xi|¬R)=qi と書くと
P(Xi|R)=pi, P(Xi|¬R)=qi と書くと
L( D)  log p (1  pi )
Xi
i
i
1 Xi
)  log q (1  qi )
Xi
i
i
pi
1  qi
  Xi log
  Xi log
1  pi i
qi
i
1  pi
 log
1  qi
i
第３項は常数なので無視
1 Xi
)
ここで、pi ， qi を求めたいが直接に求めるこ
とは難しい。そこで以下のように近似をして
いく。まず、pi はタームi の出現確率なので
非常に小さく、かつ質問に現れるようなター
ムについては一定と仮定すると、第1 項は、
cΣiXi ということになり、質問と文書におい
て同時に現れたターム数に比例するものにな
る。
qi = P(Xi = 1|¬R) だが、タームi が現れる文書の大
多数はタームi に関連性がないと仮定すると、
qi =dfi/N (<<1) とすると、 log(1-x)/x ~ –log x により
タームi の idf=log(N/df) となり、結局次ぎのように
なる。
 X   X  idf
L( D )  c
i
i
i
i
i
ベクトル空間法において類似度計算に用いられる重
みの重要な因子であるidf の理論的根拠が関連文書
と関連しない文書の対数尤度比に比例的であるとい
う結論が得られた。
Residual IDF
idf とポアソン分布から予測されるdocument
frequecy の差として次式で定義される。
RIDF =–log(df/N) – log(1–p(0;cf/N))
第２項はPoisson分布で、タームt が少なくとも1回
は現れる文書のポアソン分布における確率であ
る。ポアソン分布は文書の意味内容に直接係わ
らないnon content なタームの分布をよく近似す
る。idf は全てのタームについてのidf だから、
non content なタームの分を差し引くと意味内容
を表すタームcontent wordを特徴付ける量が得
られると考える
タームの重みその３ tf ·idf
• 文書Djに現れるタームtiの重みwijは、Djには数多く現れ、他の
文書にはあまり現れないという性質をもつべき。つまり、文書
Djをよく特徴つけることが大切。そこで、前記のtfとidfをかけ
たものがよい。つまり、 tf ·idf
w ij  tf ji idfi
文書ベクトルと質問ベクトルとそれらの類似度その１
• このようにしてタームtiの重みが決まったので、文書Djのベク
トルは、各タームを次元に割り当てた多次元空間におけるベク
トルとして表現できる。つまり、
D j  (w1j, w 2j ,....,w m
j )
• 一方質問ｑもタームtiを含めば１、含まなければ０という値に
してベクトルで表現できる。つまり
q (q1,q2 ,...,qm )
• ただし、ｍは文書集合における全ての異なりターム数
文書ベクトルと質問ベクトルとそれらの類似度その２
• さて、情報検索とは、質問ｑに対して類似度の高い文書Dｊを探
すことなので、類似度simを以下に定義する。これは、ベクトル
空間におけるｑとDｊのなす角θが０に近いほど類似度が高いと考
える方法。
sim(q,D j ) 
•
q1w1j .....q m w m
j
2
q12 ...q 2m  (w1j) 2 ...(w m
)
j
 cos
sim の大きい順に検索結果をに並べて質問者に提示する。
標準的な検索エンジン
 Okapi（Robertson)のBM２５
 原理的には，検索質問q と文書ベクトルdi が与え
られときに，その文書が検索質問に適合している
確率P(Rjq; di) を推計する
 まずベクトル空間法におけるタームtのidf相当
の部分w(t)
N  nt  0.5
w(t )  log
nt  0.5
 N:総文書数、nt:tの該当文書での出現回数
文書と質問qの類似度：Sim(d,q)
(k1  1)tf (k 3  1)qtf
Sim(d , q)  w(t ) 

K  tf
k 3  qtf
tq

dl
K  k1((1  b)  b
Avdl
tf:文書d中のタームtの出現回数
qtf:質問q中のタームtの出現回数
dl:文書長
Avdl：平均文書長
k1=1.2, k3=1000,b=0.75
パッセージ検索
•
•
•
文書の内容を特徴付けるのは文書全体よりはむしろ特定の部分
ベクトル空間モデルを文書ではなく、文書の小さな部分、例えば段落、
に適用。この小さな部分をパッセ―ジという。つまり、文書Dの代わり
にパッセ―ジPkを使って、パッセ―ジ重みwikを計算し、ベクトル空間
法を適用
パッセ―ジの候補としては、
１固定長に分割したテキストの部分
２形式段落
３形式的な節、章

Download Report