PU learningことはじめ

一般的な教師あり学習では、各サンプルについて 正例 (positive) と負例 (negative) のラベルが与えられる。 しかしながら実際のタスクでは、正例とラベルなし (unlabeled) からなる データセットを扱う場合がある。 このような問題設定において精度良く分類を行うための手法がある。

本文

Charles Elkan and Keith Noto, "Learning classifiers from only positive and unlabeled data," KDD2008, pp. 213–220.

問題設定

サンプル  x\in\mathbb{R} について、ラベル  y\in{0,1} が 2値 (negative or positive) で与えられている。 また、サンプル  x にラベルが付与されているかどうかを  s\in{0,1} で表す。 0ならばunlabeled, 1ならばlabeledである。 これら  \langle x,y,s\rangle の組に対する不変の分布が存在する(もちろん未知である)。

正例(のうちの一部)だけがラベル付けされているとする。 すなわち、

 \displaystyle
p(s=1|x,y=0)=0

である。

このような条件のもと、 f(x)=p(y=1|x) なる 関数  f(x) を学習する。

なお、ラベル付けされる正例は、真の正例からランダムに選ばれると仮定する。 すなわち、

 \displaystyle
p(s=1|x,y=1) = p(s=1|y=1)

解法

先に結論を書く。

  1.  x s を使って、ラベル付けされている確率を出力する分類器  g(x) を学習する
  2.  s=1 なる  x に対し、  c=\frac{1}{n}\Sigma_{x\in P}g(x) を求める。
    • ここで、 P はdevセット内のラベル付けされているサンプルの集合で、  n はそれらサンプルの数である
    • ちなみに、 c は真の正例のうち、ラベル付けされているサンプルの割合である
  3.  sによる重み付けを行い  f(x) を学習する。具体的には、
    •  s=1 なる  x は単位重み(すなわち1)、ラベルを  y=1 とする
    •  s=0 なる  x は複製したのち
      • 片方に  w(x)=\frac{1-c}{c}\frac{g(x)}{1-g(x)} の重み、ラベルを  y=1
      • もう片方に  1-w(x) の重み、ラベルを  y=0 とする

詳細

 f(x) g(x) の関係

ラベル付けされる正例がランダムに選ばれるとすると、

 \displaystyle
\begin{align}
p(s=1|x) &= p(y=1\wedge s=1|x) \\
&= p(y=1|x)p(s=1|y=1,x) \\
&= p(y=1|x)p(s=1|y=1) \\
&= p(y=1|x)p(s=1|y=1)
\end{align}

ここで、 p(y=1|x)=f(x) であり、 g(x)=p(s=1|x),  c=p(s=1|y=1) とおくと、  f(x)=\frac{1}{c}g(x) である。 すなわち、もともと求めたい  f(x) は、ラベル付きである確率  g(x) に比例している。

[余談]  f(x) g(x) の増加関数になっているということは、  f(x) x のランキングのみを目的としているなら、  g(x) がそのまま  f(x) の代わりに使えるということである。

 c の推定

 c=p(s=1|y=1) は真の正例のうち、ラベル付けされているサンプルの割合である。 これを見積もる方法を考える。

論文では3つの方法が紹介されているが、ここではこのうち最良とされているものだけを述べる。 その方法とは、validation set (dev set) である  V のうち、  s=1 である  x の集合  P に対する  g(x) の平均値を取る、というものである。 この方法で  c が推定できるのは以下の式展開からわかる。

 \displaystyle
\begin{align}
g(x) &= p(s=1|x) \\
&= p(s=1|x,y=1)p(y=1|x) + p(s=1|x,y=0)p(y=0|x) \\
&= p(s=1|x,y=1)\cdot 1 + 0\cdot 0 \\
&= p(s=1|y=1) \\
&= c
\end{align}

注意

 g(x) を予測するモデルは、well-calibrated classifierである必要がある。 well-calibrated classifierとは、確率値を出力する分類器のこと。 例えば、logistic regressionは該当するが、 ナイーブベイズ、ディシジョン・ツリー、SVMは該当しない。 後処理でcalibratedになりうる。後処理の代表的なものは2つある:

  • isotonic regression
  • fitting a one-dimentional logistic regression function

unlabeledであるときにpositiveである確率

unlabeledであるときにpositiveである確率は以下のように求められる。


\begin{align}
p(y=1|x,s=0) &= \frac{p(s=0|x,y=1)p(y=1|x)}{p(s=0|x)} \\
&= \frac{[1-p(s=1|x,y=1)]p(y=1|x)}{1-p(s=1|x)} \\
&= \frac{(1-c)p(y=1|x)}{1-p(s=1|x)} \\
&= \frac{(1-c)p(s=1|x)/c}{1-p(s=1|x)} \\
&= \frac{1-c}{c}\frac{p(s=1|x)}{1-p(s=1|x)} \\
&= \frac{1-c}{c}\frac{g(x)}{1-g(x)}
\end{align}

重み付き学習

さらに、上記の結果を用いて、任意の関数  h(x,y) の期待値を算出してみる。


\begin{align}
E[h] &= \int_{x,y,s} h(x,y)p(x,y,s) \\
&= \int_x p(x)\Sigma_{s=0}^1 p(s|x) \Sigma_{y=0}^1 p(y|x,s)h(x,y) \\
&= \int_x p(x)\left(p(s=1|x)h(x,1) + p(s=0|x)[p(y=1|x,s=0)h(x,1) + p(y=0|x,s=0)h(x,0)]\right) \\
&\sim \frac{1}{m}\left(\Sigma_{\langle x,s=1\rangle}h(x,1)+\Sigma_{\langle x,s=0\rangle} w(x)h(x,1)+\left(1-w(x)\right)h(x,0)\right)
\end{align}

ここで、 w(x)=p(y=1|x,s=0) である。 上式は、 s=1 であるサンプルは単位重みで、  s=0 であるサンプルは、 重み  w(x) を持つ  y=1 のサンプルと、 重み  1-w(x) を持つ  y=0 のサンプルとして扱えばよいことを表している。

実験

従来手法であるbiased SVMに比べ、accuracy, F1-scoreで1〜2ポイント上回る。 また、従来手法は学習を何度も反復する必要があるが、提案手法ではその必要が無い ("relative time"は提案:従来=2:621)。 詳細は元論文を参照されたい。

サンプルコード

github.com

参考にしたページ