Message Passing Algorithms

Khosla, Megha

Local TagsRelease HistoryDetailsSummary

Message Passing Algorithms

Khosla, M. (2009). Message Passing Algorithms. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-BA83-2 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-BA84-F

Genre: Thesis

Files

show Files

hide Files

:

Megha_Khosla_Master'sThesis_2009.pdf (Any fulltext), 550KB

File Permalink:
-

Name:
Megha_Khosla_Master'sThesis_2009.pdf

Description:
-

OA-Status:

Visibility:
Restricted (Max Planck Institute for Informatics, MSIN; )

MIME-Type / Checksum:
application/pdf

Technical Metadata:

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Khosla, Megha^{1, 2}, Author
Panagiotou, Konstantinos¹, Advisor

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551

Content

show

hide

Free keywords: -

Abstract: Constraint Satisfaction Problems (CSPs) are defined over a set of variables whose state must satisfy a number of constraints. We study a class of algorithms called Message Passing Algorithms, which aim at finding the probability distribution of the variables over the space of satisfying assignments. These algorithms involve passing local messages (according to some message update rules) over the edges of a factor graph constructed corresponding to the CSP. We focus on the Belief Propagation (BP) algorithm, which finds exact solution marginals for tree-like factor graphs. However, convergence and exactness cannot be guaranteed for a general factor graph. We propose a method for improving BP to account for cycles in the factor graph. We also study another message passing algorithm known as Survey Propagation (SP), which is empirically quite effective in solving random K-SAT instances, even when the density is close to the satisfiability threshold. We contribute to the theoretical understanding of SP by deriving the SP equations from the BP message update rules.

Details

show

hide

Language(s): eng - English

Dates: Accepted: 2009-12Date issued: 2009

Publication Status: Issued

Pages: -

Publishing info: Saarbrücken : Universität des Saarlandes

Table of Contents: -

Rev. Type: -

Identifiers: BibTex Citekey: Khosla2009

Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show