The belief in TAP

Yoshiyuki Kabashima, David Saad

    Research output: Chapter in Book/Published conference outputChapter

    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