Reworking an equation to overcome arithmetic overflow

Question

I am implementing the Maximum Entropy Markov Model (MEMM) algorithm by following Collins' notes: http://www.cs.columbia.edu/~mcollins/loglinear.pdf

The problematic term (see p. 18): $\ln\sum_y\exp(\vec v \cdot f(x^{(i)},y))$ (Although not explicitly mentioned, I'm assuming the natural logarithm is used, since Collins uses $e$ everywhere.)

I'm having problems because the dot product returns a high number which, when exponentiated, causes an arithmetic overflow. I would need to somehow rework the equation so that the numbers wouldn't be too high.

Any suggestions? Does this kind of thing has a name?

EDIT: The reasoning behind exponentiating the dot product is to produce positive numbers.

Answer 1

1. The paper has a bunch of formulas that look like $$\frac{\exp(a)}{\sum \exp(a_i)}$$ These can be rewritten as $$\frac{1}{\sum \exp(a_i-a)}$$ Since all the terms are positive, if one of them overflows, you know that the fraction (conditional probability) is practically zero.

2. Also, you can try to put $\exp(0.01 x)$ instead of $\exp(x)$ and $100\ln$ instead of $\ln$. This has the effect of changing the base from $e$ to $e^{0.01}$ everywhere. The formulas should remain valid as long as they don't depend on the calculus properties of $e$ such as $(e^x)'=e^x$. Naturally, $0.01$ could be another small number.