Entropy Message Passing
arXiv:0906.2895 · doi:10.1109/TIT.2010.2090235
Abstract
The paper proposes a new message passing algorithm for cycle-free factor graphs. The proposed "entropy message passing" (EMP) algorithm may be viewed as sum-product message passing over the entropy semiring, which has previously appeared in automata theory. The primary use of EMP is to compute the entropy of a model. However, EMP can also be used to compute expressions that appear in expectation maximization and in gradient descent algorithms.
5 pages, 1 figure, to appear in IEEE Transactions on Information Theory