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