はじめに

Mutual Information Neural Estimationを読んだのでメモ．書き終わってちょっと殴り書きすぎたと反省．正直このメモ読んでもよくわからないと思う…

気持ち

相互情報量は二つの確率変数の依存関係を知る良い指標だが一般的に計算するのが難しく，離散変数または確率分布が既知の問題を除いて基本的に扱いにくい．また，ノンパラメトリックカーネル密度推定やガウス性を仮定した場合にも高次元になると計算が困難になる．そこでscalableでflexibleでback-prop可能でcompletely trainableな新たな手法を理論解析付きで提案するという話．

相互情報量

相互情報量は簡単に言えば二つの確率変数の依存関係を測る尺度で，相互情報量が0の時二つの確率変数は独立となり， $P(X,Y)=P(X)P(Y)$ のように因子分解された形でかける．相互情報量はいろんな書き方ができるが論文では次の表現を用いる．

$\displaystyle I(X;Z):=H(X)-H(X|Z)$

$H$ は相互情報量エントロピーを示し， $H(X|Z)$ は条件付きエントロピーを表す．条件付きエントロピーは $H(X|Z)=\mathbb{E}_{P(x),P(Z)}\log P(X|Z)$ で表すことができる．これらの関係を使うと相互情報量は次のようなKLダイバージェンスの形で表現することができる．

$\displaystyle I(X,Z)=-\mathbb{E}_{P(X)}[\log P(X)]+\mathbb{E}_{P(X)P(Z)}[\log P(X|Z)]\\ \displaystyle =\mathbb{E}_{P(X),P(Z)}\left[{\log P(X|Z)}{P(X)}\right] \\ \displaystyle =\mathbb{E}_{P(X),P(Z)}\left[{\log P(X,Z)}{P(X)P(Z)}\right] = D_{KL}(P(X,Z)||P(X)P(Z))$

この辺りは情報理論の初等的な教科書に書いてある内容．式からもわかるように相互情報量が大きければ $P(X,Z)$ と $P(X)P(Z)$ のKLダイバージェンスが大きくなるということで確率変数 $X,Z$ の依存関係が強くなる．

Dual representations of the KL-divergence

以下で説明するDonsker-Varadhan representationと $f$ -divergence representationと呼ばれる二つのKL-divergenceの表現が提案手法の核となる理論らしい．

Theorem 1 (Donsker-Varahan representation)

KLダイバージェンスは次のような表現を持つ．

$\displaystyle D_{KL}(\mathbb{P}||\mathbb{Q})=\sup_{T:\Omega\rightarrow\mathbb{R}}\mathbb{E}_{\mathbb{P}}[T]-\log(\mathbb{E}_{\mathbb{Q}}[e^T])$

証明

関数 $T$ が与えられた時， $d\mathbb{G}=\frac{1}{Z}e^Td\mathbb{Q}$ で定義されるギブス分布 $\mathbb{G}$ を考える．ただし， $Z=\mathbb{E}_\mathbb{Q}[e^T]$ ．すると次のような関係を考えることができる．

$\displaystyle \mathbb{E}_\mathbb{P}[T]-\log Z=\mathbb{E}_\mathbb{P}[\log e^T]-\log(e^T\frac{d\mathbb{Q}}{d\mathbb{G}}) \\ \displaystyle =\mathbb{E}_\mathbb{P}\left[\log e^T-\log e^T-\log \frac{d\mathbb{Q}}{d\mathbb{G}}\right] \\ \displaystyle =\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{G}}{d\mathbb{Q}}\right]$

$\Delta$ を次のようなgapとして定義する．

$\displaystyle \Delta:=D_{KL}(\mathbb{P}||\mathbb{Q})-\left(\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])\right)$

すると， $\Delta$ は次のような $\mathbb{P},\mathbb{G}$ のKLダイバージェンスとして定義できる．

$\displaystyle \Delta=\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{P}}{d\mathbb{Q}}-\log\frac{d\mathbb{G}}{d\mathbb{Q}}\right]=\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{P}}{d\mathbb{G}}\right]=D_{KL}(\mathbb{P}||\mathbb{G})$

ただし， $\mathbb{E}_\mathbb{P}[T]-\log Z=\mathbb{E}_\mathbb{P}\left[\log\frac{d\mathbb{G}}{d\mathbb{Q}}\right]$ の関係を使った．KLダイバージェンスは負の値を取らないため $\Delta\leq 0$ となりあらゆる $T$ において次の不等式が成立する．

$\displaystyle D_{KL}(\mathbb{P}||\mathbb{Q})=\Delta+\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])\geq\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])$

上の関係は $\mathbb{G}=\mathbb{P}$ の時に等式が成り立ち，その時 $d\mathbb{G}=\frac{1}{Z}e^Td\mathbb{Q}$ より $T^\ast=\log\frac{d\mathbb{P}}{d\mathbb{G}}+C$ の形をとる．ただし， $C$ は定数．この時の $T^\ast$ をoptimal functionsとして名付ける．よって，右辺の上界，すなわち $T$ がoptimal functionsである場合等号が成立するのでTheorem 1が成り立つ．

$f$ -divergence representation

KLダイバージェンスは次の下界が成り立つことも知られている．

$\displaystyle D_{KL}(\mathbb{P}||\mathbb{Q})\geq\sup_{T\in\mathcal{F}}\mathbb{E}_\mathbb{P}[T]-\mathbb{E}_\mathbb{Q}[e^{T-1}]$

一般の $T\in\mathcal{F}$ においてはDonsker-Varadhanの下界の方が負の項が対数表現になっているため上式の下界よりも大きくなることがわかる．

Mutual Information Neural Estimator

提案手法であるMINEの定式化をする．MINEではパラメータ $\theta$ を持つDNNで表現された関数族 $T_\theta:\mathcal{X}\times\mathcal{Z}\rightarrow\mathbb{R}$ によって $\mathcal{F}$ を与える．このネットワークをstatistics networkと呼び，次のような相互情報量の下界を与えるものとする．

$\displaystyle I(X;Z)\geq I_\Theta(X,Z)$

この $I_\Theta(X,Z)$ をneural information measureと呼び次のように定義する．

$\displaystyle I_\Theta(X,Z)=\sup_{\theta\in\Theta}\mathbb{E}_{P(X,Z)}[T_\theta]-\log(\mathbb{E}_{P(X)P(Z)}[e^{T_\theta}])$

この期待値は $P(X,Z),P(X)P(Z)$ からのサンプリングなどを用いて計算され，勾配上昇法を使って最大化することで上界を求める．これは情報量の新しいクラスであって，ニューラルネットワークの表現力から任意の精度で相互情報量を近似することができる．

Difinition 3.1 (Mutual Information Neural Estimator)

$\mathcal{F}=\{T_\theta\}_{\theta\in\Theta}$ をニューラルネットで表現される関数の集合とするとMINEは次のように定義される．

$\displaystyle \widehat{I(X;Z)_n}=\sup_{\theta\in\Theta}\mathbb{E}_{P^{(n)}(X,Z)}[T_\theta]-\log(\mathbb{E}_{P^{(n)}(X)\hat{P}^{(n)}(Z)}[e^{T_\theta}])$

ただし， $P^{(n)}$ はi.i.dに得られた $n$ 個のサンプルから計算される経験分布を表す．また， $f$ -divergence representationに従った下界を与えたものをMINE- $f$ として定義する．今までの議論からMINEとMINE- $f$ を比較すれば，MINEの方が良い近似を与えるが，mini-batchを使ったSGDで求められる勾配にはバイアスがのるとのこと．

Correctiong the bias from the stochastic gradients

MINEの勾配は次のように計算ができる．

$\displaystyle \hat{G}_B=\mathbb{E}_B[\nabla_\theta T_\theta]-\frac{\mathbb{E}_B[\nabla_\theta T_\theta e^{T_\theta}]}{\mathbb{E}_B[e^{T_\theta}]}$

右辺第2項の期待値はミニバッチ $B$ から計算され，full batchの勾配にバイアスがのった推定結果を導く（この辺りがうまく理解できなかったがMINE- $f$ の方はunbiasな勾配を導けるらしい）．ただし，分母を期待値の移動平均として置き換えることでそのバイアスは減らせるらしい．もっと言えばsmall learning rateを使えばバイアスを任意の大きさに抑えることができるとのこと．

Theoretical properties

ここでMINEのconsistencyとconvergenceを解析する．

Consistency

MINEはstatistics networkとデータ分布 $P(X,Z)$ からのサンプルの選び方に依存する．

Definition 3.2 (Strong consistency)

次の関係性において全ての $\epsilon$ において $\epsilon\lt 0$ が成り立ち次の関係が成り立つstatistics networkを選択したとき，推定器 $\widehat{I(X;Z)_n}$ はstrongly consistentとなる．

$\displaystyle \forall n\geq N,\:|I(X,Z)-\widehat{I(X;Z)}_n|\leq\epsilon,\:a.e.$

知識不足でconsistencyの意味がいまいちわからなかったが，consistencyの話は $\mathcal{F}$ のサイズに関連したapproximation problemと経験測度（empirical measure）に関するestimation problemの二つの問題に分けられるらしい．

以下，面倒なnotationを避けるため $\mathbb{P}=P(X,Z),\:\mathbb{Q}=P(X)P(Z)$ として定義し． $\mathbb{P}_n,\mathbb{Q}_n$ をempirical versionとする．また， $\hat{I}(T)=\mathbb{E}_\mathbb{P}[T]-\log(\mathbb{E}_\mathbb{Q}[e^T])$ とする．

Lemma 1 (approximation)

$\eta\lt 0$ とする．compact domainにおいて次の関係を満たすパラメータ $\theta$ を持つニューラルネットの関数族 $T_\theta$ が存在する．

$\displaystyle |I(X,Z)-I_\Theta(X,Z)|\leq\eta,\\ \displaystyle I_\Theta(X,Z)=\sup_{\theta\in\Theta}\mathbb{E}_\mathbb{P}[T_\theta]-\log(\mathbb{E}_\mathbb{Q}[e^{T_\theta}])$

証明

$T^\ast=\log\frac{d\mathbb{P}}{d\mathbb{Q}}$ とすると， $T^\ast$ は次の式を満たす．

$\displaystyle \mathbb{E}_\mathbb{P}[T^\ast]=I(X,Z),\:\mathbb{E}_\mathbb{Q}[e^{T^\ast}]=1$

単純に左辺に $T^\ast=\log\frac{d\mathbb{P}}{d\mathbb{Q}}$ を代入すれば求まる．これに対し，関数 $T$ に関して，正のgap $I(X,Z)-\hat{I}(T)$ は次のようにかける．

$\displaystyle I(X,Z)-\hat{I}(T)=\mathbb{E}_\mathbb{P}[T^\ast-T]+\log\mathbb{E}_\mathbb{Q}[e^T]\leq\mathbb{E}_\mathbb{P}[T^\ast-T]+\mathbb{E}_\mathbb{Q}[e^T-e^{T^\ast}]$

最後の不等式は $\log x\leq x-1$ から $\log\mathbb{E}_\mathbb{Q}[e^T]\leq\mathbb{E}_\mathbb{Q}[e^T]-1=\mathbb{E}_\mathbb{Q}[e^T-\frac{d\mathbb{Q}}{d\mathbb{P}}]$ となることから示せる．

$\eta\gt 0$ の定数とし， $T^\ast$ が定数 $M$ によってboundされる場合を考える．ここで，ニューラルネットのuniversal approximation theoremを考えれば，次の関係を満たすfeedforward network function $T_\hat{\theta}\leq M$ を選択することができる．

$\displaystyle \mathbb{E}_\mathbb{P}|T^\ast-T_\hat{\theta}|\leq\frac{\eta}{2},\:\mathbb{E}_\mathbb{Q}|T^\ast-T_\hat{\theta}|\leq\frac{\eta}{2}e^{-M}$

$\exp$ が $(\infty,M]$ で $e^M$ のリプシッツ連続であることから，次の関係が得られる．

$\displaystyle \mathbb{E}_\mathbb{Q}|e^{T^\ast}-T^{T_\hat{\theta}}|\leq e^M\mathbb{E}_\mathbb{Q}|T^\ast-T_\hat{\theta}|\leq\frac{\eta}{2}$

さらに三角不等式と $I(X,Z)-\hat{I}(T)$ から次の不等式が得られる．

$\displaystyle |I(X,Z)-\hat{I}(T_\hat{\theta})|\leq\mathbb{E}_\mathbb{P}|T^\ast-T_\hat{\theta}|+\mathbb{E}_\mathbb{Q}|e^{T^\ast}-e^{T_\hat{\theta}}|\leq\frac{\eta}{2}+\frac{\eta}{2}\leq\eta$

一般の場合についても解説されていたが割愛．

Lemma 2 (estimation)

$\eta\gt 0$ とする．compact domain $\Theta\subset\mathbb{R}^k$ におけるパラメータ $\theta$ のニューラルネット $T_\theta$ の族 $\mathcal{F}$ が与えられたとき，次の関係を満たす $N\in\mathbb{N}$ が存在する．

$\displaystyle \forall n\geq N,\:Pr\left(\widehat{I(X;Z)}_n-I_\mathcal{F}(X,Z)|\leq\eta\right)=1$

証明

まずは $|\widehat{I(X;Z)}_n-\sup_{T_\theta\in\mathcal{F}}\hat{I}(T_\theta)|$ に三角不等式を使う．

$\displaystyle |\widehat{I(X;Z)}_n-\sup_{T_\theta\in\mathcal{F}}\hat{I}(T_\theta)|\leq\sup_{T_\theta\in\mathcal{F}}|\mathbb{E}_\mathbb{P}[T_\theta]-\mathbb{E}_{\mathbb{P}_n}[T_\theta]|+\sup_{T_\theta\in\mathcal{F}}|\log\mathbb{E}_\mathbb{Q}[e^{T_\theta}]-\log\mathbb{E}_{\mathbb{Q}_n}[e^{T_\theta}]|$

導出は $\widehat{I(X;Z)}_n,\hat{I}(T_\theta)$ にそれぞれ代入して $T_\theta,e^{T_\theta}$ でまとめて三角不等式を使うだけ．compact domain $\Theta\times\Omega$ 上で定義された関数 $\theta,\omega\rightarrow T_\theta(\omega)$ はboundされる．さらに関数 $T_\theta$ は定数 $M$ によって $|T_\theta|\leq M$ と一様にboundされる． $\log$ が定数 $[e^{-M},e^M]$ に対して $e^M$ のリプシッツ連続であるため次の関係が成り立つ．

$\displaystyle | \log \mathbb{E}_\mathbb{Q} [ e^{T_\theta} ] - \log \mathbb{E}_{\mathbb{Q}_n} [ e^{T_\theta} ] | \geq e^M | \mathbb{E}_\mathbb{Q} [ e^{T_\theta} ] -\mathbb{E}_{\mathbb{Q}_n}[e^{T_\theta}]|$

$\Theta$ がコンパクトで，feedforward network functionが連続であることから，関数 $T_\theta$ と $e^{T_\theta}$ の族はuniform law of large numbersを満たすらしい． $\eta\gt 0$ が与えられたとき，次の関係を満たし $\forall n\geq N$ となるような $N\in\mathbb{N}$ を選ぶことができる．

$\displaystyle \sup_{T_\theta\in\mathcal{F}}|\mathbb{E}_\mathbb{P}[T_\theta]-\mathbb{E}_{\mathbb{P}_n}[T_\theta]|\leq\frac{\eta}{2},\\ \displaystyle \sup_{T_\theta\in\mathcal{F}}|\mathbb{E}_\mathbb{Q}[e^{T_\theta}]-\mathbb{E}_{\mathbb{Q}_n}[e^{T_\theta}]|\leq\frac{\eta}{2}e^{-M}$

三角不等式とリプシッツ連続の性質を合わせることで以下の関係が導かれる．

$\displaystyle |\widehat{I(X,Z)}_n-\sup_{T_\theta\in\mathcal{F}}\hat{I}(T_\theta)|\leq\frac{\eta}{2}+\frac{\eta}{2}=\eta$

よってlemma 2が成り立つ．

Sample complexity

提案している推定器のsample complexityを議論する．まず仮定として，相互情報量はneural information measure $I_\Theta(X,Z)$ によって十分に近似可能であるとする．ここではLemma 2に手を加えてneural information measureの推定量が十分な精度と信頼度を達成するのにどれくらいのサンプル数が必要かを与える．

まず以下の仮定を置く．関数 $T_\theta$ は $M$ -bounded（ $|T_\theta|\leq M$ ）であり，パラメータ $\theta$ に関して $L$ -リプシッツであるとする．domain $\Theta\subset\mathbb{R}^d$ がboundされていて，定数 $K$ に関して $||\theta||\leq K$ が成り立つ．以下の定理は $d$ 次元のパラメータ空間において $\tilde{O}\left(\frac{d\log d}{\epsilon^2}\right)$ のsample complexityを持つことを示す．

Theorem 3

任意の値のaccuracy $\epsilon$ とconfidence parameters $\delta$ が与えられたとき，以下をの関係を満たす．

$\displaystyle Pr\left(|\widehat{I(X;Z)}_n-I_\Theta(X,Z)|\leq\epsilon\right)\geq 1-\delta, \\ \displaystyle \mathrm{whenever\:the\:number}\:n\:\mathrm{of\:samples\:satisfies}\\ \displaystyle n\geq\frac{2M^2(d\log(16KL\sqrt{d}/\epsilon)+2dM+\log(2/\delta))}{\epsilon^2}$

書くのに力尽きたので証明は割愛．

Maximizing mutual information to improve GANs

実験の一つとして行っていたGANの改善．GANの目的関数は以下のように記述される．

$\displaystyle \min_G\max_DV(D,G):=\mathbb{E}_{P(X)}[D(X)]+\mathbb{E}_{P(Z)}[\log(1-D(G(Z))]$

ここではinfoGANの枠組みを考えて，入力はノイズとコードを合わせた $Z=[\epsilon,c]$ とする．ここではサンプルとコード間の相互情報量 $I(G([\epsilon,c]);c)=H(G([\epsilon,c]))-H(G([\epsilon,c])|c)$ を最大化することでmode collapseが怒るのを防ぐアプローチを考える．するとgeneratorの目的関数は次のようになる．

$\displaystyle \mathrm{arg}\max_G\mathbb{E}[\log(D(G([\epsilon,c])))]+\beta I(G([\epsilon,c]);c)$

Generatorは $G$ のパラメータに関して微分可能で，statistics networkは微分可能な関数であることからback-propと勾配上昇法を使うことで相互情報量を最大化することができる．相互情報量は任意の大きさにできてしまうためここではadaptive gradient clippingを使ってdiscriminatorとstatistics networkからくる勾配が同じ程度になるようにしたとのこと．ちなみにadaptive gradient clippingはmutual informationから計算される勾配を次のようにclippingすること．

$\displaystyle g_a=\min(||g_u||,||g_m||)\frac{g_m}{||g_m||}$

ただし， $g_u,g_m$ はそれぞれdiscriminatorの勾配と相互情報量の勾配．実験結果を見る限りは通常のGANに比べてMode collapsを回避しているよう．

まとめ

証明等をかなり殴り書いたせいで結局論文の主張がこのメモから分かりにくくなってしまったけど，簡単に言えば相互情報量をニューラルネットを使って $I_\Theta(X,Z)=\sup_{\theta\in\Theta}\mathbb{E}_{P(X,Z)}[T_\theta]-\log(\mathbb{E}_{P(X)P(Z)}[e^{T_\theta}]$ として推定可能で，その推定精度がサンプル数 $n$ 次第で任意精度を達成可能というところを証明した論文．実装ではGANのように生成モデル+相互情報量を推定するstatistics networkを用意して目的関数に相互情報量の最大化を組み込む感じ．手法自体はすごくシンプルでアルゴリズムテーブル1を見れば実装もなんとなく予想できる．

これかなり有用な手法な気がするので，とりあえず実装してどんなもんか確認したい．ただ実装が公開されてないのとclippingの実装がめんどくさそう．

一応MINEを使ってInfoGANを実装して遊んでみた内容もメモした．

機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

Mutual Information Neural Estimationを読んだのでメモ