The belief in TAP

Yoshiyuki Kabashima, David Saad

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We show the similarity between belief propagation and TAP, for decoding corrupted messages encoded by Sourlas's method. The latter is a special case of the Gallager error- correcting code, where the code word comprises products of K bits selected randomly from the original message. We examine the efficacy of solutions obtained by the two methods for various values of K and show that solutions for K>=3 may be sensitive to the choice of initial conditions in the case of unbiased patterns. Good approximations are obtained generally for K=2 and for biased patterns in the case of K>=3, especially when Nishimori's temperature is being used.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 11
EditorsMichael J. Kearns, Sara A. Solla, David Cohn
Place of PublicationCambridge MA
PublisherMIT
Pages246-252
Number of pages7
Volume11
ISBN (Print)0262112450
Publication statusPublished - Jun 1999

Publication series

NameProceeding of the 1998 Conference
PublisherMassachusetts Institute of Technology Press (MIT press)

Bibliographical note

Copyright of the Massachusetts Institute of Technology Press (MIT press)

Keywords

  • belief propagation
  • TAP
  • decoding corrupted message
  • Sourlas's method
  • Gallager error-correcting code
  • Nishimori's temperature

Fingerprint Dive into the research topics of 'The belief in TAP'. Together they form a unique fingerprint.

  • Cite this

    Kabashima, Y., & Saad, D. (1999). The belief in TAP. In M. J. Kearns, S. A. Solla, & D. Cohn (Eds.), Advances in Neural Information Processing Systems 11 (Vol. 11, pp. 246-252). (Proceeding of the 1998 Conference). MIT.