（1）情報検索 - 芝浦工業大学

授業計画
自然言語処理
Natural Language Processing
第１２回
2014/12/17
芝浦工業大学工学部情報工学科
杉本徹
1.
2.
3.
4.
5.
6.
7.
8.
9.
自然言語処理の概要（済）
日本語（１）文の構造（済）
日本語（２）文章の構造（済）
形態素解析（１）解析手法（済）
形態素解析（２）コスト推定（済）
構文解析（１）句構造解析（済）
構文解析（２）係り受け解析（済）
意味解析（１）意味の表現（済）
意味解析（２）解析手法（済）
授業計画（続き）
10.
11.
12.
13.
14.
15.
文脈解析（済）
文章生成（済）
応用（１）情報検索 ←今回
応用（２）機械翻訳
応用（３）対話システム
期末試験と解説
今日の内容
• 応用（１）情報検索
– 情報検索の概要
– 索引付け
• tf・idf
– 情報検索のモデル
• ブーリアンモデル
• ベクトル空間モデル
– 情報検索システムの評価
• 適合率，再現率，F 値
– Web検索
情報検索（Information Retrieval）
• （広義）ユーザの持つ問題（情報要求）を解決でき
る情報を見つけ出すこと
情報検索の概要
• （狭義）ユーザの検索質問（query）に適合する文書
（document）を文書集合の中から見つけ出すこと
※ 検索質問・・・情報要求を具体化したもの
1
情報検索のモデル
情報検索モデルの実現例
（ブーリアンモデル）
文書集合
（データベース）
ユーザ
（情報のニーズ）
索引付け
（indexing）
文書集合
（データベース）
ユーザ
（情報のニーズ）
各文書を単語の
集合として表現
単語のAND・
OR・NOT結合
索引付け
（indexing）
内部表現
検索質問
マッチング
各文書が検索条件を
満たすか否か判定
文書の出力
文書の出力
情報検索の応用，関連技術
• Web 検索（サーチエンジン）
• 情報フィルタリング（ユーザプロファイルに基づく
情報の選別）
索引付け
• 言語横断情報検索（複数の言語で書かれた文書
を横断的に検索）
• マルチメディア情報検索（画像，映像，音声など）
• 情報抽出（指定した項目の情報のみを抽出）
• 文書分類（カテゴリ分類，クラスタリングなど）
情報検索のモデル
文書集合
（データベース）
文書の内部表現
ユーザ
（情報のニーズ）
索引付け
（indexing）
• 文書のモデル化
– 文字の集まりとして見る
• 文字の列（character sequence）
– 単語の集まりとして見る
内部表現
• 単語の集合（set of words）
• 単語の頻度付き集合（bag of words）
• 単語の列（word sequence）
検索質問
よく使われる
– その他
マッチング
文書の出力
• 構文構造，意味構造を持った文（文章）として見る
• 文書の構成素（表題，見出し，本文など）を考慮する
2
参考：頻度付き集合（Bag），多重集合（Multiset）
• 通常の集合を拡張して，同じ種類の対象を複数個
重複して含むことができるようしたもの
• 頻度付き集合の例
索引語（index term）
• 文書の内容を表す単語
⇔ 索引語として不適切な語（不要語，stop word）
一般的すぎる語，どの文書にも均質に現れる語
{ a, a, b } ＝ { a, b, a } ≠ { a, b, b }
• 付属語（助詞，助動詞）
• この頻度付き集合を次のように表すこともできる
{ (a, 2), (b, 1) }
「が」，「を」，「です」など
• 抽象度の高い名詞や動詞「こと」，「もの」，「する」など
• 索引語を選択するための尺度
a a
b
頻度（重複度）
1. 索引語の頻度（tf: term frequency）
1. 索引語の頻度（tf: term frequency）
2. 索引語の分布の偏り（idf: inverse document frequency）
2. 索引語の分布の偏り
（idf: inverse document frequency）
• tf (t, d) ：文書 d に単語 t が出現する頻度
• 文書の長さに依存しないように頻度を正規化する
（文書の総単語数で割る）こともある
• 文書集合において特定の文書に偏って現れる単語
は，それらの文書の特徴付けに有効
• df (t) ：（ある文書集合の中で）単語 t が出現する
文書の数（document frequency）
• idf (t)  log
例：「坊っちゃん」における単語の
出現頻度ランキング
N
df(t)
N は文書の総数
例：「坊っちゃん」における単語の出現
頻度ランキング（助詞，助動詞など除く）
順位
単語
出現頻度（tf）
順位
単語
出現頻度（tf）
1
て
2127
1
する
907
2
だ
1921
2
おれ
471
3
た
1889
3
云う
454
4
は
1711
4
ない
263
5
を
1651
5
なる
245
6
の
1577
6
ある
232
7
に
1350
7
思う
193
8
が
1256
8
赤
178
9
と
928
9
シャツ
170
10
する
907
10
山嵐
155
11
ない
770
11
君
150
12
も
639
12
出る
147
3
例：「坊っちゃん」における単語の出現
頻度ランキング（tf・idf に基づく順位）
順位
単語
tf
idf
tf・idf
1
山嵐
155
2.3
356.9
2
シャツ
170
1.2
204.7
3
おれ
471
0.3
135.5
4
云う
454
0.3
130.6
5
古賀
35
3.0
104.9
6
清
87
1.2
104.7
7
校長
70
1.4
97.0
8
教頭
39
2.3
89.8
9
バッタ
27
3.0
80.9
10
宿直
31
2.3
71.4
11
マドンナ
29
2.3
66.8
12
狸
35
1.9
66.4
idf 算出の
文書集合：
情報検索のモデル
文書集合
（データベース）
ユーザ
（情報のニーズ）
内部表現
検索質問
索引付け
（indexing）
夏目漱石の
小説20作品
マッチング
文書の出力
情報検索のモデル
情報検索のモデル
文書集合
（データベース）
ユーザ
（情報のニーズ）
内部表現
検索質問
索引付け
（indexing）
マッチング
検索質問（query）
情報検索のモデル
• 複数の単語の組み合わせ
– ブール式
• 複数の単語を AND, OR, NOT で結合した式
• 例：「（銀座 OR 丸の内) AND レストラン AND
(NOT イタリアン）」
– 単語間の重み付け（優先順位）
文書の出力
文書集合
（データベース）
ユーザ
（情報のニーズ）
内部表現
検索質問
索引付け
（indexing）
• 例：「丸の内よりも銀座のほうが望ましい（優先する）」
– 文（例：「銀座か丸の内にある美味しいレストラン」）
• 入力文を形態素解析して単語を抽出
• 質問タイプ（Wh-など）
必ずしも考慮しない
• 構文構造，意味構造
マッチング
文書の出力
4
情報検索のモデル
情報検索の代表的なモデル
• ブーリアンモデル
文書集合
（データベース）
ユーザ
（情報のニーズ）
内部表現
検索質問
索引付け
（indexing）
マッチング
– 文書を単語の集合として表現しておき，ブール式で与
えられる検索質問に対して，その条件を満たす文書を
すべて求めて出力する
• ベクトル空間モデル
– 文書，検索質問の両方を重み付き単語集合（単語ベ
クトル）として表現し，検索質問とベクトルとしての類似
度が高い文書から順に出力する
文書の出力
• 確率モデル
– 文書と検索語の関係を確率的に捉え，検索質問に適
合する確率が高い文書から順に出力する
ブーリアンモデル
ブーリアンモデル
• 前処理
文書集合
（データベース）
ユーザ
（情報のニーズ）
各文書を単語の
集合として表現
単語のAND・
OR・NOT結合
索引付け
（indexing）
転置
単語 → その単語を含む文書の集合
• 検索質問（ブール式）
– 検索語 t1 を含む文書の集合を S1，検索語 t2 を含む文書
の集合を S2 とするとき，
t1 AND t2 の検索結果 S1∩S2 （共通部分）
各文書が検索条件を
満たすか否か判定
文書の出力
t1 OR t2 の検索結果 S1∪S2 （和集合）
NOT t1 の検索結果 S1 （補集合）
索引付け（indexing），転置索引
文書１
文書２
文書３
安倍首相は
２２日の教育
基本法特別
委員会で・・・
ブレア英首相
が労働党の
不正融資疑惑
に絡んで・・・
安倍晋三首相
は教育改革
タウンミーティ
ングで・・・
形態素解析
索引語
出現文書リスト
安倍
文書１，文書３
首相
文書１，文書２，文書３
教育
文書１，文書３
基本
文書１
・・・
文書 → その文書に含まれる単語の集合
ベクトル空間モデル
文書集合
（データベース）
ユーザ
（情報のニーズ）
各文書を単語ベク
トルとして表現
検索質問ベクトル
索引付け
（indexing）
各文書ベクトルと検索質問
ベクトルの類似性判定
文書の出力
・・・
5
ベクトル空間モデル
続き
• 文書，検索質問の両方を重み付き単語集合（単語ベクトル）
として表現し，検索質問とベクトルとしての類似度が高い文
書から順に出力する
• すべての文書 di （i = 1, …, N）
すべての単語 tj （j = 1, …, M）
• 文書ベクトル di = (wi1, wi2, …, wiM) と
検索質問ベクトル q = (wq1, wq2, …, wqM) の類似度
コサイン係数
とする
• 文書 di における単語 tj の重みを wij とすると，
– 文書 di のベクトル表現 (wi1, wi2, …, wiM)
M
 
d iq
cos     
di  q
※ 重みの値： 1/0（存在/非存在），出現頻度，tf・idf など
M
w
2
ij
 wqj

M
w
j 1
2
qj
– 他にも Dice係数，Jaccard係数などがある
続き
数値例
質問
ij
j 1
j 1
– 検索質問 q のベクトル表現 (wq1, wq2, …, wqM)
文書
w
t1
t2
t3
t4
t5
d1
4
8
2
2
0
d2
1
3
0
5
7
q1
0
2
0
1
0
q2
0
1
0
2
0
単語
• 質問 q1 が与えられたとき
– q1 と文書 d1 の類似度（コサイン係数）
= d1・q1／|d1| |q1| = 18／√88√5 = 0.86
– q1 と文書 d2 の類似度
= d2・q1／|d2| |q1| = 11／√84√5 = 0.54
d1が選ばれる
• 質問 q2 が与えられたとき
– q2 と文書 d1 の類似度
= d1・q2／|d1| |q2| = 12／√88√5 = 0.57
– q2 と文書 d2 の類似度
= d2・q2／|d2| |q2| = 13／√84√5 = 0.63
d2が選ばれる
情報検索システムの評価
• 次の２点により評価する
情報検索システムの評価
– 必要な情報を漏れなく検索できたか？(完全性）
⇒ 再現率（Recall）
– 必要な情報だけを検索できたか？（正確性）
⇒ 適合率（Precision）
6
情報検索システムの評価尺度
例
全文書
全文書
ユーザの検索意図に適合する文書
B
A
検索結果に含まれる文書
C
• 再現率（recall）
R = A / (A + B)
• 適合率（precision） P = A / (A + C)
• F 値（F measure） F = 2・P・R / (P + R)
ユーザの検索意図に適合する文書
文書1
文書3
文書2
文書4
検索結果に含まれる文書
文書5
• 再現率（recall）
R = 2 / (2 + 2) = 0.50
• 適合率（precision） P = 2 / (2 + 1) = 0.67
• F 値（F measure） F = 2PR / (P+R) = 0.57
一般に，適合率と再現率はトレードオフの関係
適合率
Web 検索
再現率
• 検索結果出力の閾値を小さくすると，出力が増えて
再現率が上がるが，不適切な出力も増えるため
一般に適合率は下がる
ページのランク付け
Web検索の仕組み
• 検索の手順
• ランク付けの基準
基準１：ページ内容の関連度
１．ユーザが検索語（キーワード）を入力
２．データベースを参照して，検索語を含むページを選び出す
３．選ばれたページにランク（順序）を付けて出力
ユーザが入力した検索語との関連が強いページを優先する
基準２：ページの重要度（人気度）
ユーザにとって重要と考えられるページを優先する
ページ収集
（クロール）
ページDB
照合
索引情報DB
ランク付け
検索語
• 検索語を含むすべてのWebページに対して，
総合得点＝関連度(基準１) ＋重要度（基準２）
索引作成
検索結果
を計算し，得点が高いページから順に表示
7
今日のまとめ
自習用問題１：ブーリアンモデル
（提出は不要）
• 応用（１）情報検索
– 情報検索の概要
– 索引付け
• tf・idf
– 情報検索のモデル
• ブーリアンモデル
• ベクトル空間モデル
– 情報検索システムの評価
• 適合率，再現率，F 値
– Web検索
自習用問題２：ベクトル空間モデル
問１．２ページ後に掲載している３枚の音楽CD（アル
バム）のレビュー文から，CDごとに索引語（下線部）
を抽出し，転置索引を作成しなさい．
問２．この転置索引を用いて，次の２つの検索質問に
対する検索結果を求めなさい．
q1：「元気な曲と切ない曲の両方が入っているCD」
（「元気」 AND 「切ない」）
q2：「元気な曲と切ない曲のいずれかが入っているCD」
（「元気」 OR 「切ない」）
レビュー文データ
（複数の人が書いたレビュー文を，CDごとにまとめて１つの文書と見なす）
問１．次ページに掲載している３枚の音楽CDのレビュ
ー文から，CDごとに索引語（下線部）を抽出し，文
書ベクトルを作成しなさい．ただしベクトルの成分の
値として，各索引語の出現頻度（回数）を用いる．
問２．この文書ベクトルを用いて，次の２種類の検索
要求に対する検索結果を求めなさい．
q1：「元気な曲も聴きたいし切ない曲も聴きたい．ただし
これら２つの要望の重み（優先度）は同程度」
q2：「元気な曲も聴きたいし切ない曲も聴きたい．ただし
元気な曲よりも切ない曲を重視（優先）する」
１．「I LOVE YOU」
２．「ハチミツ」
３．「love the world」
聴いて幸せな気持
ちになれました．
幸せな気持ちで
いっぱいです！夏
の終わりを歌い上
げる．サザンより夏
らしい．夏を感じる．
幸せな思い出となる
明るい曲．元気がで
る．最高の幸せ！
明るいポップなメロ
ディーが印象的．
明るい気分になる．
夏の気分になれる．
歌詞が切ない．
切ない感じの曲．
明るい二人の世界．
明るい曲から
切ない曲まで入っ
ています．
元気がでる曲．
サビの切ないメロ
ディーがいい．
夏に踊りたい．
優しい気持ちにな
れます．
優しい気持ちに胸
を打たれます．
幸せが詰まってい
ます．
8

Download Report