7 Generative Adversarial Networks

7.1.1 Some classic ML: The Naive Bayes Classifier

Copy link

⊕Note that naive Bayes is not a Bayesian method.

The Naive Bayes algorithm is not related to GANs or deep learning, but is a classic machine learning (generative) algorithm that is worth knowing.

We have data \(\{(x^{(1)},y_1),\ldots (x^{(n)},y_n)\}\) with \(d\)-vector features and finite labels, say \(\{1,\ldots,K\}\). We assume some family of distributions \(p_\theta(\cdot)\), with parameters \(\theta\), over the data which has a key property (the ‘Naive’ property):

⊕So the key assumption is that the features of \(x\) are condtionally independent given the value of \(y\). \[ p_\theta(x,y) = p_\theta(x ~|~y) p_\theta(y) \underbrace{=}_{\text{Naive}} \Big( \prod_{i=1}^d p_{{\theta}}(x_i~|~y) \Big) p_\theta(y). \]

The naive Bayes algorithm aims to produce a classifier such that with a new observation \({x} \in {\mathbb R}^d\), we have a prediction for the label \(y\). Learning is carried out by estimating \(\hat{\theta}\) from the training data. Then in production/test time, with \(\hat{\theta}\) at hand, prediction is as follows,

⊕This is called the MAP (maximum a posteriori probability) decision rule.
Notice Bayes’ rule. \[ \begin{array}{rcl} \hat{y} &=& \text{argmax}_{y \in \{1,\ldots,K\}} p_{\hat{\theta}}(y ~|~x) \\ &=& \text{argmax}_{y \in \{1,\ldots,K\}} \frac{p_{\hat{\theta}}(x ~|~y) p_{\hat{\theta}}(y)}{p_{\hat{\theta}}(x)} \\ &=& \text{argmax}_{y \in \{1,\ldots,K\}} {p_{\hat{\theta}}(x ~|~y) p_{\hat{\theta}}(y)} \\ &=& \text{argmax}_{y \in \{1,\ldots,K\}} \Big( \prod_{i=1}^d p_{\hat{\theta}}(x_i~|~y) \Big) p_{\hat{\theta}}(y) \\ \end{array} \]

One can now suggest different probability families and use them accordingly. One of the simplest examples which holds when the features are \(\{0,1\}\) boolean is the Bernoulli naive Bayes. Here we assume, \[ p(x ~|~y) = \prod_{i=1}^d p_{yi}^{x_i}(1-p_{yi})^{1-x_i}. \] Hence the parameters \(p_{yi}\), for \(y=1,\ldots,K\) and \(i=1,\ldots,d\) is the probability of class \(y\) generating the term \(x_i\).

Naive Bayes of this sort (and generalizations) has been very popular in e-mail spam detection based on a bag of words summary of the document in question.

7.3.1 Constructing a “game”

Copy link

In training \(G\) and \(D\) we want an objective that will motivate \(G\) to create better samples and at the same time improve \(D\) in detecting if a sample is from \(G\), or is alternativly a real data sample. To formulate this object lets make use of the two probability distributions that are at play:

⊕We often take the probability distribution of the noise to be an i.i.d. Gaussians distribution of some given dimension (called the latent dimension).

• \(p_{\text{data}}(x)\) is the probability distributions of data samples.

• \(p_{z}(z)\) is the probability distribution of the noise.

Take \(D(\cdot)\) as a classifier that returns \(1\) for a real image and \(0\) for a fake image. Then the discriminator wants high values of: \[ \mathbb{E}_{X \sim p_{\text {data }}}[\log D(X)]. \]

Further for every \(Z\) we have a fake sample \(G(Z)\) and \(D(G(Z))\) is the discriminators clasification which is ideally \(0\). Hence the discriminator also wants high values of: \[ \mathbb{E}_{Z \sim p_{z}}[\log (1-D(G(Z)))]. \]

Put together for some fixed discriminator \(D(\cdot)\) and fixed generator \(G(\cdot)\) the discriminator wishes to maximize,

\[ V(G,D) :=\mathbb{E}_{X \sim p_{\text {data }}}[\log D(X)] + \mathbb{E}_{Z \sim p_{z}}[\log (1-D(G(Z)))]. \]

Now for any fixed discriminator (parameters/model) that achieves \[ \max_D V(D,G), \] the generator wants to “fool” the discriminator, so it wishes to achieve, \[ \min_G \max_D V(D,G). \]

⊕Since by now there are several other GAN formulations (see below), this type of original GAN formulation is these days refered to as vanilla GAN. This is the basic GAN formulation, formulated as a mini-max game and if we found parameters \(\theta_G\) and \(\theta_D\) such that achieve the “saddle point” \(\min_G \max_D V(D,G)\), then we have trained the GAN.

7.3.2 The basic training loop

Copy link

Achieving the idealized \(\min_G \max_D V(D,G)\) can be obtained approximately via basic iteration of stochastic gradient descent where \(G\) and \(D\) are trained jointly. The basic algorithm (still from the original GAN paper) is as follows:

Minibatches of size \(m\) are used to train both the discriminator and the generator. There is an option to carry out \(k\) discriminator training iterations for every training step of the generator, however (more) recent empirical evidence generally shows that there isn’t typically a need for this.

Here are the first ever published images generated by GAN experiments from the original 2014 paper.

⊕The rightmost yellow highlighted images are from the actual dataset closest to the GAN sample left of it. They are there to ‘show’ that these GANs did not memorize the data.

⊕GAN Lab is similar to the well know Tensor Flow Playground with which you might have played around previously. Before we dive into more examples and details, let’s play with the wonderful online GAN visualization/simulator, GAN Lab. Here is one visualization from GAN Lab:

An animation from GAN Lab live on your browser

7.3.3 We love the latent space

Copy link

⊕The use of the “latent space”, also sometimes just called a “feature vector” is a very powerful technique sometimes related to auto-encoders. More on this is in the sections below and the next unit dealing with sequence data.

Having an image represeted via the latent space is very powerful. What happens if you slightly perturb the \(Z\) in the latent space? What if you interpolate between two images?

Taken from the 2014 Goodfellow et. al. paper

Lets get a feel for such perturnabtions of the latent space by playing with a very simple analogy (almost too simple). Say we have data from a univariate exponential distribution with mean \(1\).

⊕Note that \(p(x)\) is not a probability but \(p(x) \cdot dx\) for small \(dx\) approximates the probability of falling in the region \([x,x+dx)\). The density for \(x \ge 0\) is, \[ p(x) = e^{-x}. \]

If we were to somehow have a generative model for generating \(x\), what would it be?

One general method for generating (Monte Carlo sampling) a random variable from effectively any uni-variate distribution is the inverse probability transform. Say the CDF (cumulative distribution function) of \(X\) is \(F(x)\) (and for simplicity assume it is continuous). The inverse CDF is denoted \(F^{(-1)}(u)\) (it is the quantile function). If we take a uniform \([0,1]\) random variable, \(U\), then the random variable \(F^{-1}(U)\) will be distributed with CDF \(F(\cdot)\).

In the case of exponential, \[ F(x) = \begin{cases} 0 & x < 0, \\ 1- e^{-x} & x \ge 0. \end{cases} \] Hence we can show that the inverse function is ⊕Just observe that \(F^{-1}\big(F(x)\big) = x\). \[ F^{(-1)}(u) = - \log(1-u). \]

So now we can call \(U \in [0,1]\) our latent random variable. For every \(U\) we have an \(X\) which we generate via,

⊕In this example the distribution of \(-\log(1-U)\) is the same as that of \(-\log U\), so for simplicity we can use the latter.

\[ X = - \log U. \]

Hence the model \(-\log(\cdot)\) is a ‘generative’ model for generating samples from \(p(\cdot)\) (this is a very simple example!!!).

Now if we perturb the value \(U\) in the latent space slightly then \(X\) will be perturbed slightly also! The same happens with the images perturbations on higher dimensional latent spaces as well, it is simply that the latent variable \(Z\) is a vector and the generative model \(G(\cdot)\) is (much more) complicated than our \(-\log(\cdot)\) function.

7.4.1 Conditional GAN

Copy link

The original GAN was generative with respect to \((X)\) with CGAN we also consider the labels \(Y\).

2014: Conditional Generative Adversarial Nets by Mehdi Mirza and Simon Osindero.

\[ \min _{G} \max _{D} V(D, G)=\mathbb{E}_{\boldsymbol{x} \sim p_{\text {data }}(\boldsymbol{x})}[\log D(\boldsymbol{x} \mid \boldsymbol{y})]+\mathbb{E}_{\boldsymbol{z} \sim p_{z}(\boldsymbol{z})}[\log (1-D(G(\boldsymbol{z} \mid \boldsymbol{y})))] \]

Taken from the 2014 CGAN paper

Here is conditional GAN used for MNIST:

Taken from the 2014 CGAN paper

7.4.2 Convolutional GAN

Copy link

The original GAN used fully connected networks. But it is very sensible to use convolutional networks

2016: Unsupervised representation learning with deep convolutional generative adversarial networks, by Alec Radford, Luke Metz, and Soumit Chintala.

Taken from 2016 DCGAN paper

Taken from 2016 DCGAN paper

⊕This hints that there may be meaningful semantics in the latent space.

The strength of the latent space is further demonstrated.

Taken from 2016 DCGAN paper

7.4.3 Large Scale GAN

Copy link

It took a while to generate ‘ImageNet like’ (quality) images. It is now doable. Note that this 2018 work relies on a combination of large and well-managed compute, and several other mathematical advances along the way.

2018: Large scale GAN training for high fidelity natural image synthesis by Andrew Brock, Jeff Donahue, and Karen Simonyan.

Taken from the 2018 Large Scale GAN paper

Note that in ImageNet there are about 100 dog classes and only one tennis ball class…

Taken from the 2018 Large Scale GAN paper

7.4.4 Style GAN

Copy link

See the video at the top of this unit.

2019: A style-based generator architecture for generative adversarial networks by Tero Karras, Samuli Laine and Timo Aila.

Taken from the 2019 Style GAN paper

Taken from the 2019 Style GAN paper

7.5.1 Vanilla GAN minimizes the JS Divergence

Copy link

⊕We denote \(p_g(x)\) as the distribution of samples generated by \(G(\cdot)\). Let’s first observe that for fixed \(G\), the optimal discriminator \(D\) is, \[ D^*(x) = \frac{p_{\text{data}(x)}}{p_{\text{data}(x)} + p_g(x)}, \] where \(p_g(\cdot)\) is the density of \(G(z)\) based on the density \(p_z(\cdot)\) of the latent space.

To see this observe that for fixed \(G\), the objective of \(D\) is to maximize,

\[ \begin{array}{rcl} V(G, D) &=&\int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x})) d x+\int_{z} p_{\boldsymbol{z}}(\boldsymbol{z}) \log (1-D(G(\boldsymbol{z}))) d z \\ &=&\int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x}))+p_{g}(\boldsymbol{x}) \log (1-D(\boldsymbol{x})) d x. \end{array} \]

Now consider the function \(f(y) = a \log (y)+b \log (1-y)\). It achieves it’s maximum at, \[ y = \frac{a}{a+b}, \] so for any fixed \(x\), \[\begin{align*} & \int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (D(\boldsymbol{x}))+p_{g}(\boldsymbol{x}) \log (1-D(\boldsymbol{x})) d x \\ & \le \int_{\boldsymbol{x}} p_{\text {data }}(\boldsymbol{x}) \log (\frac{p_{\text{data}(x)}}{p_{\text{data}(x)} + p_g(x)})+p_{g}(\boldsymbol{x}) \log (1-\frac{p_{\text{data}(x)}}{p_{\text{data}(x)} + p_g(x)}) d x\\ &:= C(G) \end{align*}\]

Observe that, \[ C(G) = -\log 4 + 2 D_{JS}(p_{\text{data}}||p_{g}) \]

⊕See proof details in the original 2014 GAN paper. Now the generator wants to minimize \(C(G)\). It can be shown that it is achieved when \(p_g(\cdot) = p_{\text{data}}(\cdot)\) at which point \(C(G) = - 2 \log 2\).

Hence the theoretical “solution” of a GAN has \(p_g = p_{\text{data}}\) in which case the value \(V(G,D)\) is \(-\log4 \approx -1.3862\).

7.5.2 Mode Collapse

Copy link

While the game has a theoretical equilibrium, in practice we may sometimes not converge to \(p_g = p_{\text{data}}\). This is sometimes called mode colapse. There are several possible reasons for this:

• The equilibrium is not necessarily unique.
• The fact an equilibrium exists does not necessarily mean that an iterative approach will converge to it.
• The equilibrium is only guaranteed to exist for fully expressive models where the network of \(G(\cdot)\) has “enough parameters” to specify any distribution (specifically the distribution \(p_{\text{data}}\)).
• Distributions with non-overlapping support: In cases where in the training process there is non-overlapping or little joint support between \(p_g\) and \(p_{\text{data}}\) then learning ‘gets stuck’.

We focus on the last bullet point by modifing the value function, as described below.

7.6.1 Some basis for the Earth Mover (or Wasserstein) distance

Copy link

7.6.2 The WGAN algorithm

Copy link

The infimum in the Wasserstein distance,

\[ W\left(\mathbb{P}_{r}, \mathbb{P}_{g}\right)=\inf _{\gamma \in \Pi\left(\mathbb{P}_{r}, \mathbb{P}_{g}\right)} \mathbb{E}_{(x, y) \sim \gamma}[\|x-y\|] \]

is highly non-attainable. However, the Kantorovich-Rubinstein duality tells us that,

\[ W\left(\mathbb{P}_{r}, \mathbb{P}_{\theta}\right)=\sup _{\|f\|_{L} \leq 1} \mathbb{E}_{x \sim \mathbb{P}_{r}}[f(x)]-\mathbb{E}_{x \sim \mathbb{P}_{\theta}}[f(x)], \] where the supremum is over all \(1\)-Lipschitz functions, i.e., \[ ||f(x) - f(y)|| \le 1 \cdot ||x-y|| \]

It still isn’t easy to compute this metric, but it inspires using the discrimentator \(D(\cdot)\) as \(f(\cdot)\). Note that now the discriminator is not longer a binary classifier. Hence the WGAN objective is

\[ \min_G \max_{D: ||D||_L \le 1} \mathbb{E}_{x \sim \mathbb{p}_{\text{data}}}[D(x)]-\mathbb{E}_{z \sim \mathbb{p}_{z}}[D(G(x))], \]

There is the problem of how to deal with the constraint, \(: ||D||_L \le 1\). A crude (first) way to do this is via clipping. Here is the algorithm from the WGAN paper

Taken from the WGAN paper

Here are comments also taken from the WGAN paper: