不均衡データはundersampling+baggingしろ、という話

まとめ

不均衡なデータの分類器を学習するときはundersampling+baggingすべし。 特に以下の場合に、コストを調整する手法やoversampling(SMOTEなど)に対して優れている。

  • 次元数が多い
  • 少数クラスのデータ数(の比率)が少ない
  • 学習データの規模が小さい

きっかけ

不均衡なデータを扱う問題に遭遇したので、先人たちの工夫について調べていたところ、以下のツイートを発見した。

ここで紹介されている論文、およびその解説記事などを読み漁った。本記事ではそれらをつまみ食いした知見をまとめる。

論文

Byron C Wallace, Kevin Small, Carla E Brodley and Thomas A Trikalinos, "Class imbalance, redux," Proc. Int'l Conf. Data Mining (ICDM), pp. 754–763. 2011.

不均衡データによって生じる分類器のバイアス

まず、不均衡データによって分類器にバイアスが生じる様子を示す。

f:id:mamo3gr:20210113224210p:plain
不均衡データで学習した線形分類器の識別境界(論文より引用)

簡単のため線形分類器で2値分類をする場合を考える。正規分布のような山は、それぞれ正例と負例の真の分布を表す(左側が正例、右側が負例である)。これらの分布から取り出されたサンプルを、バツ印(正例)と四角(負例)で表している。図から明らかなように、正例がminority classである。さらに、識別境界を w と表し、その左側の領域を  R^+_w, 右側の領域を  R^-_wと記す。

ここで、理想的な境界は、真の分布から  w^{*} とわかる。しかしながら、サンプルから(例えばマージン最大化で)学習された境界は、点線で示された  \hat{w} のようにバイアスがかかってしまう。

バイアスが発生する条件

次に、このようなバイアスが発生する条件を考える。

データセットに含まれる正例の集合を  D^+, 負例の集合を  D^- とする。データセット  D = D^+ \cup D^- で学習したときの経験損失 L_D(w) は、偽陰性偽陽性のコスト(ペナルティ)をそれぞれ  C_{fn}, C_{fp} とすると、

 L_D(w) = C_{fn}|\{ x|x\in D^+ \wedge x\in R^w_-\}| + C_{fp}|\{ x|x\in D^- \wedge x\in R^w_+\}|

となる。要は、偽陰性の数×コストと、偽陽性の数×コストの和である。このとき、バイアスが生じる必要十分条件は、次のように書ける。

 \exists w^\gamma s.t. \forall w' \in \{w: R^w_+ \geq R_+^{w^*}\}, L_D(w^\gamma) < L_D(w')

すなわち、理想的な境界  w^* の右側にあるすべてのどんな境界よりも、経験損失を小さくする境界が左側に存在するとき、バイアスが生じると言っている。

このようにバイアスが発生する、すなわち  w^\gamma が存在する条件を考える。正例と負例の真の分布をそれぞれ  P(x), G(x) とし、prevalence(母集団における正例の割合)を  \pi とすると、

 (1-\pi)C_{fp}\int_{R^+_{w^*}}G(x)dx>\pi C_{fn}\int_{R^-_{w^*}}P(x)dx

のとき、 w^\gamma が存在しうる。

バイアスを低減するためのアンダーサンプリング、およびbagging

上式を成立しにくくするためには、 \pi = 0.5とすればよい。すなわち、majority classをアンダーサンプリングし、クラス間のデータ数を揃えればよい。

アンダーサンプリングはバイアスを低減できる一方で、モデルのvarianceは増えてしまう(学習される識別境界が、ランダムサンプリングによってばらつくことを言っている)。このvarianceを抑えるために、baggingするのがよい。

コストの調整やオーバーサンプリング

コストの調整

不均衡データに対する対処法として、偽陰性偽陽性のコストに重みをつける手法が知られている。しかしながら、このような重み付きコストが効果を発揮しにくい場合がある。

いま、 C_{fn}=C_{fp}=1 (同じ重み)として、ある境界  \hat{w}_1 が学習できたとする。ここで、 C_{fn} \beta 倍することを考える。このコスト増加によって境界  \hat{w}_1 が動くのは、 \hat{w}_1 が1つ以上の偽陰性をもたらす場合だけである。このような偽陰性のデータが無いとき、 \beta にかかわらず、 \hat{w}_1 は既に損失関数を最小化している。なお、 \hat{w}_1 を動かすような偽陰性が観測される確率は次のように書ける。

 \pi|D|\int_{R^-_{\hat{w}_1}}P(x)dx

上式より、以下のような場合に  C_{fn} の増加が  \hat{w}_1 を動かす、すなわちバイアスの低減に寄与しにくいことがわかる。

  • prevalence  \pi が低い場合(正例の割合が小さい場合)
  • データセットの規模が小さい場合(データ数  |D| が少ない場合)

また、 P も寄与を左右する。具体的には、理想的な境界  w^* の周辺で  P が密である場合に、コストの調整はバイアス低減に寄与しやすい。

オーバーサンプリング (SMOTE)

重み付きコストの他に、SMOTEのようなオーバーサンプリングに基づく手法も知られている。SMOTEでは、minority classのデータ同士で近いものの間に新しいデータを内挿することで、データ数を増やす。したがって、SMOTEで新たに生成されるデータは、既に存在するminorityなデータの凸包 (convex hull) の外側に現れることはない。これより、SMOTEがバイアスの低減に効果を発揮するのは、コストを調整する手法が効果を発揮する場合と同様である。SMOTEによって新しく生成されたデータが境界  \hat{w}_1 を動かすには、このデータが偽陰性とならなければいけない。

実験

論文ではシミュレーションデータや実際のデータセットで実験し、ここまで述べた理論の裏付けをしている。内容は省略。

関連トピック

予測確率のバイアス

アンダーサンプリングによって、分類器の予測確率にバイアスが生じてしまう。アプリケーションにて予測確率が重要な場合は、キャリブレーションすべきとのこと。

参考:ダウンサンプリングによる予測確率のバイアス - sola

DNN (Deep Neural Network) への適用

モデルがDNNの場合は、訓練や推論の時間的にもモデルの容量的にもbaggingを単純に適用するのは難しいことが多い。これに対して、ミニバッチ内でアンダーサンプリングを行うことで、似たような効果があるようだ。

参考:不均衡データ分類問題をDNNで解くときの under sampling + bagging 的なアプローチ - BASEプロダクトチームブログ

参考文献