Re: Generalised bisection

On Fri, Mar 13, 2009 at 12:49 PM, Ealdwulf Wuffinga
[off-list ref] wrote:

On Thu, Mar 12, 2009 at 6:02 PM, Steven Tweed [off-list ref] wrote:

quoted

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...