【論文紹介】nnPU learning: Positive-Unlabeled Learning with Non-Negative Risk Estimator

PUlearning 機械学習 論文紹介

はじめに

Positive-Unlabeled Learning with Non-Negative Risk Estimator について過去論文を読みつつまとめたものになります。 勘違いしている点などあればご指摘いただけると幸いです。

従来研究における流れ

※ 記法が以前の論文と今回の論文で異なるので、この記事では今回の論文の記法に揃えます。

  • g: 決定関数

  • l(t, y): tを予測値、yをground truthとする損失関数

  • R(g): 期待損失

Positive Negative Classification

通常のpositive negative分類の期待損失R_{pn}(g)は、false negative, false positiveであるriskを最小化するものとして以下の経験損失から推定可能です


\hat{R}_{pn}(g) = π\hat{R}_p(g) + (1-π)\hat{R}_n(g)

ここで、

\hat{R}_p(g) = (1/n_p)\sum^{n_p}_{i=1} l(g({x_i^p}), +1)
\hat{R}_n(g) = (1/n_n)\sum^{n_n}_{i=1} l(g({x_i^n}), -1)


また、 π = p(Y = +1)であり、全てのsampleからpositiveが発生する確率となります。positiveが全て観測される場合は n_p / (n_p + n_n) で推定可能です。

Positive Unlabeled Classification

positive unlabeledな分類は、positiveの一部のみが観測されるという状況を問題とします。 そのため、サンプルの構成は

  • positive: 全positiveのうち観測された一部のpositive
  • unlabeled: 観測されなかったpositive + 全negative

の２種類となります。

ここで、negativeが観測できないため、期待損失 R_{pn}(g)を推定するには上記 \hat{R_n}(g)を置き換えてあげる必要があります。

また、 πも不明となりますが、これに関しては別途推定する必要があります。ここでは πは事前にわかっているものとします。

従来手法1: Non-Convex PU learning

このことから、positive unlabeledな問題設定において期待損失 R_{pn}(g)を推定するため、一つ目の論文であるAnalysis of Learning from Positive and Unlabeled Dataでは、以下の経験損失が提案されています。


\hat{R}_{pu}(g) = 2π\hat{R}_p(g) + \hat{R}_u(g) - π

ここで、

\hat{R}_u(g) = (1/n_u)\sum^{n_u}_{i=1} l(g({x_i^u}), -1)


こちらは、 l(t, +1) + l(t, -1) = 1となる損失関数、つまりnon-convexな損失関数のみbiasなく適用可能になります。

しかし、それに伴い問題点として

  • convexな損失関数を適用した際に、biasが発生し誤った決定境界の決定に繋がる
  • 経験損失がnon-convexとなるため計算量が多く局所解に陥る可能性がある

があります。

従来手法2: Convex PU learning

それらの問題点に対して、positive unlabeledな問題設定においてconvexな損失関数を使用して期待損失$R_{pn}(g)$を推定する方法を提案した論文がConvex Formulation for Learning from Positive and Unlabeled Dataで、以下の経験損失によって推定することが提案されています。


\hat{R}_{pu}(g)=\pi_{p} \hat{R}_{p}^{+}(g)-\pi_{p} \hat{R}_{p}^{-}(g)+\hat{R}_{u}^{-}(g)

ここで、

\hat{R}_p^+(g) = (1/n_p)\sum^{n_p}_{i=1} l(g({x_i^p}), +1)
\hat{R}_p^-(g) = (1/n_p)\sum^{n_p}_{i=1} l(g({x_i^p}), -1)
\hat{R}_u^-(g) = (1/n_u)\sum^{n_u}_{i=1} l(g({x_i^u}), -1)


こちらに関しては

  • 損失関数がconvexである
  • l(t, +1) - l(t, -1) = -t

の両方を満たす場合のみ、convexになります。

制約を満たさないconvexな損失関数としてはhinge lossなどが挙げられますが、こちらの論文ではhinge lossに関しては代替案としてdouble hinge lossを提案しています。

また、今回取り上げる論文ではこれらをbiasが発生しないという意味で、unbiased PU learning (uPU) と呼んでいます。この記事でもその呼び方を使用します。

uPUとPNの比較

Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learningにおいて、unbiased PUとPNの比較が行われています。

まず、uPUにおいては、以下の変形を用いています。

(1 - π)R_n^-(g) = R_u^-(g) + πR_p^-(g)

ここで、(1 - π)R_n^-(g)をnegative dataから推定する際の収束率はO_p((1-π)/\sqrt{n_n})、

R_u^-(g) + πR_p^-(g)をpositive, unlabeled dataから推定する際の収束率は O_p(π/\sqrt{n_p} + 1/\sqrt{n_u}) となります。

このことから、

π/\sqrt{n_p} + 1/\sqrt{n_u} < (1-π)/\sqrt{n_n}

である時にuPUはPNよりも良いパフォーマンスとなります。

しかし、これは常に成り立つ訳ではなく、

  • l(t, +1) + l(t, -1) = 1となる
  • 損失関数がLipschitz continuousである
  • ありうる関数の集合GのRandemacher complexityがサンプルサイズnの増加に伴いO(1/\sqrt{n})で減少する

という制約満たした場合のみ成り立ちます。

unbiased PUにおける課題

ここで、上記最後の制約により、データ量に対してモデルの複雑性が高い場合にuPUはPNよりも悪いパフォーマンスとなります。

f:id:nnkkmto:20201225124844p:plain

こちらは n_p = 100, n_u = 59,900 のデータを用いて、784-100-1のRelu層を持つMLPを学習させたものとなります。 uPUのtrainにおいて、あるepochから経験損失 \hat{R}_{pu}が負の値になり、それに伴いtestの経験損失も悪化しています。過学習しているのがわかります。

提案手法: non-negative PU learning (nnPU)

ここで、どんな gに対しても期待損失は R(g) \geq 0である一方、上記検証では \hat{R}_{pu}は減少し続け負の値になっています。

これは、期待損失に関しては常に

R_u^-(g) - \pi R_p^-(g) = (1-\pi)R_n^-(g) \geq 0

となる一方で、経験損失に関しては

\hat{R}_u^-(g) - \pi \hat{R}_p^-(g) \geq 0

が必ずしも成り立たないことが原因となっています。

non-negative risk estimastor for PU learning

このことから、

\hat{R}_u^-(g) - \pi \hat{R}_p^-(g) \geq 0

が常に成り立つような経験損失 \tilde{R}_{pu}がこの論文では提案されています。


\tilde{R}_{\mathrm{pu}}(g)=\pi_{\mathrm{p}} \hat{R}_{\mathrm{p}}^{+}(g)+\max \left\{0, \hat{R}_{\mathrm{u}}^{-}(g)-\pi_{\mathrm{p}} \hat{R}_{\mathrm{p}}^{-}(g)\right\}


ここで、経験損失 \tilde{R}_{pu} を最小化する

\tilde{g}_{pu}をEmpirical Risk Minimizerとして、

\tilde{g}_{pu}を見つけ出す過程を本論文ではnon-negative PU learning (nnPU)と呼んでいます。

使用する損失関数

f:id:nnkkmto:20201225172421p:plain

前述のように、もし関数 gが線形である場合は

  • convexな損失関数である
  • l(t, +1) - l(t, -1) = -t（以下図における(5)）

の両方を満たす損失関数を使用した場合は凸最適化になります。

一方で、関数 gが非線形である場合はこれら損失関数を使用しても凸最適化にはなりません。

そのような場合は勾配が常にnon-zeroとなり既存のgradient methodを適用できるsigmoid lossを使用することをこちらの論文では提案しています。

最適化アルゴリズム

uPUと違いnnPUは経験損失においてmaxをとるため、そのままでは並列化できません。そのため、最適化においては以下のアルゴリズムが提案されています。

f:id:nnkkmto:20201225175735p:plain

ここで、ハイパーパラメータ βは

r_i = \hat{R}_u^-(g) - \pi \hat{R}_p^-(g)

としたときの許容量で、 r_i \geq - βの範囲で許容します。そのため、 βが0に近いほど許容量は小さくなります。

もう一つのハイパーパラメータ γは

r_{i} < - β

となった時にstep-sizeをどれだけ減衰させるかを指します。 γの値が0に近いほどより強く過学習を防ぐことになります。

最後に

著者によるChainerでの実装が以下で公開されています。

github.com

参考文献

⁣C. Elkan and K. Noto. Learning classifiers from only positive and unlabeled data. In KDD, 2008.

⁣M. C. du Plessis, G. Niu, and M. Sugiyama. Analysis of learning from positive and unlabeled data. In NIPS, 2014.

⁣M. C. du Plessis, G. Niu, and M. Sugiyama. Convex formulation for learning from positive and unlabeled data. In ICML, 2015.

⁣G. Niu, M. C. du Plessis, T. Sakai, Y. Ma, and M. Sugiyama. Theoretical comparisons of positiveunlabeled learning against positive-negative learning. In NIPS, 2016.

Ryuichi Kiryo, Gang Niu, Marthinus Christoffel du Plessis, and Masashi Sugiyama. Positive-Unlabeled Learning with Non-Negative Risk Estimator. Advances in neural information processing systems. 2017.