Jeshua Bratman (jeshuabratman@gmail.com)@San Francisco |
machine learning, programming, tech, etc. |

You've reached
Jeshua Bratman's personal web page and programming blog. Most of my
content consists of tutorials or pieces of code that might be useful
to others. If you're a programmer, you'll understand the how
wonderful it is to come across the exact answer to your programming
question on someone's personal blog, or even better, a short
tutorial, so I thought I'd try to repay the kindness. My area of
expertise is in reinforcement learning and machine learning. I have
a few pieces of machine learning code available and plan to include
more in the future. Thanks for visiting, and enjoy!

I just wrote a piece about our new feature extraction pipeline that I built with Nick Pisarro at TellApart. Read it here on our new engineering blog: The Classifier

I have an elaborate method of making coffee with the few items I currently own in San Francisco (which I had left with a friend) including a semi-broken rice cooker, 1-cup coffee-pour over thingamajig, and two mugs.

Sampling and Evaluating a Poisson without Underflow

Tuesday January 22, 2013

Tags: probabilityjavascript

This entry is just a note on evaluating and sampling from a Poisson without overflow or underflow. The Poisson is a distribution over the number of events $K$ that will occur within some fixed time period, given the mean number of events $\lambda$ the PMF is:

\(P(K=k) = \frac{\lambda^k}{k!} e^{-\lambda}\)Evaluating this directly is numerical unstable for large $\lambda$ because $e^{-\lambda}$ may be very close to 0. Instead we can compute it in log domain.

\(\frac{\lambda^k}{k!} e^{-\lambda} = \prod_{i=1}^k \frac{\lambda}{i} e^{-\lambda} = exp(-\lambda + \sum_{i=1}^k log \frac{\lambda}{i})\)In Javascript:

function Poisson(lambda){ this.lambda = lambda } Poisson.prototype.evaluate = function(k) { var p = -this.lambda; for(var i = 0; i < k; ++i) p += Math.log(this.lambda / (i+1)); return Math.exp(p); }

The commonly used algorithm for sampling from a Poisson (listed in this Wikipedia Article) also runs into the underflow issue for large $\lambda$. The algorithm starts from $p=1$ and multiplies by a uniform random number in $[0,1]$ until $p < e^{-\lambda}$. Since $p > 0$ we have $log~p < – \lambda \Rightarrow p < e^{-\lambda}$

Poisson.prototype.sample = function() { var k = 0; var p = 1; do{ k += 1; p *= Math.random(); } while(Math.log(p) > -this.lambda) return k - 1; }