Fast Fr\'echet Inception Distance

The Fr\'echet Inception Distance (FID) has been used to evaluate thousands of generative models. We present a novel algorithm, FastFID, which allows fast computation and backpropagation for FID. FastFID can efficiently (1) evaluate generative model *during* training and (2) construct adversarial examples for FID.


Introduction
Generative modeling is a popular approach to unsupervised learning, with applications in, e.g., computer vision [21] and drug discovery [19]. A key difficulty for generative models is to evaluate their performance, i.e., how good is the generative model approximating the data distribution? For image data, it is most common to use the Frechet Inception Distance (FID) [14]. FID is computed using m "fake" samples from the model distribution and n "real" samples from the data distribution.
FID is used in two ways [14]. Most commonly, FID is used to compare generative models after training. However, FID can also be used to monitor improvements of a single generative model during training. Monitoring improvements during training is particularly useful when training Generative Adversarial Networks [12], which normally lack a numeric indicator for whether the generators performance improves. For model comparison after training one typically use 50000 samples, which takes a long time. For monitoring improvement during training, we find that it is sufficient to use surprisingly few fake samples m if the number of real samples n remains large.
Decreasing m appropriately reduces computation time from approximately 60s to 10s. We further reduce computation time to approximately 0.2s by introducing a novel algorithm FastFID. FastFID supports gradient computations which allow efficient construction of adversarial examples for FID, see Figure 1. FastFID generalizes to similar distances like Fréchet ChemNet Distance (FCD) [20].

Original
Bad FID

Modified
Good FID  Preprint.

Fast Fréchet Inception Distance
The FID between the model distribution P model and the real data distribution P data is computed as follows. Draw "fake" model samples f 1 , ..., f m ∼ P model and "real" data samples r 1 , ..., r n ∼ P data .
Encode all samples f i and r i by computing activations A(f i ) and A(r i ) of the final layer of the pretrained Inception network [23]. Compute the sample means µ 1 , µ 2 and the sample covariance matrices Σ 1 , Σ 2 of the activations A(f i ), A(r i ). The FID is then the Wasserstein distance [11] between the two multivariate normal distributions N (µ 1 , Σ 1 ) and N (µ 2 , Σ 2 ).
For evaluation during training, the original implementation use 10000 samples by default [14]. On our workstation, 2 this cause the FID evaluation to take approximately 20s. Of the 20s, it takes approximately 10s to compute Inception encodings and approximately 10s to compute tr(

Previous algorithm
The original FID implementation [14] computes tr( The matrix square root is computed using SCIPY.LINALG.SQRTM [24] which implements an extension of the algorithm from [3] which is rich in matrix-matrix operations [10]. The algorithm starts by computing the following Schur decomposition. The algorithm then computes a triangular matrix U such that U 2 = V by exploiting the triangular structure of both U and V . In particular, the triangular structure implies the following triangular [10]. The equations can be solved wrt. U one superdiagonal at a time. The resulting U yields a matrix square root of the initial matrix. Uniqueness. The matrix square root √ M is defined to be any matrix that satisfies √ M √ M = M . The square root of a matrix is in general not unique, i.e., some matrices have many square roots. The above algorithm does not necessarily find the same square root matrix if it is run several times, because the Schur decomposition is not unique. Furthermore, when computing U ii = √ T ii one has the freedom to choose both ±| √ T ii |. The SCIPY.LINALG.SQRTM implementation choose U ii = | √ T ii |. Our implementation of the algorithm we present in Section 2.2 computes the trace tr( √ Σ 1 Σ 2 ) such that it agrees with SCIPY.LINALG.SQRTM up to numerical errors.

Our algorithm
This subsection presents an algorithm that computes tr( Σ 1 Σ 2 ) fast. The high-level idea: construct a "small" matrix M such that the eigenvalues Since M is small, we can compute its eigenvalues faster than we can compute the matrix square root √ Σ 1 Σ 2 .
Let X 1 ∈ R d×m be a matrix with columns A(f 1 ), ..., A(f m ), let X 2 ∈ R d×n be a matrix with columns A(r 1 ), ..., A(r n ) and let 1 k be the 1 × k all ones vector. The sample covariance matrices Σ 1 and Σ 2 can then be computed as follows: This allows us to write Recall that the eigenvalues of AB are equal to the eigenvalues of BA if both AB and BA are square matrices [17]. The eigenvalues of the d × d matrix The matrix M is small in the sense that we will use m d, for example, for FID we often use m = 128 fake samples while d = 2048.
Since both U and V are triangular they have their eigenvalues on the diagonal, which means that Note that even though the Schur decomposition Σ 1 Σ 2 = QU Q T is not unique, U will always have the eigenvalues of Σ 1 Σ 2 on its diagonal and thus preserve the trace. Putting everything together, we realize that tr( For completeness, we provide pseudo-code in Algorithm 1. The algorithm can be modified to compute FCD by simply changing the Inception network to the ChemNet network. .., f m ∼ P model , the Inception network Net(x) and precomputed µ 2 , C 2 .
9: // Compute trace of square root matrix. 10: 14: // Compute trace of both covariance matrices. 15: tr Computing Gradients. If the network Net(x) used in Algorithm 1 supports gradients with respect to its input, as the Inception network does, it is possible to compute gradients with respect to the input samples f i . If f i were constructed by a generative model, one can even compute gradients wrt. the parameters of the generative model. If Algorithm 1 is implemented with autograd support, e.g., through PyTorch [18] or TensorFlow [1], these gradients are computed automatically. For example, we implemented Algorithm 1 in PyTorch and used autograd to compute gradients when constructing adversarial examples in Section 5.
Potential Further Speed-ups.
In this section, we have focused on decreasing the time consumption of tr( √ Σ 1 Σ 2 ). As a result, the majority of the time consumption of Algorithm 1 is spent computing Inception encodings. The Inception encodings could be further speed up by, e.g., compressing [6] the used network at the cost of introducing some small error.

Speed-Up
In Section 2, we presented a fast algorithm to compute tr( √ Σ 1 Σ 2 ), which can be used to speed up the computation of both FID and FCD. In this subsection, we compare the running time of our PyTorch [18] implementation of Algorithm 1 against open-source implementations. 3 The algorithms are compared as the number of different fake samples varies m = 256, 128, ..., 8.
We used images from the CelebA dataset [15] when timing FID. We used SMILES molecules from the MOSES dataset [19] when timing FCD. For both FID and FCD, we precomputed Σ 2 with 10000 real samples. We also timed tr( C T 1 Σ 2 C 1 ) in isolation, by using Σ 2 ∈ R d×d with N (0, 1) entries and computed C 1 from Equation (4) where X 1 ∈ R d×n has N (0, 1) entries. To make timings of tr( C T 1 Σ 2 C 1 ) comparable with FID, we chose d = 2048 so it matches the Inception network. For each m, we ran one warmup round and then repeated the experiment 100 times. For all m, our algorithm is at least 25 times faster than the previous algorithms, and in some cases up to hundreds or even thousands of times faster. We emphasize that both algorithms were given the same task and computed the same thing, our algorithm was just faster.

Numerical Error
To investigate the numerical error of Algorithm 1 and SCIPY.LINALG.SQRTM, we ran an experiment where the square root can easily be computed. If we choose C 1 = C 2 then C 1 C T 1 C 2 C T 2 = (C 1 C T 1 ) 2 is positive semi-definite and has an unique positive semi-definite square root (C 1 C T 1 ) 2 = C 1 C T 1 . Furthermore, it is exactly this positive semi-definite square root SCIPY.LINALG.SQRTM computes, since the implementation chooses the positive eigenvalues U ii = | √ V ii | (see Section 2.1 for details). We can then investigate the numerical errors by comparing the ground truth tr(C 1 C T 1 ) with the result from both Algorithm 1 and SCIPY.LINALG.SQRTM. To amplify the numerical errors we used 32-bit floating points instead of 64-bit floating points.
The experiment was repeated for m = 32, 64, 128, 256 number of fake samples, were C 1 was computed as done in Section 3.1. We report the ground truth tr(C 1 C T 1 ) and the absolute numerical error caused by Algorithm 1 and SCIPY.LINALG.SQRTM, e.g., we report |tr( Table 1. The numerical error of Algorithm 1 is at least 1000 times smaller than that of SCIPY.LINALG.SQRTM. We suspect Algorithm 1 is more numerically stable because it computes eigenvalues of a "small" m × m matrix instead of computing a Schur decomposition of the "full" d × d matrix.  Figure 3, which displays the error of discriminator/generator during training of a DCGAN [21] on CelebA [16] at 64 × 64 resolution. This looks quite different to supervised error functions like mean squared error, which typically drops steadily during training. Both the discriminator error and the generator error has no clear interpretation. This makes it difficult to determine whether training improves the performance of the generator.
To mitigate this issue, [14] used FID to evaluate a DCGAN [21] during training. We similarly computed FID every 10 mini-batch updates using m = 10000, see the right plot in Figure 3. 5 The FID drops steadily during training, which indicates that training does indeed improve the performance of the generator, at least as measured by FID. However, computing FID with m = 10000 is computationally expensive. Each FID computation took at least 20s, while a single mini-batch update of the DCGAN took 0.09s. This means the FID computations took at least 20 times the training time, even though we only computed FID once every 10 iterations. To speed up the evaluation, we computed FID with Algorithm 1 using just m = 128 fake samples, while still using the n = 10000 precomputed activations on the validation set. The resulting FID computation took 0.2s, at least 100 times faster. As a result, the FID computations took no more than 0.25 times the training time.
Let F ID m denote FID evaluated with m fake samples. We plot both F ID 128 and F ID 10 4 during training of the DCGAN in Figure 4. The left plot shows both FIDs during the first epoch (1500 mini-batch updates). Both FIDs drop during training, and they qualitatively appear to be very similar.
The middle plot shows that both FID losses behave similarly throughout training. To quantify the error we get by using F ID 128 instead of F ID 10 4 , we attempt to measure how good F ID 128 is at predicting F ID 10 4 . For simplicity, we fitted a linear regression model f (F ID 128 ) = a·F ID 128 +b to approximate F ID 10 4 . The linear regression model solves to f (x) = 1.086x−54.165 which attains correlation coefficient r = 0.995 and a mean squared error of 0.0032. The right plot in Figure 4 shows F ID 128 on x-axis and F ID 10 4 on y-axis and the linear regression model.
The linear model suggests that the computed F ID 10 4 and F ID 128 are roughly related by an offset. It thus seems reasonable to use F ID 128 as a measure of relative generative improvement during training. We emphasize that the 100× speed-up typically makes the difference as to whether such quantitative evaluation is practically feasible or not. One of the main difficulties when debugging and experimenting with GANs, is the lack of a single numeric measure of generative performance that can be frequently evaluated at a low cost, this is now possible with F ID 128 using Algorithm 1.

Frechet ChémNet Distance
On image data it is often possible for humans to qualitatively evaluate whether model samples improve during the early stages of training. However, it seems harder for humans to carry out such qualitative assessment when the generated samples are, e.g., molecules. This motivates the need for quantitative evaluation of molecules during training of generative models. In this section, we demonstrate that Algorithm 1 also allows efficient computation of FCD. For simplicity, we retrained the Variational AutoEncoder from [19] on the MOSES dataset and compared F CD 128 against F CD 10 4 . The results are visualized in Figure 5 following the same structure as Figure 4. It took around 1.87s to compute F CD 10 4 and only 0.055s to compute F CD 128 , at least 30 times faster.

Adversarial Examples
Previous work showed that it is possible to make images that fool neural network classifiers [13]. One well know example makes an imperceptible modification to a correctly classified input image of a panda by adding a small vector of "noise," which fools the classifier to predict the new input as a gibbon with high confidence [13].
What would adversarial examples be for FID? Here, we present two types. First, images that perceptibly look like random noise but attain good FID, denoted "adversarial noise for FID." For an example, see the second row of Figure 1a. Second, images that perceptibly look real but attain a bad FID, denoted "adversarial examples for FID." For an example, see the second row of Figure 1b. Together, these two types of adversarial attacks show that it is possible to fool the FID.
A simple way to make an adversarial input, being noise or a natural looking image, is to optimize F ID(z) by gradient updates from some starting point z. We take z to be samples from either random noise vectors z ∼ N (0, 1) or random samples from the CelebA dataset [16]. To ensure that generated samples remain valid, i.e., in the range [0; 1], under gradient updates, we apply the sigmoid function to the adversarial noise and clip values of adversarial examples. To compute FID during training, we have pre-computed that statistics for a training set of 190 thousand samples and a validation set of ten thousand samples. We optimize the same batch of 64 samples to either maximize or minimize FID. Note that the reported F ID 64 is biased in the sense that it is an upper bound of F ID 10 4 . This bias means that the adversarial noise may have a better (lower) F ID 10 4 since it is no more than F ID 64 . On the other hand, it means that the adversarial examples may be worse (lower).
Adversarial Noise for FID. Figure 6a depicts the training and validation loss during 500 gradient steps on a batch of noise. The validation loss reaches an FID of 42.6 after 500 steps, as indicated by the gray dashed line. In Figure 1a, one can compare random samples from the initial random batch of noise, which has a validation FID of 463.9, and the same samples but after the 500 gradient steps. The produced adversarial noise still visually looks like random noise but attains a low FID.
Adversarial examples for FID. Figure 6b shows the training and validation loss during 200 gradient steps on a random sample of 64 real images from the CelebA data set. After 200 steps, the validation FID is 9901.1, as indicated by the dashed grey line. Again, for a comparison between original samples and optimized samples, see Figure 1b.

Related Work
The literature contains several methods for evaluating generative models. An overview can be found in [4] which reviews a total of 29 different methods. This article concerns the FID, which is arguably the most popular method, often used to benchmark state of the art generative models like, e.g., [5].

Computational Resources
To the best of our knowledge, there exists no published article which reduces the computational resources associated with the FID. However, some open-source implementations of FID contain modifications which remove parts of the resource heavy computations. Such "modified FIDs" are faster but resolves to approximations. Below, we compare two modifications with our algorithm.
[9] reduces time consumption from O(d 3 + d 2 m) to O(dm) by computing only ||µ 1 − µ 2 || 2 2 , omitting the trace term tr(Σ 1 + Σ 2 − 2 √ Σ 1 Σ 2 ). [7] incorporates the covariance matrices while retaining the O(dm) time complexity, by only using the diagonal entries of the covariance matrices. We emphasize that leaving out parts of the FID formula can introduce arbitrarily high levels of error. In comparison, our algorithm computes the exact FID in O(d 2 m) time. Even though our algorithm has a higher asymptotic time complexity, for m ≤ 128 it consumes no more than double the time of [7,9]. This is true because both algorithms compute Inception encodings which take more than half of the computation time.
Finally, [8] computes tr( √ Σ 1 Σ 2 ) by computing the eigenvalues of √ Σ 1 Σ 2 √ Σ 1 . This has the advantage that Σ 1 is symmetric so one can compute √ Σ 1 through its eigendecomposition. Such approach is not possible for Σ 1 Σ 2 which, in general, is not symmetric. The derivations of [8] have some similarities to our derivations, but they do not exploit small m and thus take O(d 3 + d 2 m) time.

Adversarial Examples
The Inception Distance (ID) [22] was widely used before the introduction of the FID. Previous work has successfully constructed adversarial examples against ID [2]. To the best of our knowledge, such adversarial examples have not been constructed for the FID. FastFID allows constructing such adversarial examples efficiently by simple gradient descent as presented in Section 5.

Conclusion
We introduced FastFID which computes FID fast when the number of "real" samples is large and the number of "fake" samples is small. Depending on the number of "fake" samples, FastFID is between 25 to 500 times faster than a previous implementations. FastFID can be extended to the Frechet ChemNet Distance, FastFCD, which is between 30 to 150 times faster than a previous implementation. The attained speed-up is useful when evaluating FID/FCD frequently during training. Finally, FastFID allow the construction of adversarial examples for FID by simple gradient descent.

Broader Impact
Potential Positive Impact. FastFID allow researchers to quantitavely test the training of generative models faster than previously possible. This is particularly useful for researchers with a constraint on their computational budget, e.g., a PhD student with a single GPU will benefit more than a industry lab with several GPUs. We hope this decreases the computational budget needed to perform experimental research for generative models.
Potential Negative Impact. FastFID allows one to efficiently cheat FID. This could make FID less reliable, since bad actors can use FastFID to train their generative model to make adversarial examples for FID. For example, a bad actor might first train a competitive generative model, then fine-tune the model to attain state of the art performance by directly minimizing FID.