Open yoheikikuta opened 4 years ago
yoheikikuta
commented
4 years ago ACL 2020 long paper で気になった論文を読んでみようシリーズ。 ordinal classification (順序分類) における metric ということで目を引いた。
ordinal classification の問題設定でも単純な classification として解いてしまうことが多かったが、本来扱いたい情報を適切に扱えてないよなという気持ちがあった。その辺りの整理と提案 metric がどんなもんか理解してみようということで読んでみることにする。
yoheikikuta
commented
4 years ago ordinal classification は positive, neutral, negative のように相対的な順番に意味がある問題設定で、これは順序情報があるので単純な classification (class 1, 2, 3 は相対的な順番などない) とは違うものである。しかし実際には単純な classification として解いてしまうことも多く、そこで使用する metric には想定的な順番の情報はない。本来は順番があり、例えば positive が多く negative が少ないような分布をしているデータに対して、neutral を positive と間違える場合と negative と間違える場合は区別すべきはず。
この論文はそういう論点を整理し、その上で ordinal classification の metric として適切なものを提案している。
具体的な話に入る前に、誰しもがデータ分析を初めて勉強するときに学ぶ測定尺度について振り返っておく（自分は名称とかすっかり忘れていた）。
このような尺度の性質を反映した metric で測るべきだが、それができてないというのが冒頭の話。
yoheikikuta
commented
4 years ago ということで測定尺度を思い出した結果、以下のように ordinal classification は◯◯◯とは異なる、と言って違いを認識できる。
異なる、とかいうとこういう問題だと捉えて解くと間違いだという印象を与えるが、そういうことではなくて本来持っている情報を使い切っていないという意味である。そもそも間違いとは何だみたいな話はよく分からんが、とにかくこういう問題設定だと思ってもモデル学習したり新しいデータに対して予測したりはできるけど、もっと適切な設定ひいては評価方法があるという話。
ちなみに過去の公開ベンチマークで使われてきた metric には以下のようなものがある。
yoheikikuta
commented
4 years ago ordinal classification に関する先行研究がいくつか提示されるが、どれも 2010 年以前でなんか時代を感じさせますな。 詳細は必要があったら読むとして、重要なのはどの先行研究も「カテゴリ間に間隔を定めるよう事前に仮定していた」ということ。上述のようにこれは本来順序尺度が有する性質ではないので、問題を歪めて解いていたということになるだろう。
仮定する内容としては、カテゴリ間の一様な間隔（つまりは間隔尺度として扱う）、誤分類のコストが予測と答えの絶対値の差に比例するとする、などがあるらしい。
何度も繰り返すようにカテゴリ間の間隔に何か仮定して問題を解くのは順序尺度を逸脱している行為なので、それをしない適切な metric を提案しようというのがこの論文の趣旨である。
yoheikikuta
commented
4 years ago 提案 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
commented
4 years ago これを 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
commented
4 years ago 順序尺度であることを明示的に使って計算を具体化する。
$ 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
commented
4 years ago 本文中や 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
commented
4 years ago ここまで順序分類のみをターゲットにしてきたが、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 で $ x ≦^b_T a $ が示唆するのが a ≦ x ≦ b とかなのがよくわからんという話をしていたが、ここで定義したものから出発すれば確かにそうはなる。 最初英語読んだ時に x が a よりも b に近いという読み方をしてたときに $ |x - a| $ と $ |x - b| $ を比べようとしてたのが完全に間違いだった。これは紛れがないように日本語に直すなら x と a を比べた時に x の方が b に近いということだな。言語力が低すぎてヤバい。
この拡張により、置き換えをするだけで CIQ と CEM も他の尺度の場合で定義可能となる。
yoheikikuta
commented
4 years ago よく使われる metric との関係性を示す。 accuracy や precision/recall は各カテゴリの確率 P(g(d) = c) が等しいという条件の下で以下のように表現できる。
accuracy は以下。
ここはさらっと書かれてるが真面目に follow しないとよくわからない。 ちょっと考えてみたメモが以下。
これは全部間違ってれば 0 になるし全部当たってれば 1 になる。というか (当たった数) / (全データ数) になるので比例というより exact に一致するのだが、比例になっているのはちとよくわからん。もうちょっと恣意性があるんかな。
precision/recall は以下。
exact match は値が最大値で normalize されていれば成立するとのこと。 こちらは割ったりしてないのでそれは納得。
yoheikikuta
commented
4 years ago 順序分類が持っているべき 3 つの性質を紹介する。無論、この論文で定義した CEM^{ORD} はその性質を満たしている。
順序分類の性能を測る effectiveness metric Eff は以下の 3 つの条件を満足すべきである。
これらを schematic に表現したものが以下の図。上で説明したものそのままなのでいいだろう。
yoheikikuta
commented
4 years ago 上で述べた 3 つの性質に関して、過去に順序分類で使われてきたどの metric がどの性質を満たすのかをまとめたものが以下の table になる。 冒頭のモチベーションのところでも述べられていたように、先行研究では順序分類（データとして順序尺度）が満たすべき性質を全て満たしている指標はなく、今回の提案手法でそれが初めてなされた。偉い！
この表こそがポイントなので、個別の細かい説明はここでは省略しとく。
yoheikikuta
commented
4 years ago 実験。
提案手法は新 metric の提案なので、これを評価するにはこの metric を用いた時に他の metric と比べてどうかをいくつかの実験で試すというような meta-analysis が必要になる。
過去提案されてきた metric は単体では（この論文で議論されてきたように）順序予測の性質を捉えきれない。 まず、以下の 3 つの指標を複合的に使うことで評価することにする。
新しい 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
commented
4 years ago 実験の設定。実験は人工データとリアルデータの 2 パターンでやっている。
結果は以下。
一番下の 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
commented
4 years ago ということで読了。
順序予測は本来は NLP で結構現れる問題設定のはずだが、それを適切に評価できていないということで、順序尺度が満たすべき性質に基づいた（そして情報論的なアイデアを取り込んだ）評価 metric を作成したという論文。 難しいところはそんなにないけど、硬派な感じで ACL って感じの論文で良かった。ちょっと論文だけじゃ追いきれない部分があるので実験したコードが残ってればなお良かったのだが。
ここで提案しているのは評価指標だけなので、これを学習に使えるようにできればめちゃくちゃ面白いと思う。 微分可能になるよう soft 化して、データ分布全体の情報を使っているのをミニバッチ単位に落とし込んで、とか気にしないといけないところが色々あるけどトピックとしては面白いと思う。
論文リンク
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 というのを作っててそこに追加で載せているというもの。