首都大学東京自然言語処理研究室（小町研）で行われたウェブマイニング勉強会第1回に参加してきました。
今回の範囲は、1章のBoolean Retrievalで、発表者は小町さんでした。
発表スライドはこちらです：
参考：
以下、ページ番号は上記PDF形式のスライドのものです。
遅刻したのでスライド 8ページ目から（以下、ページ番号は上記スライドのもの）。
Term-document incidence matrices (p.8)
Unstructured data in 1620
非構造化データから検索を行うのが難しいという話。
たくさんのシェイクスピアの作品から、”Brutus AND Caesar but NOT Calpurnia”の条件を満たす作品（BrutusとCaesarを両方含み、Calpurniaを含まない作品）を探すことを考える。
一つの方法は、grep を使うことだが、これは正解ではない。
- NOT のような複雑な条件での検索ができない
- テキストのサイズが大きくなると遅い
- ある単語 (countrymen) の近くに出現する単語 (Romans) を探すことも現実的ではない
- スコアによるランキングができない
Term-document incidence matrices
単語 (term) を行、文書 (document) を列とする行列を考える（p.10の図参照）。
単語がその文書に出現するときは要素を 1、それ以外は 0 とする（一般的にはほとんど 0 になるので、非常にスパースな行列になる）。
すると、各単語ごとに 0/1 を要素とするベクトルを得る。
“Brutus” と “Caesar” と “Calpurnia” が全て出てくる文書（作品）を探すには、これらに対応する 3つのベクトルに対して、ビット演算の AND をとればよい。
- 110100 AND
- 110111 AND
- 101111 =
- 100100
よって以下が答えだと分かった（そうですか）。
- Antony and Cleopatra, Act III, Scene ii
- Hamlet, Act III, Scene ii
Bigger collections
文書数が 1 億とかになるとけっこうつらい。
行列のサイズを M x N とすると、
- N = 1 million documents
- 1000 words
- 6 bytes/word
- 6GB of data
- M = 500K distinct terms
よって 1 億 x 50 万の行列になる。無理。
もっとよい表現はないか？
The Inverted Index (p.15)
Inverted Index
各単語 t に対して、t を含む文書のリスト（posting list と呼ぶ）を格納する（p.17 の図参照）。
それぞれの文書は、docID というシリアル番号で区別する。
可変の posting list は、データ構造の双方向リスト (Linked List) で実装できる。
posting list は docID の昇順でソートしておく（理由は posting のマージの節で説明）。
Inverted index construction
- トークナイズ (文字列を単語に分割)
- 正規化 (例： U.S.A. を USA に)
- ステミング（例： authorize と authorization を同一視）
- ストップワードの処理（例：the, a, to, of を捨てる）
ちなみに、Google はステミングやストップワードの処理はやってない。Python の NLTK （ツールキット）にストップワードの一覧が入っているので参照するとよい（小町さん談）。
Indexer steps
2 つの文書をインデキシングする様子を見る。
トークンの列を、(Modified token, Document ID) のペアの並びにする。
単語をソート（辞書順、docID順）
1つの文書に同じ単語が現れているペア同士はマージ
単語は Dictionary に、docID は Posting に分割する（辞書には、単語頻度の情報も付加する。Query optimizationのところで説明）
Query processing with an inverted index (p.24)
Query processing: AND
インデックスはできたが、どうやってクエリを処理するか？
まず、単語を辞書でひき（2分探索でできる）、それぞれに対応する posting を取得する。
次に、2 つの posting をマージする（文書集合どうしの intersection）
The merge
マージのアルゴリズムについて（p.28 の疑似コード参照）。
2 つのリストの先頭を見て、異なっていたら docID が小さい方のリストの次の要素を見る。
docID が同じだったら、結果に追加する。
2 つのリストのサイズをそれぞれ x, y とすると、O(x + y) で計算できる。
前提：docID のリストがソートされていること
The Boolean Retrieval Model & Extended Boolean Models (p.29)
ブーリアンモデル（Boolean retrieval model）は、AND, OR, NOT を組み合わせたブーリアンクエリで問い合わせを行うことができるもの。
IR システムの最も基本的なモデル。
ブーリアンモデルは最近までずっと使われていた。電子メールや図書館の検索、少し前の Spotlight も。
例： WestLaw （法律の検索システム）
同義語（シノニム）の展開も含め、ユーザがクエリを組み立てていた。
Query optimization
AND クエリの処理を思い出すと、長い posting には、そのサイズに比例した時間がかかる(O(x + y))。
AND が複数ある場合、クエリをどの順番で処理するかによって処理時間が大きく変わる。
例（p.36参照）：(Calpurnia AND Brutus) AND Caesar
More general optimization
例：(madding OR crowd) AND (ignoble OR strife)
まず、全ての単語の posting を取得する。
次に、それぞれの OR クエリを処理した結果を推定する。
この推定値には、それぞれの posting のサイズ、つまり単語頻度を足したものとする（最悪の場合を考えている）。
この推定値が小さいものから順に AND クエリを処理する。
Exercise
以下のクエリは、どの順番で処理すればよいだろうか？
(tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes)
（p.38の単語とその頻度のテーブルを参照）
Phrase queries and positional indexes (p.41)
Phrase queries
“stanford university” というフレーズ（単語の順序を考慮したもの）で検索したい。
“I went to university at Stanford” という内容の文書はヒットしてほしくない。
A first attempt: Biword indexes
最も単純なのは、2 単語を 1 つの単語と見なす方法。
3単語以上のフレーズクエリで false positive が防げない。
また、インデックスサイズも大きい。
Solution 2: Positional indexes
posting に、docID に加えて各文書での位置情報を付加する。
<term, number of docs containing term;
doc1: position1, position2 ... ;
doc2: position1, position2 ... ;
etc.>
false positive のないフレーズクエリが可能。
ただし、インデックスサイズは大きくなる。
Proximity queries
単語どうしの近さを指定して絞り込める。
例：LIMIT! /3 STATUTE /3 FEDERAL /2 TORT
（/k は、 k 単語以内という意味を表す）
効率的に Proximity queries を処理する方法については、IIR の Fig 2.12 を参照。
Structured vs. Unstructured Data (p.54)
IR vs. databases: Structured vs unstructured data
構造化データ（DB）: 数値の範囲検索など
非構造化データ：キーワード、概念（コンセプト）での検索
Semi-structured data
半構造化データ。
タイトルや箇条書きの部分など、文書の中の構造（場所）を指定して検索できる。
例：タイトルに “data”、箇条書きに “search” と書かれている文書を検索
例：タイトルに “Object Oriented Programming” 、著者が “stro*rup”（* はワイルドカードの演算子）
0 件のコメント:
コメントを投稿