2014年4月26日土曜日

IIR 2章まとめ

首都大学東京自然言語処理研究室(小町研)で行われたウェブマイニング勉強会(別名 IIR 勉強会)第2回の参加メモです。

今回の範囲は、2章の Term Vocabulary and Postings Lists です。

発表スライド:

以下、ページ番号は上記 PDF 形式のスライドのものです。

参考:

Document ingestion (p.1)

Recall the basic indexing pipeline

前回の復習。文書をインデキシングするステップは、大きく分けると以下の 3 段階。

  1. Tokenizer でトークンの並び (Token stream) に
  2. Linguistic modules でトークンを変換 (Modified tokens に)(正規化、見出し語化など)
  3. Indexer で転置インデックスに

Parsing a document

文書のフォーマット、言語、文字コードを認識する必要がある。

これは、機械学習の問題として扱うこともできる(後ほどの章で出てくる)。

だが、実際にはヒューリスティックに行われることが多い。

Complications: Format/language

1つの文書に複数の言語、複数のフォーマットが含まれることもある。

例:フランス語のメールにドイツ語のファイルが添付されていたり、英文が引用されていたり

これらの機能をもつ、商用またはオープンソースのライブラリがある

(商用だとベイシスの Rosetta、オープンソースだと Apache Tika とかが有名かな)

Complications: What is a document?

文書をどの粒度で扱えばよいか?

なにをもって文書(”documents”)とするか?

  • ファイル
  • メール(複数の添付ファイルがあったり)
  • 複数のファイル(HTMLにPPTやLaTeXが含まれていたり)

Tokens (p.6)

Tokenization

トークンに分割する処理。以下はトークナイズの例。

入力:

  • “Friends, Romans and Countrymen”

出力:

  • Friends
  • Romans
  • Countrymen

これらのトークンは、まだインデックスのエントリーの候補(後続の処理で変化しうる)。

では、どのようなトークンを出力するのがよいだろうか?

  • Finland’s capital (sを含めるか?アポストロフィーを含めるか?)
  • Hewlett-Packard (分けて2つのトークンにするか?くっつけて1つのトークンにするか?小文字にするか?)
  • San Francisco (単一のトークンとして扱うか? 2つに分けるか?)

Numbers

以下のような文字列を、どんなトークンにすればよいか?

  • 3/20/91 (日付表現)
  • Mar. 12, 1991 (日付表現)
  • 20/3/91 (日付表現)
  • 55 B.C.
  • B-52
  • 324a3df234cb23e (PGP key: 16進数)
  • (800) 234-2333(住所?電話番号?)

昔の検索システムは、数値を含むようなトークンをインデキシングしなかった(posting が長くなりすぎるのが理由?)。

だが、Webで何かのエラーコードを調べるときなどには、非常に有用である。

「メタデータ」として、(ボディとは別のフィールドに)インデキシングされることもある。例えば、「作成日時」や「フォーマット」など。

Tokenization: language issues

トークナイズには、言語固有の問題もある。

フランス語

  • L’ensemble (1つにするか2つにするか?)

ドイツ語

複合名詞の例

  • Lebensversicherungsgesellschaftsangestellter (これは分けた方がいいよね)

(‘life insurance company employee’という意味)

ドイツ語ではcompound splitter moduleが有効 (パフォーマンスが 15% 上がる)

(小町さん曰く)コレクションのサイズによっても適切なトークナイズはかわってくる。データが増えてきたら、分けない方がprecision上がる。Google はたぶん両方やってる?

中国語

中国語と日本語はスペース区切りがない(複数のトークナイズの候補がありうる)。

  • 莎拉波娃现在居住在美国东南部的佛罗里达。

日本語

日本語は、ひらがな、カタカナ、ローマ字、漢字を含む(日付や量の表現も複数ある)。

クエリを全てひらがなで書くこともできてしまう。

  • フォーチュン500社は情報不足のため時間あた$500K(約6,000万円)

(なんか日本語変だけど…)

アラビア語・ヘブライ語

アラビア語やヘブライ語では右から左に書かれる。ただし、数字は左から右に読む。

Unicode での表現では、surface presentation は複雑に見えるが、保存されている形式は単純になっている(その他の言語と同じ並び)。

Terms - The things indexed in an IR system (p.13)

Stop words

よく出てくる単語 (a, and, to, be など) を省く処理(頻出 30 単語で全体の30%以下を占める)。

ただし、ストップワードの処理はトレンドではない。なぜなら、

  • インデックスの圧縮で、サイズの問題は軽減できる(5.3 で扱う)
  • クエリ最適化の手法 (7章で扱う) で、ストップワードの単語の処理時間もそれほど気にならない
  • フレーズにすることで役に立つ例
    • ”King of Denmark”
    • “Let it be”, “To be or not to be”
    • “flights to London” (「関係」を表す単語。”to” に意味が含まれているので残すべき)

Normalization to terms

単語の正規化の処理。

ピリオドやハイフンを取ったりして、単語を「正規化」する。

  • ピリオド:U.S.A. を USA に
  • ハイフン:anti-discriminatory を antidiscriminatory に

正規化された単語は、「辞書」のエントリーになる。

Normalization: other languages

  • アクサン:”résumé” を “resume” に
  • ウムラウト:”Tübingen” を “Tuebingen” に

  • 複数の日付の表現:7月30日 と 7/30

トークナイズと正規化の問題は、言語判定と密接に関わってくる。

例えば、以下の文の MIT はマサチューセッツ工科大学か、ドイツ語の “mit” か?

  • Morgen will ich in MIT

正規化において最も大事なのは、ユーザの書くクエリに合わせること。

Case folding

基本的には、全て小文字にするが、以下のような例外もある。

  • General Motors
  • Fed vs. fed
  • SAIL vs. sail
  • C.A.T. (Googleでは2011年までCaterpillar Inc.の意味にならなかった)

ただし、ユーザはよく小文字で入力しちゃうので、全て小文字にするのが一番良かったりする。

Normalization to terms

もう一つの方法は、ユーザの入力をクエリ展開すること。この展開は非対称的になる。

  • 入力:window, 検索語:window, windows
  • 入力:windows, 検索語:Windows, windows, window
  • 入力:Windows, 検索語:Windows

この方法は、より強力ではあるが、パフォーマンスは下がる。

Thesauri and soundex

3章と9章で詳しく扱う。

シノニム(類義語)とホモニム(同音異義語)

  • car = automobile
  • color = colour

インデックスを作るときに正規化してしまう方法と、クエリ展開でやる方法がある。

スペル訂正

発音に注目して正規化する、Soundex という方法がある。

Stemming and Lemmatization (p.21)

Lemmatization

見出し語化。

  • am, are, is → be
  • car, cars, car’s, cars’ → car

Lemma というのは、辞書の見出し語の形を意味している。

(辞書を使う、言語処理的な方法)

Stemming

語幹を取り出す処理。

  • automate(s), automatic, automation → automat

(ヒューリスティックな方法で、言語に依存する)

Porter’s algorithm

英語で最もよく使われているステミングアルゴリズム。

ふつう、5段階の処理がある(それぞれ順番に処理する)。

末尾(接尾辞)が最長一致するルールを適用して変換を行う。

  • sses → ss
  • ies → i
  • ational → ate
  • tional → tion

末尾の “EMENT” は、その前に2文字以上あれば削る。

  • replacement → replac
  • cement → cement

Other stemmers

その他のステミングアルゴリズム。

  • Lovins stemmer (1発で処理できる)
  • Paice/Husk stemmer
  • Snowball
  • 形態素解析してlemmatization(そこまで大きな効果はない、らしい)

Language-specificity

以上の方法は、言語依存だし、アプリケーション依存でもある。

オープンソースで公開されているものを使うのがよい。

Does stemming help?

  • 英語:Recallは上がるが、Precisionが下がることも
  • スペイン語、ドイツ語、フィンランド語では有用

Faster postings merges: Skip pointers/Skip lists

Recall basic merge

posting のマージアルゴリズムの復習(図を参照)。

このアルゴリズムの計算量は O(m+n) → もっと効率的にできないか?

Augment postings with skip pointers (at indexing time)

posting の中の docId に、スキップポインタを持たせる(図を参照)。

Query processing with skip pointers

上の posting が 41、下の posting が 11 を見ている瞬間を考える(図を参照)。

スキップポインタの場所を見ているとき、スキップ先(31)を見て、それと比較する。

41 と 31 を比較すると、31 の方が小さいので、下の posting は 31 までスキップできる。

Where do we place skips?

このスキップポインタの方法には、トレードオフがある。

スキップポインタを多くする(スキップの幅を小さくする):

  • スキップポインタの比較回数が多くなる
  • メモリ量もくう

スキップポインタを少なくする(スキップの幅を大きくする):

  • スキップの成功回数が少なくなる

Placing skips

√L (Lは posting の長さ) をスキップポインタの間隔とする方法 (Moffat and Zobel 1996)

インデックスが静的っぽいなら簡単。

動的なインデックスでは、 L が変化し続けるので難しい。

また、この方法は、単語の分布を無視している(静的に構築する場合で、単語の分布が分かっていれば、ある程度 L を予測できるかもしれない)。

全部オンメモリで処理するのでなければ、この方法は確実に有効である(Bahle+ 2002)。

なぜなら、メモリ上で posting をマージするコストより、posting を読み出す IO のコストの方が高いため。

2014年4月22日火曜日

Introduction to Information Retrieval (IIR) 1章まとめ

首都大学東京自然言語処理研究室(小町研)で行われたウェブマイニング勉強会第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

  1. トークナイズ (文字列を単語に分割)
  2. 正規化 (例: U.S.A. を USA に)
  3. ステミング(例: authorize と authorization を同一視)
  4. ストップワードの処理(例: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 (法律の検索システム)

http://www.westlaw.com/

同義語(シノニム)の展開も含め、ユーザがクエリを組み立てていた。

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”(* はワイルドカードの演算子)