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!


Recent Blog Posts

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

Read more -->
1208 days ago (5/2013)
Elaborate Method of Making Coffee
Monday March 4, 2013

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.

Read more -->
1275 days ago (3/2013)

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; 
} 
Read more -->
1315 days ago (1/2013)