#論文のメモ
Learning from Incomplete and Inaccurate Supervision
のメモ

弱教師あり学習の勉強の際に見つけた論文。
後述するが、新規性が高い。
論文内にある式変形を順に追っていく。

##1. Abstract
一般的に教師あり学習はground-Truthを示すラベルを持つ多くの訓練データを必要とする。
しかし、コストや手間の問題から現実的にこれらのデータを集めることは難しいとされる。
本論文では弱教師によって学習することを考える。その弱教師のパターンは以下の三つが現状存在する。
・Incomplete supervision
・Inaccurate supervision
・Inexact supervision

#2. Introduction
今回は、Incomplete supervision, Inaccurate supervisionの二つを融合したい。
ここで、一部にはラベルが与えられ、一部にはラベルが与えられていないものを訓練データとして与え、ラベルが与えられているものに関してはそのラベルが本当に正しいかはわからないと仮定する。
(正しいかわからないものの例：本当のラベルは+1だが観測値つまり訓練データに与えられているラベルは-1)
このようなデータが与えられる状況は現実世界に多く存在する。

今回二つのsupervisionを融合して考えているが、それぞれの学習タスクはSemi-Supervied Learning, Noisy Label Learning として提案されている。
しかし単純に二つのモデルを融合していしまうと、それぞれのタスクで互いの状況がマイナスに働く。
(例：SSLではLabeled dataに正確にラベルが与えられていると仮定しているのでNNLでの状況がマイナスに働く。)

この二つのタスク(SSLとNNL)からいいとこどりしたモデルを作りたい。

この論文の重要なポイントとして筆者は以下の二つにまとめている。

Incomplete,Inaccurate supervisionから同時に学習したい。現実世界で多くの活用事例が考えられるにも関わらず今まで研究がほとんど行われていない。
a novel learning method の提案。Unlabeled dataの力を借りて、Noisy labeled dataの作用を緩和させてあげる。

#3. Preliminary
##3.1 Complete&Accuracy
ここでは初めにComplete&Accuracy(つまり普通の教師あり学習)についての定式化。
まず、データ

(x,y) \in (\mathcal{X}, \mathcal{Y}), \mathcal{X}\subset\mathbb{R}^d, \mathcal{Y}=\{-1,+1\}

を用意。
そのデータは、

Clean Positive P = \{x_i,+1\}_{i=1,...n_P} \\
Clean Negative N = \{x_j,-1\}_{i=1,...n_N}

で構成される。(PはPositive, NはNegativeを表す)
一般的な学習の目的は、以下に示す二値マッピングを求めることである。

g: \mathbb{R}^d \to \mathbb{R}(x \to y)

損失関数 l, リスク関数Rを導入する。

\begin{eqnarray}
R(g) &=& \mathbb{E}_{(x,y)\sim\mathcal{D}}[l(g(x), y)] \\ 
&=& \theta_P\mathbb{E}_P[l(g(x), +1)] + \theta_N\mathbb{E}_N[l(g(x), -1)] \tag{1}
\end{eqnarray}

ここで\theta_Pはラベルが+1の, \theta_Nはラベルが-1のデータの割合のようなもの。

しかし、実際にすべてのデータが観測できるわけではないので（期待値が求められない）、観測値の平均を求め、このリスク関数を書き換えてあげる。

\begin{eqnarray}
\hat{R}(g) = \frac{\theta_P}{n_P}\sum_{i=1}^{n_P}l(g(x_i), +1) + \frac{\theta_N}{n_N}\sum_{i=1}^{n_N}l(g(x_j), -1) \tag{2}
\end{eqnarray}

このときの、最適なマッピングは、

\DeclareMathOperator*{\argmin}{arg\,min}
g^* = \argmin_{g \in \mathcal{G}}R(g), \hat{g} = \argmin_{g \in \mathcal{G}}\hat{R}(g)

である。（今後実験的に得られた値（観測値）についてはハットを付ける）

##3.2 Incomplete&Accuracy
ここではIncomplete、つまりUnlabeled data が与えられた場合について述べる。

そのデータは、

Clean Positive P = \{x_i,+1\}_{i=1,...n_P} \\
Unlabeled U = \{x_k\}_{1,...,n_U}

で構成される。(Uはunlabeledデータのこと)
ラベル付けされいるデータはすべて+1をラベルとして持つ。
今回はNegative dataが与えられていないので、(1)の二項目は用いることが出来ない。

よって、Unlabeled data がすべてNegativeであると考えると、

\begin{eqnarray}
\mathbb{E}_U[l(g(x), -1)] &=& \theta_P\mathbb{E}_P[l(g(x), +1)] + \theta_N\mathbb{E}_N[l(g(x), -1)] \\ 
&=& \theta_P - \theta_P\mathbb{E}_P[l(g(x), +1)] + \theta_N\mathbb{E}_N[l(g(x), -1)]
\end{eqnarray}

となる。

これを(1)に代入するとリスク関数は、

R(g) = 2\theta_P\mathbb{E}_P[l(g(x), +1)] + \mathbb{E}_U[l(g(x), -1)] - \theta_P

となる。

よって、観測値によるリスク関数は、

\begin{eqnarray}
\hat{R}_{PU}(g) = \frac{\theta_P}{n_P}\sum_{i=1}^{n_P}l(g(x_i), +1) +\sum_{k=1}^{n_U}l(g(x_k), -1)
\end{eqnarray}

となる。

このときの、最適なマッピングは、

\DeclareMathOperator*{\argmin}{arg\,min}
\hat{g}_{PU} = \argmin_{g \in \mathcal{G}}\hat{R}_{PU}(g) \tag{3}

である。
#4. The Proposed Approach

##4.1 Complete&Inaccurate
ここではノイズ(one_sided instance-dependent label noise)を導入する。
これは、一方的にラベルを誤って観測させるノイズ。
(i.e.　観測されたラベルが-1のものの本当のラベルは+1であるかもしれないが、観測されたラベルが+1のものの本当のラベルは確実に+1であるといえる)

このデータは、

Clean Positive \widetilde{P} = {x_i,+1}_{i=1,..,n_{\widetilde{P}}}\\
Noisy Negative \widetilde{N} = {x_i,+1}_{i=1,..,n_{\widetilde{N}}}

で構成される。

ここで\widetilde{\theta}_Pは観測されたラベルが+1の, \widetilde{\theta}_Nは観測されたラベルが-1のデータの割合のようなもの。

本当のラベルが+1であるデータが-1として観測される確率は、

h(x) = Pr[\hat{y}=-1|x,y=1]

である。

観測値が+1のものは全て正確にラベル付けされてるので、

Pr[y=+1|x,\hat{y}=+1] = 1

である。

Definition1

このときのリスク関数は、

R_{oIS} = \theta_{\widetilde{P}}\mathbb{E}_{\widetilde{P}}[\sigma_{+}l(g(x), +1)] + \theta_{\widetilde{N}}\mathbb{E}_{\widetilde{N}}[\sigma_-l(g(x), -1)]

である。

ここで、この式におけるweightは、

\begin{split}
&\sigma_+(x) = \frac{1}{Pr[\hat{y}=+1|x,y=+1]} \\
&\sigma_-(x) = Pr[y=-1|x,\hat{y}=-1] 
\end{split}

と定義される。

Theorem1

このとき、

R_{oIS}(g) = R(g)

が成り立つ。

Definition2

このときの観測値によるリスク関数は、

\hat{R}_{oIS}(g) = \frac{\theta_{\widetilde{P}}}{n_{\widetilde{P}}}\sum_{i=1}^{n_\widetilde{P}}\sigma_+(x_i)l(g(x_i), +1) +\frac{\theta_{\widetilde{N}}}{n_{\widetilde{N}}}\sum_{j=1}^{n_{\widetilde{N}}}\sigma_-(x_i)l(g(x_j), -1)

である。

このときの、最適なマッピングは、

\DeclareMathOperator*{\argmin}{arg\,min}
\hat{g}_{oIS} = \argmin_{g \in \mathcal{G}}\hat{R}_{oIS}(g)

である。

##4.2 Incompleteにおけるweightの検証
上記したweightはNoisy dataには当てあはまるが、Unlabeled dataには対応できない。
しかし、うまく調整することでそこからIncompleteのいいところを取ってくることが出来る。
ここでは、weightの推定にmaching methodを用いる。
Positiveにおけるweightは、

\sigma_+(x) = \frac{Pr[x,y=+1]}{x,\hat{y}=+1} = \frac{\theta_PPr[x|y=+1]}{\theta_{\widetilde{P}}Pr[x|\hat{y}=+1]} = \frac{\theta_P}{\theta_{\widetilde{P}}}\sigma_{+_r}(x)

となり、Negativeの方も同様に求められる。

ここで、\sigma_{+_r}は密度比であり、これを推定したい。

大数の法則より観測値のθはそれぞれ、

\begin{split}
&\hat{\theta}_P = \frac{n_{y_{PU}=+1}}{n_{\widetilde{P}} + n_{\widetilde{N}}} \\
&\hat{\theta}_{\widetilde{P}} = \frac{n_{\hat{y}=+1}}{n_{\widetilde{P}} + n_{\widetilde{N}}}
\end{split}

となる。

ここで、

n_{y_{PU}=+1}は観測されたPositive dataの数 \\
n_{\hat{y}=+1}は(3)により推定されるPositive dataの数

である。

Definition3

ブレグマンダイバージェンスを用いると、

\begin{split}
&B_f(\sigma_{+_r}||\hat{\sigma}_{+_r}) = \int Pr[x|\hat{y}=+1]\nabla f(\hat{\sigma}_{+_r}(x))\hat{\sigma}_{+_r}(x)dx \\
&- \int Pr[x|\hat{y}=+1]f(\hat{\sigma}_{+_r}(x))dx - \int Pr[x|y=+1]\nabla f(\hat{\sigma}_{x_r}(x))dx
\end{split}

となるので、
観測値によるブレグマンダイバージェンスは、

\begin{split}
\hat{B}_f(\sigma_{+_r}||\hat{\sigma}_{+_r}) = 
&\frac{1}{n_{\widetilde{P}}}\sum_{i=1}^{n_{\widetilde{P}}}\nabla f(\hat{\sigma}_{+_r}(x))\hat{\sigma}_{+_r}(x_i) - \frac{1}{m}\sum_{i=1}^{n_{\widetilde{P}}}f(\hat{\sigma}_{+_r}(x_i)) \\
&- \frac{1}{m}\sum_{j=1}^{m}\nabla f(\hat{\sigma}_{+_r}(x_j))
\end{split}

となる。

ここで、

P_{PU} = {x_i, \hat{g}_{PU}(x_i)=+1}_{i=i,..,m}

としているサイズmの訓練データ。

最適な密度比は、

\hat{\sigma}_{+_r}^* = \argmin_{\hat{\sigma}_{+_r} \in {\hat{\sigma}_{+_r}}}\hat{B}_f(\sigma_{+_r}||\hat{\sigma}_{+_r})

となる。

##4.3 Incomplete&Inaccurate
全ての準備が整ったので、提案手法の定式化をする。

まず、リスク関数は、

\begin{split}
&R_{LIoIS}(g) = (1-\gamma)R_{oIS}(g) + \gamma R_{PU}(g) \\
&= (1-\gamma)\{\theta_{\widetilde{P}}\mathbb{E}_{\widetilde{P}}[\sigma_+(x)l(g(x), +1)] + \theta_{\widetilde{N}}\mathbb{E}_{\widetilde{N}}[\sigma_-(x)l(g(x), -1)]\} \\ 
&+ \gamma\{2\theta_P\mathbb{E}_P[l(g(x),+1)] + \mathbb{E}_U[l(g(x),-1)]\}
\end{split}

となる。γはIncompleteとInaccurateの適用割合である。

Positive data \widetilde{P}を\widetilde{P}_1と\widetilde{P}_2にわける。

このときの、観測値によるリスク関数は、

\begin{split}
&\hat{R}_{LIoIS}(g) = \gamma\{2\theta_P\sum_{i=1}^{n_{\widetilde{P_2}}}l(g(x_i),+1) + \sum_{k=1}^{n_U}l(g(x_k),-1)\} \\
&+ (1-\gamma)\{\theta_{\widetilde{P}}\sum_{i=1}^{n_{\widetilde{P_1}}}\sigma_+(x_i)l(g(x_i),+1) + \theta_{\widetilde{N}}\sum_{j=1}^{n_{\widetilde{N}}}\sigma_-(x_j)l(g(x_j),-1)\}
\end{split}

となる。

このときの、最適なマッピングは、

\hat{R}_{LIoIS}(g) = \argmin_{g \in \mathcal{G}}\hat{R}_{LIoIS}(g)

となる。

#5. Expariment

本論文内で様々な現実に起こりうる状況を仮定した実験がされており、多くの場合で提案手法での優位性が確認されていた。