Re: bbchop & Wikipedia's Bayesian search theory page

[Ealdwulf Wuffinga <ealdwulf@googlemail.com>]

On Sun, Aug 16, 2009 at 6:13 PM, Johannes
Schindelin<Johannes.Schindelin@gmx.de> 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