IIR輪講復習 #1 Boolean retrieval

お知らせ たつをさんによる補足情報 http://chalow.net/clsearch.cgi?cat=IIR わかりやすい。今後もお願いします。

参考 http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 本資料は書籍の輪読会に向けたサマリ 資料内で一部上記ドキュメントからの引用あり

Information Retrieval とは Large collections (≒ コンピュータに保存されたデータ) から 欲しい情報の Unstructured nature (≒ テキスト) を含む Material (≒ドキュメント) を探す

Unstructured data コンピュータで扱いやすいようにはなってない → 検索しやすいように

情報検索のスケール システム構成はスケールに依存する 大: Web検索 中: ドメイン特定の検索、業務検索 小: 個人検索 (デスクトップ検索)

テキスト走査とインデックス

テキスト走査 O(N) grep Pros Cons 実装が容易 正規表現 大量のドキュメントに向かない 「複数のドキュメントから、一番欲しいドキュメントを検索する」(ranked retrieval) に向かない

インデックス Pros 大規模データを高速に検索 Ranked retrieval Cons 設計/実装が大変 ← これの勉強をしましょう

行列インデックス

Boolean Retrieval “渋谷” AND “ラーメン” AND NOT “とんこつ”

行列インデックス → 転置インデックス “Naive way” 大量にドキュメントがあるとメモリに載らない。インデックスが大きすぎる。 ほとんど 0 → 1 だけを記録するインデクスへ = 転置インデックス

転置インデックス 索引語 (term) => @docID (postings list)

転置インデックス dictionary をメモリに postings をディスク上 (外部ファイル化)

転置インデックスの簡単な作り方 インデックス化する文を取得 トークナイズ 言語上の (linguastic) 前処理 Friends, Romans, Countrymen So let it be with Caesar トークナイズ Friends|Romans | Countrymen |So | ... 言語上の (linguastic) 前処理 friend | roman | countryman | so | ... term => (docID) のデータ構造に friend => 1, roman => 1, countryman => 1

転置インデックス完成一歩手前

merge してソート → 完成

転置インデックスのソート dictionary はアルファベット順 posting list は docID 順 dictionary から term を探しやすいように posting list は docID 順 Boolean retrieval での Intersection 時のアルゴリズムに有利なように

posting list に向いているデータ構造 単方向リスト 可変長配列

転置インデックスと Boolean 検索 Brutus AND Calpurnia Brutus を dictionary から探す Brutus の posting list を取得 Calpurnia を dictionary から探す Calpurnia の posting list を取得 共通部分の抽出 (Intersect)

Intersect

より複雑な Boolean Retrieval (A or B) and (C or B) and (D or E) term の出現頻度を使って Intersection の演算回数を極力少なくするよう、クエリを再構成する × 各箇所の intersection を個別に行って 中間データを最後に merge ○ intersect されたデータに次の posting list を intersect メモリに結果を残したまま演算できる

出現頻度を使う / 逐次処理

Web検索と Boolean retrieval 自然言語での検索 (free text queries) より Boolean model 基本的な Boolean で十分 (AND, OR, NOT)

更に考慮すべきこと よりリッチなクエリモデル より効率のよいインデックスの構造 クエリのスペルミス対策 (もしかして) フレーズ検索 (“Operating System”) DF (document frequency)に加えて TF (term frequency) の保存 Ranked retrieval ... Rank, score 次章以降で

適合率と再現率 Precision (適合率) Recall (再現率) 「全検索結果」に対して「検索要求を満たす結果」の割合 “MacBook Air 重さ” で 100件 ヒット、うち 85 件が重さがわかるドキュメント = 85/100 = 0.85 Recall (再現率) 「検索要求を満たす全ドキュメント」に対しての「検索要求を満たす検索結果」の割合 Web上に 90件あると仮定して、ウェブ検索して 85 件が得られた → 85/90 = 0.94

まとめ 大規模データには転置インデックス 最適化していくべきもの 適合率と再現率の両方が高くなるように 転置インデックスの作成手順、データ構造 何を保存するか それをどのように前処理して保存するか どういう形で保存するか どのように走査するか 検索クエリの最適化 Boolean Retrieval のアルゴリズム 適合率と再現率の両方が高くなるように