bbchop & Wikipedia's Bayesian search theory page

Hi,

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.

Anybody know where I can find information about Bayesian search theory that is not deleted by people envious of other people's brains?

Thanks, Dscho

P.S.: yes, I am disappointed. "Wisdom of the crowds"? Not with this type of human beings in control of articles other people wrote.

Hi,

On Sun, 16 Aug 2009, Johannes Schindelin wrote:

Ah, never mind, it seems that they did not delete _this_ page (it would have been the third I looked for this week which got deleted and made extra hard to find a copy of).

The problem, really, is that the link on the bbchop GitHub site is wrong:

	http://github.com/Ealdwulf/bbchop/tree/master

The issue is that the link incorrectly includes the closing parenthesis. It should link to

	http://en.wikipedia.org/wiki/Bayesian_search_theory

not

	http://en.wikipedia.org/wiki/Bayesian_search_theory)

Scott, is it possible to fix that? Or is the README not magically made from the README in the repository (which does not contain HTML markup)?

Ciao, Dscho

Hey,

On Sun, Aug 16, 2009 at 10:18 AM, Johannes Schindelin<Johannes.Schindelin@gmx.de> wrote:

If they change the README to have spaces between the url and the
parens, it will link properly - I'll file a bug for the linking issue.
 Thanks.

Scott

On Sun, Aug 16, 2009 at 6:13 PM, Johannes Schindelin<Johannes.Schindelin@gmx.de> wrote:

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