Entropy Semiring Forward-backward Algorithm for HMM Entropy Computation

Autor:	Ilic, Velimir M.
Rok vydání:	2011
Předmět:	Computer Science - Information Theory
Druh dokumentu:	Working Paper
Popis:	The paper presents Entropy Semiring Forwardbackward algorithm (ESRFB) and its application for memory efficient computation of the subsequence constrained entropy and state sequence entropy of a Hidden Markov Model (HMM) when an observation sequence is given. ESRFB is based on forward-backward recursion over the entropy semiring, having the lower memory requirement than the algorithm developed by Mann and MacCallum, with the same time complexity. Furthermore, when it is used with forward pass only, it is applicable for the computation of HMM entropy for a given observation sequence, with the same time and memory complexity as the previously developed algorithm by Hernando et al Comment: submitted to Transactions on Advanced Research
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1108.0347 Zobrazit plný text záznamu View this record from Arxiv