[2006.01245] An Effectiveness Metric for Ordinal Classification: Formal Properties and Experimental Results [paper-reading]

[yoheikikuta]

論文リンク

https://arxiv.org/abs/2006.01245

公開日（yyyy/mm/dd）

2020/06/01

概要

順序分類タスクは reject weak reject, weak accept, accept のように順序がある（しかしカテゴリ間の間隔については等間隔とは定まっていない）ものの分類で、NLP の分類タスクとしてはよくあるものである。
このようなデータは順序尺度であるが、これまで用いられきた指標は順序尺度が持つべきいくつかの性質を全部満たすものではなく、順序分類を正しく評価できているものではなかった。
この論文では情報論的な枠組みに則りつつクラス間の近さを全体の分布に基づいて定義し、それを用いて Closeness Evaluation Measure という指標を導入した。
これは名義尺度、順序尺度、間隔尺度それぞれで使えるものであり、それぞれのケースで尺度が満たすべき性質を満たすものとして定義されている。
新たな指標を導入するという論文なので、実験では二つのシステムの出力を比べて、順序尺度が満たすべき accuracy, kendall tau-a, mutual information の全てが良くなる場合に提案したメトリックも良くなっているかの相関を測ることで、他の指標の場合と比べて良くなっているかを調べている。結果は人工データでもリアルデータでもこれまで使われてきたメトリックよりも良い結果を示した。
これは評価指標でそのままではモデル学習の損失関数として使えるものではないが、使えるように発展させられればさらに面白いと思う。

evaluation の code はこれ: https://github.com/EvALLTEAM/CEM-Ord
java なので珍しいねと思ったら、以前に online evaluation 用の EVALL http://evall.uned.es/home というのを作っててそこに追加で載せているというもの。

[yoheikikuta]

ACL 2020 long paper で気になった論文を読んでみようシリーズ。
ordinal classification (順序分類) における metric ということで目を引いた。

ordinal classification の問題設定でも単純な classification として解いてしまうことが多かったが、本来扱いたい情報を適切に扱えてないよなという気持ちがあった。その辺りの整理と提案 metric がどんなもんか理解してみようということで読んでみることにする。

[yoheikikuta]

ordinal classification は positive, neutral, negative のように相対的な順番に意味がある問題設定で、これは順序情報があるので単純な classification (class 1, 2, 3 は相対的な順番などない) とは違うものである。しかし実際には単純な classification として解いてしまうことも多く、そこで使用する metric には想定的な順番の情報はない。本来は順番があり、例えば positive が多く negative が少ないような分布をしているデータに対して、neutral を positive と間違える場合と negative と間違える場合は区別すべきはず。

この論文はそういう論点を整理し、その上で ordinal classification の metric として適切なものを提案している。

具体的な話に入る前に、誰しもがデータ分析を初めて勉強するときに学ぶ測定尺度について振り返っておく（自分は名称とかすっかり忘れていた）。

• nominal scale (名義尺度)
  単なる区分。例えば論文の分野（computer science, physics, ...) など。
• ordinal scale (順序尺度)
  名義尺度に対して相対的な順序情報を付加したもの。例えば論文評価の {accept, weak accept, weak reject, reject} など。これは weak reject より weak accept の方が良い評価とは言えるが、その違いと weak accept と accept の違いのどちらが大きいかということは何も言っていない。
• interval scale (間隔尺度)
  順序尺度に対してカテゴリ間の間隔情報を付加したもの。例えば論文をそのクオリティに応じて 1 ~ 5 点で評価するなど。これは 4 点は 1 点より 3 点分だけいいことを意味していて、評価の平均をして何点以上なら accept みたいなことができる。この点数に特別な意味はないので、6 ~ 10 点で評価しても同じ。そしてこれは裏を返せば比率については情報として意味がないことを言っている（5 点は 1 点の 5 倍とか言っても意味なし。これは 6 ~ 10 点で同じことを考えたときに 10 点が 6 点の 5 倍になっていないことから自明）。
• ratio scale (比例尺度)
  間隔尺度に対して絶対的なゼロ点の情報が付加され比率が意味を持つようになったもの。例えば論文の citation 数など。これは 0 に明確な意味があることに加えて、あの論文はこの論文より 20% 多く cite されているという statement に意味がある。

このような尺度の性質を反映した metric で測るべきだが、それができてないというのが冒頭の話。

[yoheikikuta]

ということで測定尺度を思い出した結果、以下のように ordinal classification は◯◯◯とは異なる、と言って違いを認識できる。

• n-array classification とは異なる
  ordinal classification は順序情報がある。accept は reject よりも良い。
• ranking prediction とは異なる
  ranking prediction は相対的な順番のみを考慮するが、ordinal classification はカテゴリのマッチングが必要。具体的には ranking prediction で 1,2,3 位と予測したものを ordinal classification で考えた場合、accept, weak accept, weak reject と weak accept, weak reject, reject では違う情報になっている。
• value prediction とは異なる
  値の間隔については ordinal classification は本来は何も言えないはずである。accept と weak accept の差分の大きさと weak accept と weak reject の差分の大きさは決められていないし、この差分を定量的に扱うのは ordinal classification ではやるべきではない。
• linear correlation とは異なる
  ordinal classification の出力と ground truth を比べた時、値が一致してなくても完璧に相関することはありうるので同じ問題ではない。

異なる、とかいうとこういう問題だと捉えて解くと間違いだという印象を与えるが、そういうことではなくて本来持っている情報を使い切っていないという意味である。そもそも間違いとは何だみたいな話はよく分からんが、とにかくこういう問題設定だと思ってもモデル学習したり新しいデータに対して予測したりはできるけど、もっと適切な設定ひいては評価方法があるという話。

ちなみに過去の公開ベンチマークで使われてきた metric には以下のようなものがある。

[yoheikikuta]

ordinal classification に関する先行研究がいくつか提示されるが、どれも 2010 年以前でなんか時代を感じさせますな。
詳細は必要があったら読むとして、重要なのはどの先行研究も「カテゴリ間に間隔を定めるよう事前に仮定していた」ということ。上述のようにこれは本来順序尺度が有する性質ではないので、問題を歪めて解いていたということになるだろう。

仮定する内容としては、カテゴリ間の一様な間隔（つまりは間隔尺度として扱う）、誤分類のコストが予測と答えの絶対値の差に比例するとする、などがあるらしい。

何度も繰り返すようにカテゴリ間の間隔に何か仮定して問題を解くのは順序尺度を逸脱している行為なので、それをしない適切な metric を提案しようというのがこの論文の趣旨である。

[yoheikikuta]

提案 metric の定義をしていく。

ちょっと慣れが必要なので、まずは以下の例でイメージを掴む。
reject/weak reject/undecided/weak accept/accept という 5 段階の順序尺度のデータである。縦軸は該当のカテゴリに属する論文が何本あるかである。
左右それぞれの状況で一つの論文が weak reject から weak accept に移されることを考える時、どちらの方が「大きな」移動になるのだろうか？

左の場合は weak reject, undecided, weak accept の数が多い。これはつまりこれらのどこに属するかが reject/accept を分ける鍵になるので重要な情報である。つまり weak reject -> weak accept は大きな移動でこれらのカテゴリは「遠い」と言える。あの weak reject が weak accept に変わってくれれば論文通ってたかもしれないのに！みたいな状況である。

一方で右の場合は reject, accept の数が多い。これのどちらに入るかが重要であり、数が少ない weak reject -> weak accept の移動は大した違いになってない。左の場合と比べるとこれは小さな移動でこれらのカテゴリは「近い」と言えそう。

これを情報論的に定式化してみる。データがどこのカテゴリに属するかを分布に基づいて考える時、左の例では weak reject, undecided, weak accept に属する確率は高く、こういう場合は「遠く」なるようにしたい。一方で右の例では weak reject, undecided, weak accept に属する確率が低く、こういう場合は「近く」なるようにしたい。

P(x ≦^{b}_{ORD} a) という記法を導入する。
これは item space の元 a,b,x に対して、クラスの順序尺度において [a, b] の範囲内において x として a よりも b に近いものとして得られる確率として定義する。
上の例であれば a = weak reject, b = weak accept であり、ある論文 x を考えた時にそれが weak accept に近い確率である。この確率の具体的な計算はどうやるんだというのが疑問に挙がるがそれはもう少し後でやるとして、ここでは抽象的にそういう確率が定義されてるとしておく。

確率が定義できれば情報量が定義できるので、Closeness Information Quantity (CIQ) を以下で定義する。

これは近さの指標として使うもの（であって距離的なものではない）なので、値が大きいほど近いという意味になる。
上の例では右の場合の方が、確率が低い -> CIQ は大きい -> 左の場合と比べて weak reject と weak accept は近い、というものになる。この辺の関係性はちょっと慣れないと間違いそうなので、定義に戻って考えるのがよさそう。

ちなみに ORD とかいう superscript いらんじゃんと思うけど、読んでいくとこの辺りの定義は一般化されて他の尺度の場合にも定義できるので明示的に ORD とつけてるっぽい。

この書き方をみたときに a <-> b の入れ替え対称性はあるんかな？と思ったけど、まずこの抽象的な定義の段階ではそこに関しては何も言ってない。そして具体的な ordinal classification 用の計算にするときも非対称なものを使う。

---

ここは完全に勘違いしていた部分があった。

これは item space の元 a,b,x に対して、クラスの順序尺度において [a, b] の範囲内において x として a よりも b に近いものとして得られる確率として定義する。

ここを x から b の方が近くて、x から a の方が遠い、という感じに解釈してしまったが、これでは以降の議論がおかしくなってしまう。
ここは簡単に言うと a < x < b という意味になる。簡単に言うと、というのは他の尺度まで考慮するとこの不等号で表せるものというわけではなくなるのだが、まず念頭に ordinal scale を置くならこう思っておけばよい。

なので weak reject とかの例で言えば weak reject < x < weak accept のような話になる。

[yoheikikuta]

これを system (model) の output と ground truth の場合に書き下す。

$ D $: item 集合
$C = $ {$ c_1, ..., c_n $}: sort されたクラスの集合 （$ c_1 < c_2 < ... < c_n $）
$ g,s: D \rightarrow C $ なる map で $ g $ は ground truth で $ s $ は system を意味する

これらが与えられた時に、先ほどの CIQ を以下のように書く。
これによってあるデータ d に対する system の出力と ground truth の近さを測ることができる。

これまでは単一のデータに対する定義だったが、データセットが与えられ時に ordinal classification 用の metric を作りたいというのがこの論文のメインのモチベーションであった。データセット全体に対して、以下のように Closeness Evaluation Measure (CEM) を定義する。

ここで、分母は normalizing factor である。これは同じクラスで比較してるので、クラスの確率分布のようなものになるのだろう。
出力が近いほど CIQ が大きくなることを思い出せば、この metric の値が大きいほど優れた system output ということになる。

[yoheikikuta]

順序尺度であることを明示的に使って計算を具体化する。

$ x ≦^{b}_{ORD} a $ は a ≦ x ≦ b もしくは a ≧ x ≧ b を示唆している（これは x が a よりも b に近い確率という話だったと思うので、なぜ単純な a ≦ x ≦ b になってるのかは理解できてない）。
ni を ground truth で class ci に割り当てられたデータの数として、全体のデータ数を N としたとき、CEM を具体的に次のように表現する。

この定義の書き方はなかなか酷いのでもう少し詳しくみる。

まず、$ i = j $ となるパターンの場合、summation の方は落とす。つまり $ prox(c_i, c_j) = - log(n_i / 2 N) $ となる。
次にこの 1/2 の factor がなぜなのか気になる。すぐに分かるのは、この 1/2 を除いてしまうと、仮に $ N $ 個のデータが全て同じクラスだった場合（分類問題として意味がない問題設定だが、ここでは式の性質を知りたいだけなのでこういう extreme なのも考える）、$ prox(g(d), g(d)) = 0 $ となるので CEM の分母が 0 になって定義が ill defined になってしまう。
これを回避するだけなら 1/2 じゃなくてもいいのだが、$ i = j $ のうち仮想的に $ i $ と $ j $ を分けるとしたら半分のところで分けるという気持ちなのだろうか。よくわからん。

そしてこの定義がやはりちょっとよく分からない。元の確率 $ x ≦^{b}_{ORD} a $ で $ x $ が $ b $ に近い確率とか言ってたのをちゃんと反映してる気がしない。

ここは全体的によく分かってないのでもう少し考えてみるとしてとりあえず先に進める。

---

勘違いが伝播してたのでここに書いてたのもだいぶ意味がわかってないという感じになっていた。

x ≦^{b}_{ORD} a は ordinal scale ではまさしく a ≦ x ≦ b もしくは a ≧ x ≧ b である。x と a を比べたら x の方が b に近いという意味だったので。

1/2 に関しては著者に聞いてみたが empirical なものらしい。色々考えたけど理論的な justification はできてなくて、実験をしたりしてこの factor が重要だと経験的に分かったとのこと。

factor 1 にすると上で述べたように ill-defined な場合が発生してしまうし、factor 0 にすると ground truth のケースが表現できないので、まあ間の 1/2 やという温度感と理解した。

[yoheikikuta]

本文中や appendix に具体的な数値を入れた計算が載っているのがなかなか丁寧な論文ではある。

Figure 1 の weak_reject と weak_accept を間違えて予測する場合を考える。
proximity はデータ数が全体に比して少ない方が大きくなる（データが少ないカテゴリ間の違いは小さい。すなわち近い）ので、右側の分布の方が weak_reject と weak_accept の proximity は大きい。当たり前だがこの proximity は同じクラス同士の場合が最も大きくなる。
つまり、CEM を考えた場合は、weak_reject と weak_accept を間違えた場合に、左の分布は遠いカテゴリを間違えているので CEM は少ししか上昇せず、右の分布は近いカテゴリを間違えているので CEM は左の分布の場合よりは大きく上昇する（CEM 大きい方がいい指標で、これを最も高くするのは ground truth と同じ予測をした場合となる）。

これは Closeness Evaluation Measure が高い方が良い予測であることを考えると、同じ一件の予測の間違いでも左の分布の間違いの方がシビアであることを意味している。つまり proximity が小さいクラスを間違える（遠い）クラスを間違える方をより厳しく罰するという話になる。

全体からみた時にレアなクラス間（Figure 1 の weak_reject と weak_accept で言えば右の分布の方）が proximity の値が大きくなるが、それは情報量としてそっちの方が多くの情報を持ってるからだ、というのが情報量的な見方になる。
ナイーブには情報量が多いクラスの間違える方がペナルティが大きいという話と考えたいのだが、これは全体の分布やどこからどのクラスへ間違えたのかとかを複合的に考えなければならないので注意。ちゃんと CEM の定義の分母分子を考えないといけない。

ということで、以上まとめると CEM^{ORD} は

• 順序の関係性を考慮している
• クラス間の間隔について事前仮定なし（教師データの分布に基づいて近い遠いが決まる）

というものになっている。これは確かに単純な accuracy とかより順序分類に適していそうだ。

[yoheikikuta]

ここまで順序分類のみをターゲットにしてきたが、prox で具体的な表現に入る前までは実は割と抽象的な定義になっていて、他の尺度の場合にも一般化することができる。以下のように x ≦^b_T a を定義する（これは定義）。

ここで T としては NOMINAL, ORDINAL, INTERVAL を考えていて、F_T がそれぞれ bijective, strictly increasing, linear function となっている。これは名目尺度であれば被りのないものに map しても同値なので全単射で、順序尺度は順番が守られればいいので単調増加関数で map してもいいし、間隔尺度は間隔を保つ変換の下で性質が変わらないので linear function です、というだけの話。

この定義に基づいて $ x ≦^b_T a $ の条件を考えれば以下のようになる。

• ordinal scale: (a ≦ x ≦ b) or (b ≦ x ≦ a)
• nominal scale: (b = x) or (b ≠ a)
• interval scale: |b - x| ≦ |b - a|

ordinal scale で $ x ≦^b_T a $ が示唆するのが a ≦ x ≦ b とかなのがよくわからんという話をしていたが、ここで定義したものから出発すれば確かにそうはなる。
最初英語読んだ時に x が a よりも b に近いという読み方をしてたときに $ |x - a| $ と $ |x - b| $ を比べようとしてたのが完全に間違いだった。これは紛れがないように日本語に直すなら x と a を比べた時に x の方が b に近いということだな。言語力が低すぎてヤバい。

この拡張により、置き換えをするだけで CIQ と CEM も他の尺度の場合で定義可能となる。

[yoheikikuta]

よく使われる metric との関係性を示す。
accuracy や precision/recall は各カテゴリの確率 P(g(d) = c) が等しいという条件の下で以下のように表現できる。

accuracy は以下。

ここはさらっと書かれてるが真面目に follow しないとよくわからない。
ちょっと考えてみたメモが以下。

これは全部間違ってれば 0 になるし全部当たってれば 1 になる。というか (当たった数) / (全データ数) になるので比例というより exact に一致するのだが、比例になっているのはちとよくわからん。もうちょっと恣意性があるんかな。

precision/recall は以下。

exact match は値が最大値で normalize されていれば成立するとのこと。
こちらは割ったりしてないのでそれは納得。

[yoheikikuta]

順序分類が持っているべき 3 つの性質を紹介する。無論、この論文で定義した CEM^{ORD} はその性質を満たしている。

順序分類の性能を測る effectiveness metric Eff は以下の 3 つの条件を満足すべきである。

• Ordinal Invariance
  strictly increasing function で map しても値が不変。

• Ordinal Monotonicity
  system の出力が正解に近くなれば Eff の値は大きくなる。ちょっとごちゃっとしてるように見えるが、ようは少なくとも出力結果が異なるデータが存在して、それが s' の方が s より優れていれば、Eff(s', g) の方が大きい（良い）値になっていますよという意味。

• Imbalance
  数が小さいクラスのものを間違える方が影響が大きい。
  c1,c2,c3 が連続しているクラスで c1 が c3 よりも数が多いクラスのとき、以下を満たしているべき。情報量が多いクラスについて間違えてしまうと Eff が小さくなってしまうという話。

これらを schematic に表現したものが以下の図。上で説明したものそのままなのでいいだろう。

[yoheikikuta]

上で述べた 3 つの性質に関して、過去に順序分類で使われてきたどの metric がどの性質を満たすのかをまとめたものが以下の table になる。
冒頭のモチベーションのところでも述べられていたように、先行研究では順序分類（データとして順序尺度）が満たすべき性質を全て満たしている指標はなく、今回の提案手法でそれが初めてなされた。偉い！

この表こそがポイントなので、個別の細かい説明はここでは省略しとく。

[yoheikikuta]

実験。

提案手法は新 metric の提案なので、これを評価するにはこの metric を用いた時に他の metric と比べてどうかをいくつかの実験で試すというような meta-analysis が必要になる。

過去提案されてきた metric は単体では（この論文で議論されてきたように）順序予測の性質を捉えきれない。
まず、以下の 3 つの指標を複合的に使うことで評価することにする。

• Accuracy: class matching の情報をカバーするために使用
• Kendall Tau-a: class 順序の情報をカバーするために使用
• Mutual Information: 教師データと予測の分布を比較することで class imbalance の情報をカバーするために使用

新しい metric を使うことでこれらの情報を全てうまく扱えるようになれると期待しているが、それを測るために Unanimous Improvement Ratio (UIR) を用いる。Unanimous は全会一致という意味らしい。
やりたいことは二つの system s, s' を比較する時に、上記三つの全ての metric において性能が上回るケースがいかほどあるのかを測ることである。
それを素直に表現したものが以下である。m ∈ M はある metric である。

ここまでが meta-analysis の準備で、これを使って個別の metric の良し悪しを判定したい。
この論文では Coverage という量を定義してそれで評価をする。
これは system s, s' の出力に対して、個別の metric の差 m(s) - m(s') と UIR のスピアマン相関を取ったものである。
この論文では UIR で順序分類の評価をするという話をしたので、それが単一の metric での評価とどれくらい相関があるかというのを見ることになる。peason でなく spearman を使っているので、順位相関がみたいというものになっている。

これは 一つの dataset に対して system output s がいくつかあり、その全ての組み合わせに対して m(s) - m(s') と UIR を算出し、その相関をみているというものになる。

[yoheikikuta]

実験の設定。実験は人工データとリアルデータの 2 パターンでやっている。

• 人工データ
  • なんかごちゃごちゃ書いてあるが、結局 20,000 のラベルを準備する。平均 4 で分散が 1~3 のでトピック毎に変えながら（これは論文読んだだけだと謎概念なんだが、恐らく一定数のデータ毎に変えてるだけだと思う）数を割り当て、それを離散化して imbalanced なラベルを作成
  • 擬似的な system の出力を作成する。これは基本的には正解ラベルを出力するもので、間違える確率として {0.1, 0.2, ..., 0.9, 1} の 10 パターンの出力を作成する。間違え方（といっても以下のルールで出力するということなので必ず間違えるわけじゃなくて出力を変えようとしたけど結局当たってるというパターンもある）として以下の 5 パターンを独立につくるので、合計 10*5 = 500 個のシステム出力が作られる。以下のパターンは accuracy は高くなるけど他の指標は低くなるとかを考慮して作っている。
    • 平均値を出力 : smaj (d) = 4
    • ランダムに出力 : srand(d) = v with v ∼ U(1, 1)
    • 次のカテゴリとして出力 : stDisp(d) = g(d) + 1.
    • 順序を変更して出力 : soDisp(di) = g(d' : ord(d') = ord(d) + n/10) （これはちょっと論文だけ読んでも判断できないところがあるのだが、基本的に離散化前のラベルを振った順番で並べて、そこで順番をずらしてまた離散化するという感じ。一個上のパターンをもう少し細かいロジックにしてるくらい）
    • 近いものに変更して出力 : sprox(d) = g(d' : ord(d') = (ord(d) + rPos)/2) （rPos は U(1,n) で、これはランダムよりかは正解データに近いくらいのレベルで出力を変更している）
  • これで s の各組み合わせ 500_C_2 で m(s) - m(s') と UIR を計算してスピアマン相関係数を計算すれば Coverage が求められる
  • 実験では全ての sytem 出力を使うパターンと上の 5 個の間違い方のどれかを除いたパターンで結果を算出している
• リアルデータ
  • ラベルデータと複数の system 出力が必要なので、コンペのデータを使っている
  • 極性分析のデータ Replab 2013 と感情分析のデータ SemEval-2014, 2015 を使用
  • 自分はこれらのデータを触ったことないのでよく知らないが、著者らは http://evall.uned.es/home のシステムに関わっているのでこのデータを使っているという感じだろう

結果は以下。

一番下の CEM_{ORD}_{flat} は log を使わないバージョンで情報量的な解釈でできない場合である。
人工データでもリアルデータでも大体の場合提案 metric である CEM^ORD が最も良い（ここでの良いは accuracy, kendall tau-a, mutual information の全てが良い場合と CEM^ORD が良い場合とが高い相関係数にある）という結果になっている。

リアルデータでは一部他の metric の方が良い結果も出ているが、数値自体が 1 に近く誤差というか違いがなさそうという感じである。

accuracy, kendall tau-a, mutual information の全てが良いというのが順序分類の性質を表現するためにこの論文が用いた条件だが、それぞれの metric 単体では coverage は高くはなく、順序分類はこれまでの metric 単体では評価が難しかったことを雄弁に物語っている。（3 つの中では分布の情報を有する mutual information が最も coverage が高そう）

そのほかにも classification metric, よく使われる誤差函数, 相関係数なども単体では順序分類を評価しきれていないことがみて取れる。

また、一つの s_x を抜いた場合に最も性能がよくなるのは stDisp (あるデータのカテゴリを順序集合の次のカテゴリに map する) 場合である。順序集合として正しい出力が重要であるが、それを問答無用で一つ次のカテゴリにするというのはかなり性能に悪影響を与えていたことが如実に出ている。soDisp も他のものよりそれに近しいはずだが、実際にやってみるとそこまでカテゴリが変わらなかったということなのだろう（この辺は実験結果のデータとか残ってれば確認しやすいんだけどなぁ）。

[yoheikikuta]

ということで読了。

順序予測は本来は NLP で結構現れる問題設定のはずだが、それを適切に評価できていないということで、順序尺度が満たすべき性質に基づいた（そして情報論的なアイデアを取り込んだ）評価 metric を作成したという論文。
難しいところはそんなにないけど、硬派な感じで ACL って感じの論文で良かった。ちょっと論文だけじゃ追いきれない部分があるので実験したコードが残ってればなお良かったのだが。

ここで提案しているのは評価指標だけなので、これを学習に使えるようにできればめちゃくちゃ面白いと思う。
微分可能になるよう soft 化して、データ分布全体の情報を使っているのをミニバッチ単位に落とし込んで、とか気にしないといけないところが色々あるけどトピックとしては面白いと思う。