GANs and the Birthday Paradox

One of the biggest challenges in evaluating GAN samples is to understand how much of the real distribution the generator has learned. For example, let’s consider the size of the support for the set of all the possible images of dogs. Naturally, this set must include millions of dog images that portray combinations of all dog features, including size, breed, hair color, pose, and more.

Assuming there are millions of dogs in real life that we humans perceive as unique, a GAN that has truly learned the distribution of dogs must be able to produce a similar number of unique dog images. Estimating the number of unique images of dogs a GAN is able to produce might seem like a daunting task at first, but researchers have found a brilliant crude estimate of this by using the birthday paradox.

The birthday paradox

The birthday paradox is commonly addressed in undergraduate classes where teachers ask students in the class what the probability is that two people in the class have the same birthday. After some speculation, students are normally dazzled to find out that even with only 23 people in a room, the chances that two of them have the same birthday is about 50%. With 23 people in a room, there are $23*22/2$ unique unordered pairs. We divide by $2$ because the order does not matter. The probability that people in a pair have a different birthday is $364/365$. Therefore, the probability that none of the unique unordered pairs represent a match in birthday is equal to $(364/365)^{253}$, which is approximately 50%.

The birthday paradox states that in a discrete distribution of support, $N$, a random sample of size $\sqrt{N}$ is likely to have a duplicate. GANs have continuous support and, therefore, some intervention is needed to adapt the birthday paradox to the GAN framework.

Implementation of the test

A simple yet efficient intervention is to use some image similarity measure to detect a collision and then, given a sample image, use the number of similar images to identify the size of the support of the distribution. Naturally, this method is dependent on the image similarity measure. Normally, two images are considered similar if the distances between them are within some epsilon. This epsilon parameter directly influences the number of collisions that will be found.

The birthday paradox test for GANs proposed by Sanjeev Aurora is as follows:

1. Pick a sample $S$ of size $n$, produced with the generator.

2. Use some similarity measure to compute the similarity between the images in $S$.

3. Flag the 20 most similar pairs in the sample.

4. Visually inspect the flagged images for near duplicates.

5. Repeat the process.

After running this experiment several times, we gather information about how likely it is to find near duplicates in the sample, $S$. If the samples of size $n$ have duplicates with good probability, we’d suspect that the distribution has a support size of about $n^2$.

The birthday paradox works for GANs, especially under the assumption that the generator applies uniform probability to images in its distributions. In cases where the probability distribution is not uniform, the birthday paradox fails.

GAN face similarity analysis

The following imageSource: Do GANs Actually Learn the Distribution? An Empirical Study (https://arxiv.org/abs/1706.08224) is from the paper, “Do GANs Actually Learn the Distribution? An Empirical Study.”