{"thread":{"id":"18223","subject":"Generalised bisection","startedAt":"2009-03-09T01:40:08Z","lastAt":"2009-03-16T22:47:09Z","messageCount":25,"participants":["Ealdwulf Wuffinga","Christian Couder","John Tapsell","Johannes Schindelin","Steven Tweed"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"107429","messageId":"efe2b6d70903081840v18e77aa7w2dac2bed553d0d6a@mail.gmail.com","threadId":"18223","inReplyTo":null,"subject":"Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-09T01:40:08Z","receivedAt":"2009-03-09T01:40:08Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"[whoops, mail server does not like html. trying again...]\n\nHi,\n\nI have developed a generalised bisection algorithm, for the case where\na bug is intermittent. The code may be found at\ngit://github.com/Ealdwulf/bbchop.git. It should be considered\nexperimental.\n\nThis should cover the use cases requested by Ingo\n(http://article.gmane.org/gmane.comp.version-control.git/108565) and\nJohn  (http://article.gmane.org/gmane.comp.version-control.git/112280),\nalthough it does not work in the same way as your proposed solutions -\nit is intended to be more general, working when the bug is not\nalmost-deterministic. It is based on Bayesian Search Theory\n(http://en.wikipedia.org/wiki/Bayesian_search_theory, although that\ndescription is a bit simplistic) which is usually used to find\nsubmarines, or people lost on mountains.\n\nTo try it out, you need python and mpmath (from\nhttp://code.google.com/p/mpmath/ or your distribution).\nOnce your have obtained the source, you can immediately run BBChop/source/bbchop\nwhich is the main driver program.\n\nIt is not currently integrated into git, although doing so should only\ninvolve minor scriptery.\n\nThe simplest way to try it out to is run it in manual mode:\n\n\n>   bbchop -l 10 -c 0.9\n\nThis means, search in a linear history of 10 revisions, numbered 0 to\n9, until bbchop thinks it has found\nthe faulty location with probability at least 0.9. It will start\nasking questions:\n\n] Most likely location is 0 (probability 0.100000).\n] Please test at location 3.\n] Target detected at 3? Y/N/S(kip)\n\nEventually the search will terminate and BBChop will print out its\nconclusion, with evidence, eg:\n\n] Search complete.  Most likely location is 3 (probability 0.919614).\n] Number of tests at 3: 3 of which 1 detected\n] Number of tests at parents of 3:\n]         At 2, 5 of which 0 detected\n\nMore information canbe found in the readme file.\n\nFeel free to reply with any comments, questions, etc. If anyone tries\nit out on a real bug, please let me know how it goes.\n\nregards,\n\nEaldwulf\n"},{"id":"107546","messageId":"200903100808.15875.chriscool@tuxfamily.org","threadId":"18223","inReplyTo":"efe2b6d70903081840v18e77aa7w2dac2bed553d0d6a@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-03-10T07:08:15Z","receivedAt":"2009-03-10T07:08:15Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Le lundi 9 mars 2009, Ealdwulf Wuffinga a écrit :\n> [whoops, mail server does not like html. trying again...]\n>\n> Hi,\n>\n> I have developed a generalised bisection algorithm, for the case where\n> a bug is intermittent. The code may be found at\n> git://github.com/Ealdwulf/bbchop.git. It should be considered\n> experimental.\n\nI will try to have a look at the end of this week.\nBut do you want it to be integrated with Git or do you want it to be an \nindependant project that works with many different version control system?\n\nBest regards,\nChristian.\n"},{"id":"107655","messageId":"efe2b6d70903110159h78de744yc141effaf5aa0821@mail.gmail.com","threadId":"18223","inReplyTo":"200903100808.15875.chriscool@tuxfamily.org","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-11T08:59:58Z","receivedAt":"2009-03-11T08:59:58Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Tue, Mar 10, 2009 at 7:08 AM, Christian Couder\n wrote:\n\n> I will try to have a look at the end of this week.\n> But do you want it to be integrated with Git or do you want it to be an\n> independant project that works with many different version control system?\n\nHmm. Whatever works, I guess. On the one hand the code does seem\nnaturally generic. On the other hand, it's good if users don't\nhave to separately obtain an extra package to use it. Supposing that\nthe algorithm proves useful, would the git project be okay with an\nextra dependency, or would you want to integrate it? Right now it's in\npython, which I understand is an obstacle to integration.\n\nIn the short term, I assume the algorithm needs to prove its\nusefulness before either being integrated or added as a dependency.\nIt seems the majority of potential users - developers of code of the\nsort likely to have intermittent bugs, such as the kernel or xorg -\nuse git,\nso I would like it to be as easy as possible for git users to try it\nout. Maybe it could live in the contrib directory for a while?\n\nEaldwulf\n"},{"id":"107660","messageId":"43d8ce650903110235q5e2a59f6t201d5e65a4937476@mail.gmail.com","threadId":"18223","inReplyTo":"efe2b6d70903110159h78de744yc141effaf5aa0821@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-03-11T09:35:37Z","receivedAt":"2009-03-11T09:35:37Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/3/11 Ealdwulf Wuffinga :\n> On Tue, Mar 10, 2009 at 7:08 AM, Christian Couder\n> wrote:\n>\n>> I will try to have a look at the end of this week.\n>> But do you want it to be integrated with Git or do you want it to be an\n>> independant project that works with many different version control system?\n>\n> Hmm. Whatever works, I guess. On the one hand the code does seem\n> naturally generic. On the other hand, it's good if users don't\n> have to separately obtain an extra package to use it. Supposing that\n> the algorithm proves useful, would the git project  be okay with an\n> extra dependency, or would you want to integrate it? Right now it's in\n> python, which I understand is an obstacle to integration.\n\nThere used to be a dependency on python. git-merge-recursive for\nexample, before it was converted to C.\n\nmpmath might be the more annoying dependency - what functions do you\nuse from it? Could they trivially be reimplemented?\n\nJohn Tapsell\n"},{"id":"107677","messageId":"alpine.DEB.1.00.0903111304520.10279@pacific.mpi-cbg.de","threadId":"18223","inReplyTo":"43d8ce650903110235q5e2a59f6t201d5e65a4937476@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-03-11T12:05:48Z","receivedAt":"2009-03-11T12:05:48Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 11 Mar 2009, John Tapsell wrote:\n\n> 2009/3/11 Ealdwulf Wuffinga :\n> > On Tue, Mar 10, 2009 at 7:08 AM, Christian Couder\n> > wrote:\n> >\n> >> I will try to have a look at the end of this week.\n> >> But do you want it to be integrated with Git or do you want it to be an\n> >> independant project that works with many different version control system?\n> >\n> > Hmm. Whatever works, I guess. On the one hand the code does seem\n> > naturally generic. On the other hand, it's good if users don't\n> > have to separately obtain an extra package to use it. Supposing that\n> > the algorithm proves useful, would the git project  be okay with an\n> > extra dependency, or would you want to integrate it? Right now it's in\n> > python, which I understand is an obstacle to integration.\n> \n> There used to be a dependency on python. git-merge-recursive for\n> example, before it was converted to C.\n\nNot \"for example\". It was the only dependency of git.git on Python, and \nthe rewrite of merge-recursive was only done to break that dependency, as \nI had a platform where I could not install Python.\n\nCiao,\nDscho\n"},{"id":"107679","messageId":"43d8ce650903110508o3d12f32m8202fae750d215a@mail.gmail.com","threadId":"18223","inReplyTo":"alpine.DEB.1.00.0903111304520.10279@pacific.mpi-cbg.de","subject":"Re: Generalised bisection","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-03-11T12:08:10Z","receivedAt":"2009-03-11T12:08:10Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/3/11 Johannes Schindelin :\n> Hi,\n>\n> On Wed, 11 Mar 2009, John Tapsell wrote:\n>\n>> 2009/3/11 Ealdwulf Wuffinga :\n>> > On Tue, Mar 10, 2009 at 7:08 AM, Christian Couder\n>> > wrote:\n>> >\n>> >> I will try to have a look at the end of this week.\n>> >> But do you want it to be integrated with Git or do you want it to be an\n>> >> independant project that works with many different version control system?\n>> >\n>> > Hmm. Whatever works, I guess. On the one hand the code does seem\n>> > naturally generic. On the other hand, it's good if users don't\n>> > have to separately obtain an extra package to use it. Supposing that\n>> > the algorithm proves useful, would the git project  be okay with an\n>> > extra dependency, or would you want to integrate it? Right now it's in\n>> > python, which I understand is an obstacle to integration.\n>>\n>> There used to be a dependency on python.  git-merge-recursive for\n>> example, before it was converted to C.\n>\n> Not \"for example\".  It was the only dependency of git.git on Python, and\n> the rewrite of merge-recursive was only done to break that dependency, as\n> I had a platform where I could not install Python.\n\nBut installing perl was no problem? (Just curious)\n\nJohn\n"},{"id":"107686","messageId":"alpine.DEB.1.00.0903111358260.10498@intel-tinevez-2-302","threadId":"18223","inReplyTo":"43d8ce650903110508o3d12f32m8202fae750d215a@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-03-11T13:04:08Z","receivedAt":"2009-03-11T13:04:08Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 11 Mar 2009, John Tapsell wrote:\n\n> 2009/3/11 Johannes Schindelin :\n>\n> > On Wed, 11 Mar 2009, John Tapsell wrote:\n> >\n> >> There used to be a dependency on python.  git-merge-recursive for \n> >> example, before it was converted to C.\n> >\n> > Not \"for example\".  It was the only dependency of git.git on Python, \n> > and the rewrite of merge-recursive was only done to break that \n> > dependency, as I had a platform where I could not install Python.\n> \n> But installing perl was no problem? (Just curious)\n\nPerl was installed, albeit in an ancient version, and compiling Perl \nmodules written in C was out. It just did not work.\n\nBut the good part was: after converting rerere to be a builtin, there \nwere no Perl scripts left that I wanted/needed to use.\n\nThese days, we only have these Perl scripts left: add--interactive, \narchimport, cvsexportcommit, cvsimport, cvsserver, relink, send-email and \nsvn.\n\nIgnoring the scripts to interact with other SCMs (which I can do on \nanother computer), that leaves add--interactive, relink (which could be \nmoved to contrib/ AFAIAC) and send-email.\n\nI use \"add -e\" instead of \"add -i\", and stay away from send-email...\n\nCiao,\nDscho\n"},{"id":"107688","messageId":"43d8ce650903110624t47e37b19n3fc72e3243978200@mail.gmail.com","threadId":"18223","inReplyTo":"alpine.DEB.1.00.0903111358260.10498@intel-tinevez-2-302","subject":"Re: Generalised bisection","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-03-11T13:24:09Z","receivedAt":"2009-03-11T13:24:09Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/3/11 Johannes Schindelin :\n> Hi,\n>\n> On Wed, 11 Mar 2009, John Tapsell wrote:\n>\n>> 2009/3/11 Johannes Schindelin :\n>>\n>> > On Wed, 11 Mar 2009, John Tapsell wrote:\n>> >\n>> >> There used to be a dependency on python.  git-merge-recursive for\n>> >> example, before it was converted to C.\n>> >\n>> > Not \"for example\".  It was the only dependency of git.git on Python,\n>> > and the rewrite of merge-recursive was only done to break that\n>> > dependency, as I had a platform where I could not install Python.\n>>\n>> But installing perl was no problem?  (Just curious)\n>\n> Perl was installed, albeit in an ancient version, and compiling Perl\n> modules written in C was out.  It just did not work.\n\nI wonder if it would then be acceptable to have a python script for\nthis generalised bisect? Since it's not core functionality. Not\nquite sure how it would fit in though (I'd rather it was called from\n\"git bisect\" rather than adding another separate git command)\n\nJohn\n"},{"id":"107743","messageId":"efe2b6d70903111514r2855d910heac71bc0029d2766@mail.gmail.com","threadId":"18223","inReplyTo":"43d8ce650903110624t47e37b19n3fc72e3243978200@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-11T22:14:28Z","receivedAt":"2009-03-11T22:14:28Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"[John will get this twice, sorry]\n\nOn Wed, Mar 11, 2009 at 1:24 PM, John Tapsell wrote:\n\n>   Not\n> quite sure how it would fit in though (I'd rather it was called from\n> \"git bisect\" rather than adding another separate git command)\n\nI guess the most obvious route would be to add an option to 'git bisect start'\n to specify that it should be used instead of the usual algorithm.\n\nEaldwulf\n"},{"id":"107744","messageId":"efe2b6d70903111515p2b9f656bp186d0b3cc7ae483d@mail.gmail.com","threadId":"18223","inReplyTo":"43d8ce650903110235q5e2a59f6t201d5e65a4937476@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-11T22:15:59Z","receivedAt":"2009-03-11T22:15:59Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"[John will get this twice, sorry; not used to this mail interface yet.]\n\nOn Wed, Mar 11, 2009 at 9:35 AM, John Tapsell wrote:\n\n> mpmath might be the more annoying dependency - what functions do you\n> use from it?  Could they trivially be reimplemented?\n\nWhat I use is the multiprecision floating point number class. doubles\ndon't seem to be long enough.\nThe reason for using mpmath rather than the more widespread GMP (and\nits python wrapper gmpy) is that the latter only supports\ninteger powers, whereas BBChop needs fractional powers.\n\nSo, it might be possible to switch to gmpy, or some other widespread\nlibrary, by implementing a pow() which supports fractional powers.\nI think I only use the normal arithmetic operators, log, and pow, so\nin principle those could be reimplemented, to eliminate the dependency\naltogether.\nIt seems a little bit of a waste of time, though.\n\nEaldwulf\n"},{"id":"107765","messageId":"43d8ce650903112345x3d40b70ap7e4c0f8c7d0b6069@mail.gmail.com","threadId":"18223","inReplyTo":"efe2b6d70903111515p2b9f656bp186d0b3cc7ae483d@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-03-12T06:45:43Z","receivedAt":"2009-03-12T06:45:43Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/3/11 Ealdwulf Wuffinga :\n> [John will get this twice, sorry; not used to this mail interface yet.]\n>\n> On Wed, Mar 11, 2009 at 9:35 AM, John Tapsell wrote:\n>\n>> mpmath might be the more annoying dependency - what functions do you\n>> use from it?  Could they trivially be reimplemented?\n>\n> What I use is the multiprecision floating point number class. doubles\n> don't seem to be long enough.\n\nHmm, really really? Sometimes this sort of thing can be fixed by just\nreadjusting the formulas. What formulas are you using that require\nmore precision than doubles?\n\n> The reason for using mpmath rather than the more  widespread GMP (and\n> its python wrapper gmpy) is that the latter only supports\n> integer powers, whereas BBChop needs fractional powers.\n>\n> So, it might be possible to switch to gmpy,  or some other widespread\n> library,  by implementing a pow() which supports fractional powers.\n> I think I only use the normal arithmetic operators, log, and pow, so\n> in principle those could be reimplemented, to eliminate the dependency\n> altogether.\n> It seems a little bit of a waste of time, though.\n\nA little bit of math trickery helps here :-)\n\ny = x^b\n\nlog(y) = log(x^b) = b * log(x)\ne^log(y) = e^(b log(x))\n\ny = exp(b * log(x))\n\nSo as long as you have 'exp' and 'log' functions, you can raise x to\nthe power of b, even if b is fractional.\n\nJust to prove it, square root of 2 is:\n\n$ echo \"e(0.5*l(2))\" | bc -l\n1.41421356237309504878\n\nJohn\n"},{"id":"107801","messageId":"alpine.DEB.1.00.0903121154560.10279@pacific.mpi-cbg.de","threadId":"18223","inReplyTo":"43d8ce650903112345x3d40b70ap7e4c0f8c7d0b6069@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-03-12T10:55:26Z","receivedAt":"2009-03-12T10:55:26Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 12 Mar 2009, John Tapsell wrote:\n\n> 2009/3/11 Ealdwulf Wuffinga :\n> > [John will get this twice, sorry; not used to this mail interface yet.]\n> >\n> > On Wed, Mar 11, 2009 at 9:35 AM, John Tapsell wrote:\n> >\n> >> mpmath might be the more annoying dependency - what functions do you\n> >> use from it?  Could they trivially be reimplemented?\n> >\n> > What I use is the multiprecision floating point number class. doubles\n> > don't seem to be long enough.\n> \n> Hmm, really really? Sometimes this sort of thing can be fixed by just \n> readjusting the formulas. What formulas are you using that require more \n> precision than doubles?\n\nMaybe you could post the formulae instead of forcing people to deduct them \nfrom the source code?\n\nThanks,\nDscho"},{"id":"107858","messageId":"d9c1caea0903121102y5452603fua0e7a1b82e121b01@mail.gmail.com","threadId":"18223","inReplyTo":"alpine.DEB.1.00.0903121154560.10279@pacific.mpi-cbg.de","subject":"Re: Generalised bisection","fromName":"Steven Tweed","fromEmail":"orthochronous@gmail.com","sentAt":"2009-03-12T18:02:37Z","receivedAt":"2009-03-12T18:02:37Z","isPatch":false,"sender":{"key":"orthochronous@gmail.com","avatar":null},"body":"On Thu, Mar 12, 2009 at 10:55 AM, Johannes Schindelin\n wrote:\n> On Thu, 12 Mar 2009, John Tapsell wrote:\n> > 2009/3/11 Ealdwulf Wuffinga :\n> > > What I use is the multiprecision floating point number class. doubles\n> > > don't seem to be long enough.\n> >\n> > Hmm, really really?  Sometimes this sort of thing can be fixed by just\n> > readjusting the formulas.  What formulas are you using that require more\n> > precision than doubles?\n>\n> Maybe you could post the formulae instead of forcing people to deduct them\n> from the source code?\n\nI haven't even looked at the source code so a description of the\nmathematical algorithm would help, but I'll just point out that\nunderflow (in the case of working with probabilities) and overflow\n(when working with their negated logarithms) is inherent in most\nmulti-step Bayesian algorithms. The only solution is to rescale things\nas you go so that things stay in a \"computable\" range. (You're almost\nnever interested in absolute probabilities anyway but rather relative\nprobabilities or, in extreme cases, just the biggest probability, so\nrescaling isn't losing any useful information.)\n\ncheers,\ndave tweed\n"},{"id":"107921","messageId":"efe2b6d70903130258t2594b027m5812e9a5895f477e@mail.gmail.com","threadId":"18223","inReplyTo":"43d8ce650903112345x3d40b70ap7e4c0f8c7d0b6069@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-13T09:58:46Z","receivedAt":"2009-03-13T09:58:46Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Thu, Mar 12, 2009 at 6:45 AM, John Tapsell wrote:\n> 2009/3/11 Ealdwulf Wuffinga :\n>> On Wed, Mar 11, 2009 at 9:35 AM, John Tapsell wrote:\n>> What I use is the multiprecision floating point number class. doubles\n>> don't seem to be long enough.\n>\n> Hmm, really really?  Sometimes this sort of thing can be fixed by just\n> readjusting the formulas.  What formulas are you using that require\n> more precision than doubles?\n\nI'll have to reply to this later when I have more time. However, there\nis a (rather verbose)\nfile in the doc directory which describes them - in texmacs format,\nbut I've just uploaded\na pdf version as well. It is BayesianSearch_Debugging.pdf. The\ndescription of this code starts in\nsection 2.2 (since I wrote that, I have generalised it to the DAG case\nas in git).\n\n\n> A little bit of math trickery helps here :-)\n>\n> y =  x^b\n>\n> log(y) = log(x^b) = b * log(x)\n> e^log(y) = e^(b log(x))\n>\n> y = exp(b * log(x))\n>\n> So as long as you have 'exp' and 'log' functions, you can raise x to\n> the power of b, even if b is fractional.\n\nSadly gmp does not have log or exp. mpfr does, but it does not have a python\ninterface.\n\nAlex\n"},{"id":"107923","messageId":"efe2b6d70903130300q4ea2aa99q7e956d3bcbcfec4c@mail.gmail.com","threadId":"18223","inReplyTo":"d9c1caea0903121102y5452603fua0e7a1b82e121b01@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-13T10:00:53Z","receivedAt":"2009-03-13T10:00:53Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Thu, Mar 12, 2009 at 6:02 PM, Steven Tweed wrote:\n\n> I haven't even looked at the source code so a description of the\n> mathematical algorithm would help, but I'll just point out that\n> underflow (in the case of working with probabilities) and overflow\n> (when working with their negated logarithms) is inherent in most\n> multi-step Bayesian algorithms. The only solution is to rescale things\n> as you go so that things stay in a \"computable\" range. (You're almost\n> never interested in absolute probabilities anyway but rather relative\n> probabilities or, in extreme cases, just the biggest probability, so\n> rescaling isn't losing any useful information.)\n\nHmm, I'll have to think about that one.\n\nEaldwulf\n"},{"id":"107929","messageId":"alpine.DEB.1.00.0903131154190.10279@pacific.mpi-cbg.de","threadId":"18223","inReplyTo":"efe2b6d70903130258t2594b027m5812e9a5895f477e@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-03-13T10:55:06Z","receivedAt":"2009-03-13T10:55:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 13 Mar 2009, Ealdwulf Wuffinga wrote:\n\n> It is BayesianSearch_Debugging.pdf.\n\nNow I'll only need a bayesian-search-for-original-url-in-mails.py.\n\nCiao,\nDscho\n"},{"id":"107937","messageId":"43d8ce650903130542o4125fef3rdddea4a31c23aa30@mail.gmail.com","threadId":"18223","inReplyTo":"alpine.DEB.1.00.0903131154190.10279@pacific.mpi-cbg.de","subject":"Re: Generalised bisection","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-03-13T12:42:00Z","receivedAt":"2009-03-13T12:42:00Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/3/13 Johannes Schindelin :\n> Hi,\n>\n> On Fri, 13 Mar 2009, Ealdwulf Wuffinga wrote:\n>\n>> It is BayesianSearch_Debugging.pdf.\n>\n> Now I'll only need a bayesian-search-for-original-url-in-mails.py.\n\nI managed to work it out:\n\nhttp://github.com/Ealdwulf/bbchop.git/BBChop/doc/BayesianSearch_Debugging.pdf\n\nJohn\n"},{"id":"107939","messageId":"efe2b6d70903130549m63ae9bdeg1cd3f24a43b3e66f@mail.gmail.com","threadId":"18223","inReplyTo":"d9c1caea0903121102y5452603fua0e7a1b82e121b01@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-13T12:49:41Z","receivedAt":"2009-03-13T12:49:41Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Thu, Mar 12, 2009 at 6:02 PM, Steven Tweed wrote:\n\n> I haven't even looked at the source code so a description of the\n> mathematical algorithm would help, but I'll just point out that\n> underflow (in the case of working with probabilities) and overflow\n> (when working with their negated logarithms) is inherent in most\n> multi-step Bayesian algorithms. The only solution is to rescale things\n> as you go so that things stay in a \"computable\" range. (You're almost\n> never interested in absolute probabilities anyway but rather relative\n> probabilities or, in extreme cases, just the biggest probability, so\n> rescaling isn't losing any useful information.)\n\nAre you sure you aren't thinking of when you are using fixed point? I\nwas under the impression\nthat Bayesian algorithms usually worked okay in floating point.\n\nOne issue in BBChop which should be easy to fix, is that I use a dumb\nway of calculating Beta functions. These\nare ratios of factorials, so the subexpressions get stupidly big very\nquickly. But I don't think that is the only problem.\n\n\nEaldwulf\n"},{"id":"107948","messageId":"alpine.DEB.1.00.0903131455530.6288@intel-tinevez-2-302","threadId":"18223","inReplyTo":"43d8ce650903130542o4125fef3rdddea4a31c23aa30@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-03-13T13:56:04Z","receivedAt":"2009-03-13T13:56:04Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 13 Mar 2009, John Tapsell wrote:\n\n> 2009/3/13 Johannes Schindelin :\n>\n> > On Fri, 13 Mar 2009, Ealdwulf Wuffinga wrote:\n> >\n> >> It is BayesianSearch_Debugging.pdf.\n> >\n> > Now I'll only need a bayesian-search-for-original-url-in-mails.py.\n> \n> I managed to work it out:\n> \n> http://github.com/Ealdwulf/bbchop.git/BBChop/doc/BayesianSearch_Debugging.pdf\n\nThanks, very much appreciated,\nDscho\n"},{"id":"107956","messageId":"d9c1caea0903130819u770686b1w867f074ffef8fabf@mail.gmail.com","threadId":"18223","inReplyTo":"efe2b6d70903130549m63ae9bdeg1cd3f24a43b3e66f@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Steven Tweed","fromEmail":"orthochronous@gmail.com","sentAt":"2009-03-13T15:19:38Z","receivedAt":"2009-03-13T15:19:38Z","isPatch":false,"sender":{"key":"orthochronous@gmail.com","avatar":null},"body":"On Fri, Mar 13, 2009 at 12:49 PM, Ealdwulf Wuffinga\n wrote:\n> On Thu, Mar 12, 2009 at 6:02 PM, Steven Tweed wrote:\n>> I haven't even looked at the source code so a description of the\n>> mathematical algorithm would help, but I'll just point out that\n>> underflow (in the case of working with probabilities) and overflow\n>> (when working with their negated logarithms) is inherent in most\n>> multi-step Bayesian algorithms. The only solution is to rescale things\n>> as you go so that things stay in a \"computable\" range. (You're almost\n>> never interested in absolute probabilities anyway but rather relative\n>> probabilities or, in extreme cases, just the biggest probability, so\n>> rescaling isn't losing any useful information.)\n>\n> Are you sure you aren't thinking of when you are using fixed point? I\n> was under the impression\n> that Bayesian algorithms usually worked okay in floating point.\n\nUnderflow when using probabilities and lack of precision (rather than\noverflow) when using negated logarithms are well known problems in the\nkind of probabilistic object tracking, inference in graphical networks\nand object identification processes I work with (in computer vision).\nI there may well be other areas of Bayesian decision theory where this\ndoesn't happen, and indeed a _very_ quick scan through your document\nsuggests that you're adding to tallying information on each timestep\nand recalcuating the entire model from those tallys, which is one of\nthe few cases where you can't really do rescaling. I'll try and have a\nmore detailled read over the weekend.\n\n> One issue in BBChop which should be easy to fix, is that I use a dumb\n> way of calculating Beta functions. These\n> are ratios of factorials, so the subexpressions get stupidly big very\n> quickly. But I don't think that is the only problem.\n\nYes, \"Numerical Recipes\" seems to suggest that computing with\nlog-factorials and exponentiating works reasonably, although I've\nnever tried it and NR does occasionally get things completely wrong...\n"},{"id":"108052","messageId":"efe2b6d70903151216q4a8881e5t797cf5d3bebc5697@mail.gmail.com","threadId":"18223","inReplyTo":"d9c1caea0903130819u770686b1w867f074ffef8fabf@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-15T19:16:16Z","receivedAt":"2009-03-15T19:16:16Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Fri, Mar 13, 2009 at 3:19 PM, Steven Tweed wrote:\n\n> Underflow when using probabilities and lack of precision (rather than\n> overflow) when using negated logarithms are well known problems in the\n> kind of probabilistic object tracking, inference in graphical networks\n> and object identification processes I work with (in computer vision).\n> I there may well be other areas of Bayesian decision theory where this\n> doesn't happen, and indeed a _very_ quick scan through your document\n> suggests that you're adding to tallying information on each timestep\n> and recalcuating the entire model from those tallys, which is one of\n> the few cases where you can't really do rescaling. I'll try and have a\n> more detailled read over the weekend.\n\nThat is useful information, thanks.\n\nIt is not obvious how to perform this algorithm incrementally, because\nof the need to\nmarginalise out the fault rate. As I understand it, marginalisation\nhas to be done after you\nhave incorporated all your information into the model, which means we\ncan't use the\nusual bayesian updating.\n\n> On Fri, Mar 13, 2009 at 12:49 PM, Ealdwulf Wuffinga\n> wrote:\n>> One issue in BBChop which should be easy to fix, is that I use a dumb\n>> way of calculating Beta functions. These\n>> are ratios of factorials, so the subexpressions get stupidly big very\n>> quickly. But I don't think that is the only problem.\n>\n> Yes, \"Numerical Recipes\" seems to suggest that computing with\n> log-factorials and exponentiating works reasonably, although I've\n> never tried it and NR does occasionally get things completely wrong...\n\nI have implemented this and it does indeed allow the program to work\nin more cases\nwithout underflow, with ordinary floating point. However, I think the\nunderflow can still occur\nin plausible use cases.\n\nThe problem is still the Beta function. In bbchop it is always passed\nD and T where D is\nthe sum of the number of detecting observations in some of the\nrevisions, and T is the\nsame for nondetecting observations. Beta(x,y) underflows a python float\nif both x and y are > ~550, and also in other cases when one is\nsmaller and the other,\nlarger. BBChop never looks again at a revision if the bug has been\nobserved there, but if\nthere are a large number of revisions, it might look at enough of them\nto cause a problem.\n\nObviously no-one is going to manually do hundreds of observations, but\n I want BBChop\nto work in the case where someone runs it on a machine in the corner\nfor a few days,\nor even weeks, to track down a bug which occurs too infrequently to\nbisect manually.\n\nWhich means I'm still stuck with mpmath, or some equivalent.\n\nEaldwulf\n"},{"id":"108074","messageId":"d9c1caea0903160329v3c1a1600m9913eafa00cc2f37@mail.gmail.com","threadId":"18223","inReplyTo":"efe2b6d70903151216q4a8881e5t797cf5d3bebc5697@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Steven Tweed","fromEmail":"orthochronous@gmail.com","sentAt":"2009-03-16T10:29:12Z","receivedAt":"2009-03-16T10:29:12Z","isPatch":false,"sender":{"key":"orthochronous@gmail.com","avatar":null},"body":"On Sun, Mar 15, 2009 at 7:16 PM, Ealdwulf Wuffinga\n wrote:\n> On Fri, Mar 13, 2009 at 3:19 PM, Steven Tweed wrote:\n> It is not obvious how to perform this algorithm incrementally, because\n> of the need to\n> marginalise out the fault rate. As I understand it, marginalisation\n> has to be done after you\n> have incorporated all your information into the model, which means we\n> can't use the\n> usual bayesian updating.\n\nI had a look over the weekend, and got a bit sidetracked on one of\nyour assumptions. You seem to be assuming that the bug is such that\nobserving a single positive observation of the symptom at a position i\nin the linear history _does not_ completely rule out that the guilty\ncommit occurs after that point. I would have thought the generally\nmore applicable assumption is that, given that generally you don't\nhave a bug ridden system where more than one bug causes the same\nsymptom _within the history of interest_, that a single observation of\nthe symptom does totally rule out the bug after that point (whilst\nintermittency clearly not having observed the bug before that point\ndoesn't completely rule out the guilty commit being earlier, although\nit should increase the liklihood estimate of the bug being later).\n\nI wonder what your thoughts are on this? (I started formulating a\nmodel over the weekend, but work is a bit hectic so I may not get to\nwrite it up in LaTeX very quickly.)\n"},{"id":"108075","messageId":"43d8ce650903160337p5a48c429nd9efd7f35e66248d@mail.gmail.com","threadId":"18223","inReplyTo":"d9c1caea0903160329v3c1a1600m9913eafa00cc2f37@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"John Tapsell","fromEmail":"johnflux@gmail.com","sentAt":"2009-03-16T10:37:45Z","receivedAt":"2009-03-16T10:37:45Z","isPatch":false,"sender":{"key":"johnflux@gmail.com","avatar":"https://gravatar.com/avatar/25f70d4c0f96396b84a2e34bcd9bdc233462c7b4be29b5fdca8266fc53f30b0c?d=mp&s=160"},"body":"2009/3/16 Steven Tweed :\n> On Sun, Mar 15, 2009 at 7:16 PM, Ealdwulf Wuffinga\n> wrote:\n>> On Fri, Mar 13, 2009 at 3:19 PM, Steven Tweed wrote:\n>> It is not obvious how to perform this algorithm incrementally, because\n>> of the need to\n>> marginalise out the fault rate. As I understand it, marginalisation\n>> has to be done after you\n>> have incorporated all your information into the model, which means we\n>> can't use the\n>> usual bayesian updating.\n>\n> I had a look over the weekend, and got a bit sidetracked on one of\n> your assumptions. You seem to be assuming that the bug is such that\n> observing a single positive observation of the symptom at a position i\n> in the linear history _does not_ completely rule out that the guilty\n> commit occurs after that point. I would have thought the generally\n> more applicable assumption is that, given that generally you don't\n> have a bug ridden system where more than one bug causes the same\n> symptom _within the history of interest_, that a single observation of\n> the symptom does totally rule out the bug after that point (whilst\n> intermittency clearly not having observed the bug before that point\n> doesn't completely rule out the guilty commit being earlier, although\n> it should increase the liklihood estimate of the bug being later).\n\nI think it's reasonable to expect false-positives as well as\nfalse-negatives. e.g. you're looking for a commit that slows down the\nframe rate. But on one of the good commits the hard disk hits a bad\nsector and takes a bit longer to retrieve data and so you get a\nfalse-positive.\n\nIt's a bit contrived, but I'm sure you can think of better example\n\nJohn\n"},{"id":"108148","messageId":"efe2b6d70903161508i19c16f6bm7f695452748a06a1@mail.gmail.com","threadId":"18223","inReplyTo":"d9c1caea0903160329v3c1a1600m9913eafa00cc2f37@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-16T22:08:15Z","receivedAt":"2009-03-16T22:08:15Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Mon, Mar 16, 2009 at 10:29 AM, Steven Tweed wrote:\n\n> I had a look over the weekend, and got a bit sidetracked on one of\n> your assumptions. You seem to be assuming that the bug is such that\n> observing a single positive observation of the symptom at a position i\n> in the linear history _does not_ completely rule out that the guilty\n> commit occurs after that point. I would have thought the generally\n> more applicable assumption is that, given that generally you don't\n> have a bug ridden system where more than one bug causes the same\n> symptom _within the history of interest_, that a single observation of\n> the symptom does totally rule out the bug after that point (whilst\n> intermittency clearly not having observed the bug before that point\n> doesn't completely rule out the guilty commit being earlier, although\n> it should increase the liklihood estimate of the bug being later).\n\nI must have been unclear somewhere, because I do indeed assume that\na single observation of the symptom rules out the origin of the bug being\nlater than that observation.\n\n If you have a play with the software in manual mode, you can see that its\nbehaviour reflects this - it starts out doing something like an\nordinary binary search, albeit skewed towards older revisions (it\nseems to go for\na roughly 1:2 division, rather than the usual 1:1). Then once it has got to the\npoint where a deterministic search would end, it hammers away at the parent(s)\nof the newest revision where the fault was observed, until it is satisfied that\nit cannot be found there. All this just emerges from the generic least-entropy\nalgorithm; I didn't know what it would do until I got it running.\n\n> I wonder what your thoughts are on this? (I started formulating a\n> model over the weekend, but work is a bit hectic so I may not get to\n> write it up in LaTeX very quickly.)\n\nIt will be interesting to see whether your model turns out to be different from\nmine. I'm only doing this in my spare time, so I'm in no hurry.\n\nEaldwulf\n"},{"id":"108157","messageId":"efe2b6d70903161547m4cb8b16co542e2f7bb3afd043@mail.gmail.com","threadId":"18223","inReplyTo":"43d8ce650903160337p5a48c429nd9efd7f35e66248d@mail.gmail.com","subject":"Re: Generalised bisection","fromName":"Ealdwulf Wuffinga","fromEmail":"ealdwulf@googlemail.com","sentAt":"2009-03-16T22:47:09Z","receivedAt":"2009-03-16T22:47:09Z","isPatch":false,"sender":{"key":"ealdwulf@googlemail.com","avatar":null},"body":"On Mon, Mar 16, 2009 at 10:37 AM, John Tapsell wrote:\n\n> I think it's reasonable to expect false-positives as well as\n> false-negatives.  e.g. you're looking for a commit that slows down the\n> frame rate.  But on one of the good commits the hard disk hits a bad\n> sector and takes a bit longer to retrieve data and so you get a\n> false-positive.\n\nIt's true that you could get false positives, as you say. What's less\nobvious to me is whether it would be a good idea for the algorithm to try\nto deal with them, or just report the earliest revision that failed\nand leave it\nup to the intelligence of the user to decide whether it is a false positive,\nand what to do about it.\n\nIn the absence of some user-provided way of discriminating, the only way\nI can see for the algorithm can distinguish between revisions affected by\n the real bug as opposed to ones affected by false positives is to\nassume that\nthe false positives occur at some lower rate. There are two\ndifficulties with this:\nfirst, presumably it would have to start sampling more times at some locations\nin order to figure out what the rate is at them. This sounds like it\nwould be expensive -\ncurrently the algorithm can usually get away with looking at most locations no\nmore than once. Secondly, I'm not sure how to justify this\nassumption, or model it.\nIn short, false positives look like a can of worms to me; I'm hoping\nthe algorithm is\nuseful without considering them.\n\nThe algorithm actually has one potentially problematic assumptions\nalready - or rather,\nit has two alternative assumptions, neither of which is completely believable.\nIt can either assume that the bug causes faults at the same rate in\nall affected revisions,\nor that the affected revisions each have their own completely\nindependent rate. Originally\nI thought that the latter would be the more conservative assumption -\nit certainly assumes less.\nHowever, the following argument convinces me that the other one is\nactually more conservative:\n\nSuppose that in the latest revision, we observe a fault in one run out\nof ten. Under the second\nassumption, this observed rate has no effect on our belief about the\nfault rate in other affected\nrevisions, if any. This means that with a uniform prior on the fault\nrate, we more or less start out\nassuming a fault rate of 50% on any other affected revisions - much\nhigher, implausably so.\n If any of them are only affected at a rate of one in ten, the\nalgorithm is quite likely to terminate without\nseeing a fault there, concluding that the bug was introduced later\nthan it really was.\n\nOn the other hand, we know quite well that the fault rate isn't\nnecessarily going to be\nidentical either. Of the two, I think the assumption of identical\nrates is the more practical one, more\nlikely to actually identify the correct location. It does leave me\nwondering whether some intermediate\nassumption would more accurately represent our experience of fault\nrates, but I haven't thought of a\nreally convincing one.\n\nEaldwulf.\n"}]}