# Show, Attend, Tell why monte carlo sampling?

In the paper Show, Attend and Tell the authors derive the Loss function as $$L_s = \sum_s p(s|a)\log(p(y|s,a)) ,$$ with $s_i \sim \text{Multinoulli}(\alpha_i)$ so that $p(s_i|a) = \alpha_i$, which is parameterized by a one hidden layer MLP. Now, for the backpropagation, they write $$\frac{\partial L_s}{\partial W} = \sum_s p(s|a)\left( \frac{\partial \log(p(y|s,a))}{\partial W} + \log(p(y|s,a)) \frac{\partial \log(p(s|a))}{\partial W}\right),$$ which is simply the expaction value over $p(s|a)$. In the paper they estimate this expectation value by a Monte-Carlo simulation with $s^n \sim \text{IID Multinoulli}(\alpha_i)$ and $$\frac{\partial L_s}{\partial W} \approx \frac{1}{N} \sum_{n=1}^N \left( \frac{\partial \log(p(y|s^n,a))}{\partial W} + \log(p(y|s^n,a)) \frac{\partial \log(p(s^n|a))}{\partial W}\right).$$ What I dont understand is, why do we need the Monte-Carlo sampling? The multinoulli distribution is discrete, so we could calculate the expectation value exactly by just calculating the sum. Where is my mistake here?

In the paper you are referring to, the sum is taken over the variable $s$ which has $L \times T$ categories, with the former dimension being image locations and the latter being word locations. If this number of possible outcomes is large then the sum might be computationally infeasible to calculate, and in this case it would make sense to fall back on Monte Carlo simulation with some smaller number of randomly generated outcomes $N \ll L \times T$. The authors of the paper don't specify if this is the case, but since they are dealing with image data and vocabulary data, it is likely that they have a large number of categories of outcomes, so I suspect that this is the reason they us MC sampling.
• With $3136$ terms in the sum, it should be very easy to get an exact answer, so in that case I would see no reason to use MC sampling.