A Mathematical Introduction to Generative Adversarial Nets (GAN)

Generative Adversarial Nets (GAN) have received considerable attention since the 2014 groundbreaking work by Goodfellow et al [4]. Such attention has led to an explosion in new ideas, techniques and applications of GANs. Yann LeCun has called “this (GAN) and the variations that are now being proposed is the most interesting idea in the last 10 years in ML, in my opinion.” In this note I will attempt to provide a beginner’s introduction to GAN from a more mathematical point of view, intended for students in mathematics. Of course there is much more to GANs than just the mathematical principle. To fully understand GANs one must also look into their algorithms and applications. Nevertheless I believe that understanding the mathematical principle is a crucial first step towards understanding GANs, and with it the other aspects of GANs will be considerably easier to master.

The original GAN, which we shall refer to as the vanilla GAN in this paper, was introduced in [4] as a new generative framework from training data sets. Its goal was to address the following question: Suppose we are given a data set of objects with certain degree of consistency, for example, a collection of images of cats, or handwritten Chinese characters, or Van Gogh painting etc., can we artificially generate similar objects?

This question is quite vague so we need to make it more mathematically specific. We need to clarify what do we mean by “objects with certain degree of consistency” or “similar objects”, before we can move on.

First we shall assume that our objects are points in ${\mathbb{R}}^{n}$. For example, a grayscale digital image of 1 megapixel can be viewed as a point in ${\mathbb{R}}^{n}$ with $n=10^{6}$. Our data set (training data set) is simply a collection of points in ${\mathbb{R}}^{n}$, which we denote by ${\mathcal{X}}\subset{\mathbb{R}}^{n}$. When we say that the objects in the data set ${\mathcal{X}}$ have certain degree of consistency we mean that they are samples generated from a common probability distribution $\mu$ on ${\mathbb{R}}^{n}$, which is often assumed to have a density function $p(x)$. Of course by assuming $\mu$ to have a density function mathematically we are assuming that $\mu$ is absolutely continuous. Some mathematicians may question the wisdom of this assumption by pointing out that it is possible (in fact even likely) that the objects of interest lie on a lower dimensional manifold, making $\mu$ a singular probability distribution. For example, consider the MNIST data set of handwritten digits. While they are $28\times 28$ images (so $n=784$), the actual dimension of these data points may lie on a manifold with much smaller dimension (say the actual dimension may only be 20 or so). This is a valid criticism. Indeed when the actual dimension of the distribution is far smaller than the ambient dimension various problems can arise, such as failure to converge or the so-called mode collapsing, leading to poor results in some cases. Still, in most applications this assumption does seem to work well. Furthermore, we shall show that the requirement of absolute continuity is not critical to the GAN framework and can in fact be relaxed.

Quantifying “similar objects” is a bit trickier and holds the key to GANs. There are many ways in mathematics to measure similarity. For example, we may define a distance function and call two pints ${\mathbf{x}},{\mathbf{y}}$ “similar” if the distance between them is small. But this idea is not useful here. Our objective is not to generate objects that have small distances to some existing objects in ${\mathcal{X}}$. Rather we want to generate new objects that may not be so close in whatever distance measure we use to any existing objects in the training data set ${\mathcal{X}}$, but we feel they belong to the same class. A good analogy is we have a data set of Van Gogh paintings. We do not care to generate a painting that is a perturbation of Van Gogh’s Starry Night. Instead we would like to generate a painting that a Van Gogh expert will see as a new Van Gogh painting she has never seen before.

A better angle, at least from the perspective of GANs, is to define similarity in the sense of probability distribution. Two data sets are considered similar if they are samples from the same (or approximately same) probability distribution. Thus more specifically we have our training data set ${\mathcal{X}}\subset{\mathbb{R}}^{n}$ consisting of samples from a probability distribution $\mu$ (with density $p({\mathbf{x}})$), and we would like to find a probability distribution $\nu$ (with density $q({\mathbf{x}})$) such that $\nu$ is a good approximation of $\mu$. By taking samples from the distribution $\nu$ we obtain generated objects that are “similar” to the objects in ${\mathcal{X}}$.

One may wonder why don’t we just simply set $\nu=\mu$ and take samples from $\mu$. Wouldn’t that give us a perfect solution? Indeed — if we know what $\mu$ is. Unfortunately that is exactly our main problem: we don’t know. All we know is a finite set of samples ${\mathcal{X}}$ drawn from the distribution $\mu$. Hence our real challenge is to learn the distribution $\mu$ from only a finite set of samples drawn over it. We should view finding $\nu$ as the process of approximating $\mu$. GANs do seem to provide a novel and highly effective way for achieving this goal. In general the success of a GAN will depend on the complexity of the distribution $\mu$ and the size of the training data set ${\mathcal{X}}$. In some cases the cardinality $|{\mathcal{X}}|=N$ can be quite large, e.g. for ImageNet data set $N$ is well over $10^{7}$. But in some other cases, such as Van Gogh paintings, the size $N$ is rather small, in the order of 100 only.

To approximate $\mu$, the vanilla GAN and subsequently other GANs start with an initial probability distribution $\gamma$ defined on ${\mathbb{R}}^{d}$, where $d$ may or may not be the same as $n$. For the time being we shall set $\gamma$ to be the standard normal distribution $N(0,I_{d})$, although we certainly can choose $\gamma$ to be other distributions. The technique GANs employ is to find a mapping (function) $G:~{}{\mathbb{R}}^{d}{\longrightarrow}{\mathbb{R}}^{n}$ such that if a random variable ${\mathbf{z}}\in{\mathbb{R}}^{d}$ has distribution $\gamma$ then $G({\mathbf{z}})$ has distribution $\mu$. Note that the distribution of $G({\mathbf{z}})$ is $\gamma\circ G^{-1}$, where $G^{-1}$ maps subsets of ${\mathbb{R}}^{n}$ to subsets of ${\mathbb{R}}^{d}$. Thus we are looking for a $G({\mathbf{z}})$ such that $\gamma\circ G^{-1}=\mu$, or at least is a good approximation of $\mu$. Sounds simple, right?

Actually several key issues remain to be addressed. One issue is that we only have samples from $\mu$, and if we know $G$ we can have samples $G({\mathbf{z}})$ where ${\mathbf{z}}$ is drawn from the distribution $\gamma$. How do we know from these samples that our distribution $\gamma\circ G^{-1}$ is the same or a good approximation of $\mu$? Assuming we have ways to do so, we still have the issue of finding $G({\mathbf{z}})$.

The approach taken by the vanilla GAN is to form an adversarial system from which $G$ continues to receive updates to improve its performance. More precisely it introduces a “discriminator function” $D(x)$, which tries to dismiss the samples generated by $G$ as fakes. The discriminator $D(x)$ is simply a classifier that tries to distinguish samples in the training set ${\mathcal{X}}$ (real samples) from the generated samples $G({\mathbf{z}})$ (fake samples). It assigns to each sample ${\mathbf{x}}$ a probability $D({\mathbf{x}})\in[0,1]$ for its likelihood to be from the same distribution as the training samples. When samples $G({\mathbf{z}}_{j})$ are generated by $G$, the discriminator $D$ tries to reject them as fakes. In the beginning this shouldn’t be hard because the generator $G$ is not very good. But each time $G$ fails to generate samples to fool $D$, it will learn and adjust with an improvement update. The improved $G$ will perform better, and now it is the discriminator $D$’s turn to update itself for improvement. Through this adversarial iterative process an equilibrium is eventually reached, so that even with the best discriminator $D$ it can do no better than random guess. At such point, the generated samples should be very similar in distribution to the training samples ${\mathcal{X}}$.

So one may ask: where do neural networks and deep learning have to do with all this? The answer is that we basically have the fundamental faith that deep neural networks can be used to approximate just about any function, through proper tuning of the network parameters using the training data sets. In particular neural networks excel in classification problems. Not surprisingly, for GAN we shall model both the discriminator function $D$ and the generator function $G$ as neural networks with parameters $\omega$ and $\theta$, respectively. Thus we shall more precisely write $D(x)$ as $D_{\omega}(x)$ and $G(z)$ as $G_{\theta}(z)$, and denote $\nu_{\theta}:=\gamma\circ G^{-1}_{\theta}$. Our objective is to find the desired $G_{\theta}({\mathbf{z}})$ by properly tuning $\theta$.

One way to measure the discrepancy between two probability distributions $\mu$ and $\nu$ is through the Kullback-Leibler divergence, or KL divergence. Let $p(x)$ and $q(x)$ be two probability density functions defined on ${\mathbb{R}}^{n}$. The KL-divergence of $p$ and $q$ is defined as

Note that $D_{KL}(p\|q)$ is finite only if $q(x)\neq 0$ on ${\rm supp}(p)$ almost everywhere. While KL-divergence is widely used, there are other divergences such as the Jensen-Shannon divergence

where $M:=\frac{p(x)+q(x)}{2}$. One advantage of the Jensen-Shannon divergence is that it is well defined for any probability density functions $p(x)$ and $q(x)$, and is symmetric $D_{JS}(p\|q)=D_{JS}(q\|p)$. In fact, following from Proposition 2.1 the minimization part of the minimax problem in the vanilla GAN is precisely the minimization over $q$ of $D_{JS}(p\|q)$ for a given density function $p$. As it turns out, both $D_{KL}$ and $D_{JS}$ are special cases of the more general $f$-divergence, introduced by Ali and Silvey [1].

Let $f(x)$ be a strictly convex function with domain $I\subseteq{\mathbb{R}}$ such that $f(1)=0$. Throughout this paper we shall adopt the convention that $f({\mathbf{x}})=+\infty$ for all ${\mathbf{x}}\not\in I$.

Now clearly $r\leq 1$. If ${\rm supp}(p)\subseteq{\rm supp}(q)$ then $r=1$, and we have $D_{f}(p\|q)\geq 0$. The equality holds if and only if $p=q$. If $f(t)>0$ for all $t\in[0,1)$ then we also have $D_{f}(p\|q)\geq f(r)\geq 0$. For $r<1$ we will have $D_{f}(p\|q)\geq f(r)>0$. Thus if $D_{f}(p\|q)=0$ we must have $r=1$ and $p=q$.  

It should be noted that $f$-divergence can be defined for two arbitrary probability measures $\mu$ and $\nu$ on a probability space $\Omega$. Let $\tau$ be another probability measure such that $\mu,\nu\ll\tau$, namely both $\mu,\nu$ are absolutely continuous with respect to $\tau$. For example, we may take $\tau=\frac{1}{2}(\mu+\nu)$. Let $p=d\mu/d\tau$ and $q=d\nu/d\tau$ be their Radon-Nikodym derivatives. We define the $f$-divergence of $\mu$ and $\nu$ as

Again we adopt the convention that $f(\frac{p(x)}{q(x)})q(x)=0$ if $q(x)=0$. It is not hard to show that this definition is independent of the choice for the probability measure $\tau$, and Proposition 3.1 holds for the more general $D_{f}(\mu\|\nu)$ as well.

With $f$-divergence measuring the discrepancy between two measures, we can now consider applying it to GANs. The biggest challenge here is that we don’t have an explicit expression for the target distribution $\mu$. As with the vanilla GAN, to compute $D_{f}(p\|q)$ we must express it in terms of sample averages. Fortunately earlier work by Nguyen, Wainwright and Jordan [8] has already tackled this problem using the convex conjugate of a convex function.

The convex conjugate of a convex function $f(x)$ is also known as the Fenchel transform or Fenchel-Legendre transform of $f$, which is a generalization of the well known Legendre transform. Let $f(x)$ be a convex function defined on an interval $I\subseteq{\mathbb{R}}$. Then its convex conjugate $f^{*}:{\mathbb{R}}{\longrightarrow}{\mathbb{R}}\cup\{\pm\infty\}$ is defined to be

As mentioned earlier we extend $f^{*}$ to the whole real line by adopting the convention that $f(x)=+\infty$ for $x\not\in I$. Below is a more explicit expression for $f^{*}(y)$.

A consequence of Lemma 3.2 is that under the assumption that $f$ is continuously differentiable, $\sup_{t\in I}\,\{ty-f(t)\}$ is attained for some $t\in I$ if and only if $y$ is in the range of $f^{\prime}(t)$. This is clear if $y\in f^{\prime}(I^{o})$, but it can also be argued rather easily for finite boundary points of $I$. More generally without the assumption of differentiability, $\sup_{t\in I}\,\{ty-f(t)\}$ is attained if and only if $y\in\partial f(t)$ for some $t\in I$, where $\partial f(t)$ is the set of sub-derivatives. The following proposition summarizes some important properties of convex conjugate:

The table below lists the convex dual of some common convex functions:

To estimate $f$-divergence from samples, Nguyen, Wainwright and Jordan [8] has proposed the use of the convex dual of $f$. Let $\mu,\nu$ be probability measures such that $\mu,\nu\ll\tau$ for some probability measure $\tau$, with $p=d\mu/d\tau$ and $q=d\nu/d\tau$. In the nice case of $\mu\ll\nu$, by $f(x)=(f^{*})^{*}(x)$ we have

where $T(x)$ is any Borel function. Thus taking $T$ over all Borel functions we have

On the other hand, note that for each $x$, $\sup_{t}\bigl{\{}t\frac{p(x)}{q(x)}-f^{*}(t)\bigr{\}}$ is attained for some $t=T^{*}(x)$ as long as $\frac{p(x)}{q(x)}$ is in the range of sub-derivatives of $f^{*}$. Thus if this holds for all $x$ we have

In fact, equality holds in general under mild conditions.

To establish the last part of the theorem, assume that $p(x)\in I$. By Lemma 3.2, set $s(t)=f^{\prime-1}(t)$ for $t$ in the range of $f^{\prime}$ so we have

Thus $g_{x}^{\prime}(t)=p(x)-{f^{*}}^{\prime}(t)=p(x)-f^{\prime-1}(t)$. It follows that $g_{x}(t)$ attains its maximum at $t=f^{\prime}(p(x))$. This proves that $T^{*}(x)=f^{\prime}(p(x))$ is an optimizer for (3.8).  

The above theorem requires that $\mu\ll\nu$. What if this does not hold? We have