Why Discriminator converges to 1/2 in Generative Adversarial Networks?

Why expect the Discriminator network to converge to probability 1/2 when it is defined as

indicating the probability that x is a real training example rather than a fake sample drawn from the model [1] [2]

Given this definition, I would expect it to converge to 1, i.e. thinking constantly that x is from the real training sample?

What am I missing?

I'll try to skip math, and use intuition instead.

You show Discriminator a lot of examples. Some are real, some are fake (coming from the Generator).

Intuitively, you want Generator to be able to fool Discriminator every time into thinking that a fake example is a real one. It shouldn't be able to differentiate between real and fake examples.

You don't show it real examples exclusively for it to tell you that it's always a real one. You show it real examples 50% of the time. Other 50% of the time you show it fake examples. You want it to think that it's a real example when it really is. You also want it to think it's a fake when it really is. But, when the fakes are really good, it won't be able to tell a difference. It will classify some real examples as fake, and some fakes as real. There are two classes. On average, two classes have probability of 50% each, if they have the same number of samples. If everything's perfect, the best D can do is guess whether it's a fake or a real example it's been shown, which gives probability of 50%.

What would you say if I showed you two twin brothers, that you don't know, and asked you to tell me which one is which? The best you could do is guess. You could flip a coin, too, which is the same. If a GAN cannot differentiate, then it can only guess, because it knows there are two classes, and that further means we have trained our generator well.

On a large number of examples, if D can't differentiate between real and fake ones, your GAN has achieved a state of Nash equilibrium. It's a game that G and D play against each other, and we hope they reach the equilibrium at some point.

D is a common classifier. If it always outputs '1', for real examples, then P('1') = 1. If it always outputs '0', for fake examples, then P('0') = 1, or, P('1') = 0. So, either your G is really bad, or D is somehow broken. In the beginning, D will be able to differentiate between real and fake examples more easily. But you want to train your G to produce better examples. At the same time, you also train your D to be able to recognize fakes more accurately. You want your GAN to achieve the state of equilibrium, when neither player can improve.

{1} explains why the output of discriminator network $D$ converges to $\frac{1}{2}$:

For $G$ fixed, the optimal discriminator $D$ is $D^*_G(\mathbb{x}) = \frac{p_\text{data}(\mathbb{x})}{p_\text{data}(\mathbb{x}) + p_g(\mathbb{x})}$.

Therefore, if you have $p_g=p_\text{data}$, meaning that the neural network $G$ has learned the true distribution, then $D^*_G(\mathbb{x})=\frac{1}{2}$.

{1} gives some proof of that claim, but intuitively you can consider Algorithm 1's weight update strategy:

• Sample minibatch of $m$ noise samples $\{ \mathbb{z}^{(1)}, \dots, \mathbb{z}^{(m)} \}$ from noise prior $p_g(\mathbb{z})$.
• Sample minibatch of $m$ examples $\{ \mathbb{x}^{(1)}, \dots, \mathbb{x}^{(m)} \}$ from data generating distribution $p_\text{data}(\mathbb{x})$.
• Update the discriminator by ascending its stochastic gradient:

$$\nabla_{\theta_d} \frac{1}{m} \sum_{i=1}^m \left[ \log D\left(\mathbb{x}^{(i)}\right) + \log \left(1-D\left(G\left({z}^{(i)}\right)\right)\right) \right].$$

When $\mathbb{x}^{(i)}$ is undistinguishable from $\mathbb{z}^{(i)}$, $D$ simply cuts in the middle, i.e. $\mathbb{x}^{(i)} = \mathbb{z}^{(i)} = \frac{1}{2}$.

References:

• {1} Goodfellow, Ian, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. "Generative adversarial nets." In Advances in Neural Information Processing Systems, pp. 2672-2680. 2014. https://arxiv.org/abs/1406.2661v1
• The optimal $D^*_G(\mathbb{x})$ is due to the utility function when maximized over $D$. So it doesn't matter what $D$ is? That is the point that is confusing for me. If I am to construct a Discriminator for my learning problem, should I make it such that it converges to 1/2 whenever I thinks that $p_g=p_\text{data}$ and converges to 0 or 1 whenever it thinks that $p_g \ne p_\text{data}$? Because only it that case I can be sure that $D$ learned to discriminatie at the end, no? Anyway, the more I think about this, the more I think that $D$ can be completely arbitrary - which seems odd. – Davor Josipovic Dec 16 '16 at 6:43
• But then again, looking at it as a zero-sum game with mixed (i.e. probabilistic) strategies, it isn't all that odd that it converges to 1/2 in Nash equilibrium. If it were a pure strategy game, then it would converge to 1. So it might be that it is due to the fact that the strategies are mixed. Anyway, it is still fuzzy to me... and I still am not sure about how I should construct $D$. – Davor Josipovic Dec 16 '16 at 6:54

If $p_g=p_d$ the input data $x_1,...,x_n\sim p_d$ and the generated data $G(z_1),...,G(z_n)\sim p_g$ come from the same distribution. It is thus impossible to distinguish between samples of real and generated data because they are samples of the same distribution. The best the discriminator can do is thus guessing if $x$ was generated or real. For the discriminator guessing corresponds to $D(x)=1/2$, that is, the probability of $x$ being real is $1/2$. Note this also makes the probability of $x$ being generated $1/2$.

More formally, this follows directly from [1]'s Proposition 1. It says that for any fixed generator $G$ the optimal discriminator is

$$D^*_G(x)=\frac{p_d(x)}{p_d(x)+p_g(x)}$$

Inserting $p_d(x)=p_g(x)$ we get

$$D^*_G(x)=\frac{p_g(x)}{p_g(x)+p_g(x)}=\frac{1}{2}$$

In other words. If the generator recovers the real data distribution, the optimal discriminator blindly guess

The idea of Proposition 1's proof is to find $D$ that minimizes the value of the game

$$V(D, G)=\mathbb{E}_{x\sim p_d}\left[\log D(x)\right]+\mathbb{E}_{z\sim p_z}\left[\log(1-D(G(z)))\right]$$

for fixed $G$. This can be done by rewriting $V(D, G)$ a bit, then differentiating with respect to $D$ and solving for 0. This is the rough idea, however, to make the details work one needs to be a little bit more careful. Check out [1]'s proof if you want to see the details.

• What is the meaning of $D(x) =1$? – Davor Josipovic Oct 31 '17 at 12:00
• D stands for 'discriminator'. The discriminators' job is to distinguish real data from generated data. Given one data point x, D(x) is the probability the discriminator assigns to x being a real. D(x)=1 then means the discriminator assigns 100% probability that x is real. – Alexander Mathiasen Nov 1 '17 at 22:40
• The discriminator gets data $G(z_1),...,G(z_n) \sim p_g$ from the generator. It assigns it a probability ~0 (i.e. highly unlikely that $p_g = p_{data}$) or ~1 (otherwise). The ~0.5 is when it is not sure. Why would that discriminator be better than one that can discriminate with a higher probability? Suppose $p_{data}=N(0,1)$. If my discriminator checks for $N(0,1)$, then $D(x)$ will always be higher when $p_g = p_{data}$. In that case, will $E[D(x)]$ be 0.5 or 1? I don't know, but I certainly don't see why I should train it to 0.5 instead of 1. – Davor Josipovic Nov 1 '17 at 23:16
• Actually - as I think of it now - if $D(x)=1$, then it means that the generator is doing a bad job from an adversarial point of view. So from the minimax perspective it would have to generate "special" data that discriminator can not discriminate well, to maximize its own return. So they balance out at 0.5. To relate to the example, the generator would have to generate data from something close to $N(0,1)$, but not exactly. Isn't that what they call the Nash equilibrium: they both loose? Well... guess I miss a few IQs for this... – Davor Josipovic Nov 1 '17 at 23:31
• They balance out at 0.5: Exactly, it is vital that you consider both terms in the sum. The generator would have to generate data EXACTLY as N(0, 1). Check out the definition on Nash Equilibrium. en.wikipedia.org/wiki/Nash_equilibrium – Alexander Mathiasen Nov 4 '17 at 14:20