Efficient algorithms for modifying and sampling from a categorical distribution

Understand

Probabilistic programming languages and other machine learning applications often require samples to be generated from a categorical distribution where the probability of each one of $n$ categories is specified as a parameter.

• If the parameters are hyper-parameters then they need to be modified, however, current implementations of categorical distributions take $\mathcal{O}(n)$ time to modify a parameter.
• If $n$ is large and the parameters are being frequently modified, this can become prohibitive.
• Here we present the insight that a Huffman tree is an efficient data structure for representing categorical distributions and present algorithms to generate samples as well as add, delete and modify categories in $\mathcal{O}(\log(n))$ time.