ブログではないです

ブログでなくはないです

共参照解析の評価指標

coreference_resolution memo

以前読んだ共参照解析の話をはじめ最近の話で評価に用いられるconll 2012 shared taskの評価指標であるMUC，{ \displaystyle B^3}, { \displaystyle CEAF_e}辺りが馴染みがなかったので 自然言語処理シリーズの文脈解析を片手に調べた3.3節のメモ。この辺全く詳しくないのでなんか間違いがあるかも。

まず，多くの場合評価は同一エンティティを指す言及の集合に対して行われる。 個々の先行詞-言及のペアについてPrecision/Recallを出す方法も出来なくはないが，それだと例えば正解が { \displaystyle \{A_1 \leftarrow A_2, B_1 \leftarrow B_2 \}} であった時，システムが { \displaystyle \{A_1 \leftarrow B_1, B_1 \leftarrow B_2 \}} というリンクを推定した場合と{ \displaystyle \{B_1 \leftarrow A_1, A_1 \leftarrow B_2\}} というリンクを推定した場合で、どちらも{ \displaystyle A_1, B_1, B_2}の3つを同じエンティティに対する言及の集合だと考えているにも関わらず結果が異なってしまう。

MUC (Message Understanding Conference)

上記の問題を解決するために，MUCでは「正解データのそれぞれの集合を生成するのに必要となるリンクのうちいくつをシステムが生成したか」でRecallを，逆に「システムが生成したそれぞれの集合を生成するのに必要となるリンクのうちいくつが正解データに含まれていたか」でPrecisionを評価する。 p97の図が分かりやすい。

具体的にどう計算するかというと

{ \displaystyle Recall = { {\sum_{i=1}^{N_k} (K_i - p(K_{i}))} \over {\sum_{i=1}^{N_k} (K_i - 1)} } }

{ \displaystyle Precision = { {\sum_{i=1}^{N_r} (R_i - p'(R_{i}))} \over {\sum_{i=1}^{N_r} (R_i - 1)} } }

{ \displaystyle K_i , R_i}は正解データ / システム出力のi番目のエンティティに関する集合の要素（言及）数，{ \displaystyle p(K_i)} は{ \displaystyle K_i}の要素をシステム出力における集合ごとにまとめたもの，{ \displaystyle p'(R_i)} は{ \displaystyle R_i}の要素を正解データにおける集合ごとにまとめたもの（別々のクラスタだとみなした数），{ \displaystyle N_k , N_r}は正解データ / システム出力におけるエンティティの数。

Recallを例に式の意味を説明すると，{ \displaystyle K_i}個の要素があった時にそれら全てを繋いだグラフ（正解データ）を作るのに必要なエッジの数が { \displaystyle K_i - 1}本 （分母）で，そこからエッジが1本減るごとに細かいグラフに分かれる（分子）ので，逆に言うとグラフがどれだけ細かく分かれてしまっているかで足りないエッジの数が計算出来るということ。

しかしMUCはなるべく多くのリンクを出力したほうが良いスコアになりがちであったり，例えば正解データが{ \displaystyle K = \{\{a,b,c\} \{d,e,f,g\}\} }であったとして，システムの出力{ \displaystyle R_1 = \{\{a,b,c, d,e,f,g\}\} }と{ \displaystyle R_2 = \{\{a,b,c\}, \{d,e,f,g,h\}\} }を比べた時に本来異なる2つのエンティティを同一の集合で考えてしまっている前者と，関係ないリンク（{ \displaystyle h}）が1つ紛れ込んでいるだけでそれ以外はほぼ完璧な後者が同じスコアになるなど問題点もあるため，{ \displaystyle B^3}やCEATが提案されたらしい。

{ \displaystyle B^3} （B-CUBED）

{ \displaystyle B^3}での計算式は以下の通り。

{ \displaystyle Recall = {\sum_{i=1}^{N_k}\sum_{j=1}^{N_r} {{|K_i \cap R_j|^2 } \over {K_i}} \over {\sum_{i=1}^{N_k} K_i}} }

{ \displaystyle Precision = {\sum_{i=1}^{N_k}\sum_{j=1}^{N_r} {{|K_i \cap R_j|^2 } \over {R_j}} \over {\sum_{j=1}^{N_r} R_j}} }

Recallを例にとると，それぞれのエンティティについて正解データでもシステムの出力でも同一の集合に含まれる言及の割合を計算（{ \displaystyle \sum_{j=1}^{N_r} {{|K_i \cap R_j|} \over {\cdot}} } まで）して各要素ごとのRecallを出し，その平均を取って全体のRecallとしている。*1

CEAF

MUCやB-CUBEDは正解データとシステム出力それぞれの集合だけが与えられればそれぞれの集合間の対応を気にせず*2に計算できるタイプの評価指標だったが、 CEAFはスコア計算時にスコアがよくなるように対応付けを取った上で計算をするタイプ。*3 { \displaystyle CEAF_e}や{ \displaystyle CEAF_m}などいくつかバリエーションがある。

{ \displaystyle CEAF_m}はそれぞれのペアのRecall / Precisionの重み付き平均を取るだけ。 { \displaystyle CEAF_e}は

類似度関数 { \displaystyle \phi_4 (K_i, R_j) = {{2 \times |K_i \cap R_j|} \over {K_i + R_j}} } を用いて， 全ペアの総和を { \displaystyle N_k}で割ったものがRecall, { \displaystyle N_r}で割ったものがPrecision となる。

*1:2乗しているように見えるのはRecallが{ \displaystyle \sum_{j=1}^{N_r} {{|K_i \cap R_j|} \over {R_j}} }となる要素の数が{ \displaystyle |K_i \cap R_j|} 個あるからある種の重み付き平均を取っている。ここ理解するの苦戦した

*2:{entity0: {a,b}, entity1:{c}} と{entity0:{c}, entity1:{a, b}}を区別しない

*3:以前読んだコードではsklearn.utils.linear_assignmentを使ってスコアが最大になるように割り当てていた