7 Apr
2015
7 Apr
'15
5:48 a.m.
On Mon, 6 Apr 2015, wren romano wrote:
For many models, normalization isn't computationally feasible.
Even for HMMs, when the tag/state space is large, I shudder to think of the overhead. The best cost I can imagine for normalizeFactor is O(log S); thus, increasing the S-dependent factor of the forward/backward algorithm's complexity from O(S^2) to O(S^2*log S). And that's at best; a naive implementation would cost O(S), making the forward/backward algorithm cubic in the size of the tag/state space!
I apply normalization with complexity ~ S after a matrix multiplication with complexity ~ S^2, thus overall complexity remains quadratic per list element.