Re: bbchop & Wikipedia's Bayesian search theory page

On Sun, Aug 16, 2009 at 6:13 PM, Johannes
Schindelin[off-list ref] wrote:

I tried to find some documentation for Bayesian search theory, but it
seems those ridiculous Wikipedia admins struck once again, in their
mission to reduce the world's intellect to their own.

It looks like it is still there to me:
http://en.wikipedia.org/wiki/Bayesian_search_theory

It looks like github has included a ')' on the end when html-ifying
the link inthe README, making it into a dead link. I'll fix that.

The wikipedia article is still not amazing,though. Unfortunately most
of the online descriptions
of Bayesian Search Theory, such as:
http://www.sarinz.com/index.cfm/3,112,261/landsearchmethodsreview.pdf
seem to go heavily into the minutia of search-and-rescue, which while
interesting, is not
relevant to git.

However, although I got the idea of bbchop from search theory, it is
not necessary to know much
of search theory in order to understand bbchop. The basic algorithm is
very simple:

At each step, test the commit for which the expected gain of information (about
the location of the bug) is greatest.

That is basically all I got from search theory so far - the
calculation of the probability of the
bug existing in each location is standard bayesian probability theory,
which maybe you already
know. If not, a very readable reference is:
http://www.inference.phy.cam.ac.uk/mackay/itila/book.html (free on-line book).

So all the code does is compute N entropies and pick the best. Most of the
complexity is introduced by:
 - calculating the N entropies without calculating N^2 probabilities
 - calculations over a DAG.

Ealdwulf