IIR輪講復習 #2 The term vocabulary and postings lists

お知らせ たつをさんによる補足情報 復習資料おきば http://chalow.net/clsearch.cgi?cat=IIR http://bloghackers.net/~naoya/iir/ppt/

参考 http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html 本資料は書籍の輪読会に向けたサマリ 資料内で一部上記ドキュメントからの引用あり

第2章前半の概要 インデクシング前の前処理 Document delineation The vocabulary of terms の決定 リニアな文字列へのデコード ドキュメント単位の決定 The vocabulary of terms の決定 トークナイズ ストップワード 正規化 ステミング / lemmatization

1. Document delineation リニアな文字列へのデコード ドキュメントの単位を決める

リニアな文字列にデコード bytes → linear sequene of characters エンコーディング 様々なフォーマット ASCII は trivial。UTF-8 などをどうするか ヒューリスティクス ユーザーに選択させる メタデータ 様々なフォーマット Word Doc, zip, ppt, PDF, XML ... ドキュメントの種類に合わせて前処理する リニアな並びでない言葉 アラビア語 digital representation に変換できる

ドキュメントの単位を決める 粒度の違うドキュメント群 “Index granularity” (インデックスの粒度) ファイル UNIX の mbox (1つのファイルに複数のメール) Zip (1つのファイルに複数のファイル) ppt (mbox とは逆、全体を一つに扱いたい) “Index granularity” (インデックスの粒度) Precision と recall のトレードオフ 目的に合わせてちょうどよい単位にする そのためにはドメインをよく知ること 例: ウェブ検索 → HTMLページ1枚で１件、ppt や pdf は複数ページで1件

2. the vocabulary of terms を決める 必要な作業 トークナイズ ストップワードの導入 正規化 ステミング / 分類整理 (lemmatize)

トークナイズ

トークナイズ Friend, Romans, Countrymen, lend me your ears Friends | Romans | Countrymen | lend | me | your | ears

様々な問題 どこで区切るか問題 専門用語問題 ハイフネーション問題 ホワイトスペース問題 言語固有の問題

どこで区切るか問題 区切りが分からない “Mr. O’Neil” aren’t 対策方法 クエリとドキュメント解析で同じトークナイザを使う

区切りと言語判定 区切りは言語毎の問題 言語判定重要 短い文字列で十分判定できる 特徴的なパターン

専門用語問題 専門用語 コンピュータ関連 C++, C# や B-52, M*A*S*H jblack@mail.yahoo.com 142.32.48.231 1Z9999W998453999981 (トラッキング番号)

専門用語問題への対策 インデクスから取り除く方法もあり メタデータとして別にインデクス化 ただし、検索の際の大きな制限になる semantic type が明らかなもの メールの日付など → 6.1

ハイフネーション問題 “Hewlett-Packard” “co-education” “the hold-him-back-and-drag-him-away maneuver”

ホワイトスペース問題 ホワイトスペース問題 ハイフネーション問題と一部共通 Los Angels White Space / whitespace ハイフネーション問題と一部共通 over-eager / over eager / overeager

ハイフネーション / WS への対策 妥協案 もっと良い方法は? 以下を同じ term とみなす ユーザーにハイフンを使わせる over-eager “over eager” overeager ユーザーにハイフンを使わせる もっと良い方法は? equivalence classing

言語ごとの問題 言語固有の問題 日本人涙目 ドイツ語 中国語 etc .. 単語境界がない 漢字とひらがなとカタカナ 日本語は難しい。自然言語処理重要。

日本語のトークナイズ手法例 大規模ボキャブラリから最長マッチ 機械学習 (e.g 隠れマルコフモデル) N-gram

ストップワード

ストップワード the, as, a, an ... ストップリスト Web検索では使われない ただし、やりすぎ良くない 出現頻度でソートして手で作る Web検索では使われない 近年の IR システムではコストでない 圧縮、rank、impact sorted indexes See Also: 5.3, 6.2.1, 7.1.5

正規化 (Normalization)

正規化 USA == U.S.A. term を、表層的に違っても意味は同じとみなすこと

equivalence classing 以下を同じ単語として扱う anti-discriminatory 後者に同じ Query Expansion に比較すると、機械的な処理

Query Expansion query expansion equivalence classing より柔軟 同意語の関係辞書を作る (人手、機械学習) car = automobile 詳しくは 9 章で

Query expantion の方法 x 2 Unnormalized なままインデクシング、クエリ拡張リストを別に用意 ○ 空間 × 時間 インデクシング中に対応辞書を作る × 空間 ○ 時間

やりすぎよくない equivalence classing も query expansion もやりすぎはよくない ○ U.S.A → USA × C.A.T → cat

よくやる正規化の一部#1 ステミングと lemmatization 後述

よくやる正規化の一部#2 アクセント記号、発音区別記号 大文字と小文字 英語での問題 記号を削除 ユーザーは多くの場合 non-ASCII テキストは入力しないから 大文字と小文字 全部小文字にする ほとんどのユーザーは小文字で検索する 英語のヒューリスティクス 「タイトルに出てくる全大文字もしくは殆ど大文字」「文中のセンテンスの capitalize されているもの」は残す 英語での問題 ne’er => never, colour => color 日付 3/12/91 = Mar. 12 1991 ...

英語以外の言語での正規化 Other languages 重要 Equivalence classing においてそれぞれの言語で固有の問題 WWW の 6割英語、4割が他言語 今後も他言語は増えていく 英語 blog は全世界で 1/3 でしかない Equivalence classing においてそれぞれの言語で固有の問題 言語に特化したトークナイズ、正規化を行う 日本語が良い例 複数言語が混在しているドキュメントへの対応

ステミングと Lemmatization

Stemming / Lemmatization 語尾変化や派生などに対応する方法 am, are, is => be car, cars, car’s, cars’ => car equivalence classing の手法に含まれる

ステミング (Stemming) 基本語尾を chop アルゴリズムはあるものの、形態素解析などは行わない (文脈判断はあまりしない) Porter 1980 Lovins 1968 Paice 1990

ステミング例 例 正確なステミングの結果ではなく、equivalence classes になるのが重要 caresses => caress ponies => poni cats => cat 正確なステミングの結果ではなく、equivalence classes になるのが重要

Lemmatization 形態素解析を行い “lemma” を求める 問題点 ステミングよりも正確だが、パフォーマンスのトレードオフが大きい equivalence classing を構築するという観点ではステミング以上の効果はそれほど大きくない

今回のまとめ インデクシング前の前処理の詳細 Practical か本格的にやるか 日本語は日本語に特化した文献を参照する必要がありそう 実装にはそこまで踏み込まず 文字列へのデコード トークナイズと正規化 Practical か本格的にやるか 多くをカバーできるなら Practical に 日本語は日本語に特化した文献を参照する必要がありそう