Empirical Evaluation of Approximation Algorithms for Probabilistic
  Decoding
  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.
