1

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.

Howie
  • 111

1 Answers1

2

  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.

ˈjuː.zɚ79365
  • 3,004
  • Unfortunately my values in a are varying too much for the 1st options, and the 2nd option doesn't produce the same results. I feel I should instead normalize my vector... – Howie May 30 '13 at 12:14
  • @Howie Then you should not mark my answer as accepted. An accepted answer means it helped you solve the problem.... I thought that the second version should have the same effect as rescaling of vectors. – ˈjuː.zɚ79365 May 30 '13 at 12:20
  • Oops, I've made a mistake in implementing the 2nd option. It works fine now. The values in a are rising every quickly, though... I'm starting to think, I might have other bugs in my code. I will leave your answer as accepted, as it did actually answer the question. – Howie May 30 '13 at 12:31