ANN: logfloat 0.13.3
Henning Thielemann
lemming at henning-thielemann.de
Tue Apr 7 09:48:20 UTC 2015
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.
More information about the Libraries
mailing list