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 のコストの方が高いため。

0 件のコメント:

コメントを投稿