IR本輪読#10

2020-09-29

8 Evaluation in informationretrieval

これまでいろんな手法をみてきたけど、どの手法がどういったアプリケーションに効くのかどうやって知ればいいのか

情報検索は経験的な学問で、実際にテストコレクションを用いて慎重に計測することで評価する

この章では

8.1 情報検索システムの効果の計測について議論する

8.2 テストコレクションとその実際の用途を紹介する

8.3 順位なしの情報検索システムの評価

8.4 順位ありの情報検索システムの評価

8.5 信頼性が高く有益なテストコレクションの開発について

8.6 実用性とドキュメント関連性への近似

8.7 ユーザの幸福の計測 (意訳が雑)

特定用途の情報検索システムの効果を一般的な方法で測るにはテストコレクションを使う

テストコレクションは以下の3つを含む

文章コレクション

テスト用の検索クエリ

各クエリに対する各ドキュメントの関連しているかしていないかの情報

効果測定の一般的なアプローチとして2値分類の概念が中心

「関連する」「関連しない」

様々な情報ニーズ

これに耐えうるか判定するには経験的には50クエリは必要

情報ニーズに対する誤解

クエリに含まれる単語がすべて含まれているからといってその文章が「関連する」とは断定できない

単純化

１クエリの結果からでもユーザーは判定出来るが、評価時に判定するにはもっと大げさなクエリが必要

本来の関連具合はグラデーション

8.5.1でなぜ2値を使うのかと他の方法を議論する

パラメータチューニング

情報検索システムのパラメータをチューニングして結果を最大化するのはご法度

テストコレクション上でパラメータを変更

このパラメータを使ってテストを実行する

8.2 Standard test collections

テストコレクションを紹介する

特定用途向けの情報検索システム向け中心

文書分類のものも紹介する

テストコレクションの先駆者的存在

現代では規模が小さすぎる

米国国立標準技術研究所 (NIST) が行ったIRテストベットの評価シリーズ

いくつかのサブセットをもっている

規模が大きくトピックの一貫性が高いため

網羅的な関連性の判定はない (tok k 件だけとか)

GOV2

NISTが最近出したテストコレクション

これでも某大手インターネット検索の会社がもっているインデックスの規模に2桁及ばない

東アジアの言語に特化したTRECと同程度のサイズのテストコレクション

ヨーロッパの言語に特化したテストコレクション

Reuters-RCV1

文書分類用のテストコレクション

20 Newsgroups

8.3 Evaluation of unranked retrieval sets

$ Precision = \frac{\#(relevant\ items\ retrived)}{\#(retrieved\ items)} = P(relevant|retrieved)

検索ノイズの少なさを表す

$ Recall = \frac{\#(relevan\ items\ retrieved)}{\#(relevant\ items)} = P(retrieved|relevant)

検索漏れの少なさを表す

以下の分割表を採用する分かりやすい

table:contingency table

Relevant Nonrelevant

Retrieved true positives (tp) false positives (fp)

Not retrieved false negatives (fn) true negatives (tn)

整理すると

$ P = tp/(tp + fp)

$ R = tp/(tp+fn)

$ accuracy = (tp + tn) / (tp + fp + fn + tn)

なぜ適切じゃないか

ふつうクエリに対しては99.9%が関連性のない文章となる

しかし情報検索システムとしてはどうなんだろうか

適合率と再現率の(荷重)調和平均

荷重のかけかた

なぜ調和平均か

100%の再現率を達成するには毎回全件返せばいい

算術平均だと50%くらいになるが明らかに有益ではない

調和平均が一番最小値に近く、常に他の方法と比べて最小

https://gyazo.com/9b9945996a1777d0a397597100ce8106

8.4 Evaluation of ranked retrieval results

順序ありの情報検索システムの評価には指標をする必要がある

のこぎり波の形になる

関連文書が出ると再現率と適合率が上がるので右上に移動する

関連文章が出ないと再現率は変わらず適合率が下がるので下に移動する

https://gyazo.com/3aff9d225491763855f900359cc730e4

再現率毎の適合率 (Figure 8.2の赤い線)

$ P_{interp} (r) = \max_{r' \geq r} p(r')

Interpolated Average Precision

再現率毎に補間適合率の算術平均を出したもの

table:11 points of recall level

再現率 補間適合率

0.0 1.00

0.1 0.67

0.2 0.63

0.3 0.55

0.4 0.45

0.5 0.41

0.6 0.36

0.7 0.29

0.8 0.13

0.9 0.10

1.0 0.08

$ MAP(Q) = \frac{1}{|Q|}\sum_{j=1}^{|Q|}\frac{1}{m_j}\sum_{k=1}^{m_j}Precision(R_{jk})

table:1クエリの例

順位 関連するか 適合率

1 ☓ -

2 ○ 1/2=0.5

3 ☓ -

4 ☓ -

5 ○ 2/5=0.4

合計 0.9

平均 0.9/2=0.45

これを全クエリで実施してクエリ数で割る

情報ニーズのセットは十分な大きさと多様性を持っている必要がある

1つのシステムに対して複数の情報ニーズのMAPを計算するとニーズによって大きく異なる

1つの情報ニーズを複数のシステムに対してMAPを計算したほうが成績がいい

Precision at k

Web検索などでは上位の検索結果が重要

top kの適合率の平均を用いて評価する

(利点)ので 関連文書数を推定する必要がない

(欠点) 一般的に使われている評価方法の中ではもっとも安定性が低くうまく平均化できない

R-Precision

クエリに対するすべての適合する文章の数までの結果を使って適合率を出す

50件の適合する文章がある場合は Precision at 50 と同等の計算になる

これがなぜ有効なのかは不明瞭

経験的にはMAPと高い相関があると分かっている

ROC curve

縦軸に再現率

$ fp/(fp+tn) = 1 - tn/(fp+tn)

順序なしの場合は有益とされていなかった

なぜなら関連性のない文章の方が圧倒的に多くてほぼ1になるから

検索スペクトル全体を見るのに有益

precision-recall curve というとこちらのことろ指す場合もあるが正確ではない

機械学習の評価指標

関連度を2値ではなくした場合の効果 (詳しくは8.5.1で見る)

$ NDCG(Q, k) = \frac{1}{|Q|}\sum_{j=1}^{|Q|}Z_{kj}\sum_{m=1}^k\frac{2^{R(j,m)}-1}{\log_2(1_m)'}