IIR 2章まとめ

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

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

発表スライド：

• Term Vocabulary and Postings Lists (IIR Ch. 2) (PDF)
• Term Vocabulary and Postings Lists (IIR Ch. 2) (PowerPoint)

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

参考：

• スタンフォード大学の講義ページ
• IIR Ch. 2 (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 のコストの方が高いため。