git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: bbchop & Wikipedia's Bayesian search theory page

From
EWEaldwulf Wuffinga <ealdwulf@googlemail.com>
Date
Aug 17, 2009, 14:46 UTC
Message-ID
<efe2b6d70908170746o36fca4bfy9db81a3a25878e4f@mail.gmail.com>
In-Reply-To
<alpine.DEB.1.00.0908161907580.8306@pacific.mpi-cbg.de>

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
Previous: Scott Chacon
Message 4 of 4 in “bbchop & Wikipedia's Bayesian search theory page”
  1. Johannes SchindelinAug 16, 2009
  2. GitHub linking, was Re: bbchop & Wikipedia's Bayesian search theory pageJohannes Schindelin, Aug 16, 2009
  3. Scott ChaconAug 16, 2009
  4. Ealdwulf WuffingaAug 17, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.