Gumbel max trick and weighted reservoir sampling
A while back, Hanna and I stumbled upon the following blog post: Algorithms Every Data Scientist Should Know: Reservoir Sampling, which got us excited about reservior sampling.
Around the same time, I attended an talk by Tamir Hazan about some of his work on perturb-and-MAP (Hazan & Jaakkola, 2012), which is inspired by the Gumbel-max-trick (see previous post). The apparent similarity between weighted reservior sampling and the Gumbel max trick lead us to make some cute connections, which I'll describe in this post.
Read full article from Gumbel max trick and weighted reservoir sampling
No comments:
Post a Comment