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

Re: Generalised bisection

From
STSteven Tweed <orthochronous@gmail.com>
Date
Mar 13, 2009, 15:19 UTC
Message-ID
<d9c1caea0903130819u770686b1w867f074ffef8fabf@mail.gmail.com>
In-Reply-To
<efe2b6d70903130549m63ae9bdeg1cd3f24a43b3e66f@mail.gmail.com>

On Fri, Mar 13, 2009 at 12:49 PM, Ealdwulf Wuffinga <ealdwulf@googlemail.com> wrote:

Show 14 quoted lines
> On Thu, Mar 12, 2009 at 6:02 PM, Steven Tweed <orthochronous@gmail.com> wrote:
>> I haven't even looked at the source code so a description of the
>> mathematical algorithm would help, but I'll just point out that
>> underflow (in the case of working with probabilities) and overflow
>> (when working with their negated logarithms) is inherent in most
>> multi-step Bayesian algorithms. The only solution is to rescale things
>> as you go so that things stay in a "computable" range. (You're almost
>> never interested in absolute probabilities anyway but rather relative
>> probabilities or, in extreme cases, just the biggest probability, so
>> rescaling isn't losing any useful information.)
>
> Are you sure you aren't thinking of when you are using fixed point? I
> was under the impression
> that Bayesian algorithms usually worked okay in floating point.

Underflow when using probabilities and lack of precision (rather than overflow) when using negated logarithms are well known problems in the kind of probabilistic object tracking, inference in graphical networks and object identification processes I work with (in computer vision). I there may well be other areas of Bayesian decision theory where this doesn't happen, and indeed a _very_ quick scan through your document suggests that you're adding to tallying information on each timestep and recalcuating the entire model from those tallys, which is one of the few cases where you can't really do rescaling. I'll try and have a more detailled read over the weekend.

> One issue in BBChop which should be easy to fix, is that I use a dumb
> way of calculating Beta functions. These
> are ratios of factorials, so the subexpressions get stupidly big very
> quickly. But I don't think that is the only problem.

Yes, "Numerical Recipes" seems to suggest that computing with log-factorials and exponentiating works reasonably, although I've never tried it and NR does occasionally get things completely wrong...

Previous: Ealdwulf WuffingaNext: Ealdwulf Wuffinga
Message 16 of 25 in “Generalised bisection”
  1. Ealdwulf WuffingaMar 9, 2009
  2. Christian CouderMar 10, 2009
  3. Ealdwulf WuffingaMar 11, 2009
  4. John TapsellMar 11, 2009
  5. Johannes SchindelinMar 11, 2009
  6. John TapsellMar 11, 2009
  7. Johannes SchindelinMar 11, 2009
  8. John TapsellMar 11, 2009
  9. Ealdwulf WuffingaMar 11, 2009
  10. Ealdwulf WuffingaMar 11, 2009
  11. John TapsellMar 12, 2009
  12. Johannes SchindelinMar 12, 2009
  13. Steven TweedMar 12, 2009
  14. Ealdwulf WuffingaMar 13, 2009
  15. Ealdwulf WuffingaMar 13, 2009
  16. Steven TweedMar 13, 2009
  17. Ealdwulf WuffingaMar 15, 2009
  18. Steven TweedMar 16, 2009
  19. John TapsellMar 16, 2009
  20. Ealdwulf WuffingaMar 16, 2009
  21. Ealdwulf WuffingaMar 16, 2009
  22. Ealdwulf WuffingaMar 13, 2009
  23. Johannes SchindelinMar 13, 2009
  24. John TapsellMar 13, 2009
  25. Johannes SchindelinMar 13, 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.