Candidate Sampling for Softmax - Tensorflow; Sampling Probability I am trying to understand the mathematics behind the sampled softmax in Tensorflow. They have the following document, trying to explain how the sampling process works: https://www.tensorflow.org/extras/candidate_sampling.pdf
So, the document has the following part which confuses me:

The document is very poorly written and I am not sure what this probability term really calculates. To the best of my understanding, they sample a number of classes from the set of all classes $L$. The sampling probability of a certain class, given the sample $x_i$ is driven by the distribution $Q(y|x_i)$. Then the probability of obtaining an instantiation $S=\{y_1,y_2,\dots,y_N\}$ of $S_i$ should be (assuming independence):
$$P(S_i=S|x_i) =\prod_{n=1}^{N}Q(y_n|x_i)$$
Curiously, the term given in the document is independent from the sample count $N$. And it involves the probability of not sampling a class $y$, namely $1-Q(y|x_i)$. So, I think I have completely misunderstood the sampling process for $S_i$. How does one obtain the $P(S_i=S|x_i)$ term as stated in the document here?
 A: By $P(y|x)$ we denote the typical outputs distribution that we try to approximate using the neural network (we usually try to directly approximate it's logarithm $F(x, y) = log( P(y | x) )$). $Q(y | x)$ is different because it's probability of a Bernoulli trial where we either include or exclude some label $y$ from our sample. We are actually interested in $P(S_i = S | x_i)$ distribution which tells us how likely it is to sample a whole set of labels $S_i$.
The explanation of the formula from the document is that given some sample $S$ we would like the Bernoulli trial from $Q$ to succeed for all of the labels in $S$ and fail for all other samples. Using your simplified version of the equation would mean that you don't care about the results from the rest of the trials. So, instead of probability of given subset of labels $S$, you would compute the probability of any superset of $S$.
I think that the equations from the document might be too generalized. In particular one could be surprised that the $Q(y | x)$ distribution depends on $x$. In practice it would depend directly on the target label $t$ (which in turn depends on $x$). Moreover it would be often the case that $Q$ doesn't depend on any input at all as in case of the uniform ($Q(y) = \frac{1}{|L|}$) or "zipfian" (log-uniform) distribution. I suppose that we condition on $x$ only to cover some more sophisticated samplers, e.g. where we would also like to include labels that are very similar to the target $t$.
