スライド 1

Size: px

Start display at page:

Download "スライド 1"

ふさこひがき
5 years ago
Views:

1 知識情報演習 Ⅲ( 後半第 2 回 ) 辻慶太 1

2 情報検索システムの世界観情報の生産者研究者, 作家, 記者など情報の最終利用者 ( エンドユーザ ) 生産情報の登録者 DB 登録者, 分類者, 索引作成者など登録検索計算機上のシステム検索エンジン,DB, インタフェースなど支援蓄積される情報図書, 雑誌, 画像, 音声など人間の仲介者代行検索者, 図書館員などオフライン処理オンライン処理 2

3 情報検索の基本モデル情報解釈情報要求文書索引付け検索質問内部表現照合内部表現狭義の情報検索 3

4 索引付け? ブックマークでタグを付けるようなイメージ南アジアのというページに対して, この人は : University, Science, 図書館オープンアクセスといったタグを付けている = 索引を付けている 4

5 照合索引語を中継して検索質問と文書を照合し, 条件に一致する文書を取得する図書館というキーワードで検索してくる人がいたら, 図書館という索引語が付与された文書がないか探す 2 つの検索モデルに大別することができる完全一致 (exact match) 最良一致 (best match) 図書館という索引語が付与された文書だけを出力する図書館という索引語が付与されていなくても, 何となく 5 図書館に関する文書と判断できるならば出力する

6 照合索引語を中継して検索質問と文書を照合し, 条件に一致する文書を取得する図書館というキーワードで検索してくる人がいたら, 図書館という索引語が付与された文書がないか探す 2 つの検索モデルに大別することができる完全一致 (exact match) 最良一致 (best match) 図書館という索引語が付与された文書だけを出力する図書館という索引語が付与されていなくても, 何となく 6 図書館に関する文書と判断できるならば出力する

7 照合索引語を中継して検索質問と文書を照合し, 条件に一致する文書を取得する図書館というキーワードで検索してくる人がいたら, 図書館という索引語が付与された文書がないか探す 2 つの検索モデルに大別することができる完全一致 (exact match) 最良一致 (best match) 図書館という索引語が付与された文書だけを出力する図書館という索引語が付与されていなくても, 何となく 7 図書館に関する文書と判断できるならば出力する

8 照合索引語を中継して検索質問と文書を照合し, 条件に一致する文書を取得する図書館というキーワードで検索してくる人がいたら, 図書館という索引語が付与された文書がないか探す 2 つの検索モデルに大別することができる完全一致 (exact match) 最良一致 (best match) 図書館という索引語が付与された文書だけを出力する図書館という索引語が付与されていなくても, 何となく 8 図書館に関する文書と判断できるならば出力する

9 完全一致ブーリアンモデルが代表的古典的なキーワード検索論理演算子 (AND,OR,NOT) で式を構成例 : 中華料理 AND レシピ NOT スープ論理式に一致する文書だけが検索されるただし, 厳密な NOT ではないことが多い絞込み情報としての利用が中心例 : NOT 犬犬を含まない文書が全て出るわけではない 9

10 最良一致文書が検索質問に一致する度合い ( スコア ) を計算するスコアを用いて文書を順位付けて表示するスコア : Retrieval Status Value (RSV) 検索質問は, キーワードの集合として表現 bag-of-words キーワード間の関係や語順は無視 10

11 最良一致の代表的なモデルベクトル空間モデルシステムの例 : SMART 確率型モデルシステムの例 : OKAPI どちらのモデルも 1970 年代に提案され, 現在も改良が重ねられている両モデルの検索精度に大きな違いはない 11

12 最良一致の代表的なモデルベクトル空間モデルシステムの例 : SMART 確率型モデルシステムの例 : OKAPI 文書と検索式を共に言葉の頻度ベクトルなどで表し, 両者の内積が高い文書を出力する OKAPI BM25: 文書 d がキーワード q に適合している確率を推定し, 値が高いものを出力するどちらのモデルも 1970 年代に提案され, 現在も改良が重ねられている両モデルの検索精度に大きな違いはない 12

13 索引付けの手順概要 (1) 索引語の抽出文字バイグラム, 単語, フレーズなど (2) 不要語の削除 (3) 接辞処理 (4) 索引語の重み付け検索手法 ( 検索モデル ) によっては不要例えば, 論理式によるブーリアンモデルでは不要 (5) 索引ファイルの編成図書館システムからバイグラムを切り出すと図書書館館シシス 13

14 不要語 (stopword) 検索の役に立たない語 (they, might など ) 不要語辞書を用意しておくことが多い高頻度語 : WWW など機能語 : 前置詞(of) など語の分類内容語 : 名詞, 動詞, 形容詞など機能語 : 助詞, 助動詞, 冠詞, 前置詞など 14

15 接辞処理 (stemming) 活用形を原形に戻し, 索引語の表記を統一質問と文書における表記の違いを吸収いくつかの手法がある辞書の利用語尾の自動削除自動削除の場合は, 必ずしも言語学的に意味のある単位ではない点に注意例 : facility( 単数形 ),facilities( 複数形 ) どちらも facilit になるかもしれない 15

16 接辞処理 (stemming) 活用形を原形に戻し, 索引語の表記を統一質問と文書における表記の違いを吸収いくつかの手法がある辞書の利用語尾の自動削除 libraries という表記で検索してきた人に対しては library という表記で索引付けされている文献も出力したい自動削除の場合は, 必ずしも言語学的に意味のある単位ではない点に注意例 : facility( 単数形 ),facilities( 複数形 ) どちらも facilit になるかもしれない 16

17 ホデレ賞 (2008 年度 ) の受賞者が決まりました形態素原形品詞ホデレホデレ未知語賞賞名詞 ( ( 記号数字年度年度助数詞 ) ) 記号のの助詞受賞受賞名詞者者接尾辞がが助詞決まり決まる動詞まします助動詞たた助動詞記号手順 (1)~(3) の例上の例文に対する形態素解析結果赤字部分を索引語として抽出する 17

18 索引語の重み付けある文書を特徴付ける索引語には高い重みを与える伝統的な手法に TF.IDF 法がある TF: 索引語頻度 IDF: 逆文書頻度完全一致 ( ブーリアンモデル ) では不要ブーリアンモデルでは索引語にあるかないかだけ考えるどれくらいあるかは考えない 18

19 TF: 索引語頻度 Term Frequency(TF) ここで言う Term とは索引語を表す tf ( t, d) と表す文書 d における索引語 t の出現頻度なぜ用いるか? ある文書によく出現する索引語は, その文書をよく特徴付けるだろうという仮説に基づく 19

20 TF の例犬犬犬犬ネコネコ犬犬文書 A 文書 B tf ( 犬, A) 5 tf ( ネコ, A) 2 tf ( 犬, B) 1 20

21 IDF: 逆文書頻度 Inverse Document Frequency(IDF) 少数の文書にしか現れない索引語を重視する idf N ( t) log 1 df ( t) N: コレクション中の文書総数 df(t): 索引語 t が出現する文書数なぜ用いるか? TF だけでは問題がある TF が高い語は多くの文書に出現する為, 特定の文書を弁別する能力が低い 21

22 逆文書頻度 ( つづき ) N=100 の場合逆数を取ることで df(t) が小さいほど大きな値にする対数を取ることで変化分をなだらかにする 1 を足して, 重みを正数にする df(t) N/df(t) log(n/df(t)) log(n/df(t))

23 IDF の例動物ネコ動物犬犬動物犬ネコ動物犬ロボット動物動物犬 N = 5 df 動物 =5, 犬 =4, ネコ =2, ロボット =1 動物 =6, 犬 =5 idf( 動物 ) = 1 idf( 犬 ) = 1.32 idf( ネコ ) = 2.32 idf( ロボット ) = 3.32 idf の最小値動物では全文書が検索されてしまい, 弁別性が低い 23

24 TF.IDF 法による重みの計算簡単な計算方法 w( t, d) tf ( t, d) idf ( t) 文書 d における索引語 t の重み以下のような行列で表現できる w(t 2,d 3 ) の値 d 1 d 2 d 3 d 4 d 5 t 1 t 2 t 3 t 4 24

25 転置ファイルの例索引語文書 ID 索引語の重みハブハブ酒

26 オンライン処理 1 検索質問から索引語 ( 検索語 ) を抽出する 2 各索引語について索引から以下を取得するその索引語を含む文書の集合その索引語の重みw(t,d) 3 各文書のスコアを計算するその文書が含む検索語の重みを総和する 4 スコアに基づいて文書を整列 ( ソート ) する 26

27 オンライン処理の図解犬ロボット 1 索引語の抽出検索索引付け ( オフライン ) 文書集合 D1~D10 犬ロボット D2(0.1) D3(0.8) D5(1.2) D9(0.1) D1(1.3) D3(0.7) D5(0.1) 3スコアの計算 2 文書と重みの探索索引転置ファイル D1 = 1.3 D2 = 0.1 D3 = = 1.5 D5 = = 1.3 D9 = 文書の整列 1. D3 2. D5 3. D1 4. D2 5. D9 個別の文書を読む場合 27

28 演習 : Perl 入門が終了した人複数のテキストファイル ( 英文 ) を読み込んで, 単語の重み w(t,d) を計算するプログラムを作成せよここで,t = 1 つの単語,d = 1 つのファイル入力や出力の形式は各自で決めてよい入力するファイルの件数の大きさは段階的に拡張すること少ない件数の小さなファイルから始める 28

スライド 1

スライド 1 知識情報演習 Ⅲ( 後半第 2 回 ) 辻慶太 http://slis.sakura.ne.jp/cje3 1 情報検索システムの世界観情報の生産者研究者, 作家, 記者など情報の最終利用者 ( エンドユーザ ) 生産情報の登録者 DB 登録者, 分類者, 索引作成者など登録検索計算機上のシステム検索エンジン,DB, インタフェースなど支援蓄積される情報図書, 雑誌, 画像, 音声など