首都大学東京自然言語処理研究室(小町研)で行われたウェブマイニング勉強会(別名 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 形式のスライドのものです。
参考:
Document ingestion (p.1)
Recall the basic indexing pipeline
前回の復習。文書をインデキシングするステップは、大きく分けると以下の 3 段階。
- Tokenizer でトークンの並び (Token stream) に
- Linguistic modules でトークンを変換 (Modified tokens に)(正規化、見出し語化など)
- 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 件のコメント:
コメントを投稿