SIGIR2013 勉強会 Session 11: Evaluation I 担当 : 加藤 ( 京都大学 )

Size: px

Start display at page:

Download "SIGIR2013 勉強会 Session 11: Evaluation I 担当 : 加藤 ( 京都大学 )"

まれあわくや
4 years ago
Views:

1 SIGIR2013 勉強会 Session 11: Evaluation I 担当 : 加藤 ( 京都大学 )

2 Evaluation I 1. On the Measurement of Test Collection Reliability Julián Urbano (University Carlos III of Madrid), Mónica Marrero (University Carlos III of Madrid), Diego Martín (Technical University of Madrid) テストコレクションの信頼性分析 : クエリは少なくとも 130 使え 2. Deciding on an Adjustment for Multiplicity in IR Experiments Leonid Boytsov (Carnegie Mellon University), Anna Belova (Abt Associates Inc), Peter Westfall (Texas Tech University) 情報検索索での多重比較 : Family-wise error に気をつけろ 3. Preference Based Evaluation Measures for Novelty and Diversity Praveen Chandar (University of Delaware), Ben Carterette (University of Delaware) 比較ベースの新規性多様性考慮型評価指標 : 評価はユーザに委ねろ 2 図表は論文より引用

3 テストコレクション (Cranfield モデル ) } 文書集合, トピック ( クエリ ), 適合文書, 検索索評価指標のセット ( ベンチマークのようなもの ) トピック京都観光ハリーポッタートピック適合京都観光 1, 4 ハリーポッター 5 文書集合テストコレクション検索評価指標 P@k MAP ndcg 検索システム G1 G2 B1 B2 クエリ : 京都観光 ndcg 100 点 60 点 100 点 0 点

4 テストコレクションの一例 } TREC (Text REtrieval Conference) Web Track } 文書集合 : ClueWeb (10 億の Web ページ ) } クエリ : 50 個 (e.g. disneyland hotel, gps, etc.) } 適合文書 : 50 クエリに対する適合文書 ( 人手で決定 ) } 検索索評価指標 : MAP, ndcg

On the Measurement of Test Collection Reliability Julián Urbano, Mónica Marrero Diego Martín } 目的 } Generalizability Theory を使ってテストコレクションの信頼性を検証する方法の詳細を検討 } 信頼性 1.

5 On the Measurement of Test Collection Reliability Julián Urbano, Mónica Marrero Diego Martín } 目的 } Generalizability Theory を使ってテストコレクションの信頼性を検証する方法の詳細を検討 } 信頼性 1. 得られた評価指標の値がどれくらい安定しているか 2. 得られたシステム間の差がどれくらい安定しているかトピック京都観光ハリーポッター Qrel 文書適合度文書 A 4 文書 B 5 検索評価指標 P@k MAP ndcg 検索システム評価指標の値 Session N: XXX 担当 : (XX 大 )

6 テストコレクションの信頼性の測り方トピック京都観光ハリーポッター文書文書 A 4 文書 B 5 Qrel 適合度検索評価指標 P@k MAP ndcg 1 検索システム評価指標の値以下のものを減らしてみる } トピック数 } システム数 (or Qrel 数 ) 2. 評価指標の値検索索システムの順位の変化を計測 6 Session N: XXX 担当 : (XX 大 )

7 Generalizability Theory [Bodoff and Li, 2007] } ANOVA 的にシステムクエリによる分散を推定 } クエリ数 : n q } システムによる分散 : σ s 2 } クエリによる分散 : σ q 2 } システム + クエリによる分散 : σ s:q 2 } Generalizability Coefficient システム間の差の安定性 } Index of Dependability 評価指標の値の安定性 Φ = Eρ 2 = σ 2 s σ 2 s +σ 2 s:q / n q σ 2 s σ 2 s + (σ 2 s +σ 2 s:q ) / n q 7 Session N: XXX 担当 : (XX 大 )

8 Generalizability Coefficient の歴史 Relative Stability Ad Hoc Web adhoc Web distillation Web diversity Novelty Genomics Robust Terabyte Enterprise 1MQ MTC 1MQ statap Medical Microblog Linear trend Eρ^ Year 全体的にテストコレクションの信頼性は低下? 8 Session N: XXX 担当 : (XX 大 )

9 Take-away Messages } システム間の差の安定性 95% を得るには? } クエリ数 80 } タスクによってこれは変わるので一概には言えない } 評価指標の値の安定性 95% を得るには? } クエリ数 130 } [Web Ad- hoc 検索索 ] システム間の差の安定性 : [0.8, 0.93] ~ケンドール τ: [0.53, 0.81] 9 Session N: XXX 担当 : (XX 大 )

10 Deciding on an Adjustment for Multiplicity in IR Experiments Leonid Boytsov, Anna Belova (Abt Associates Inc) } IR における多重比較の p 値調整 } 多重比較をするときには少なくとも 1 つの false positive が出る確率率率が α (e.g. 0.05) 以下になるように調整 } 特に IR の実験環境ではどんな風にするとよいのか 10 Session N: XXX 担当 : (XX 大 )

11 多重比較の注意点 (family-wise error) } 各群間で単純に t 検定を行行ってはいけない ndcg システムA システムB システムC クエリクエリクエリ t 検定 t 検定クエリクエリ平均

12 なぜ単純に比較してはいけないのか? } 例例えばシステム A- B, B- C 間で t 検定をしたとき } 誤って帰無仮説を棄却する確率率率 : α( 有意水準 ) } 少なくとも A- B, B- C 間のどちらかで誤って帰無仮説を棄却する確率率率 : 1- (1- α) 2 } 1- (1- α) 2 > α (0<α<1 のため ) より検定を繰り返せば繰り返すほど誤って帰無仮説を棄却する確率率率が高くなる } 多重性のための調節 } Bonferroni correction } 検定をする回数 n で有意水準 α を α/n と補正する } Tukey's HSD test } 最も厳しい水準を用いて一律律に検定を行行う

13 Permutation Test } 二つのシステムの検索索指標の値 x = (x 1, x 2, x 3, ), y = (y 1, y 2, y 3, ) } 統計量量 : T(x, y) } e.g. T(x, y) = x avg y avg } 仮説 H: 両システムに差はない } Permutation Test 1. x, y の値をランダムに入れ替えて xʼ, yʼ とする 2. 1 を B 回繰り返し T(xʼ, yʼ ) T(x, y) の回数を C とする 3. p = C/B とする 13 Session N: XXX 担当 : (XX 大 )

14 イメージ図 x y T(x, y)=0.4 T(x, y )<T(x,y) T(x, y )>T(x,y) T(x, y )<T(x,y) T(x, y )=0.3 T(x, y )=0.5 T(x, y )=0.2 x y x y x y p = (T >T の回数 )/( 試行回数 ) = 1/3 14 Session N: XXX 担当 : (XX 大 )

15 MaxT Permutation Test [Westfall and Young] } あるベースラインと他のシステムの検索索指標の値 x 0 = (x 01, x 02, x 03, ), x 1 = (x 11, x 12, x 13, ), x 2 = (x 21, x 22, x 23, ), } 統計量量 : T(X) (X=(x 0, x 1, x 2, )) } T i (X) = T(x 0, x i ) } 仮説 H i : システム i とベースラインには差がない } MaxT Permutation Test 1. X の値をランダムに入れ替えて Xʼ とする 2. MaxT i (X) = max i j m T j (X) 3. B 回ランダムに 1,2 を行行い,MaxT i (Xʼ )>MaxT i (X) の回数を C i とする 4. p i = max j i C j /B とする 15 Session N: XXX 担当 : (XX 大 )

16 Preference Based Evaluation Measures for Novelty and Diversity Praveen Chandar, Ben Carterette } 背景 } 評価指標の一般形 = gain*discount } e.g. DCG Metric = } Novelty- aware の評価指標 n i=1 n i=1 } ERR (Expected Reciprocal Rank) g(i)d(i) DCG = (2 r(i) 1) ERR = n i 1 R i (1 R j ) i=1 j=1 diminishing return 1 log(i +1) R i : i 位の文書の適合度 [0, 1] 16 Session N: XXX 担当 : (XX 大 ) 1 i

17 背景の続き } Novelty&Diversity- awareの評価指標 } α- DCG m j=1 g(i) = R(i, j)(1 α) } これまでの Novely&Diversity- aware 評価指標 } Subtopic ベース or ナゲットベースめんどくさい } e.g. ハリーポッター : 本, 映画, 登場人物 } e.g. SIGIR: 歴史,2014, ベストペーパー } 文書に対する比較評価でできないか? c(i, j) diminishing return R(i, j): i 位の文書のトピック j への適合度 c(i, j): i 位までのトピック j に適合する文書数 m: トピック数 17 Session N: XXX 担当 : (XX 大 )

18 比較評価ベースの適合性判定 } 比較によって文書の Utility( 有用度度 ) を推定 A, B どっちが良い? X を見た後だったら A, B どっちが良い? U(A) >U(B) U(A X) <U(B X) 18 Session N: XXX 担当 : (XX 大 )

19 比較評価による Novelty&Diversity-aware 評価指標 } 提案指標 n i=1 i j=1 PRF = U(d S ) P(i) j j Utility j 位までの文書 S j を見た上での i 位の文書の有用度 Discounting factor i 位でユーザが諦める確率例えば j 1 k=1 U(d j S j ) = U(d j d k ) 比較評価を利用実際の TREC データに利用してみると α-ndcg や ERR-IA と相関あり 19 Session N: XXX 担当 : (XX 大 )

Medical3

Medical3 Chapter 1 1.4.1 1 元配置分散分析と多重比較の実行 3つの治療法による測定値に有意な差が認められるかどうかを分散分析で調べますこの例では因子が1つだけ含まれるため1 元配置分散分析 one-way ANOVA の適用になりますまた多重比較法 multiple comparison procedure を用いて具体的のどの治療法の間に有意差が認められるかを検定します 1. 分析メニュー