Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Message Passing Algorithms

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

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-BA83-2 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-BA84-F
Genre: Hochschulschrift

Dateien

einblenden: Dateien
ausblenden: Dateien
:
Megha_Khosla_Master'sThesis_2009.pdf (beliebiger Volltext), 550KB
 
Datei-Permalink:
-
Name:
Megha_Khosla_Master'sThesis_2009.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Eingeschränkt (Max Planck Institute for Informatics, MSIN; )
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Khosla, Megha1, 2, Autor           
Panagiotou, Konstantinos1, Ratgeber           
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              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2009-122009
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Saarbrücken : Universität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Khosla2009
 Art des Abschluß: Master

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: