Coda

メモ Learning on the Border: Active Learning in Imbalanced Data Classification

August 31, 2019

概要

表題にある論文は、不均衡データの二値分類についての予測性能を能動学習で改善する手法を提案している。 着想は、学習器のマージン付近では正例と負例がよりバランスしていると仮定し、 マージン付近にあるデータを集めることで、均衡のとれたデータセットを用意することにある。 具体的には、ラベルづけしたデータでSVMをオンライン学習し、無作為に抽出されたラベルのないデータの中で最も超平面に近いデータにラベルをつける手順をマージンの中にあるデータ数が変わらなくなるまで繰り返す。

SVMの超平面はマージン内にあるサンプルによって定められるので、当論文ではマージン内にあるサンプルは外にあるサンプルよりも貢献するという立場をとる。

超平面は次の目的関数を最小化することで求まる。

$$ \min_{{\bf w},\boldsymbol{b}, \xi_i}\frac{1}{2}{\bf w}\cdot{\bf w}^{T}+C\sum^{N}_{i=1}\xi_i $$ $$ \begin{cases} \forall i\ y_i ({\bf w}^T\phi(x_i)-b) \ge 1 -\xi_i \\
\forall i \ x_i \ge 0 \end{cases} $$

ただし、\({\bf w}\)は超平面のノルム、\(b\)はオフセット、\(y_i\)はラベル、\(\phi(\cdot)\)は入力を対応する特徴空間上のベクトルへの写像を示す。

以上の目的関数の最小化の双対問題に、次の\(W(\alpha)\)の最大化がある。

$$ \max W(\alpha) \equiv \sum^N_{i=1}\alpha_i - \frac{1}{2}\sum_{j,j}\alpha_i\alpha_jy_iy_jK({\bf x_i}, {\bf x_j}) $$ $$ \begin{cases} \forall i\ 0 \le \alpha_i \le C \\
\sum^N_{i=1}\alpha_iy_i = 0 \end{cases} $$ ただし、\(K({\bf x_i}, {\bf x_j})=\langle\phi({\bf x_i}),\phi({\bf x_j})\rangle\)はカーネル行列を示す。 このとき超平面\({\bf w}\)は $$ w = \sum^n_{i=1}\alpha_i\phi(x_i) $$ であり、\(x_i\)がマージンの外にある場合は\(\alpha_i=0\)となり、超平面の位置に影響しない。以上から、すべてのサンプルが等しく学習に貢献するわけではないことを導いている。

論文中の実験では、59件のサンプルを一度に無作為に選び、最も超平面に近いサンプルを探す。 無作為に選んだ\(L\)件のサンプルの中に母集団内で超平面に近い上位\(p\%\)にあるサンプルが含まれる確率が\(1-\eta\)であるとき、 $$ 1-(1-p\%)^{L} = 1 -\eta $$ より $$ L=\frac{\log \eta}{\log (1-p\%)} $$ となり母集団の大きさによらず\(L=59\)のとき95%の確率で超平面に近い上位5%のサンプルを抽出することができる。

感想

提案手法で集めたデータセットでSVM以外の学習器を訓練した場合にも、不均衡なデータに対して高い予測性能をだすことができるのか気になる。


論文はこちらからダウンロードできます。