[GitHub] [incubator-mxnet] zixuanweeei commented on issue #15231: mxnet.nd.random.multinomial is very slow on CPU and stucked on GPU

[GitBox <gi...@apache.org>]

zixuanweeei commented on issue #15231: mxnet.nd.random.multinomial is very slow on CPU and stucked on GPU
URL: https://github.com/apache/incubator-mxnet/issues/15231#issuecomment-502459544
 
 
   While `np.random.multinomial` gives the frequency of each outcome drawn from n experiments (sampling without replacement), `mx.nd.random.multinomial` gives the outcomes sampled from the multinomial distribution (sampling with replacement). At first thought, they produce the result in different ways. `mx.nd.random.multinomial` uses a very simple method as described in [this link](https://en.wikipedia.org/wiki/Multinomial_distribution#To_simulate_a_multinomial_distribution). The complexity of the method above can be O(N^2) for sampling K times from K possible outcomes with replacement. So it will be time-consuming for a large value of K as 300000 in your script. Any method can be taken to optimize the sampling method after that we further analysis the complexity and take some surveys on advance sampling algorithms.
   Any insights of this?

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services