I don't have experience with the K2 algorithm, but in the past I've been
able to work around overflow (and underflow) prolems by doing some of the
arithmetic with logs. If you're just multiplying and dividing you can do
it all with logs. (Stirling's formula may save you some CPU time, too: n!
is approximately (n**n)/(e**n), so ln n! is about n*ln n - n).
If you need to do add these factorials, you can represent each number using
two doubles, a scaled version of the original and a log of the scaling
factor (i.e. a mantissa and an exponent). To do addition, use the same
scaling factor for all the addends (e.g. the largest of them) and just add
the mantissas.
Dan Upper
> Hi all,
>
> I'm using the K2 algorithm (Cooper & Herskovitz, 1992) to learn a bayesian
> model from data. The point is that in this algorithm I need to compute the
> fatorial of Nijk (the number of cases in which a variable xi has the value
> vik, and the parent of x is instantiated as wij). When the number of cases
> (in the database) is big, I can't compute this fatorial.
> I was wondering if anybody have already faced this problem and have any
> sugestion.
>
> Thank you in advance,
>
> Estevam.
>
> - -_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
> Estevam Rafael Hruschka Junior
> Curitiba - PR - Brazil
> e-mail: estevamr@terra.com.br
>
This archive was generated by hypermail 2b29 : Tue May 22 2001 - 09:59:07 PDT