Representation Learning with Mutual Information Maximization

$f$-GAN

2016 NIPS - $f$-GAN: Training Generative Neural Samplers using Variational Divergence Minimization ¹

$f$-divergence

Suppose we want to train a generative model $Q$ that generates data as realistic (close to the true data distribution $P$) as possible. In other words, we wish to minimize the $f$-divergence

$${\mathcal{D}}_f(P\Vert Q)={\int }_{\mathcal{X}}q(x)f\left(\frac{p(x)}{q(x)}\right)\mathrm{d}x={\mathbb{E}}_{q(x)}f\left(\frac{p(x)}{q(x)}\right)$$

where $f:{\mathbb{R}}^{+}\to \mathbb{R}$ is convex, lower-semicontinuous and satisfies $f(1)=0$.

Below is a table of the $f$-divergence family.

Name	${\mathcal{D}}_f(P\Vert Q)$	$f(u)$	$T^{\ast }(u)$
Total variation	$\frac{1}{2}\int |p(x)-q(x)|\mathrm{d}x$	$\frac{1}{2}|u-1|$	$\frac{1}{2}\mathrm{sign}(u-1)$
Kullback-Leibler (KL)	$\int p(x)\log \frac{p(x)}{q(x)}\mathrm{d}x$	$u\log u$	$1+\log u$
Reverse KL	$\int q(x)\log \frac{q(x)}{p(x)}\mathrm{d}x$	$-\log u$	$-\frac{1}{u}$
Pearson ${\chi }^2$	$\int \frac{(q(x)-p(x){)}^2}{p(x)}\mathrm{d}x$	$(1-u{)}^2$	$2(u-1)$
Neyman ${\chi }^2$	$\int \frac{(p(x)-q(x){)}^2}{q(x)}\mathrm{d}x$	$\frac{(1-u{)}^2}{u}$	$1-\frac{1}{u^2}$
Squared Hellinger	$\int {(\sqrt{p(x)}-\sqrt{q(x)})}^2\mathrm{d}x$	$(\sqrt{u}-1{)}^2$	$(\sqrt{u}-1)\sqrt{\frac{1}{u}}$
Jeffrey	$\int (p(x)-q(x))\log \left(\frac{p(x)}{q(x)}\right)\mathrm{d}x$	$(u-1)\log u$	$1+\log u-\frac{1}{u}$
Jensen-Shannon	$\frac{1}{2}\int p(x)\log \frac{2p(x)}{p(x)+q(x)}+q(x)\log \frac{2q(x)}{p(x)+q(x)}\mathrm{d}x$	$-\frac{u+1}{2}\log \frac{1+u}{2}+\frac{u}{2}\log u$	$\frac{1}{2}\log \frac{2u}{u+1}$
$\alpha$-divergence	$\frac{1}{\alpha (\alpha -1)}\int p(x)[{\left(\frac{q(x)}{p(x)}\right)}^{\alpha }-1]-\alpha (q(x)-p(x))\mathrm{d}x$	$\frac{1}{\alpha (\alpha -1)}(u^{\alpha }-1-\alpha (u-1))$	$\frac{1}{\alpha -1}(u^{\alpha -1}-1)$

Fenchel conjugate

The Fenchel conjugate of function $f(x)$ is defined as $f^{\ast }(x^{\ast })=\underset{x\in \mathrm{dom}f}{sup}\{⟨x,x^{\ast }⟩-f(x)\}$.

We can easily verify that $f^{\ast }$ is convex and lower-semicontinuous. When $f$ is also convex and lower semi-continuous, $f^{\ast \ast }=f$.

Variational representation of the $f$-divergence

We now derive the variational lower bound on $f$-divergence:

$$\begin{array}{rl}{\mathcal{D}}_f(P\Vert Q)& ={\int }_{\mathcal{X}}q(x)\underset{t\in \mathrm{dom}{f}^{\ast }}{sup}\{t\frac{p(x)}{q(x)}-f^{\ast }(t)\}\mathrm{d}x\\ & \ge \underset{T\in \mathcal{T}}{sup}\{{\int }_{\mathcal{X}}p(x)T(x)\mathrm{d}x-{\int }_{\mathcal{X}}q(x)f^{\ast }(T(x))\mathrm{d}x\}\\ & =\underset{T\in \mathcal{T}}{sup}\{{\mathbb{E}}_{p(x)}T(x)-{\mathbb{E}}_{q(x)}{f}^{\ast }(T(x))\}\end{array}$$

where $\mathcal{T}$ is a class of functions $T:\mathcal{X}\to \mathbb{R}$. It is straightforward to see that the optimal $T^{\ast }(x)=f^{\prime }\left(\frac{p(x)}{q(x)}\right)$ (please do not confuse with conjugate function) by substituting the definition of $f^{\ast }$ and let $t$ be $\frac{p(x)}{q(x)}$

$${\mathcal{D}}_f(P\Vert Q)\ge {\mathbb{E}}_{p(x)}T(x)-{\mathbb{E}}_{q(x)}[\frac{p(x)}{q(x)}T(x)-f\left(\frac{p(x)}{q(x)}\right)]={\mathcal{D}}_f(P\Vert Q)$$

The critical value $f^{\prime }(1)$ can be interpreted as a classification threshold applied to $T(x)$ to distinguish between true and generated samples.

$f$-GAN Objective

We parameterize the generator $Q$ with parameter $\theta$ and the discriminator $T$ with parameter $\omega$. The $f$-GAN objective is then defined as

$$\underset{\theta }{min}\underset{\omega }{max}F(\theta ,\omega )={\mathbb{E}}_{p(x)}{T}_{\omega }(x)-{\mathbb{E}}_{q_{\theta }(x)}{f}^{\ast }(T_{\omega }(x)).$$

To account for $\mathrm{dom}{f}^{\ast }$ of various $f$-divergence, we further decompose $T_{\omega }(x)$ into $T_{\omega }(x)=g_f(V_{\omega }(x))$, where $V_{\omega }:\mathcal{X}\to \mathbb{R}$ is a neural network and $g_f:\mathbb{R}\to \mathrm{dom}{f}^{\ast }$ is an output activation function.

Name	$g_f$	$\mathrm{dom}{f}^{\ast }$	$f^{\ast }(t)$	$f^{\prime }(1)$
Total variation	$\frac{1}{2}\tanh (v)$	$[-\frac{1}{2},\frac{1}{2}]$	$t$	$0$
Kullback-Leibler (KL)	$v$	$\mathbb{R}$	${\mathrm{e}}^{t-1}$	$1$
Reverse KL	$-{\mathrm{e}}^v$	${\mathbb{R}}_{-}$	$-1-\log (-t)$	$-1$
Pearson ${\chi }^2$	$v$	$\mathbb{R}$	$\frac{1}{4}{t}^2+t$	$0$
Neyman ${\chi }^2$	$1-{\mathrm{e}}^v$	$(-\mathrm{\infty },1)$	$2-2\sqrt{1-t}$	$0$
Squared Hellinger	$1-{\mathrm{e}}^v$	$(-\mathrm{\infty },1)$	$\frac{t}{1-t}$	$0$
Jeffery	$v$	$\mathbb{R}$	$W({\mathrm{e}}^{1-t})+\frac{1}{W({\mathrm{e}}^{1-t})}+t-2$	$0$
Jensen-Shannon	$\frac{\log 2}{2}-\frac{1}{2}\log (1+{\mathrm{e}}^{-v})$	$(-\mathrm{\infty },\frac{\log 2}{2})$	$-\frac{1}{2}\log (2-{\mathrm{e}}^{2t})$	$0$
$\alpha$-div. ($\alpha \in (0,1)$)	$\frac{1}{1-\alpha }-\log (1+{\mathrm{e}}^{-v})$	$(-\mathrm{\infty },\frac{1}{1-\alpha })$	$\frac{1}{\alpha }(t(\alpha -1)+1{)}^{\frac{\alpha }{\alpha -1}}-\frac{1}{\alpha }$	$0$
$\alpha$-div. ($1<\alpha$)	$v$	$\mathbb{R}$	$\frac{1}{\alpha }(t(\alpha -1)+1{)}^{\frac{\alpha }{\alpha -1}}-\frac{1}{\alpha }$	$0$

where $W$ is the Lambert-$W$ product log function.

Mutual Information Neural Estimator (MINE)

2018 ICML - MINE: Mutual Information Neural Estimation ²

MINE has two variants termed MINE and MINE-$f$. The former uses the Donsker-Varadhan representation of the KL divergence, which results in a tighter estimator; the latter uses the $f$-divergence representation described above.

The Donsker-Varadhan representation of KL

$${\mathcal{D}}_{\mathrm{KL}}(P\Vert Q)\ge \underset{T\in \mathcal{T}}{sup}\{{\mathbb{E}}_{p(x)}T(x)-\log {\mathbb{E}}_{q(x)}{\mathrm{e}}^{T(x)}\}$$

Proof: Consider the Gibbs distribution $g(x)=\frac{1}{Z}q(x){\mathrm{e}}^{T(x)}$ where $Z={\mathbb{E}}_{q(x)}{\mathrm{e}}^{T(x)}$. Then

$$\begin{array}{rl}\mathrm{\Delta }:& ={\mathcal{D}}_{\mathrm{KL}}(P\Vert Q)-{\mathbb{E}}_{p(x)}T(x)-\log {\mathbb{E}}_{q(x)}{\mathrm{e}}^{T(x)}\\ & ={\mathcal{D}}_{\mathrm{KL}}(p(x)\Vert q(x))-{\mathbb{E}}_{p(x)}T(x)-\log Z\\ & ={\mathcal{D}}_{\mathrm{KL}}(p(x)\Vert q(x))-{\mathbb{E}}_{p(x)}(T(x)-\log Z)\\ & ={\mathbb{E}}_{p(x)}\frac{p(x)}{q(x)}-{\mathbb{E}}_{p(x)}\frac{g(x)}{q(x)}\\ & ={\mathcal{D}}_{\mathrm{KL}}(p(x)\Vert g(x))\ge 0\end{array}$$

where $\mathcal{T}$ is a class of functions $T:\mathcal{X}\to \mathbb{R}$ such that the two expectations are finite. The equality holds when $g(x)\equiv p(x)$, i.e. $T^{\ast }(x)=\log \frac{p(x)}{q(x)}+C$.

The $f$-divergence representation of KL

Adopting the variational lower bound for $f$-divergence, we have

$${\mathcal{D}}_{\mathrm{KL}}(P\Vert Q)\ge \underset{T\in \mathcal{T}}{sup}\{{\mathbb{E}}_{p(x)}T(x)-{\mathbb{E}}_{q(x)}{\mathrm{e}}^{T(x)-1}\}$$

and the optimal $T^{\ast }(x)=1+\log \frac{p(x)}{q(x)}$.

Estimating Mutual Information

$$I(X;Z)={\mathcal{D}}_{\mathrm{KL}}(p(x,z)\Vert p(x)p(z))\ge \underset{\theta \in \mathrm{\Theta }}{sup}\{{\mathbb{E}}_{p(x,z)}{T}_{\theta }(x,z)-\log {\mathbb{E}}_{p(x)p(z)}{\mathrm{e}}^{T_{\theta }(x,z)}\}$$

We estimate the expectations with empirical samples

$$\hat{I}(X;Z{)}_n=\underset{\theta \in \mathrm{\Theta }}{sup}\mathcal{V}(\theta )=\underset{\theta \in \mathrm{\Theta }}{sup}\{{\mathbb{E}}_{p^{(n)}(x,z)}{T}_{\theta }(x,z)-\log {\mathbb{E}}_{p^{(n)}(x){\hat{p}}^{(n)}(z)}{\mathrm{e}}^{T_{\theta }(x,z)}\}$$

When using stochastic gradient descent (SGD), the gradient update of MINE

$${\mathrm{\nabla }}_{\theta }\mathcal{V}(\theta )={\mathbb{E}}_B{\mathrm{\nabla }}_{\theta }T(\theta )-\frac{{\mathbb{E}}_B{\mathrm{e}}^{T_{\theta }}{\mathrm{\nabla }}_{\theta }{T}_{\theta }}{{\mathbb{E}}_B{\mathrm{e}}^{T_{\theta }}}$$

is a biased estimate of the full gradient update (Why?). This is corrected by an exponential moving average applied to the denominator. For MINE-$f$, the SGD gradient is unbiased.

Contrastive Predictive Coding (CPC) and the InfoNCE Loss

2010 AISTATS - Noise-contrastive estimation: A new estimation principle for unnormalized statistical models ³

2018 NeurIPS - Representation Learning with Contrastive Predictive Coding ⁴

Noise-Contrastive Estimation (NCE)

Suppose we have observed data $\mathbf{x}\sim p_d(\cdot )$ and we want to estimate a model from a family $\{p_{\mathrm{m}}(\cdot ;\alpha ){\}}_{\alpha }$ where $\alpha$ is the model parameter. The challenge is that often it is more convenient to define an unnormalized model $p_{\mathrm{m}}^0$ such that

$$p_{\mathrm{m}}(\cdot ;\alpha )=\frac{p_{\mathrm{m}}^0(\cdot ;\alpha )}{Z(\alpha )}\text{where}Z(\alpha )=\int p_{\mathrm{m}}^0(\mathbf{u};\alpha )\mathrm{d}\mathbf{u}.$$

The integral $Z(\alpha )$ is rarely analytically tractable, and if the data is highdimensional, numerical integration is difficult. We include the normalization constant $Z(\alpha )$ as an additional parameter $c\approx -\log Z(\alpha )$, so that

$$\log p_{\mathrm{m}}(\cdot ;\theta )=\log p_{\mathrm{m}}^0(\cdot ;\alpha )+c\text{where}\theta =\alpha ,c.$$

Performing Maxmimum Likelihood Estimation (MLE) on this objective is not feasible as $c$ would be pushed to infinity. Instead we learn to discriminate between the data $\mathbf{x}$ and some artificially generated noise $\mathbf{y}\sim p_{\mathrm{n}}$. With $T$ positive (data) and $T$ negative (noise) examples, we aim to correctly classify each of them, and thus define the NCE objective as

$$\begin{array}{rl}{J}_T(\theta )& =\frac{1}{2T}\sum _{t=1}^T[\log h({\mathbf{x}}_t;\theta )+\log (1-h({\mathbf{y}}_t;\theta ))]\\ & =\frac{1}{2T}\sum _{t=1}^T[\log \frac{p_{\mathrm{m}}({\mathbf{x}}_t;\theta )}{p_{\mathrm{m}}({\mathbf{x}}_t;\theta )+p_{\mathrm{n}}({\mathbf{x}}_t)}+\log \frac{p_{\mathrm{n}}({\mathbf{y}}_t)}{p_{\mathrm{m}}({\mathbf{y}}_t;\theta )+p_{\mathrm{n}}({\mathbf{y}}_t)}]\end{array}$$

where $h(\mathbf{u};\theta )=\sigma (\log p_{\mathrm{m}}(\mathbf{u};\theta )-\log p_{\mathrm{n}}(\mathbf{u}))$.

This blog post (in Chinese) shows by gradient calculation that when the number of negative samples approches infinity, the NCE gradient equals to the MLE gradient.

Contrastive Predictive Coding

Let $\{x_t\}$ be a sequence of observations, $z_t=g_{\mathrm{enc}}(x_t)$ be the encoded latent representation at time step $t$, and $c_t=g_{\mathrm{ar}}(z_{\le t})$ be the summarized context (global, ar for auto-regressive) latent representation at time step $t$. Given a set $X=\{x_1,\cdots ,x_N\}$ of $N$ random samples containing one positive sample from $p(x_{t+k}|c_t)$ and $N-1$ negative samples from the 'proposal' distribution $p(x_{t+k})$, we wish to preserve the mutual information between the $k$-step-later input $x_{t+k}$ and the current context $c_t$, by trying to identify the positive sample among all the samples:

$$p(d=i|X,c_t)=\frac{p(x_i|c_t)\prod _{l\ne i}p(x_l)}{\sum _{j=1}^{N}p(x_j|c_t)\prod _{l\ne j}p(x_l)}=\frac{\frac{p(x_i|c_t)}{p(x_i)}}{\sum _{j=1}^N\frac{p(x_j|c_t)}{p(x_j)}}=\frac{f_i(x_i,c_t)}{\sum _{j=1}^N{f}_j(x_j,c_t)}$$

where $f_k(x_{t+k},c_t)=C\frac{p(x_{t+k}|c_t)}{p(x_{t+k})}$ and $C$ is an arbitrary constant. Note that $f$ is unnormalized and can be parameterized by a simple log-bilinear model

$$f_k(x_{t+k},c_t)=\exp (z_{t+k}^T{W}_k{c}_t).$$

To maximize our contrastive predictive capabilities, we minimize the following InfoNCE loss:

$${\mathcal{L}}^{(\mathrm{InfoNCE})}=-{\mathbb{E}}_X[\log \frac{f_k(x_{t+k},c_t)}{\sum _{x_j\in X}{f}_k(x_j,c_t)}]$$

Relation with Mutual Information

$$I(x_{t+k};c_t)\ge \log N-{\mathcal{L}}^{(\mathrm{InfoNCE})}$$

Proof:

$$\begin{array}{rl}{\mathcal{L}}^{(\mathrm{InfoNCE})}& ={\mathbb{E}}_X\log (1+\frac{p(x_{t+k})}{p(x_{t+k}|c_t)}\sum _{j\ne t+k}\frac{p(x_j|c_t)}{p(x_j)})\\ & \approx {\mathbb{E}}_X\log (1+\frac{p(x_{t+k})}{p(x_{t+k}|c_t)}(N-1){\mathbb{E}}_{x_j\in X_{\mathrm{neg}}}\frac{p(x_j|c_t)}{p(x_j)})\\ & \approx {\mathbb{E}}_X\log (1+\frac{p(x_{t+k})}{p(x_{t+k}|c_t)}(N-1))\\ & \ge {\mathbb{E}}_X\log (N\frac{p(x_{t+k})}{p(x_{t+k}|c_t)})\\ & =-I(x_{t+k};c_t)+\log N\end{array}$$

Note that the approximation is more accurate as the number of negative samples increases.

Relation with MINE

Let $F(x,c)=\log f(x,c)$, then

$$\begin{array}{rl}{\mathcal{L}}^{(\mathrm{InfoNCE})}& =-{\mathbb{E}}_X\left[\frac{f_k(x_{t+k},c_t)}{\sum _{x_j\in X}{f}_k(x_j,c_t)}\right]\\ & ={\mathbb{E}}_{X}F(x_{t+k},c_t)-{\mathbb{E}}_X\log ({\mathrm{e}}^{F(x_{t+k},c_t)}\sum _{x_j\in X_{\mathrm{neg}}}{\mathrm{e}}^{F(x_j,c_t)})\\ & \le {\mathbb{E}}_{X}F(x_{t+k},c_t)-{\mathbb{E}}_{c_t}\log \sum _{x_j\in X_{\mathrm{neg}}}{\mathrm{e}}^{F(x_j,c_t)}\\ & ={\mathbb{E}}_{X}F(x_{t+k},c_t)-{\mathbb{E}}_{c_t}[\log \frac{1}{N-1}\sum _{x_j\in X_{\mathrm{neg}}}{\mathrm{e}}^{F(x_j,c_t)}+\log (N-1)]\end{array}$$

which is equivalent to the MINE estimator:

$$\hat{I}(X;Z{)}_n=\underset{\theta \in \mathrm{\Theta }}{sup}\mathcal{V}(\theta )=\underset{\theta \in \mathrm{\Theta }}{sup}\{{\mathbb{E}}_{p^{(n)}(x,z)}{T}_{\theta }(x,z)-\log {\mathbb{E}}_{p^{(n)}(x){\hat{p}}^{(n)}(z)}{\mathrm{e}}^{T_{\theta }(x,z)}\}$$

Deep InfoMax (DIM)

2019 ICLR - Learning deep representations by mutual information estimation and maximization ⁵

Deep InfoMax is a principled framework for training a continuous and (almost everywhere) differentiable encoder $E_{\psi }:\mathcal{X}\to \mathcal{Z}$ to maximize mutual information between its input and output, with neural network parameters $\psi \in \mathrm{\Psi }$.

Assume that we are given a set of training examples on an input space, $\mathbf{X}:=\{x^{(i)}\in \mathcal{X}{\}}_{i=1}^N$, with empirical probability distribution $P$. We define $U_{\psi ,P}$ as the marginal distribution of $z=E_{\psi }(x)$ where $x$ is sampled from $P$, i.e., $u(z=E_{\psi }(x))=({\mathrm{\nabla }}_x{E}_{\psi }(x){)}^{-1}p(x)$.

We assert our encoder should be trained according to the following criteria:

• Local and global mutual information maximization
• Statistical constraints (prior in the latent space $v(z)$).

$$\underset{\psi }{min}-I(X;Z)+\lambda {\mathcal{D}}_{\mathrm{KL}}(v(z)\Vert u(z))$$

As a preliminary, we introduce the local feature encoder $C_{\psi }$, the global feature encoder $E_{\psi }=f_{\psi }\circ C_{\psi }$ and the discriminator $T_{\psi ,\omega }=D_{\omega }\circ g\circ (C_{\psi },E_{\psi })$, where $D_{\omega }$ is a neural classifier, and $g$ is a function that combines the local and global features.

The overall DIM objective consists of three parts, global MI, local MI and statistical constraints.

$$\begin{array}{rl}\underset{{\omega }_1,{\omega }_2,\psi }{max}& (\alpha {\hat{I}}_{{\omega }_1,\psi }(X;E_{\psi }(X))+\frac{\beta }{M^2}\sum _{i=1}^{M^2}{\hat{I}}_{{\omega }_2,\psi }(X^{(i)};E_{\psi }(X)))+\\ & \underset{\psi }{min}\underset{\varphi }{max}\gamma {\hat{D}}_{\varphi }(V\Vert U_{\psi ,P})\end{array}$$

In the following sections, we first introduce how to enfore statistical constraints ${\hat{D}}_{\varphi }$ and local MI maximization, then discuss objectives for general MI maximization $\hat{I}$.

Statistical Constraints

Why use adversarial objectives for KL regularization?

Here we could also use VAE-style prior regularization $min{\mathcal{D}}_{\mathrm{KL}}(q(z|x)\Vert p(z))$, but this assumes for every data point $x$, its latent $q(z|x)$ is close to $p(z)$. This will encourage $q(z)$ to pick the modes of $p(z)$, rather than the whole distribution of $p(z)$. See the Adversarial AutoEncoders paper for more details.

DIM imposes statistical constraints onto learned representations by implicitly training the encoder so that the push-forward distribution, $U_{\psi ,P}$, matches a prior $V$. Following variational representation of the Jensen-Shannon divergence, we optimize this objective by

$$\underset{\psi }{min}\underset{\varphi }{max}{\mathcal{D}}_{\mathrm{JS}}(V\Vert U_{\psi ,P})={\mathbb{E}}_{v(z)}\log D_{\varphi }(z)+{\mathbb{E}}_{p(x)}\log (1-D_{\varphi }(E_{\psi }(x)))$$

Note that the discriminator $D_{\varphi }$ operates in the latent space rather than the input space.

Local MI Maximization

Maximizing the mutual information b/t encoder input and output may not be meaningful enough. We propose to maximize the average MI between the high-level representation and local patches of the image. Because the same global representation is encouraged to have high MI with all the patches, this favours encoding aspects of the data that are shared across patches.

First we encode the input to a feature map, $C_{\psi }(x)=\{C_{\psi }^{(i)}{\}}_{i=1}^{M\times M}$ that reflects useful structure in the data (e.g., spatial locality). Next, we summarize this local feature map into a global feature, $E_{\psi }(x)=f_{\psi }\circ C_{\psi }(x)$. We then define our MI estimator on global/local pairs, maximizing the average estimated MI:

$$\underset{\omega ,\psi }{max}\frac{1}{M^2}\sum _{i=1}^{M^2}{\hat{I}}_{\omega ,\psi }(C_{\psi }^{(i)}(X);E_{\psi }(X)).$$

MI Maximization Objectives

The Donsker-Varadhan Objective

This lower-bound to the MI is based on the Donsker-Varadhan representation of the KL-divergence. It is the tightest possible bound on KL divergence, but it is less stable and requires many negative samples.

$$I(X;Z)\ge {\hat{I}}_{\psi ,\omega }^{\text{(DV)}}(X;Z)={\mathbb{E}}_{p(x,z)}{T}_{\psi ,\omega }(x,z)-\log {\mathbb{E}}_{p(x)p(z)}({\mathrm{e}}^{T_{\psi ,\omega }(x,z)})$$

The Jensen-Shannon Objective

Since we do not concern the precise value of mutual information, and rather primarily interested in its maximization, we could instead optimize on the Jensen-Shannon divergence. This objective is stable to optimize and requires few negative sample, but it is a looser bound to the true mutual information.

Following $f$-GAN formulation, with output activation $g_f=-\log (1+{\mathrm{e}}^{-v})$ and conjugate function $f^{\ast }(t)=-\log (1-{\mathrm{e}}^t)$, we define the following objective:

$$\begin{array}{rl}& {\hat{I}}_{\psi ,\omega }^{\text{(JS)}}(X;E_{\psi }(X))\\ =& \widehat{{\mathcal{D}}_{\mathrm{JS}}}(p(x,E_{\psi }(x))\Vert p(x)p(E_{\psi }(x)))\\ =& {\mathbb{E}}_{p(x)}[{\tilde{T}}_{\psi ,\omega }(x,E_{\psi }(x))-{\mathbb{E}}_{p(x^{\prime })}{f}^{\ast }({\tilde{T}}_{\psi ,\omega }(x^{\prime },E_{\psi }(x)))]\\ =& {\mathbb{E}}_{p(x)}[-\log (1+{\mathrm{e}}^{-T_{\psi ,\omega }(x,E_{\psi }(x))})-{\mathbb{E}}_{p(x^{\prime })}\log (1+{\mathrm{e}}^{T_{\psi ,\omega }(x^{\prime },E_{\psi }(x))})]\\ =& {\mathbb{E}}_{p(x)}[\log \sigma (T_{\psi ,\omega }(x,E_{\psi }(x)))+{\mathbb{E}}_{p(x^{\prime })}\log (1-\sigma (T_{\psi ,\omega }(x^{\prime },E_{\psi }(x))))]\end{array}$$

where $\tilde{T}=g_f\circ T$ is the discriminator output after activation $g_f$. In section A.1 of the DMI paper ⁵, the authors show theoretically and empirically that $\underset{\psi ,\omega }{max}{\mathcal{D}}_{\mathrm{JS}}(p(x,z)\Vert p(x)p(z))$ is indeed a good maximizer of $I(X;Z)$.

The InfoNCE Objective

This objective uses noise-contrastive estimation to bound mutual information. It obtains strong results, but requires many negative samples.

$$\begin{array}{rl}{\hat{I}}_{\psi ,\omega }^{\text{(InfoNCE)}}(X;E_{\psi }(X))& ={\mathbb{E}}_{p(x,z)}[T_{\psi ,\omega }(x,E_{\psi }(x))-{\mathbb{E}}_{p(x^{\prime })}[\log \sum _{x^{\prime }}{\mathrm{e}}^{T_{\psi ,\omega }(x^{\prime },E_{\psi }(x))}]]\end{array}$$

Deep Graph Infomax

2019 ICLR - Deep Graph Infomax ⁶

Deep Graph Infomax (DGI) is a general approach for learning node representations within graph-structured data in an unsupervised manner. It relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs.

We first introduce

• The encoder $E:{\mathbb{R}}^{N\times F^{\mathrm{in}}}\times {\mathbb{R}}^{N\times N}\to {\mathbb{R}}^{N\times F}$ such that $E(\mathbf{X},\mathbf{A})=\mathbf{H}=({\mathbf{h}}_1,\dots ,{\mathbf{h}}_N{)}^{\mathrm{\top }}$ produces node embeddings (or patch representations) that summarize a patch of the graph centered around node $i$.
• The readout function $R:{\mathbb{R}}^{N\times F}\to {\mathbb{R}}^F$ which summarizes the obtained patch representations into a graph-level representation $\mathbf{s}=R(E(\mathbf{X},\mathbf{A}))$. It is implemented as a sigmoid after a mean $R(\mathbf{H})=\sigma \left(\frac{1}{N}\sum _{i=1}^N{\mathbf{h}}_i\right)$.
• The discriminator $D:{\mathbb{R}}^F\times {\mathbb{R}}^F\to \mathbb{R}$ such that $D({\mathbf{h}}_i,\mathbf{s})$ represents the logit scores assigned to this patch-summary pair (should be higher for patches contained within the summary). It is implemented as a bilinear function $D({\mathbf{h}}_i,\mathbf{s})={\mathbf{h}}_i\mathbf{W}\mathbf{s}$.
• Negative samples are generated by pairing the summary vector $\mathbf{s}$ of a graph with patch representations ${\tilde{\mathbf{h}}}_j$ from another graph $(\tilde{\mathbf{X}},\tilde{\mathbf{A}})$. This alternative graph is obtained as other elements of a training set in a multi-graph setting, or by an explicit corruption function $(\tilde{\mathbf{X}},\tilde{\mathbf{A}})=C(\mathbf{X},\mathbf{A})$ which permutes row-wise the node feature matrix $\mathbf{X}$.

Next we introduce the DGI objective for one training graph $\mathcal{G}=(\mathbf{X},\mathbf{A})$, based on the Jensen-Shannon objective for Deep InfoMax

$$\begin{array}{rl}max\mathcal{L}=\frac{1}{N+M}(& \sum _{i=1}^N{\mathbb{E}}_{x_i\sim V(\mathcal{G})}\log \sigma (D({\mathbf{h}}_i,\mathbf{s}))\\ +& \sum _{j=1}^M{\mathbb{E}}_{{\tilde{x}}_j\sim V(\tilde{\mathcal{G}})}\log (1-\sigma (D({\tilde{\mathbf{h}}}_j,\mathbf{s}))))\end{array}$$

InfoGraph

2020 ICLR - InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization ⁷

InfoGraph studies learning the representations of whole graphs (rather than nodes as in DGI) in both unsupervised and semi-supervised scenarios. Its unsupervised version is similar to DGI except for

• Batch-wise generation of negative samples rather than random-sampling- or corruption-based negative samples.
• GIN methodologies for better graph-level representation learning.

In semi-supervised setting, directly adding a supervised loss would likely result in negative transfer. The authors alleviate this problem by separating the parameters of the supervised encoder $\phi$ and those of the unsupervised encoder $\varphi$, and adding a student-teacher loss which encourage mutual information maximization between the two encoders at all levels. The overall loss is:

$$\begin{array}{rl}\mathcal{L}=& \sum _{G\in {\mathcal{G}}_{\mathrm{l}}}\mathcal{l}({\tilde{y}}_{\varphi }(G),y_G)+\\ & \sum _{G\in {\mathcal{G}}_{\mathrm{l}}\cup {\mathcal{G}}_{\mathrm{u}}}\frac{1}{|V|}\sum _{u\in V}\hat{I}(h_{\phi }^u(G),H_{\phi }(G))-\\ & \lambda \sum _{G\in {\mathcal{G}}_{\mathrm{l}}\cup {\mathcal{G}}_{\mathrm{u}}}\frac{1}{|V|}\sum _{k=1}^K\hat{I}(H_{\varphi }^{(k)}(G),H_{\phi }^{(k)}(G))\end{array}$$

In practice, to reduce the computational overhead, at each training step, we enforce mutual-information maximization on a randomly chosen layer of the encoder.

---

1. NeurIPS 2016 - $f$-GAN: Training Generative Neural Samplers using Variational Divergence Minimization; A blog post explaining the paper in Chinese. ↩

2. ICML 2018 - MINE: Mutual Information Neural Estimation ↩

3. AISTATS 2010 - Noise-contrastive estimation: A new estimation principle for unnormalized statistical models ↩

4. NeurIPS 2018 - Representation Learning with Contrastive Predictive Coding ↩

5. ICLR 2019 - Learning deep representations by mutual information estimation and maximization (slides, video); A blog post explaining the paper in Chinese. ↩↩

6. ICLR 2019 - Deep Graph Infomax. For relations with previous unsupervised graph representation learning methods, see the IPAM tutorial Unsupervised Learning with Graph Neural Networks by Thomas Kipf and also Daza's Master Thesis A Modular Framework for Unsupervised Graph Representation Learning. ↩

7. ICLR 2020 - InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization ↩

Comments