SVM と GAN との関連性を考える.
SVM は Maximum-Margin Classifiers の一種である.
簡単に二値分類としての線形 SVM を考える. ラベル \(y\) を \(\{-1, +1\}\) とし, 超平面 \(w\) の上と下で分類するとすると,
\[wx>0 \iff y=+1\] \[wx<0 \iff y=-1\]という条件がデータを正しく分離できたことを表す. \(y=+1\) のときと \(y=-1\) のときとをまとめるとこの条件はさらに簡単に
\[y(wx) > 0\]だと書き直せる.
ところでこの \(wx\) という量はデータ \(x\) と平面との距離という量に関連していて, その距離は \(\frac{|wx|}{\|w\|_2}\) である. SVM はこの距離が大きいほどよいとしている. 分子の絶対値はラベルを掛けてしまえばよくて, すなわち
\[\max_w \frac{y(wx)}{\|w\|_2}\]を目指すものと言える.
ただしどの点 \(x\) からも上記の最大化を目指すのではなくて, データの中でも最も平面に近いものとの距離だけに注目する（そのような距離をマージンと呼ぶのだった）. すなわち、 \(w\) を固定したときに
\[\min_x \frac{y(wx)}{\|w\|_2}\]を取ってくれるような操作があるとしている.
２つの最大化と最小化を合わせると
\[\max_w \min_x \frac{y(wx)}{\|w\|_2}\]となる.
max min の最適化は GAN として解釈できる. \(\min_x\) の部分は判別器を騙す生成器であって, \(\max_w\) の部分は騙されないような頑強な分類器を表す. GAN の場合はこの２つを交互に学習させるが, SVM では一発で最適化する.
実際には SVM はこの max min の式を直接解くのでは無く, まず
\[\min_w \frac{1}{N} \relu{y(wx)} \text{ s.t. } \|w\|_2=1\]という制約付き最適化問題に書き直し（双対を取った）, さらに KKT 条件を用いて
\[\min_{w,\lambda} \frac{1}{N} \sum_{(x,y)} \relu{y(wx)} + \lambda ( \|w\|_2^2 - 1 )\]とする. ここで \(\relu{x} = \max(0,x)\) のこと. この最適化問題を解く.
実データの空間 \(\X\) とその上の分布があるとする. また適当な分布を仮定した空間 \(\Z\) を用意する. 関数 \(G \colon \Z \to \X\) は実データらしいものを生成する. 関数 \(C \colon \X \to \R\) はデータが実データ由来か \(G\) 由来かを判定する.
そのために \(C, G\) に関して次の２つの最適化を解く.
ただしここで \(f_1,f_2,f_3\) は値を補正する関数 \(\R \to \R\) で, いくつものバリエーションが有る.
違う形式の GAN もある.
Integral Probability Metrics (IPMs) は２つの確率分布どうしの距離を測る指標で
\[\mathrm{IPM}(P \| Q) = \sup_C \E{x}{C(x)} - \E{x}{C(x)}\]としている（ただし \(C\) は実数関数全体から取る）. ところで GAN の \(G\) というのは結局 \(G(z)\) が実データの分布に近くなることを目指してるのだから, IPM の最小化を目的関数にすることが考えられる.
\[\min_G \max_C \sup_C \E{x}{C(x)} - \E{z}{C(G(z))}\]これが IPM-based GAN と呼ばれる. IPM based なものも多く亜種があるが, WGAN もその一つ.
WGAN は距離に Wasserstein 距離を使う. これは \(C\) として 1-Lipschitz 連続なものに限定した IPM である.
\(f(x) = wx\) とする. 一時近似してやると \(\|w\|_2 \approx \nabla_x f(x)\) . このためさっきの \(\frac{y(wx)}{\|w\|_2}\) という量は \(\frac{yf(x)}{\| \nabla_x f(x) \|_2}\) に近似できる. これの最大化を目的関数にしていい.
カーネルも一般化して \(f(x) = w \phi(x)\) としても \(f(x) \approx wx\) である範囲ではこの近似は通用すると言っている.
ここまではデータが線形分離可能であることを仮定していた. そうでない場合のために SVM には soft-margin という考え方があった. \(\gamma\) の修正する関数 \(F \colon \R \to \R\) を用意して \(F(\gamma(x,y;f))\) の最大化を目指すことに置き換える.
先に掲げた SVM の目的関数は
\[\min_{w,\lambda} \frac{1}{N} \sum_{(x,y)} \relu{y(wx)} + \lambda ( \|w\|_2^2 - 1 )\]であった. 今言った近似と soft-margin をこれに導入する. また \(\frac{1}{N} \sum_{(x,y)}\) の部分は要はデータ上の期待値だと見れるのでそうする.
\[\min_{w,\lambda} \E{(x,y)}{ F(y f(x)) } + \lambda \left( (\nabla_x f(x))^2 - 1 \right)\]この最後の部分は罰則化項に見える. すると \(g\) で一般化したくなってきて
\[\min_{w,\lambda} \E{(x,y)}{ F(y f(x)) } + \lambda g(\nabla_x f(x))\]となる. SVM であれば \(g(z) = z^2-1\) である. しかしまあ実際はもっと緩やかな罰則でいいので \(g(z)=(z-1)^2\) とか \(g(z)=\relu{z-1}\) がいいそう.
SVM の最後の式はだいぶ WGAN っぽい. \(F(z)=z\) , \(g(z)=\relu{z-1}\) にするとそのもの？