Dynamic Programming in Python: Bayesian Blocks (2012)

the article is painfully verbose, and doesn't even get into what the objective function is! (it just gives a high level description of what dynamic programming is) And the paper is worse, droning on the idea for 82 pages!! The idea is interesting, but its on the level of a programming puzzle.

The idea:

If there are k bins in a histogram. The "fitness" of a bin is

N[k] ( logN[k] − logT[k])

N[k] is the number of elements in bin k

T[k] is the width of the bin k

The fitness of a histogram is the sum of the fitnesses of all the bins. The larger the above number, the better. The optimal segmentation of the bins can be found by a simple recursion on the elements,

(Best Histogram for points 1..n) = max_j { (Best Histogram for points 1..j) + (Fitness of final bin from j...n) }

Finally, the formula has a simple interpretation. If we think of the histogram as a probability density function, we can be said to be trying to minimize the KL divergence between the histogram's distribution and the empirical distribution.

Here's the revised AstroML version of the code - the demo using it still works with it, too...

https://github.com/astroML/astroML/blob/master/astroML/densi...