1

I am implementing the Naive Bayes method with Gaussian distribution.

The problem that I have is that the variance used on the Gaussian curve (calculated from a training set) is REALLY small. They are on the order of e-07. That means the whole equation,

(1/:math.sqrt(2*:math.pi*:math.sqrt(variance))) *
:math.exp(-0.5*(:math.pow(elem - mean, 2) / variance))

results in really high values (such as 500, or even more). That becomes a problem later, when I multiply every probability p(x|C) together (it is a vector of 256 features).

I heard that is possible to use logarithms to avoid these kind of numbers. I searched on google but didn't find anything related to the subject. Does anyone know about that?

5

Working with log-probabilities helps with the problem of intermediate values overflowing (and underflowing). Instead of calculating L = P(x1|C)P(x2|C)..., you calculate log L = log P(x1|C) + log P(x2|C) + .... You can do two things with log L:

  1. If you're trying to maximize likelihood, you can directly maximize log-likelihood instead since log is monotonic and increasing.

  2. If you want a normalized probability L/Z in [0,1], you can calculate this as exp(log L - log Z), which is possible even if L and Z are too large to fit in your floating point type.

In my experience this trick is often necessary when implementing probabilistic graphical models.

2

Your problem is likely a typo: you calculate 1 / sqrt(2 * pi * sqrt(variance)), while the formula expectedly has 1 / sqrt(2 * pi * variance**2). (Square root from variance taken twice is highly unlikely in a normalizing factor.)

While we're at it, I don't think rounding errors have anythig to do with your formula's problem.

With usable range of a 64-bit floating point number being around 1e+308, I'd not call 1e-7 "really small". Even if you use 32-bit floats (with range around 1e+38), things are not that bad.

Common sources of rounding errors is operations with wildly different magnitudes: 1e+15 + 0.2 gives you a number which is suddenly 1000000000000000.25. Also, sqrt, exp, and pow are complex computations that remove some of the precision. I bet pow(x, 2) differs slightly form x * x for many values of x.

Obviously, log(a * b) = log(a) + log(b), and exp(a + b) = exp(a) * exp(b). I don't see, though, how this could help your case: calculating exp twice will introduce more error than calculating it once.

  • thanks for the answer, I corrected the formula. The problem with 1e-7 is that on the formula, 1/ (...1e-7) gives me back a big result. And after that I will have to multiply that result about 256 times with other similar results. That gives me back an arithmetic error: :erlang.*(417.62100246853674, 6.504406716503509e307). – lhahn May 24 '15 at 17:57
  • Where do you need to multiyply 256 such results (basically raising it to 256th power)? What it the formula? That formula can be rewritten differently to avoid out-of-range resuts. – 9000 May 24 '15 at 18:21
0

Your problem is floating-point number formats. They're basically stored as Sign*Man*2^Exp. For 32 bits floating point types, there's only 9 bits of exponent available, and even 64 bits FP uses a mere 11 bits.

But once you take the log of that value, you're effectively user the far large magnitude field to store your original exponent.

There's also another alternative. Roll your own FP format, of the form 2^(-Exp/4294967296). operator+ is quite imprecise for this type, but operator* is just a mater of adding (integral) exponents and pow is a multiplication of exponents.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.