教師ナシで ImageNet を解く. Noise As Target (NAT) という手法を提案しており、文字通り、ノイズを教師信号に用いる.
\(n\) 枚ある画像データを用いて、適切な \(d\) 次元特徴ベクトルへ写す \(f_\theta\) を学習したい. 画像 \(x_i\) に対して 適切なラベル \(y_i\) がある教師アリの状態では、これは例えば
\[\min_{\theta, \phi}\ell(g_\phi(f_\theta(x_i)), y_i)\]
を解くことなどによって良さそうな特徴ベクトルが得られる. ここで \(\ell\) は適当な損失関数.
今問題を簡単にするために、特徴ベクトルを \(S^{d-1}\) 上に限る. 即ち (非ゼロな) \(d\) 次元ベクトルを得た後に正規化を行う. \(n\) 枚の画像がこの上に写るわけだが、一様に写ることを理想だとする. 基本のアイデアは、\(S^{d-1}\) から十分個数の点を一様にサンプリングしたとき、いずれかの画像が写るべき点が1つはあるはずだ、というものである. また、異なる画像が同じ点には写らない (縮退しない) こともついでに要請する.
画像が \(n\) 枚に対して十分多くの \(k\) 個のベクトル \[c_1, c_2, \ldots,c_k\] を \(S^{d-1}\) から一様サンプリングする. これを並べて出来る行列
\[C = \left[c_1, c_2, \ldots, c_k\right] (\in \mathbb{R}^{k \times d})\]
これと、どの特徴ベクトル \(c_j\) がどの画像 \(x_i\) に割り当てられるかという行列
\[P = \{0,1\}^{n \times k}\]
とを掛けあわせた
\[Y = PC\]
が、\(X\) が写るべき先というわけで、
\[\min_{\theta, P}\ell(f_\theta(X), PC)\]
を目指す. ここで割当行列 \(P\) もパラメータであることに註意.
さて \(P\) には制約がある. それは、一つの画像は一つの特徴ベクトルが割り当てられ、同じ特徴ベクトルは高々一つの画像にしか割り当てられないというものである. 論文ではこれを
と書かれていた. これは独自解釈だが、\(1_k, 1_n\) はそれぞれ \(k \times n, n \times k\) な対角成分が 1 の行列なんだと思う. じゃないと合わないので. でも普通、\(1_m\) って正方な単位行列だと思わん？？？？
\(P\) の更新と \(\theta\) の更新を交互に繰り返す.
\(\theta\) の更新は所謂勾配法による. ここは普通に CNN の学習.
\(P\) の更新は割当問題を解くことによる.
厳密的に解くにはハンガリアン法で解けるがこれはかなり遅い (分かんないけど \(O(n^2k)\) か \(O(nk^2)\) かですかね). そこでまず \(k=n\) とする (マジかよ…). 特徴ベクトルはちょうどどれか一つの画像に割り当てられているという条件から、制約は \(P 1_n = 1_n, P^t 1_n = 1_n\) と書かれる.
そして、どうせ深層学習の部分で \(n\) の画像を一つのサイズを \(b\) とする \(n/b\) 個のミニバッチに分けている. そこで、ミニバッチごとに \(b \times b\) の割当行列 \(P\) を求めることにする. この \(P\) の最適化はハンガリアン法でやって \(O(b^3)\) 掛かる. これが \(n/b\) 個なので結局、全体で \(O(nb^2)\) かかる.
ランダムはベクトルを教師信号に使うとだけ聞くとかなり驚いたが、割当行列も一緒に学習すると聞けば納得する. 上手いなあ. ただ \(P\) の学習方法がしょぼい…。