4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ As far as I know, the paper states that they used L=196 and T=16. So the direct computing would need 3136 summands. Is in this case the MC sampling really faster as long as you want the result to be accurate? $\endgroup$ – zimmerrol Jun 22 '18 at 10:05
  • $\begingroup$ 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. $\endgroup$ – Ben Jun 22 '18 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.