Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding
Irina Rish, Kalev Kask, Rina Dechter
Abstract:
It was recently shown that the problem of decoding messages transmitted through a noisy channel can be formulated as a belief updating task over a probabilistic network [McEliece]. Moreover, it was observed that iterative application of the (linear time) Pearl's belief propagation algorithm designed for polytrees outperformed state of the art decoding algorithms, even though the corresponding networks may have many cycles. This paper demonstrates empirically that an approximation algorithm approx-mpe for solving the most probable explanation (MPE) problem, developed within the recently proposed mini-bucket elimination framework [Dechter96], outperforms iterative belief propagation on classes of coding networks that have bounded induced width. Our experiments suggest that approximate MPE decoders can be good competitors to the approximate belief updating decoders.
Keywords: Approximate inference, belief propagation, MPE, probabilistic decoding, empirical eva
Pages: 455-463
PS Link: http://www.ics.uci.edu/~irinar/papers/uai98.ps
PDF Link: /papers/98/p455-rish.pdf
BibTex:
@INPROCEEDINGS{Rish98,
AUTHOR = "Irina Rish and Kalev Kask and Rina Dechter",
TITLE = "Empirical Evaluation of Approximation Algorithms for Probabilistic Decoding",
BOOKTITLE = "Proceedings of the Fourteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-98)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1998",
PAGES = "455--463"
}


hosted by DSL   •   site info   •   help