2017-ICML-[PNU]Semi-Supervised Classification Based on Classification from Positive and Unlabeled Data

Appendixもある版:

Introduction

既存のSemi-supervised Learningでは、データ分布の特定の分布に依存した手法で、Unlabeledデータに依存していた(低次元の多様体の上に分布してると仮定するなど)。既存の手法では、普通に訓練した結果を仮定に従って捻じ曲げいくことでいい性能を出してきた。しかし、仮定が間違っていたとなればより悪くなる可能性だってある。

そこに、近年Cost-sensitiveでPU Learningに対処する手法が開発されてきているので、これを用いたのがこの論文である。

Background

問題設定

サンプルは $\mathbf{x} \in \mathbb{R}^d$ であり、ラベルは $y \in \{ +1, -1 \}$ の二値。
$X_p \sim_{i.i.d.} p(\mathbf{x} | y = +1)$
$X_n \sim_{i.i.d.} p(\mathbf{x} | y = -1)$
$X_u \sim_{i.i.d.} p(\mathbf{x}) = \pi p(\mathbf{x} | y = +1) + (1- \pi)p(\mathbf{x} | y=-1)$
- $\pi = p(y=+1)$ でClass Prior。
損失関数 $l$ を設け、負の値を入れると損失が出るようにする。具体的な各学習の損失を以下のように定める。

真のリスク損失 $R(g) = \mathbb{E}_{\mathbf{x},y} [l(y g(\mathbf{x}))]$ となるが、真の分布を知らないのでこれをうまく分類する必要がある。

PU Classification

$\pi = Pr(y=+1)$ とすると、以下の式の最小化となる。

R_{PU}^{NC}(g) = 2 \pi R_P(g) + \mathbb{E}_U [l(-g(\mathbf{x}))] - \pi

先行研究によって、非凸関数の損失関数が望ましいとか、 📄2014-NIPS-[Ramp]Analysis of Learning from Positive and Unlabeled Data 。

凸関数のまま割り切って使うアプローチもある。これは以下の関数の最小化となる(式変形で上の形にできる)

R_{PU}^{C}(g) = \pi \mathbb{E}_P[l(-g(\mathbf{x}))] + \mathbb{E}_U [l(-g(\mathbf{x}))]

凸であると割り切って使ってもそこまで悪くない 📄2015-ICML-[uPU] Convex Formulation for Learning from Positive and Unlabeled Data という先行研究がある。

NU Classification

同様に式変形すると、以下のようになる。

R_{NU}^{NC}(g) = 2 (1 - \pi) R_N(g) + \mathbb{E}_U[l(g(\mathbf{x}))] \\ R_{NU}^{C}(g) = (1 - \pi) \mathbb{E}_N[l(g(\mathbf{x}))] + \mathbb{E}_U [l(g(\mathbf{x}))]

PN, PU, NUベースのSemi-supervised Classification

PUNU Classification

非常に簡単なアプローチで、Positive, Negative, Unlabeledを統合するには、ある $\gamma \in [0, 1]$ によって、以下のリスクを最小化すればいい。

R_{NC-PUNU} ^ \gamma (g) = \gamma R_{PU}^{NC}(g) + (1 - \gamma) R_{NU}^{NC}(g)

これを展開すると以下のようになる。ここで、 $\gamma = 1/2$ とすれば通常のPN学習と同じであることに注意(ちょうど $\mathbb{E}_U$ の中身で打ち消し合うので)

しかし、Convexな損失関数を用いるときは、以下のような式になる。

ここで、 $\gamma = 1/2$ ならば $(1 - \gamma)l(g(\mathbf{x})) + \gamma l(-g(\mathbf{x}))$ はちょうど半々となり、これらの和は $-g(\mathbf{x})$ になる。

このことから、 $\gamma < 1/2$ の時、Negativeのクラスに対する損失がPositiveのものよりは小さくなり、 $\gamma > 1/2$ ならばPositiveのクラスに対する損失が減る。

PNU Classification

単にPU+NUにするだけではない。今度はPN+PUとPN+NUをそれぞれ用意し、新たなパラメタによってその都度PN+PUを使うか、PN+NUを使うか、単純なPNを使うかを決める。

数式では、 $\eta \in [-1, +1]$ を導入して以下のような関数にしている。 $\eta = 0$ はPNに相当で、 $\eta = +1$ はPNPU、 $\eta = -1$ はPNNUである。

導入することで、上のPNPU、PNNUについての統合した設計であると言える。

では、ConvexとNon-Convexのどちらが性能がいいのか？は実験で後述する。

実際の実装

今回の実装はカーネル法のSVMでやっており、パラメタの二乗正則化をしている。

\min _\mathbf{w} \mathbf{w} ^ T \boldsymbol{\Phi}(\mathbf{x}) + \lambda \mathbf{w} ^ T \mathbf{w}

理論解析

いつもの。

Generalization Error Bound

カーネル法で写像した先のヒルベルト空間は、重みや写像した先の関数に上界があるといういつもの仮定。

便宜のために以下のように書くとする。

Non-Convex

$1 - \delta$ 以上の確率で以下の3つの式が成り立つ。 $I(\cdot)$ は01損失における期待値。 $C_{w, \phi, \delta} = 2 C_w C_\phi + \sqrt{2 \log (3 / \delta)}$

証明

まず、展開すると以下のような式になる。

このように展開した以上、 $R_P(g), R_N(g), R_{U,P}(g), R_{U,N}(g)$ について、それぞれ経験損失と理想損失の差(同じ識別器において)の上界で評価することができる。(📄(講義ノート)統計的機械学習第2回にあるように $L_n(\hat{h}) - L(h^*)$ よりもこの形でやるとやりやすい)。それぞれ、 $1 - \delta / 3$ 以上の確率で成立する。

上の式はMcDirmidの不等式で評価している。あとはこれを代入することによって、以下の式が成り立つ。 $1 - \delta$ 以上の確率で以下が成り立つ。( $1 - \delta / 3$ 以上の確率で3つなら、 $(1 - \delta / 3) ^ 3 = 1 - \delta + \cdots$ で、後ろの省略した部分は正なので、成り立つ)