Comments
Description
Transcript
第1回 情報検索 - 知識ベース研究室
知識ベース特論 第1回 ―情報検索(1)― 吉岡真治 本講義のすすめかた n 情報検索とその応用 – 様々な情報検索モデル – 情報抽出・質問応答 n Semantic Web – コンピュータがWebページの意味(Semantic)を理解し、 組み合わせて問題解決にあたれるようにするための 方法論 n n n Web上の知識活用 授業資料（前日の午後には公開） http://www-kb.ist.hokudai.ac.jp/~yoshioka/kb/ 質問・レポートはメールで [email protected] 情報検索とデータベース検索 n データベース検索 – 特定の条件に合ったデータを検索 例：店舗情報のデータベースから、所定の条件を満 たす店を検索 n 情報検索 – ユーザの情報要求に応じた情報を検索 • ユーザの情報要求はデータベース検索のように は明示化されていない • 例：検索質問として「札幌 ラーメン」にどのような 情報を提供するのが適切なのかは、ユーザ依存 である。 曖昧な要求の取り扱い n 検索質問の曖昧性 – 検索質問に含まれる全ての単語を含んでいる文書 に必ず満足する訳ではない。 → 文書中での単語の役割や重要度などを考慮 – 検索質問に含まれる単語を含んでいなくても満足す る文書が存在する。 → 検索質問中の単語に対応する語が存在する 場合を考慮 情報検索システムを評価する指標 n 再現率と精度 検索文書集合中の正解文書数 再現率＝ 正解文書数 検索文書集合中の正解文書数 精度＝ 検索文書数 – 再現率と精度はトレードオフの関係 • 検索文書数を増やせば、再現率は上昇するが、 精度は減少する • 再現率を向上させるための技術は多くの場合、 精度を減少させる より良い情報検索のために n 検索質問との関連性が高い文書を判定 – ランキングを用いた情報検索モデル n 網羅的な検索の実現 – 検索語拡張 • 表記の違いの吸収 – シソーラスによる類義語展開 • 関連文書フィードバック（Relevance Feedback） – 関連文書に現れる語を関連概念を表す語として使って 検索式を拡張 – 表記が異なっていても、関連概念を表す語が共通な場 合がある。 – 検索語の重要度を推定するための利用法もあり 文書データベースのインデックス n インデックスの単位 – 単語ベース – 字面ベース n 出現位置情報の利用 – Bag of words – 出現位置処理 – 構文解析結果の利用 単語ベースインデックス n n 単語に分解して登録する 正規化 – 活用がある場合標準形に • 例：起きた⇒起きる – 代表表記 • 例：子供、こども⇒こども – 接辞処理(Stemming) • 例：library, librarian -> libra 単語ベースインデックス n 単語の単位 – 辞書ベース（辞書で単語としてある物を単語として 利用） • 形態素解析の結果などを利用 – 複合語（単語の意味を考えて長い単位を考慮） • 情報検索⇒情報＋検索ではなく、「情報検索」で 登録 • ただし、その場合、「情報を検索」とインデックス がマッチしない 字面ベースインデックスの種類 n nグラム – 単語ではなく、文字のならびに注目してインデックス を作成 – n個の文字列ごとに区切ってインデックスを作成 – 例：バイグラム（2-gram) • 情報検索：「情報」＋「報検」＋「検索」 • インターネット：「イン」＋「ンタ」＋「ター」＋「ーネ 」＋「ネッ」＋「ット」 – 辞書に依拠しないため、新語などに対応や細かな 表記ぶれには対応可能 • 例：「インタネット」 ：「イン」＋「ンタ」＋「タネ」＋「 ネッ」＋「ット」 • 多くのインデックスが一致 出現位置情報の考慮 n 出現位置を考慮しないインデックス – Bag of words アプローチ（単語がどのような位置に あったかを考慮しない） n 出現位置情報の利用 – 出現位置情報を利用して、単体でのインデックスを 組み合わせた複合インデックスが利用可能 – 近接演算子：ある一定の近さに単語があることを要請 • 例：映画＋（5文字）＋情報＋（5文字）＋検索 – 映画情報検索：○ – 映画の情報を広く検索する:○ – 映画の情報。映画の後のレストラン検索：× 構文解析結果の利用 n 構文解析 – 係り受け関係に基づいたインデックスの作成 • 例：映画の情報を検索する 映画の 情報を 検索する 映画⇒情報 情報⇒検索 自然言語処理ツールの解析結果の利用 n 利用可能な解析結果 – 代表表記（JUMAN) • インド・印 – 語・句の同義表現 • 障害・バリア・妨げ – 係り受け関係（KNP) • インドの経済発展の障害 インドの 印 経済 発展の 障害 妨げ バリア 検索クエリの柔軟な扱い n 重要な表現、不要な表現の検出 – 基本的には単語は必須・係り受けは加点 n 例外 – 係り受けを必須にする場合 • 固有名、漢字一文字の連続、つながりの強い複 合名詞 – 単語を必須にしない場合 • 意味がオプショナルな場合 • 固有名とそのカテゴリ 情報検索モデル n n Bag of Wordsアプローチが基本 完全一致モデルと部分一致モデル – 完全一致モデル：検索式と完全に対応が取れた文 書のみを候補に • ブーリアン式を用いたデータベース検索に近い モデル – 部分一致モデル：検索式の一部と対応が取れれば 候補に • 検索式との対応関係を元にしたランキングを行う モデル 完全一致モデルと部分一致モデルの特徴 検索される 文書 ユーザに 対する仮定 部分マッチ 全ての検索語 ユーザは適 モデル を含む必要は 切なキー ない ワードを選 択すること が困難 検索式の 可読性 多くの検索語 を用いる場合、 検索式と結果 の関係を理解 するのが困難 完全マッチ 必要とされる ユーザは適 検索式を満た モデル 検索語は必ず 切なキー している理由を 含む ワードを選 確認することが 択可能 容易 ブーリアンモデル Boolean Model n 検索要求をブーリアン式として表現 – 検索要求：サッカーのチームを知りたい。ただ、フット ボールと書く場合もある。でも、ラグビーやアメフトの ページは除きたい。 – 検索式：（（フットボール or サッカー） and チーム and not(ラグビー or アメフト)) n 特徴 – 検索式との完全マッチ • ユーザは検索語を適切に選ぶ必要性が高い – 適切なブーリアン式の形で表現するのが難しい – ランキングができない 拡張ブーリアンモデル n ブーリアン検索式との親和性に基づき文書をラ ンキングする手法 – ブーリアン検索式に含まれる語だけを用いてベクト ル空間を構成し、ベクトル空間によるランキングを 行う。 A B C A and B and C 部分一致モデル n 代表的なモデル – TF・IDFモデル • 文書中で顕著に現れる語は何かという指標である TF (Term Frequency)と語の一般性を表す指標であ るIDF (Inverted Document Frequency)の組み合 わせにより文書の適合度をランキング – 確率モデル • 検索要求に含まれる語が適合文書に含まれる確 率を考えることにより、各々の文書の適合度をラ ンキング – ベクトル空間モデル • 主に語の存在に対応する基底ベクトルから構成 されるベクトル空間を構成し、ベクトルの類似性 を評価し文書の適合度をランキング TF・IDFモデル n 検索語の重要性の指標 – Term Frequency (TF): 文書中での語の出現頻度 • 文書を特徴付ける重要な語は繰り返し用いられる – 全文書集合中における語が含まれる文書数(DF)の逆数 • 多くの文書に存在する語（一般性の高い語）は、検索 に役立ちにくい • TFに比べてDFはオーダーが大きく異なるため、単な る逆数を使うのではなく、対数を用いることが多い N tf × log ∑ wi df wi wi ∈Q Q : 検索語の集合、w：検索語 i tf w：各文書中における wiの頻度 i df w：文書データベース中 のwiを含む文書数 i N：全文書数 n 各文書において、検索式に含まれる各々の語につ いて重要性の指標を計算し、その和を計算 確率モデル n 検索語の重要度の指標 – 適合文書中の語の存在確率により評価 • 多くの適合文書に存在する語は役に立つが、多 くの文書に存在する語は役立ちにくい(IDF的指標) – 文書中での語の出現頻度に基づく指標（TF的指標） を組み合わせて利用 n 語の存在に関する独立性を仮定 g (d ) = log P( R | d ) P(d | R) P( R) = log + log 文書ｄのスコア P( R | d ) P(d | R ) P( R ) P(d | R) = ∏ P( X i = 1 | R) ti ∈T P(d | R ) = ∏ P( X i = 1 | R ) ti ∈T g (d ) = ∑ log ti ∈T ∏ P( X = 0 | R) Rである場合に、Tだけを含む文書を生成する確率 j t j ∈Q −T ∏ P( X j = 0 | R) t j ∈Q −T P( X j = 0 | R) 1− p j P( X i = 1 | R) p P( R) P( R) + ∑ log + log = ∑ log i + ∑ log + log P( X i = 1 | R ) t j ∈Q −T P( X j = 0 | R ) P( R ) ti ∈T pi t j ∈Q −T 1− p j P( R ) 確率モデル n 検索性能の良いシステムが提案されている – Okapi/BM25 • Robertson Sprck Jonesの指標 w(1) = log (r + 0.5) /( R − r + 0.5) (n − r + 0.5) /( N − n − R + r + 0.5) r: 語Tを含む適合文書数、n: 語Tを含む文書数 R: 全適合文書数、N: 全文書数 • 各文書のスコアリング – 文章中の長さで正規化 (1) w ∑ T ∈Q (k1 + 1)tf (k3 + 1)qtf K + tf k3 + qtf tf : 文書中のTの頻度 qtf : 検索式中のTの頻度 K = k1 ((1 − b) + b × document length ) average document length w(1): 文献中の語Tの重み（Roberson Sparck Jones) k1,k3,b: パラメータ（デフォルトk1=1,k3 =1000,b =1) ベクトル空間モデル n 検索語の存在を基底とするベクトルで構成され るベクトル空間で表現 – 文書と同様に検索式をベクトル空間で表現し、類似 度を評価 n 類似度の評価指標 – ベクトル距離 – 内積 – 余弦尺度（文書の長さによる正規化） n ベクトルの各次元の値 – 語の頻度 – TF・IDFの利用 言語モデル n n 文章を生成するための言語モデルを推定し、 その類似度によって、検索を行う手法 言語モデルの例 I wish I wish I wish I wish I wish I wish I wish q qが終わる確率0.2 unigram単語の発生確率 P(“a”)= 0.2 P(t ) = 1 P(“the”)= 0.1 ∑ t∈V P(“frog”)=0.05.... a frogという文の生成確率 (0.2*0.05)*0.8*0.2 言語モデルによる検索 n クエリが与えられた時に各々のドキュメントが 生成される確率が高い順に文書をランキング – クエリの言語モデルを推定するのは難しいので、文 書の言語モデルをあらかじめ推定しておき、その言 語モデルを用いてランキングを行う。 P(d | q) = P(q | d ) P(d ) P(q) P(q | M d ) = K q ∏ P(t | M d ) t∈V tft ,q , Kq = Lq ! tft1 ,q ! f t2 ,q !! f t M ,q ! 言語モデルの推定 n 単純なモデル – 文書中の単語頻度から推定 • 文書中に現れていない単語が存在すると確率が 0になる。 tf Pˆ (q | M d ) = ∏ Pˆmle (t | M d ) t ,q t∈V n ⎛ tf = ∏ ⎜⎜ t ,d t∈V ⎝ Ld ⎞ ⎟⎟ ⎠ tft ,q スムージング – コーパス中での単語の出現確率を考慮に入れたス ムージング Pˆ (t | M d ) = λPˆmle (t | M d ) + (1 − λ ) Pˆmle (t | M c ) ˆ (t | M ) tf + α P t , d c Pˆ (t | M d ) = Ld + α グラフィカルモデルによる表現 n 情報検索とグラフィカルモデル 持橋 大地 氏（統計数理研究所 准教授） http://www.quantmedia.org/ias2013/IFAT2013Graphical.pdf 検索式の修正 n 関連文書フィードバック – 検索語の重み付けの修正 – 検索語の追加 n 単純なモデル – 初期検索式＋関連文書＝新しい検索式 北海道大学 情報科学研究科 コンピュータサイエンス専攻 コンピュータサイエンス専攻 のページ 教員名 原口誠、吉岡真治… … ＋ – 重みの修正(rocchioの式) ! ! ! q ' = α × q + (1 − α ) × d ＝ 北海道大学 情報科学研究科 コンピュータサイエンス専攻 原口誠、吉岡真治、… 検索語の追加 n シソーラスの利用 – 人手で構築したシソーラスの利用 • 関連語・同義語を追加 – 自動構築したシソーラスの利用 • 共起関係などの統計的情報に基づくシソーラス • DICE係数によるシソーラス Dice(t x , t y ) = 2 × p (t x , t y ) p (t x ) + P(t y ) • 文書データベースが持つ性質を反映 n 単純な検索語の追加の場合は、自動構築のシ ソーラスのほうが検索性能の向上に役立つこ とが多い 参考文献 n Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008. http://nlp.stanford.edu/IR-book/informationretrieval-book.html