抄訳 RUSBoost: A Hybrid Approach to Alleviating Class Imbalance(2010)

#Under Sampling

November 13, 2022

RUSBoostは、random undersampling(RUS)とAdaBoostを応用し、不均衡データの予測性能を改善する。類似の先行研究であるSMOTEBoostよりも学習時間が短く、アルゴリズムが単純である。アンダーサンプリングで学習データを減らせば、学習時間を短くできるが、学習器に与える情報が減る。一方、AdaBoostは、前に訓練した弱学習器が誤分類したデータに高い重みを与え、次の弱学習器を学習し、予測性能を上げる。 AdaBoostを借りることで、単分類の難しい少数クラスのサンプルに高い重みを単純に与えられる。

$(x_1, y_1),\dots (x_m, y_m)$からなる学習データの集合を$S$とし、$y^r\in Y, |Y|=2$の二値分類のタスクをとく。 $t\in [1,T]$回目の学習における$i$番目のサンプルの重みを$D_t(i)$とし、$D_1(i)$で$1/m$で初期化する。 $t$回目の訓練には、少数クラスの割合が$N\%$になるようにアンダーサンプリングしたデータ集合$S’_t$を使い、弱学習器$h_t:X\times Y\rightarrow [0, 1]$を訓練する。 $D_t$で重みづけした$S$に$h_t$を適用し、疑似損失$\epsilon_t$から重みの更新パラメタ$\alpha_t$を求め、$t+1$回目の重みを計算する。

$$ \begin{align*} \epsilon\_t &= \sum\_{(i,y): y\_i\neq y}D\_t(i)(1-h\_t(x\_i, y\_i) + h\_t(x\_i, y))\\\\ \alpha\_t&=\frac{\epsilon\_t}{1-\epsilon\_t}\\\\ D\_{t+1}(i)&=D\_t(i)\alpha\_t^{\frac{1}{2}(1+h\_t(x\_i,y\_i)-h\_t(x\_i,y:y\neq y\_i))}\\\\ D\_{t+1}(i)&:=\frac{D\_{t+1}(i)}{\sum\_iD\_{t+1}(i)} \end{align*} $$

以上により、弱学習器を束ねた学習器$H(x)=\textrm{argmax}_{y\in Y}\sum^T_{t=1}h_t(x,y)\log\frac{1}{\alpha_t}$をえる。

論文へのリンク

所感

SMOTEBoostよりも学習時間が短いとあるが、論文中には学習時間を比較した評価がない。アンダーサンプリングとバギングで不均衡データに対処する手法もある。抄訳はこちら