Toward a Generalization Metric for Deep Generative Models

A generative model $\mathcal{G}$ is trained on $\mathscr{D}_{train}$ to produce $p_{model}$, an estimate of $p_{data}$. The quality of $\mathcal{G}$ is defined by the divergence/distance between $p_{data}$ and $p_{model}$. Let $f$ be a divergence/distance function. Because $f(p_{data},p_{model})$ is intractable for most distributions of interest, we approximate it with $f(\mathscr{D}_{r},\mathscr{D}_{g})$ where ${\mathscr{D}_{r}},{\mathscr{D}_{g}}$ are polynomial sized datasets.

Inception Score (IS) [24] is defined as:

where $\bm{x}\sim p_{model}$ is the input, $y$ is the label, and $p(y)=\mathbb{E}_{\bm{x}\sim p_{model}}\left[p(y|\bm{x})\right]$. $p(y|\bm{x})$ is computed by feeding the generated data point through a pretrained classifier, e.g. the Inception network [26]. IS is maximized when $\textnormal{H}\left(Y|\bm{X}\right)=0$ and $\textnormal{H}(Y)=\ln C$ where $C$ is the number of classes. Barratt and Sharma [4] showed that $\textnormal{IS}\left(p_{model}\right)\leq C$. To make our writing consistent, we convert all of the metrics in this paper to (pseudo) divergences. A lower divergence should imply that $p_{model}$ is closer to $p_{data}$. We define the following pseudo divergence:

This is a pseudo divergence because (1) it only contains 1 distribution, $p_{model}$, the other distribution is implicitly the dataset on which the classifier was trained, and (2) $f_{is}\left(p_{model}\right)=0$ does not imply that the two distributions are the same (more on this in Section 3). A fundamental flaw of IS is that a smaller $f_{is}\left(p_{model}\right)$ implies that $p(y)$ is closer to the uniform distribution, not that $p(y)$ is closer to the true distribution over the labels. Fortunately (or unfortunately), the distribution over the labels in the Imagenet dataset [6] is uniform. This makes IS a popular and somewhat abused tool for evaluating image generation models.

Fréchet Inception Distance (FID): Heusel et al. [12] approximate $p_{data}$, $p_{model}$ with two Gaussian distributions $\mathcal{N}\left(\bm{\mu}_{r},\bm{\Sigma}_{r}\right)$ and $\mathcal{N}\left(\bm{\mu}_{g},\bm{\Sigma}_{g}\right)$, respectively, and then compute the Fréchet distance between the two Gaussians:

Because FID compares only the first 2 moments of $p_{data}$ and $p_{model}$, $f_{fid}\left(p_{data},p_{model}\right)=0$ does not guarantee that the 2 distributions are the same.

Neural Net Divergence (NND) [11, 2] uses neural nets to compute the divergence between $p_{data}$ and $p_{model}$

where $f_{\bm{\phi}}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is usually a neural network with finite capacity. $f_{\bm{\phi}}$ is trained to maximize the difference in Eqn. 4. Arora et al. [2] showed that NND can detect the lack of diversity in generated data. Gulrajani et al. [11] leveraged that capability to estimate the generalizability of GMs. We show in Section 3 that the diversity in generated data can be faked easily by adding white noise to the data. This fake diversity is present in real-world models such as GANs and VAEs. We propose a fix to NND that removes the effect of fake diversity while retaining the discriminative power of NND.

The above metrics use scalars to measure both the quality and diversity of generated samples. The following metrics are designed to separate quality from diversity.

$k$-means based Precision-Recall ($k$-means PR) [23] applies $k$-means algorithm to $\mathscr{D}_{r}\cup\mathscr{D}_{g}$, builds 2 histograms to approximate $p_{data}$ and $p_{model}$, and computes the difference between these histograms. The results are 2 F-scores, $F_{\beta}$ and $F_{1/\beta}$. For $\beta>1$, $F_{\beta}$ can be interpreted as the recall (diversity) and $F_{1/\beta}$ can be interpreted as the precision (quality) of the generated data (Algo. 1). We define the following pseudo divergences: $f_{p\textnormal{-}kmeans}=1-F_{1/\beta}$, $f_{r\textnormal{-}kmeans}=1-F_{\beta}$.

$k$-nn based Precision-Recall ($k$-nn PR) [17] computes the precision and recall by comparing the reconstructed real manifold and the reconstructed fake manifold (Algo. 2 and Fig. 1). Kynkäänniemi et al. [17] claimed that $k$-nn PR has better discriminative power than $k$-means PR and demonstrated that on several datasets. However, we show in Section 3 that $k$-nn PR has the worst worst-case performance, and in practice, it cannot distinguish a good model from a very bad model. We define the following pseudo divergences: $f_{p\text{-}knn}=1-P$, $f_{r\text{-}knn}=1-R$.

Similar to IS and FID, $k$-means PR and $k$-nn PR assign (near) perfect scores to generative models that produce the entire training set.

Metrics for class-conditional models: Esteban et al. [7] proposed the “Train on Synthetic Test on Real” (TSTR) approach to evaluate class-conditional GANs. The metric is expensive to compute as it requires training a classifier on a labeled synthetic dataset. Shmelkov et al. [25] extended the idea to a Precision-Recall-like metric for class-conditional GANs. Because these metrics are applicable only to class-conditional GMs, we do not consider them in this paper.

Topological/Geometrical approaches: Khrulkov and Oseledets [15], Horak et al. [13] applied geometrical and topological tools to measure the difference between the fake manifold and the real manifold. These metrics are not designed for measuring generalizability and are not considered in this paper. Karras et al. [14] used the pairwise perceptual distance - the pairwise distance between data points on the feature manifold - to measure the smoothness of the feature manifold. The intuition is that if the perceptual distance is small, then the manifold is smoother, and the GM might learn better representations and have better generalizability. We show in Section 4 that the pairwise distance does not well reflect the smoothness of the manifold, and it is minimized when total mode collapse occurs. Therefore, pairwise perceptual distance is not a good metric for GMs.

Non-parametric approaches: Arora et al. [3] used the birthday paradox and human evaluation to estimate the number of distinct modes that a GM can generate. The method cannot be automated and has high variance and bias because humans are involved in the loop. Meehan et al. [18] proposed a three sample test for data copying in GMs. The metric can detect data copying but cannot measure the generalizability of a model or the quality of the generated samples.

When mode collapse or training set memorization [8] happen, the generative model generates slightly different versions of the memorized data points. We simulate this kind of behavior with the following generative procedure:

Given a dataset $\mathscr{D}\subseteq\mathscr{D}_{train}$, a constant $\epsilon\in\mathbb{R}$, a new data point is generated by

1. 1.

   Draw a data point $\bm{x}\in\mathscr{D}$ at random

2. 2.

   Draw a noise vector $\bm{u}\sim p_{u}$, where $p_{u}$ is the noise distribution.

3. 3.

   Output the noisy data point: $\tilde{\bm{x}}=\bm{x}+\epsilon\bm{u}$

In our experiments, $p_{u}=\mathcal{U}(-\bm{1},\bm{1})$ (see Fig. 7 for samples from MNIST dataset). We tried replacing $\mathcal{U}(-\bm{1},\bm{1})$ with $\mathcal{N}(\bm{0},\textbf{I})$ and found no difference in performance. This generator, denoted as $\mathcal{G}_{\mathscr{D},\epsilon}$, has no real generalization capacity and the number of essentially different modes in $p_{\mathcal{G}_{\mathscr{D},\epsilon}}$ is $\left\lvert\mathscr{D}\right\rvert$. For $\epsilon>0$, this generator can be approximated with a neural net with finite capacity.

Let $\mathscr{D}^{*}$ be the smallest subset of $\mathscr{D}_{train}$ that satisfies $\mathbb{E}_{\mathscr{D}_{test}\sim p_{data},\ \left\lvert\mathscr{D}_{test}\right\rvert=m}\left[f(\mathscr{D}_{test},\mathscr{D}^{*})\right]\leq\mathbb{E}_{\mathscr{D}_{test}\sim p_{data},\ \left\lvert\mathscr{D}_{test}\right\rvert=m}\left[f(\mathscr{D}_{test},\mathscr{D}_{train})\right]$. The divergence $f$ cannot distinguish a model that produces only $\mathscr{D}^{*}$ and a model that produces $\mathscr{D}_{train}$. By memorizing only $\mathscr{D}^{*}$, a generator can fool $f$ that it can produce a larger dataset. The smaller $\left\lvert\mathscr{D}^{*}\right\rvert$ is, the more vulnerable $f$ is to training set memorization. We construct $\mathscr{D}^{*}$ for the metrics mentioned above and discuss the relationship between $\mathscr{D}^{*}$ and the performance of a metric in practice. Because NND is the only metric designed to be robust against training set memorization, it is the focus of this section. We defer the details for other metrics to the appendix.

Inception Score

where $\mathscr{C}_{i}\subset\mathscr{D}_{train}$ is the $i$-th class of the training set. Details in Appx. A.

$k$-means Precision-Recall

where $\mathscr{C}_{i}$ is the $i$-th cluster of the $k$-means clustering algorithm. Details in Appx. C.

$k$-nn Precision-Recall

Details in Appx. D.

Neural Net Divergence is computed by training a finite capacity neural net $f_{\bm{\phi}}$ to maximize the objective in Eqn. 4. Because the value of NND depends on the network and the training procedure, there is no fixed $\mathscr{D}^{*}_{nnd}$. However, given a network $f_{\bm{\phi}}$, we can still estimate the size of $\mathscr{D}^{*}_{nnd}$ through experiments.

First, we investigate the effect of noise on NND. In our experiment, the dataset is the MNIST dataset, $f_{\bm{\phi}}$ is an MLP with 3 hidden layers and 512 neurons in each layer. Details about the architecture and hyper parameters are in Appx. B. We use the generator described in Section 2.4 to generate noisy versions of data points in $\mathscr{D}$, a random subset of $\mathscr{D}_{train}$ (see Fig. 7 for noisy images generated by the generator). The number of essentially different data points that the generator can generate is $\left\lvert\mathscr{D}\right\rvert$. We vary $\left\lvert\mathscr{D}\right\rvert$ from $1000$ to $60000$ and $\epsilon$ from $0$ to $1$. The noisy samples are generated continuously throughout the training process as recommended by the authors NND metric, [11]. As we can see in Fig. 7, for $\epsilon=0.1$ and $\epsilon=0.5$ the noisy images are very clear and easily recognizable. For $\epsilon=1$, the images are much more noisy but still recognizable. At first glance, one might think that adding noise to clean data will increase the NND because the quality of generated data is worsened. The result in Fig. 2 shows the opposite. As we can see from the figure, when $\epsilon$ and $\left\lvert\mathscr{D}\right\rvert$ increase, $f_{nnd}$ decreases. Increasing $\epsilon$ results in a bigger decrease in $f_{nnd}$ than increasing $\left\lvert\mathscr{D}\right\rvert$. For $\epsilon=1$, a noisy random subset of size 1000 outperforms a noiseless set of size 60000 by a large margin. The network also cannot distinguish noisy sets of size 10000 and 60000 and gives them the same score (the red solid line in Fig 2). We conclude that $\left\lvert\mathscr{D}^{*}_{nnd}\right\rvert\leq 1000$ for this specific network.¹¹1We note that our experiments with $p_{u}=\mathcal{N}(\bm{0},\textbf{I})$ produces the same results.

On the positive side, we observe that the NND decreases as $\left\lvert\mathscr{D}\right\rvert$ increases. However, the NND is plateauing as $\left\lvert\mathscr{D}\right\rvert$ reaches $60000$. If we continue to increase $\left\lvert\mathscr{D}\right\rvert$ to much larger numbers, the network will assign about the same NND to these datasets. This behavior is expected as the capacity of the network is polynomial in $d$. A neural network of a polynomial size can only distinguish datasets of polynomial sizes (for a more detailed discussion, please refer to [2]). We can still use NND to test for generalization if the network can distinguish datasets of sizes larger than $\left\lvert\mathscr{D}_{train}\right\rvert$. The larger the network is, the more discriminative the NND becomes.

If we can remove the fake diversity caused by noise, we can use NND to estimate the diversity of generated data. We can reduce the effect of noise by generating a noisy data set $\mathscr{D}_{g}$ of a fixed and polynomial size and train $f_{\bm{\phi}}$ on $\mathscr{D}_{g}$ and $\mathscr{D}_{test}$. For the experiment in Fig. 2, we use $\mathcal{G}_{\mathscr{D},\epsilon}$ to generate a dataset $\mathscr{D}_{g}$ of $60000$ noisy data points. In contrast to the previous experiment, the NND increases with the level of noise. This behavior is expected as a larger $\epsilon$ results in worse images, making the task of separating $\mathscr{D}_{g}$ from $\mathscr{D}_{test}$ easier. By fixing the size of $\mathscr{D}_{g}$, we can effectively remove the fake diversity.

The outputs of GMs usually contain noise. For Autoregressive Models and Energy Based Models, the noise comes from the randomness in the sampling process. For generative latent variable models like GANs, VAEs, and flows, the noise comes from the prior distribution. A generative model can memorize a subset of the training data, add noise to the memorized data points, and fool $f_{nnd}$ that it has learned to faithfully reproduce the target distribution. Our next experiment investigates this phenomenon in real-world models. We use GANs as our example. We select a random subset $\mathscr{D}$ from $\mathscr{D}_{train}$, train a GAN on $\mathscr{D}$, and use the resulting model to generate fake data. For each model, we compute 2 NND scores following the original procedure and our new procedure described in the previous paragraph. Fig. 2 shows the changes in NND of models over 500 epochs. As expected, the NND of ‘Fix’ datasets is higher than that of ‘Inf’ datasets. However, the difference between ‘Fix’ and ‘Inf’ datasets is small, suggesting that the level of noise in the outputs of GAN is much lower than that in our experiment in Fig. 2.

Because $-\log(\mathscr{D}|H)$, the description length of the training data given the GLVM is not easily computable in some GLVMs like GANs, we replace it with the divergence between $\hat{p}_{data}$ and $\hat{p}_{model}$. The divergence can be computed using one of the methods in Section 2.1.

If $\mathcal{G}$ memorizes $\mathscr{D}_{train}$, then $f(\mathscr{D}_{train},\mathscr{D}_{g})$ goes to 0 but $\text{COMP}(\mathcal{G})$ blows up. If $\text{COMP}(\mathcal{G})$ goes to 0, then generated samples are concentrated in a small region, making $f(\mathscr{D}_{train},\mathscr{D}_{g})$ goes up (assuming that $f$ is a divergence that is good at detecting the lack of diversity, e.g., our fixed NND). Therefore, our metric cannot be fooled by training set memorization. In general, $f_{gen}$ cannot be 0 because the two terms cannot be 0 at the same time.

A metric with large $\alpha$ will prefer models that can reproduce the training set more faithfully. A small $\alpha$ will result in a metric that prefers simpler models. $\alpha$ can be removed if we are comparing models with the same divergence.

A GLVM that produces constant speed paths in the space of generated data is desirable because (1) it is less likely to memorize the training set, (2) it does not make sudden jumps from one memorized data point to another, thus produces smoother interpolation. We propose the following constant speed regularizer for the generator $\mathcal{G}$ in GANs:

where $\mathcal{L}_{\mathcal{G}}$ is the original loss function of $\mathcal{G}$, $\bar{s}$ is the average speed on the path from $\mathcal{G}(\bm{z}_{i})$ to $\mathcal{G}(\bm{z}_{j}),$ and the interpolation method is a constant speed interpolation method, i.e. $\left\lVert\frac{\partial\bm{z}}{\partial t}\right\rVert=\mathrm{const}$. The regularizer forces the variance of the speed to 0, making the speed constant. As noted by other authors [e.g. 14], for complicated datasets like the Imagenet, it might be better to apply the regularizer to the feature space. In the experiments below, we apply the regularizer directly to the data space because the dataset is simple.

We measure the performance of evaluation metrics on GANs trained on MNIST to see how their worst-case performances correlate to their real-world performances. The result is shown in Fig. 4 - 4.²²2IS and FID are not included because computing them requires the Inception model. Gulrajani et al. [11] empirically showed that IS and FID are not robust against training set memorization. We refer readers to their experimental results. We trained 5 variants of GAN on the MNIST dataset. The variants are GAN with 0GP regularizer [28] (GAN0GP), GAN with R1 regularizer [19] (GANR1), WGAN with gradient penalty [1, 10] (WGAN-1GP), WGAN with 0GP [28], and WGAN1GP with our new constant speed regularizer (WGAN1GP-const). Thanh-Tung et al. [28] showed in their paper that 0GP improves the generalization capacity of the discriminator and that, in turn, improves the generator’s generalization capacity. They also claimed that 1GP [10] does not help improving generalization. We verify their claims with our fixed NND metric.

The result for NND is shown in Fig. 4. WGAN0GP consistently has lower NND than WGAN1GP. That confirms the claims by Thanh-Tung et al. [28]. We also find that GAN0GP also more stable than GANR1 as GANR1 can suddenly collapse during training. Fig. 4 shows that GANR1 suffers from overfitting after epoch 400, and its NND starts to increase. GAN0GP’s NND decreases as the training progresses. Our constant speed does a very good job at improving the generalization capacity of WGAN1GP. WGAN1GP-const has almost the same NND as WGAN0GP while producing smoother interpolation (see Fig. 5, 5).

$k$-means PR does not do a good job at distinguishing models with different generalization capacities. Fig. 4 shows that all models achieve almost perfect precision (i.e. $F_{1/\beta}$) after 400 epochs. In contrast to NND, $k$-means PR assigns the highest precision and recall to GANR1. This result is expected as Thanh-Tung and Tran [27] and Thanh-Tung et al. [28] suggested that the R1 regularizer may encourage the generator to memorize the training set. The other GANs with better generalization capacity will produce more data points that are further away from the training and test sets. The far data points result in a lower recall, as we see in Fig. 4.

$k$-nn PR does a much better job distinguishing different models (Fig. 4). The result seems to justify the claim of its authors [17]. However, Fig. 4 shows that $k$-nn PR assigns very high recall to a very bad GAN. Fig. 1 illustrates the same phenomenon on a lower-dimensional dataset. $k$-nn works fine for good models that distribute the fake data evenly across the real manifold, but it is vulnerable to bad models that generate many outliers.

Discussion: This experiment shows that the robustness of evaluation metrics on real-world datasets is directly correlated to the size of their minimal dataset $\mathscr{D}^{*}$. $k$-nn PR has the smallest minimal set and is the most vulnerable to outliers in the data. $k$-means PR has $\left\lvert\mathscr{D}^{*}_{kmeans}\right\rvert=k$ and different data points in $\mathscr{D}^{*}_{kmeans}$ must lie in different clusters. To fool $k$-means PR, a generator must produce fake data points belonging to different clusters. That is nontrivial for real-world generative models. NND (both the original and our updated version) has the biggest $\mathscr{D}^{*}_{nnd}$ and is the most robust. Our updated NND can be used to estimate the generalization capacity of GMs.

Fig. 5 shows the interpolation results for WGAN1GP and WGAN1GP-const. Interpolations produced by WGAN1GP contain many sudden jumps (red boxes in Fig. 5). At the beginning and the end of an interpolation path, the image at a step is almost identical to the image at the previous step (yellow boxes in Fig. 5). The phenomenon suggests that similar to the generator in Fig. 3, WGAN1GP memorizes the training data. In contrast, WGAN1GP-const produces smooth interpolations with no sudden jumps. Fig. 4 shows that WGAN1GP-const has a very good generalization capacity, i.e., it can produce many more images that are not in the training set. Our constant speed regularizer helps the generator avoids training set memorization and generalizes.

We test the discriminative power of the computational complexity. We compare the computational complexity with the pairwise path length [14]. The result is shown in Fig. 6. The pairwise path length is not good for distinguishing different models. WGAN1GP and WGAN0GP have roughly the same pairwise path length. The same is true for GANR1 and GAN0GP. In contrast, the computational complexity can clearly separate different models. We also see that the complexity of each model increases as the training progresses. GANs with 0GP have lower complexity than GANs with 1GP and R1 penalty. The result confirms that 0GP can help to reduce the complexity and improve generalization. Our constant speed regularizer does an outstanding job in minimizing the complexity. The complexity of WGAN1GP-const is much lower than other models and does not increase as the training progresses. The result again confirms the effectiveness of our constant speed regularizer.