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

はじめに

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

の2種類となります。

ここで、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.

【論文紹介】unbiased PU learning: Convex Formulation for Learning from Positive and Unlabeled Data

こちらの記事の続きになります。

nnkkmto.hatenablog.com

はじめに

Convex Formulation for Learning from Positive and Unlabeled Data についてまとめたものです。

また、こちらの論文は Analysis of Learning from Positive and Unlabeled Data での研究結果における課題を解決するものになっています。

概要

  • こちらの論文で、pu分類を重み付き分類に落とし込むことができた一方で、convexなlossを使用した際はbiasが発生するという課題があった
  • そのため、pu分類においてconvexなlossを使用できる方法を提案

従来手法における課題

従来手法としてこちらの論文で提案された以下のNon-Convex PU classificationにおいて、

R(f) = 2πR_1(f) + R_X(f) − π

convexなlossを使用した場合、以下のように通常の誤差項に加え、biasとなるsuperfluous penaltyが発生します。そのため、log lossやhinge lossなどのconvexなlossを適用した場合は誤った決定境界の決定に繋がります。

f:id:nnkkmto:20210511212246p:plain

loss ll(z)+l(-z)=1 を満たす場合、つまりnon-convexなlossを使用した場合はこのbiasは発生しないが、non-convexなlossを使用した場合目的関数もnon-convexとなるため計算量も多く、局所解に陥る可能性があります。

この課題を解決するため、本論文ではconvexなpu分類(Convex PU classification)を提案しています。

提案手法:Convex PU classification

ここで、zero-one lossを考えたとき、以下が成り立ちます。

f:id:nnkkmto:20210511212305p:plain

pu分類においてnegativeは観測できないため、通常のpn分類における以下の目的関数に代入すると、

f:id:nnkkmto:20210511212321p:plain

こちらの目的関数を得ることができます。

f:id:nnkkmto:20210511212337p:plain

ここで、\tilde{l}(x)=l(z)-l(-z)となるcomposite loss \tilde{l}(x) を導入した場合、pu分類の目的関数は以下のように、positiveに対してはcomposite lossを、unlabeledに対しては通常のlossを適用するものとして書くことができます。

f:id:nnkkmto:20210511212351p:plain

ここで、全てのlossに対してこちらの目的関数がconvexになる訳ではなく、

  • lossがconvexである
  • \tilde{l}(x)=-z つまり l(z)-l(-z)=-z

を満たす場合のみ、上記目的関数がconvexとなります。

条件を満たすloss

詳細は論文を見ていただきたいのですが、convexなlossの中でも \tilde{l}(x)=-z を満たす、つまり目的関数がconvexになるlossは以下の通りです。(NotesがConvexであるもの)

f:id:nnkkmto:20210511212410p:plain

hinge lossに関しては条件を満たさないため、その代替案としてdouble hinge lossが論文内で提案されています。

最後に

NNやGBDTなど非線形なモデルにも適用可能にしたものがPositive-Unlabeled Learning with Non-Negative Risk Estimatorとなります。こちらの論文を前の論文と共に、以下の記事でまとめています。

nnkkmto.hatenablog.com

【論文紹介】Analysis of Learning from Positive and Unlabeled Data

はじめに

Analysis of Learning from Positive and Unlabeled Data の内容をまとめたものになります。

pu-learningを重み付き分類問題に落とし込むという点で、以前以下の記事で検証したLearning Classifiers from Only Positive and Unlabeled Data に続く研究となっているように思います。

nnkkmto.hatenablog.com

また、こちらの研究での課題を引き継いだ研究としてConvex Formulation for Learning from Positive and Unlabeled Dataがあります。

論文概要

  • pu分類問題は重み付き分類(cost-sensitive classification)に落とし込めるため、weighted SVMなどで解くことができる
  • ただし、提案手法ではhinge lossを含むconvexなlossを使用した場合、誤った分類に繋がる
  • 一方で、non-convexなlossを使用した場合は局所解に陥る可能性がある

pu分類問題の重み付き分類問題への落とし込み

pu-learningとは何かに関しては、こちらの記事をご参照ください

通常のpn分類問題と重み付き分類問題

positive(1) vs negative(-1) の誤分類を最小化する関数は以下のように書くことができます。

f:id:nnkkmto:20210511210157p:plain

π は全sampleのうちpositiveの含まれる割合であり、n_positive / (n_positive + n_negative) で推定可能です。

ここで、P_1 はpositive, P_{-1} はnegativeとなる確率とした時、以下のように R_1 はfalse negative rate, R`_{-_1} はfalse positive rateの期待値です。

f:id:nnkkmto:20210511210214p:plain

言い換えると、R_1f(X)P_1 に対してnegativeをとなる確率、 R_{-1}P_{-_1} に対してpositiveとなる確率となります。

また、ここでcost-sensitiveつまり重み付き分類は、上記分類器にクラス単位のcostを加えたものとして以下のように書くことができます。

f:id:nnkkmto:20210511210231p:plain

pu分類問題

ここで上記pn分類の R(f) において、pu-learningにおいてはnegativeが観測できないため、上記pn分類から R_{-1} 項をなくしたいというのがモチベーションになります。

まず、unlabeled(positiveとnegativeが含まれる)である確率 P_x を以下とします。

f:id:nnkkmto:20210511210251p:plain

ここで、Rx(f)f(X)P_x に対してpositiveとなる確率とした場合、Rx は以下のように変形できます。

f:id:nnkkmto:20210511210309p:plain

そのため、上記pn分類における R(f) は以下のように変形することができます。

f:id:nnkkmto:20210511210338p:plain

そして、ηP_x に対して P_1 が占める割合とすると、以下のようにcost-sensitiveな分類に落とし込むことができます。また、ηn_positive / (n_positive + n_unlabeled) で推定することができ、pn分類における π と対応するものになっています。

f:id:nnkkmto:20210511210355p:plain

これにより、R_{-1}(X) 項をなくした上で重み付き分類問題へと落とし込むことができています。

ただしここで、π のみpositive negativeなデータセットからしか推定できない値となるため、他の方法を使って推定することが必要になります。

convexなlossの使用

SVMで使用されるlossのうち、convexなlossであるhinge loss

f:id:nnkkmto:20210511210412p:plain

non-convexなlossであるramp loss

f:id:nnkkmto:20210511210425p:plain

こちらの二つのlossに関して、上記pnでの R(f) へ適用できるかを考えます。

ramp lossを適用した場合は以下となります。

f:id:nnkkmto:20210511210438p:plain

non-convexであるramp lossに関して、以下が成り立ちます。

f:id:nnkkmto:20210511210455p:plain

そのため、pnと同じ式に変形可能です。

f:id:nnkkmto:20210511210510p:plain

一方で、下記の図からわかるように、hinge lossに関してはconvexであるため、以下の図からわかるように、l(-z)+l(z)=1 が成り立ちません

f:id:nnkkmto:20210511210525p:plain

そのため、hinge lossを適用した場合、以下のように余計な項(superfluous penalty)がつくため、誤った決定境界になります。

f:id:nnkkmto:20210511210541p:plain

論文のexperimentsではこの内容が検証されていて、superflous penaltyは π が大きくなるにつれ大きくなるため、それに伴いhinge lossとramp lossのaccuracyの差も開くことなども明記されています。

後続の論文

この次の論文がConvex Formulation for Learning from Positive and Unlabeled Dataであり、positive項とunlabeled項で違うlossを使用することでconvexなlossを使えるようにし、pu分類においてglobalな解を得られるようになっています。

また、Positive-Unlabeled Learning with Non-Negative Risk Estimatorは、非線形モデルに対しても適用できるようにした手法が提案されています。

追記

後続の論文であるConvex Formulation for Learning from Positive and Unlabeled Dataは以下に、

その後続であるPositive-Unlabeled Learning with Non-Negative Risk Estimatorに関しては、これら論文のまとめを含めて以下にまとめています。

nnkkmto.hatenablog.com