Re: Generalised bisection

[Steven Tweed <orthochronous@gmail.com>]

On Fri, Mar 13, 2009 at 12:49 PM, Ealdwulf Wuffinga
<ealdwulf@googlemail.com> wrote:
> 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...