# 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?

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$.
• Thanks for the answer. I still can't see why we need to include the results of that fail. Aren't we already including them? I mean, let's assume that we draw $N$ samples. We have now a set of labels like $S=\{y_1,y_2,\dots,y_N\}$. Assuming independent trials, the probability that we obtain $S$ should be: $Q(y_1|x_1)Q(y_2|x_2) \dots Q(y_N|x_N)$. Am I misinterpreting what $S$ does really contain? Aug 30 '18 at 8:58
• Let's assume that you want to choose exactly one $y$ from the set of $\{y_1, y_2\}$ and you decide whether to include given $y$ by performing a coin flip. You make the flip for $y_1$ and accept it with probability of 0.5, however it does not necessarily meet your requirements. You also need to make sure that the outcome is negative for the $y_2$. Otherwise you would select 2 $y$s while you are only allowed to choose one. To calculate the probability that you would select only $y_1$ you need to include the probability that you will not include $y_2$, hence $0.5 (1 - 0.5) = 0.25$. Aug 31 '18 at 8:07
• Thanks for the clarification. So, the actual process is like that if I understand correctly: When there are $L$ class labels, for a given sample $x_i$, for each label $l$, we sample $Q(y_l|x_i)$ and look whether it is accepted or not. So, our sample space for each $x_i$ corresponds to each combination of $L$ labels, where a subset is accepted and the others not, each one is tried once. Is this understanding correct? Aug 31 '18 at 9:14