Show, Attend, Tell why monte carlo sampling?

Question

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?

Answer 1

You are correct that your finite sum can be computed exactly in principle. However, you should bear in mind that if the number of elements in your sum is very large, it might be computationally infeasible to calculate the exact sum.

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.