IIR (Introduction to Information Retrieval) 勉強会 #09
[
今日は IIR (Introduction to Information Retrieval) 勉強会の9回目。
- Introduction to Information Retrieval
-- http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html
今までの復習資料(by naoyaさん)は以下です。
# 良い資料です。是非ご一読を！
http://bloghackers.net/~naoya/iir/ppt/
今回の、8章のテーマは「Evaluation in information retrieval」です。
検索エンジンの出力結果を評価する際の手法や指標に関するお話です。
7章が、検索結果として出力する結果のスコア算出法に関してだったので、
次はそれだろうなぁ、と思います。
----
7章の復習
- 基本はcos類似度
- cos類似度の計算量を削減する工夫が必要
-- 内積計算の積算を加算に
--- クエリもベクトルとして扱える
---- 0,1で次元を構成して単位ベクトルにする？
----- クエリくらいなら内積を計算せず、スコアを足すだけで良い。
-- ソートにはヒープを使おう
--- ヒープに格納しておけばTopKを、より低いコストで取得できる
-- 計算対象の文書を事前に削減する
--- 人間に重要そうな記事を残す
---- 全ての文書より遥かに少ない数まで絞る
----- 転置indexを使う
------ クエリの単語群からidfの高いものだけ残す
------- 紐づく文書も大量に削除できる
----- 残ったidfの高いクエリを、全て同時に含む文書だけ取得する
------ posting listの中から、最もらしいr個を求める手法
------ tfの閾値を決めて、足切りする
-- 足切りし過ぎに気をつける
-- 計算のIterateを減らす
--- posting listをtf順に、クエリをidf順にソートしておく
---- tf順のリストを閾値で切る
----- tfの値の変動が高い間だけ取得する
---- 重要なクエリから処理する
----- これ重要
---- 欲しい量が集まったらおしまい
- Tired index
-- tfの閾値ごとにindexを分けておいてFall Backするとか
- Query term proximity
-- クエリの単語の、文書中での距離が近いとスコアが高い、とか
- 構文解析
-- 単純なところだと、ABCというクエリを、ABC, AB, BC,
- スコアリング
-- スコアはさまざまある。どうやって統合するか。
--- 手動でも良い
--- でも機会学習でやった方が良いだろう
- ベクトル空間法と今まで勉強してきたindexの間には使えるものと、使えない物があるよ。
----
8.1 情報検索システムの効果の評価
必要なものは
- 文書コレクション
- テスト用のクエリなど
- 評価方法
-- 関連しているか、していないか
これらを使うような手法を、gold standardとかground truthと呼ぶ。
クエリとユーザの要求が完全に一致しなかったり、
ユーザの要求に最適なように結果をしぼりこめなかったりする。
# python -> プログラミング言語、動物
inside data(学習データ)とoutside data(評価用データ)を分けよう。
交差検定とか。
学習データでチューニングして、学習データで評価したら
良い結果になるのはあたりまえ。
8.2 標準的なテストコレクションの紹介
- Crabfield
-- 小さいコレクションなので、適合性い関する評価がきちんと行なわれている
- TREC
-- indormation needに対して、文書コレクションから、抽出する手法を作成する
- GOV2
-- 巨大
- NTICIR
-- アジアの言語横断のテストコレクション
- CLEF
-- ヨーロッパの言語横断のテストコレクション
- REUTERS
-- ロイター
- 20 Newsgroups
-- テキスト分類のテストコレクション
8.3 ランク付けされていない検索セットの評価
適合率の定義 : 検索結果中の実際に適合している文書
再現率の定義 : 検索結果中の適合した文書数が、文書コレクション中の適合する文書を被覆する割合
判定の種類の呼び方。
<table class="hiki_table"><tr><td> |relevant<td>nonrelevant<tr><td>retrieve<td>true positive(真にPo)<td>false positive(間違ってPo)<tr><td>not retrieve<td>false negative(間違ってNe)<td>true negative(真にNe)</table>
検索結果は、適合率も重要になる場合もあるし、
適合率が重要になる場合もある。
一般には適合率を重視すると良いだろう。
適合率と再現率はトレードオフ。バランスが大切。
加重調和平均をみてみよう。式8.5。
F-measure。
頻繁に業界標準なF値は、F_B=1 = 2*P*R / (P + R)。式8.6。
調和平均の妥当性は図8.1を見ると分かる
8.4 ランク付けされた検索結果の評価
interpolater precisionを使う。
再現率を一定以上に固定された状態での、適合率。
たとえば、検索結果の評価では、一定の再現率を満たすように
検索結果を出力して、その検索結果の適合率を測定する。
現実にも、検索結果の1ページ目がそこそこの結果なら、
欲しい結果が1ページ目になくても、検索を続けるだろう。
評価時には、あまり細かいinterpolater precisionを使わず
0.1刻みで11点で測定するのが良いだろう
Precision at k : k個とった時の適合率。文書セットのサイズは確定してなくても良い。
R-precision : 上位R件の時点の適合率。文書セットのサイズが分かっている必要がある。
Break even point : 適合率と再現率が等しくなる点
DCG : 検索検索の出力結果のランキングが、指標の値でソートされた場合に近いのかを判断する
nDCG : さまざまな検索課題に対するDCGの平均
8.5 関連度の付与
検索結果と人の判断の一致度は興味深い。
Kappa値を良く使う。
k = (P(A) - P(E)) / (1 - P(E))
P(A) = (true positive + true negative) / document size
P(E) = P(positive)^2 + P(negative)^2
P(positive) = (false negative + true negative) / 2 * (document size)
P(negative) = (true positive + false positive) / 2 * (document size
)
例えば、2人のアノテータの一致度を計る。
2人の判断がばらついてたら値が低くなる。
よって、タスクの難しさなども測定できるよ。
8.6 より広い評価
8.6.1
システム的な指標
- indexingの早さ
- 検索可能になるまでの早さ
- クエリ言語のコスト
- 文書コレクションの大きさ
8.6.2
ユーザビリティ的なことはほっとく。
8.6.3 既にデプロイされたシステムの改良
ユーザからのクリックによるフィードバック。
1から10%くらいの割合で、クリックログを得るための検索結果にとばす。
A/Bテストは、説明しやすい評価指標としてよく使われる。
8.7 スニペット
スニペットにはクエリに依存するものと、依存しないものがある。
前者のような静的なスニペットは、metatagなどから作る。
NLPを使って、オリジナルの文書から内容を良く表す文書を抜き出す。
高度に、文書の要約や校正などもすることはできるけど、研究じゃなければやらない。
keyword-in-context (KWIC) snippetsというものがある。
検索キーワードの左右のコンテキストを示す。
その際に、ユーザのための工夫を、NLPなども交えておこなう。
- 英語例文検索 EReK
-- http://erek.ta2o.net/s/factor%20out.html
スニペットの生成は高速じゃないといけない。
大半の文章と、巨大な文章の主題や主要な話題を高速にキャッシュするには、現実問題、10000文字くらいの間にあるのではないか。
おしまい
