Two suggestions:
1. When working with scores (such as K2) always keep log of the numbers you
care about. The K2 score is multiplicative, so all operations reduce to
additions of logarithmic representation.
2. To compute factorials and such, use the gamma function. This is
implemented in most numerical libraries (for example standard "C" math
library has the function lgamma() that computes log of gamma). This is
usually a more refined version of Stirlings approximation, and in most
implementations optimized quite a bit. Then you use the identity n! =
Gamma(n+1).
Hope this helps,
- -Nir
> -----Original Message-----
> From: owner-uai@cs.orst.edu [mailto:owner-uai@cs.orst.edu]On Behalf Of
> Daniel Upper
> Sent: Tuesday, May 22, 2001 12:58 PM
> To: uai@cs.orst.edu
> Subject: Re: [UAI] K2 learning
>
>
> 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 - 13:32:48 PDT