Title: TOWARDS A TESTABLE NOTION OF GENERALISATION FOR GENERATIVE ADVERSARIAL NETWORKS

Abstract: We consider the question of how to assess generative adversarial networks, in particular with respect to whether or not they generalise beyond memorising the training data. We propose a simple procedure for assessing generative adversarial network performance based on a principled consideration of what the actual goal of generalisation is. Our approach involves using a test set to estimate the Wasserstein distance between the generative distribution produced by our procedure, and the underlying data distribution. We use this procedure to assess the performance of several modern generative adversarial network architectures. We find that this procedure is sensitive to the choice of ground metric on the underlying data space, and suggest a choice of ground metric that substantially improves performance. We finally suggest that attending to the ground metric used in Wasserstein generative adversarial network training may be fruitful, and provide a concrete formulation for doing so.

1. INTRODUCTION:

Generative adversarial networks (GANs) (Goodfellow et al., 2014) have attracted significant interest as a means for generative modelling. However, recently concerns have been raised about their ability to generalise from training data and their capacity to overfit (Arora & Zhang, 2017; Arora et al., 2017) . Moreover, techniques for evaluating the quality of GAN output are either ad hoc, lack theoretical rigor, or are not suitably objective -often times "visual inspection" of samples is the main tool of choice for the practitioner. More fundamentally, it is sometimes unclear exactly what we want a GAN to do: what is the learning task that we are trying to achieve?

In this paper, we provide a simple formulation of the GAN training framework, which consists of using a finite dataset to estimate an underlying data distribution. The quality of GAN output is measured precisely in terms of a statistical distance D between the estimated and true distribution. Within this context, we propose an intuitive notion of what it means for a GAN to generalise.

We also show how our notion of performance can be measured empirically for any GAN architecture when D is chosen to be a Wasserstein distance, which -unlike other methods such as the inception score (Salimans et al., 2016) -requires no density assumptions about the data-generating distribution. We investigate this choice of D empirically, finding that its performance is heavily dependent on the choice of ground metric underlying the Wasserstein distance. We suggest a novel choice of ground metric that we show performs well, and also discuss how we might otherwise use this observation to improve the design of Wasserstein GANs (WGANs) (Arjovsky et al., 2017) .

2. THE OBJECTIVE OF GENERATIVE MODELLING:

GANs promise a means for learning complex probability distributions in an unsupervised fashion. In order to assess their effectiveness, we must first define precisely what we mean by this. We seek to do so in this section, presenting a formulation of the broader goal of generative modelling that we believe is widely compatible with much present work in this area. We also provide a natural notion of generalisation that arises in our framework.

Our setup consists of the following components. We assume some distribution π on a set X . For instance, X may be the set of 32x32 colour images, and π the distribution from which the CIFAR-10 dataset was sampled. We assume that π is completely intractable: we do not know its density (or even if it has one), and we do not have a procedure to draw novel samples from it. However, we do suppose that we have a fixed dataset X consisting of samples x 1 , • • • , x |X| iid ∼ π. Equivalently, we have the empirical distribution

X := 1 |X| |X| n=1 δ xn ,

where δ denotes the Dirac mass.

Let P(X ) denote the set of probability distributions on X . Our aim is to use X to produce a distribution in P(X ) that is as "close" as possible to π. We choose to measure closeness in terms of a function D : P(X ) × P(X ) → R. Usually D will be chosen to be a statistical divergence, which means that D(P, Q) ≥ 0 for all P and Q, with equality iff P = Q. The task of a learning algorithm α in this context is then as follows:

Select α(X) ∈ P(X ) such that D(α(X), π) is as small as possible.

(1)

We believe (1) constitutes an intuitive and useful formulation of the problem of generative modelling that is largely in keeping with present research efforts. Now, we can immediately see that one possibility is simply to choose α(X) := X. Moreover, in the case that D is a metric for the weak topology on P(X ) such as a Wasserstein distance, we have that D( X, π) → 0 almost surely as |X| → ∞, so that, assuming |X| is large enough, we can already expect D( X, π) to be small. This then suggests the following natural notion of generalisation:

A choice of α generalises for a given

EQUATION

In other words, using α here has actually achieved something: perhaps through some process of smoothing or interpolation, it has injected additional information into X that has moved us closer to π than we were a priori.

3. GENERALISATION IN GANS:

The previous section presented (1) as a general goal of generative modelling. In this section, we turn specifically to GANs. We begin by providing a general model for how many of the existing varieties of GAN operate, at least ideally. We then show how this model fits into our framework above, before considering the issue of generalisation in this context.

Most GAN algorithms in widespread use adhere to the following template: they take as input a distribution P , from which we assume we can sample, and compute (or approximate)

Γ(P ) := arg min Q∈Q D Γ (P, Q)

for some choices of Q ⊆ P(X ) and D Γ : P(X ) × P(X ) → R. In other words, in the ideal case, a GAN maps P to its D Γ -projection onto Q. Note that we will not necessarily have that D Γ = D: D Γ is fixed given a particular GAN architecture, whereas the choice of D is simply a feature of our problem definition (1) and is essentially ours to make.

In practice, Q is the set of pushforward measures ν • G -1 obtained from a fixed noise distribution ν on a noise space Z and some set G of functions G : Z → X . Precisely,

Q = ν • G -1 : G ∈ G .

G itself usually corresponds to the set of functions realisable by some neural network architecture, and ν is some multivariate uniform or Gaussian distribution. However, numerous choices of D Γ have been proposed: the original GAN formulation (Goodfellow et al., 2014) took D Γ to be the Jenson-Shannon divergence, whereas the f -GAN (Nowozin et al., 2016) generalised this to arbitrary f -divergences, and the Wasserstein GAN (Arjovsky et al., 2017) advocated the Wasserstein distance. Many of the results proved in these papers involve showing that (usually under some assumptions, such as sufficient discriminator capacity) a proposed objective for G is in fact equivalent to D Γ (P, ν• G -1 ).

In terms of our framework in the previous section, using a GAN Γ amounts to choosing

α(X) := Γ( X) = arg min Q∈Q D Γ ( X, Q).

We emphasise again the important distinction between D and D Γ . In our setup, minimising D defines our ultimate goal, whereas minimising D Γ (over Q) defines how we will attempt to achieve that goal. Even if D = D Γ , it is still at least conceivable that D(Γ( X), π) might be small, and therefore this choice of α might be sensible. Also note that, crucially, Γ receives X as input rather than π itself. We only have access to a fixed number of CIFAR-10 samples, for example, not an infinite stream. Moreover, training GANs usually involves making many passes over the same dataset, so that, in effect, sampling from P will repeatedly yield the same data points. We would not expect this to occur with nonzero probability if P = π for most π of interest.

The observation that P is X rather than π was also recently made by Arora et al. (2017) . The authors argue that this introduces a problem for the ability of GANs to generalise, since, if D Γ is a divergence (which is almost always the case), and if Q is too big (in particular, if it is big enough that X ∈ Q), then we trivially have that Γ( X) = X. In other words, the GAN objective appears actively to encourage Γ( X) to memorise the dataset X, and never to produce novel samples from outside of it. The authors' proposed remedy involves trying to find a better choice of D Γ . The problem, they argue, is that popular choices of D Γ do not satisfy the condition

D Γ (π, Q) ≈ D Γ ( X, Q) with high probability given a modest number of samples in X. (3)

They point out that this is certainly violated when D Γ is the Jensen-Shannon divergence JS, since

JS(P Q) = log 2

when one of P and Q is discrete and the other continuous, and give a similar result for D Γ a Wasserstein distance in the case that π is Gaussian. As a solution, they introduce the neural network distance D NN defined by

D NN (P, Q) := max f ∈F E x∼P [f (x)] -E x∼Q [f (x)]

for some choice of a class of functions F. They show that, assuming some smoothness conditions on the members of F, the choice D Γ = D NN satisfies (3), which means that if we minimise D NN ( X, Q) in Q then we can be confident that the value of D NN (π, Q) is small also.

However, we do not believe that (3) is sufficient to ensure good generalisation behaviour for GANs.

What we care about ultimately is not the value of D Γ , but rather of D, and (3) invites choosing D Γ in such a way that gives no guarantees about D at all. We see, for instance, that the degenerate choice D 0 (P, Q) := 0 trivially satisfies (3), and indeed is also a pseudometric, just like D NN . It is therefore unclear what mathematical properties of D NN render it more suitable for estimating π than the obviously undesirable D 0 . The authors do acknowledge this shortcoming of D NN , pointing out that D NN (P, Q) can be small even if P and Q are "quite different" in some sense.

The problematic consequences of the fact that P = X apply only in the case that Q is too large. In practice, however, Q is heavily restricted, since G is restricted via a choice of neural network architecture; hence we do not know a priori whether Γ( X) = X is even possible. As such, we do not see the choice of α(X) = Γ( X) as necessarily a bad idea, and instead believe that it is an open empirical question as to how well GANs perform the task (1). In fact, this α falls perfectly within the framework of minimum distance estimation (Wolfowitz, 1957; Basu et al., 2011) , which involves estimating an underlying distribution by minimising a distance measure to a given empirical distribution.

4. TESTING GANS:

Our goal in this section is to assess how well GANs achieve (1) by estimating D(Γ(X), π) for various Γ and π. This raises some difficulties, given that π is intractable. Our approach is to take D to be the first Wasserstein distance W d X defined by

W d X (P, Q) = inf γ∈Π(P,Q) X ×X d X (x, y) dγ(x, y),

where d X is a metric on X referred to as the ground metric, and Π(P, Q) denotes the set of joint distributions on the product space X × X with marginals P and Q. The Wasserstein distance is appealing since it is sensitive to the topology of the underlying set X , which we control by our choice of d X . Moreover, W d X metricises weak convergence for the Wasserstein space P d X (X ) defined by P d X (X ) := P ∈ P(X ) :

X d X (x 0 , y) dP (y) < ∞ for some x 0 ∈ X (see (Villani, 2008) ). Consequently, if we denote by A a set of samples

a 1 , • • • , a |A| iid ∼ α(X),

and by Y a set of samples (separate from

X) y 1 , • • • , y |Y |

iid ∼ π, with Â and Ŷ the corresponding empirical distributions, then, provided

EQUATION

we have that D( Â, Ŷ ) → D(α(X), π) almost surely as min {|A| , |Y |} → ∞. Note that condition (4) holds automatically in the case that (X , d X ) is compact, since then P d X (X ) = P(X ).

As such, to estimate D(α(X), π), for D = W d X , we propose the following. Before training, we move some of our samples from X into a testing set Y . We next train our GAN on X, obtaining α(X). We then take samples A from α(X), and obtain the estimate

W d X ( Â, Ŷ ) ≈ W d X (α(X), π),

where the left-hand side can be computed exactly by solving a linear program since both Â and Ŷ are discrete (Villani, 2003) . We can also use the same methodology to estimate W d X ( X, π) by

EQUATION

as a proxy for determining whether (2) holds. A summary of our procedure is given in Algorithm 1.

Algorithm 1 Procedure for testing GANs 1: Split samples from π into a training set X and a testing set Y 2: Compute α(X) by training a GAN on X 3: Obtain a sample A from α(X)

4: Approximate W (α(X), π) ≈ W ( Â, Ŷ ),

where the right-hand side can be computed by solving a linear program 5: Similarly, test whether

W ( Â, Ŷ ) < W ( X, Ŷ )

as a proxy for W (α(X), π) < W (A, π)

4.1. RESULTS:

We applied our methodology to test two popular GAN varieties -the DCGAN (Radford et al., 2015) and the Improved Wasserstein GAN (I-WGAN) (Gulrajani et al., 2017) -on the MNIST and CIFAR-10 datasets. In all cases when computing the relevant Wasserstein distances, our empirical distributions consisted of 10000 samples.

4.1.1. L 2 AS GROUND METRIC:

We initially took our ground metric d X to be the L 2 distance. This has the appealing property of making (X , d X ) compact when X is a space of RGB or greyscale images, therefore ensuring that (4) holds. both datasets, W L 2 ( Â, Ŷ ) decays towards an asymptote in a way that nicely corresponds to the visual quality of the samples produced. Moreover, W L 2 ( Â, Ŷ ) is much closer to W L 2 ( X, Ŷ ) towards the tail end of training for MNIST than for CIFAR-10. This seems to reflect the fact that, visually, the eventual I-WGAN MNIST samples do seem quite close to true MNIST samples, whereas the eventual I-WGAN CIFAR-10 samples are easily identified as fake.

However, when we re-ran the same experiment using a DCGAN on CIFAR-10, we obtained the W L 2 ( Â, Ŷ ) trajectories shown in Figure 2 . Typical examples are shown in Figure 8 . Strangely, we observe that W L 2 ( Â, Ŷ ) < W L 2 ( X, Ŷ ) very early on in training -at around batch 500 -when the samples resemble the heavily blurry Figure 8b . This raises some obvious concerns about the appropriateness of W L 2 as a metric for GAN quality.

We therefore sought to understand this strange behaviour. Motivated by the visual blurriness of the samples in Figure 8b , we explored the effect on W L p ( X, Ŷ ) of blurring the CIFAR-10 training set X. In particular, we let X and Y each consist of 10000 distinct CIFAR-10 samples in X. We then independently convolved each channel of each image with a Gaussian kernel having standard deviation σ, obtaining a blurred dataset β σ (X) and corresponding empirical distribution βσ (X). The visual effect of this procedure is shown in Figure 9 in the appendix. We then computed W L p ( βσ (X), Ŷ ) with σ ranging between 0 and 10 for a variety of values of p. The results of this experiment in the case p = 2 are shown in Figure 3 , and similar results were observed for other values of p: in all cases, we found that

W L p ( X, Ŷ ) > W L p ( βσ (X), Ŷ )

whenever σ > 0. That is, blurring X by any amount brings X closer to Ŷ in W L p than not. This occurs even though X is distributed identically to Y (both being drawn from π), while β σ (X) (presumably) is not when σ > 0. To remedy these issues, we sought to replace L 2 with a choice of d X that is more naturally suited to the space of images in question. To this end we tried mapping X through a fixed pre-trained neural network η into a feature space Y, and then computing distances using some metric d Y on Y, rather than in X directly. It is easily seen that, provided

η is injective, d Y • η : X × X → R defined by (d Y • η)(x, x ) := d Y (η(x), η(x )) is a metric. It also holds that, when η is (d X , d Y )-continuous, (X , d Y • η) is compact when (X , d X )

is: given a sequence x i ⊆ X , there exists a subsequence x i that converges in d X to some x (by compactness), so that

(d Y • η)(x i , x) = d Y (η(x i ), η(x)) → 0 by continuity of η.

Neither of these conditions on η -injectivity and (d X , d Y )-continuity -are unreasonable to expect from a typical neural network trained using stochastic gradient descent (at least, when d X and d Y are typical metrics such as L p distances). Consequently,

EQUATION

is automatically satisfied.

To test the performance of W d Y •η , we repeated the blurring experiment described above. We took η(x) to be the result of scaling x ∈ X to size 224x224, mapping the result through a DenseNet-121 (Huang et al., 2016) pre-trained on ImageNet (Deng et al., 2009) , and extracting features immediately before the linear output layer. Under the same experimental setup as above otherwise, we obtained the plot of W L 2 •η (β σ ( X), Ŷ ) shown in Figure 3 . Happily, we now see that this curve increases monotonically as σ grows in accordance with the declining visual quality of β σ (X) shown in Figure 9 .

Next, we computed W L 2 •η ( Â, Ŷ ) over the course of GAN training. For the I-WGAN we obtained the results on MNIST and CIFAR-10 shown in Figure 4 ;1 for the DCGAN on CIFAR-10, we obtained the curve shown in Figure 5 . In all cases we see that W L 2 •η ( Â, Ŷ ) decreases monotonically towards an asymptote in a way that accurately summarises the visual quality of the samples throughout the training run. Moreover, there is always a large gap between the eventual value of

W L 2 •η ( Â, Ŷ ) and W L 2 •η ( X, Ŷ )

, which reflects the fact that the GAN samples are still visually distinguishable from real π samples. In particular, we see an improvement in this respect for the I-WGAN on MNIST: in Figure 1 the asymptotic value of W L 2 ( Â, Ŷ ) for MNIST was barely discernible from W L 2 ( X, Ŷ ), despite the fact that it is still quite easy to tell real samples from generated ones (see e.g. the various mistakes present in Figure 6 ).

5. DISCUSSION AND FUTURE WORK:

We believe our work reveals two promising avenues of future inquiry. First, we suggest that W L p •η is an appealing choice of D, both due to its nice theoretical properties -it metricises weak convergence, and does not require us to make any density assumptions about π -and due to its sound empirical performance demonstrated above. It would be very interesting to use this D to produce a systematic and objective comparison of the performance of all current major GAN implementations, and indeed to use this as a metric for guiding future GAN design. We also view the test (5) as potentially useful for determining whether our algorithms are overfitting. This would be particularly so if applied via a cross-validation procedure: if we consistently observe that (5) holds when training a GAN according to many different X and Y partitions of our total π samples, then it seems reasonable to infer that α(X) has indeed learnt something useful about π.

We also believe that the empirical inadequacy of W L 2 that we observed suggests a path towards a better WGAN architecture. At present, WGAN implementations implicitly use W L 2 for their choice of D Γ . We suspect that altering this to our suggested W L 2 •η may yield better quality samples. We briefly give here one possible way to do so that is largely compatible with existing WGAN setups.

In particular, following Arjovsky et al. (2017) , we take

D Γ (P, Q) = max f ∈F E x∼P [f (x)] -E x∼Q [f (x)]

for a class F of functions f : X → R that are all (L 2 • η, d R )-Lipschitz for some fixed Lipschitz constant K. Here d R denotes the usual distance on R. To optimise over such an F in practice, we can require our discriminator f : X → R to have the form f (x) := h(η(x)), where h :

Y → R is (d Y , d R )

-Lipschitz, which entails that f is Lipschitz provided η is (which is almost always the case in practice). In other words, we compute

D Γ (P, Q) = max h∈F E x∼P [h(η(x))] -E x∼Q [h(η(x))] ,

where F is a class of (d Y , d R )-Lipschitz functions. Optimising over this objective may now proceed as usual via weight-clipping like (Arjovsky et al., 2017) , or via a gradient penalty like (Gulrajani et al., 2017) . Note that this suggestion may be understood as training a standard WGAN with the initial layers of the discriminator fixed to the embedding η; our analysis here shows that this is equivalent to optimising with respect to W L 2 •η instead of W L 2 . We have begun some experimentation in this area but leave a more detailed empirical inquiry to future work.

It is also clearly important to establish better theoretical guarantees for our method. At present, we have no guarantee that the number of samples in A and Y are enough to ensure that D( Â, Ŷ ) ≈ D(α(X), Ŷ )

(perhaps with some fixed bias that is fairly independent of α, so that it is valid to use the value of D( Â, Ŷ ) to compare different choices of α), or that (5) entails (2) with high probability. We do however note that some recent theoretical work on the convergence rate of empirical Wasserstein estimations (Weed & Bach, 2017) does suggest that it is plausible to hope for fast convergence of D( Â, Ŷ ) to D(α(X), Ŷ ). We also believe that the convincing empirical behaviour of W L 2 •η does suggest that it is possible to say something more substantial about our approach, which we leave to future work.

6. RELATED WORK:

The maximum mean discrepancy (MMD) is another well-known notion of distance on probability distributions, which has been used for testing whether two distributions are the same or not (Gretton et al., 2012) and also for learning generative models in the style of GAN (Li et al., 2015; Dziugaite et al., 2015; Sutherland et al., 2016; Li et al., 2017) . It is parameterised by a characteristic kernel k, and defines the distance between probability distributions by means of the distance of k's reproducing kernel Hilbert space (RKHS). The MMD induces the same weak topology on distributions as the one of the Wasserstein distance. Under a mild condition, the MMD between distributions P and Q under a kernel k can be understood as the outcome of the following two-step calculation. First, we pushforward P and Q from their original space X to a Hilbert space H (isomorphic to k's RKHS) using a feature function φ : X → H induced by the kernel k. Typically, H is an infinite-dimensional space, such as the set 2 of square-summable sequences in R ∞ as in Mercer's theorem. Let P and Q be the resulting distributions on the feature space. Second, we compute the supremum of ) ] over all linear 1-Lipschitz functions f : H → R. The result of this calculation is the MMD between P and Q.

E P (X) [f (X)] -E Q (X) [f (X

This two-step calculation shows the key difference between MMD and our use of Wasserstein distance and neural embedding η. While the co-domain of the feature function φ is an infinitedimensional space (e.g. 2 ) in most cases, its counterpart η in our setting uses a finite-dimensional space as co-domain. This means that the MMD possibly uses a richer feature space than our approach. On the other hand, the MMD takes the supremum over only linear functions f among all 1-Lipschitz functions, whereas the Wasserstein distance considers all these 1-Lipschitz functions. These different balancing acts between the expressiveness of features and that of functions taken in the supremum affect the learning and testing of various GAN approaches as observed experimentally in the literature. One interesting future direction is to carry out systematic study on the theoretical and practical implications of these differences.

A EXAMPLE I-WGAN SAMPLES 

:

Note that on MNIST in this case we first duplicated each input across three channels for shape compatibility with the DenseNet.

Figures and Tables:

Figure1shows W L 2 ( Â, Ŷ ) plotted over multiple training runs for MNIST and CIFAR-10 when A is obtained from an I-WGAN, with typical samples shown in Figures6 and 7in the appendix. For

Figure 3: Effect of blurring CIFAR-10 on W L 2 (left) and W L 2 •η (right)

Figure 4: Output of Algorithm 1 with d X = L 2 • η for I-WGAN trained on MNIST (left) and CIFAR-10 (right)

Figure 6: Samples from I-WGAN trained on MNIST

Figure 7: Samples from I-WGAN trained on CIFAR-10

Peer review (iclr2018):
 `The papers aims to provide a quality measure/test for GANs. The objective is ambitious an deserve attention. As GANs are minimizing some f-divergence measure, the papers remarks that computing a Wasserstein distance between two distributions made of a sum of Diracs is not a degenerate case and is tractable. So they propose evaluate the current approximation of a distribution learnt by a GAN by using this distance as a baseline performance (in terms of W distance and computed on a hold out dataset). A first remark is that the papers does not clearly develop the interest of puting things a trying to reach a treshold of performance in W distance rather than just trying to minimize the desired f-divergence. More specifically as they assess the performance in terms of W distance I would would be tempted to just minimize the given criterion. This would be very interesting to have arguments on why being better than the "Dirac estimation" in terms of W2 distance would lead to better performance for others tasks (as other f-divergences or image generation). According to the authors the core claims are: "1/ We suggest a formalisation of the goal of GAN training (/generative modelling more broadly) in terms of divergence minimisation. This leads to a natural, testable notion of generalisation. " Formalization in terms of divergence minimization is not new (see O. Bousquet & all https://arxiv.org/pdf/1701.02386.pdf ) and I do not feel like this paper actually performs any "test" (in a statistical sense). In my opinion the contribution is more about exhibiting a baseline which has to be defeated for any algorithm interesting is learning the distribution in terms of W2 distance. "2/ We use this test to evaluate the success of GAN algorithms empirically, with the Wasserstein distance as our divergence." Here the distance does not seems so good because the performance in generation does not seems to only be related to W2 distance. Nevertheless, there is interesting observations in the paper about the sensitivity of this metric to the bluring of pictures. I would enjoyed more digging in this direction. The authors proposes to solve this issue by relying to an embedded space where the L2 distance makes more sense for pictures (DenseNet). This is of course very reasonable but I would expect anyone working on distribution over picture to work with such embeddings. Here I*m not sure if this papers opens a new way to improve the embedding making use on non labelled data. One could think about allowing the weights of the embeddings to vary while f-divergence is minimized but this is not done in the submitted work. "3/ We find that whether our proposed test matches our intuitive sense of GAN quality depends heavily on the ground metric used for the Wasserstein distance." This claim is highly biased by who is giving the "intuitive sense". It would be much better evaluated thought a mechanical turk test. "4/ We discuss how to use these insights to improve the design of WGANs more generally." As our understanding of the GANs dynamics are very coarse, I feel this is not a good thing to claim that "doing xxx should improve things" without actually trying it.