2016-NIPS-Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning

$X \in \mathbb{R}^d$ がサンプルで、ラベルが $Y \in \{+1. -1 \}$ である。シナリオはCase Controlである。つまり、 $p(s=+1)$ が得られないというもの。

📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data では、代理損失が非凸で対称的であるなら、提案したものが不偏な分類器であると証明されている。ならば、普通のPNやNUの学習器と同様に比較できる。

リスクの不偏推定器

PNにおいての不偏推定器

p_+(x) = p(x | Y=+1), p_-(x) = p(x | Y=-1)

$g: \mathbb{R}^d \to \mathbb{R}$ を実数の決定関数として、これによって二値分類をしている。そして $l: \mathbb{R} \times \{ +1, -1 \} \to \mathbb{R}$ をリプシッツ連続な損失関数だとする。

そして以下のようにリスクを定義する。それぞれ $p_+, p_-$ においての期待値である。

R_+(g) = \mathbb{E}_+ [ l(g(X), +1) ] \\ R_-(g) = \mathbb{E}_- [ l(g(X), -1) ]

そして。PN Learningにおける全体の損失は、 $\pi = p(Y=+1)$ だとすると、以下のような式になる。一番下は不偏推定量での推定。

R(g) = \pi R_+(g) + (1 - \pi) R_-(g) \\ \hat{R}_{PN}(g) = \frac{\pi}{n_+} \sum _{x \in X_+} l(g(x), +1) + \frac{1 - \pi}{n_-} \sum _{x \in X_-} l(g(x), -1)

下の式は先行研究によって、 $O(1 / \sqrt{n_+} + 1 / {\sqrt{n-}})$ で $R(g)$ に収束する不偏推定器であることがわかる。

PU, NUでの不偏推定器

PUではNegativeサンプルは手に入らないので、うまく $R_-(g)$ を書き換える必要がある。📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data では書き換えの一種を提案し、対称的な損失は足すと定数になるので最適化しやすいという結果になった。

そこでは、以下のように書き換えることができ、目的関数を作れる(それをさらに分解すると対称的なものがいいとかの話になる)

\mathbb{E}_X[l(g(X), -1)] = \pi \mathbb{E}_+ [l(g(X), -1)] + (1 - \pi) R_-(g) \\ R_{PU}(g) = 2\pi R_+(g) + R_X(g) - \pi \\ \hat{R}_{PU}(g) = -\pi + \frac{2 \pi}{n _+} \sum _{x \in X_+} l(g(X), +1) + \frac{1}{n_X} \sum_{x \in X_X} l(g(X), -1)

同様に、NUについても以下の式が得られる。

R_{NU}(g) = 2(1 - \pi) R_-(g) + R_X(g) - (1 - \pi) \\ \hat{R}_{NU}(g) = -(1 - \pi) + \frac{2(1 - \pi)}{n _-} \sum _{x \in X_-} l(g(X), -1) + \frac{1}{n_X} \sum_{x \in X_X} l(g(X), +1)

代理損失

01損失の代わりに、 📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data ではScaled Ramp Lossを提案している。

l_{sr}(t, y) = \max(0, \min(1, (1 - t_y) / 2))

当然だが、これはリプシッツ連続である。

リスク境界に基づいた理論的比較

識別器の所属クラスは $\mathcal{G}$ である。
真の最適の識別器は $g^*$ である。
PNで学習したときの真の識別器は $\hat{g}_{pn} = \argmin _{g} \hat{R}_{pn}(g)$ である。
PUで学習したときの真の識別器は $\hat{g}_{pu} = \argmin _{g} \hat{R}_{pu}(g)$ である。
NUで学習したときの真の識別器は $\hat{g}_{nu} = \argmin _{g} \hat{R}_{nu}(g)$ である。
代替損失関数 $l$ による損失の最小化されたものは、 $R^* = \inf _g R(g)$ である。
01損失関数 $l$ による損失の最小化されたものは、 $I^* = \inf _g I(g)$ である。

Rademacher複雑度の定義からして、所属クラス $\mathcal{G}$ のRademacher複雑度は定数 $C_G$ によって抑えられる。 $q$ はPositiveデータ、Negativeデータ、PN両方のデータの分布みたいな感じ。

R_{n,q}(\mathcal{G}) \leq C_G / \sqrt{n}

そして、以下のように、カーネル法を使うときの仮定を置いている。ヒルベルト空間 $\mathcal{H}$ を定義したら、写像した先の特徴空間もある定数で抑えられるとする。

カーネル法についての統計的機械学習で分析するときによくある手法。

Risk Bounds

同様に、 $\phi$ を広義単調増加かつ $\phi(0) = 0$ であるならば、 $1 - \delta$ 以上の確率で以下の式が成り立つ。

誤差上界としては、表現力が高いほど低く、かつ学習するデータが多いほどまた低くなる。

Rademacher複雑度を上から押さえる都合上、これらの上限の減るスピードは $O(1 / \sqrt{n_+} / \sqrt{n_-})$ である。(Rademacher複雑度を抑えると同じルートになって、後ろのルートと同じオーダーになる)この速度で、 $R$ の差は0へ、 $I$ の差は $\phi(R(g^*) - R^*)$ へ収束する。

証明の紹介

PUの式は以下のようになっている。

R(g) = 2 \pi R_+(g) + R_X(g) - \pi \\ \hat{R}(g) = 2 \pi \hat{R}_+(g) + \hat{R}_X(g) - \pi

これをもとに $\sup_g |\hat{R}_{pu}(g) - R(g)|$ を計算する。これは証明したい式から、統計的学習理論で上から評価するときに一番向いている形への変形である(同じ $g$ についてなので)。これは📄(講義ノート)統計的機械学習第2回 📄(講義ノート)統計的機械学習第3,4回にある通りである。まずここでPUにおける経験誤差と理想的なものに分解する。