テキスト検索の技術
• テキストデータのベクトル表現
• 検索
2
テキスト検索を行う局面
• 図書館で本を探す
• 特許出願で，関連の特許を探す
• 論文執筆で，関連研究を探す
• 新聞等から株価情報を抜き出す
• WWWを使って，興味のある情報を探す
• 判例を探す
3
テキスト検索
テキスト１
テキスト４
テキスト３
テキスト２
テキスト６
テキスト５
検索条件
条件に合致するテキスト
（検索の単位はテキスト）
4
テキストのベクトル表現例
テキ
スト
１
テキ
スト
２
テキ
スト
３
テキ
スト
４
テキ
スト
５
term １
term ２
term ３
term ４
term ５
term ６
term ７
あり
あり
あり
あり
あり
あり
あり
あり
あり
あり
あり
あり
あり あり
あり
これで１ベクトル
5
テキストのベクトル表現
• term の有無や登場回数を使って，ベクトル表現
• 非常に長いベクトルで表現（理由： キーワードの数
が多い）
• 「検索条件」も，キーワードによるベクトル表現
• 類似検索を，ベクトルマッチングで行う
• 検索時には，「term ごとに重要度を変えたい」ことも
ある
6
content word とは
• content word
• 検索に使う単語
• テキスト中の有無／登場回数を使って，検索を行う
• non-content word
• 検索に使わない単語
• of, a, 「の」，「が」 など
7
テキストのベクトル表現例
• テキスト
[f1 ... fi ... fn]
n : term の総数
fi : i番目の term の有無／登場回数
• 問い合わせ
[d1, ..., di, ..., dn]
di : i番目の term の重要度
8
document frequency
• term (Xとする）について，Xが登場する文章の数
を document frequency という
• document frequency は term ごとに定まる値
9
document frequency
• document frequency が低い
• あまり多くの文章に登場する
• 「文章を区別するのに役に立つ term だ」と考える
• document frequency が高い
• たくさんの文章に登場する
10
inverse document frequency (idf)
• log (m/d)
m: document の総数
d: term の document frequency
d=m ならば log(m/d) = 0
d=1 ならば log(m/d) = log m
11
log (m/d) のグラフ
0
0.2
0.4
0.6
0.8
1
1.2
0 2 4 6 8 10 12
m=10 のとき
d (document frequency)
log (m/d)
(inverse document frequency)
12
term occurrence frequency(tf)
• ある term が，文章中に登場する回数のこと
• term occurrence frequency が高いと
• その term が何度も使われている
• 筆者は，意図して何度も使っているはず
• その文章において, その term は, 「重要度が高い」と考
える
13
tf/idf
f・log (m/d)
m: document の総数
d: term の document frequency
f: term の term occurrence frequency
単語ごと, 文章ごとに定まる値
14
テキストのベクトル表現例
テキスト [x1 ... xi ... xn]
n : term の総数
xi : i番目の term の 「tf/idf」値
15
Retrieval
テキスト１
テキスト３
テキスト２
検索条件
ベクトル表現
ベクトル表現
ベクトル表現
ベクトル表現
各々，ベクトルマッチングを行い，
ベクトル空間中での「距離」が近いもの同士を
類似度が高いとみなす（→解とする）
16
ベクトルの距離
• dot product による距離
x1y1 + x2y2 + ・・・ +xnyn
（x1, x2, ..., xn）
（y1, y2, ..., yn）
17
dot product を使用しない理由
• 各 xi 値は，tf/idf 値
• 長い文章と短い文章では，長い文章の方が tf/idf 値が大
きくなって，マッチしやすくなる
→ dot product による距離に代わる何かが必要
18
Cosine距離
• Cosineθ のこと（２つのベクトルのなす角：θ）
• Cosine(X, Y) = Cosine(cX, Y) = Cosine(X, cY)
Cosine（X，Y）＝
X・Y
√（X・X)・（Y・Y）
（x1, x2, ..., xn）
（y1, y2, ..., yn）
原点
θ
19
テキスト検索における課題
• Relevance Feedback
• インデックス
• tf/idf 以外のベクトル表現法
など
20
Performance
問い合わせの解
真の正解
間違い
もれ
もれ
21
Relevance Feedback(1/3)
Qの解
Q
22
Relevance Feedback(2/3)
Q
ユーザは，どれが正しくて，どれが正しくないか分かる
Qの解
23
Relevance Feedback(3/3)
Q
システムは，新しい Q’ を自動的に求め，再度問い合わせを実行
Q’
24
Relevance Feedback
Q
Q` ＝ Q ＋ C１・ｆ（RR) － C2・ｆ（RI)
Q’
RR
RI
25
Relevance Feedback
User
Query
Q
Similarity
Retrieval
Retrieved
Documents
R
Relevant
Documents
RR
Irrelevant
Documents
RI
Feedback
Query
Q’
26
インデックス
• inverted file
• signature file ← ハッシュを利用
• Clustering
27
inverted file
t1
(D1, 3), (D3, 3), (D5, 1)
t2
(D2, 2), (D5,2)
t3
(D4, 1), (D5, 3)
term t3 は，D4, D5 にのみ登場し，
それぞれのtf/idf 値は 1, 3
28
inverted file
t1
(D1, 3), (D3, 3), (D5, 1)
t2
(D2, 2), (D5,2)
t3
(D4, 1), (D5, 3)
Q( 0, 2, 1 )に対して
「D2, D4, D5 のみ処理の対象とすべき」
ことが分かる
29
inverted file
t1
t2
t3
tn
この部分は普通 B+-tree
30
ベクトル表現での課題
• 単語は違うが（ほぼ）同じ意味
• 「おいしい」，「美味しい」
• 「不思議」,「謎」
• ２単語で無く，１単語とみなすべき
• 「オペレーティング」，「システム」
• → 「オペレーティングシステム」
31
ベクトル表現の限界
• 文章の意味には立ち入らない
• 人が魚を食べた
• 魚が人を食べた
• 登場する term は同じだが，意味は違う
32
