2013/01/30 by Irina Rish, Rish, Irina, Kalev Kask +3
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Error Correcting Code Techniques #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1301.7409
openalex publication_date 2013/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It was recently shown that the problem of decoding messages transmitted\nthrough a noisy channel can be formulated as a belief updating task over a\nprobabilistic network [McEliece]. Moreover, it was observed that iterative\napplication of the (linear time) Pearl's belief propagation algorithm designed\nfor polytrees outperformed state of the art decoding algorithms, even though\nthe corresponding networks may have many cycles. This paper demonstrates\nempirically that an approximation algorithm approx-mpe for solving the most\nprobable explanation (MPE) problem, developed within the recently proposed\nmini-bucket elimination framework [Dechter96], outperforms iterative belief\npropagation on classes of coding networks that have bounded induced width. Our\nexperiments suggest that approximate MPE decoders can be good competitors to\nthe approximate belief updating decoders.\n