Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Cavity Method: Message Passing from a Physics perspective
KTH, Skolan för datavetenskap och kommunikation (CSC), Beräkningsvetenskap och beräkningsteknik (CST).ORCID-id: 0000-0002-1252-2899
2016 (engelsk)Inngår i: Statistical Physics, Optimization, Inference, and Message-Passing Algorithms: Lecture Notes of the Les Houches School of Physics - Special Issue October 2013 / [ed] F. Krzakala et al., Oxford University Press, 2016Kapittel i bok, del av antologi (Annet vitenskapelig)
Abstract [en]

In this three-sections lecture cavity method is introduced as heuristic framework from a Physics perspective to solve probabilistic graphical models and it is presented both at the replica symmetric (RS) and 1-step replica symmetry breaking (1RSB) level. This technique has been applied with success on a wide range of models and problems such as spin glasses, random constrain satisfaction problems (rCSP), error correcting codes etc. Firstly, the RS cavity solution for Sherrington-Kirkpatrick model---a fully connected spin glass model---is derived and its equivalence to the RS solution obtained using replicas is discussed. Then, the general cavity method for diluted graphs is illustrated both at RS and 1RSB level. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as example of an actual problem, K-SAT is investigated using belief and survey propagation.

sted, utgiver, år, opplag, sider
Oxford University Press, 2016.
Emneord [en]
cavity method, message passing, survey propagation, tree-like graphs
HSV kategori
Forskningsprogram
Fysik
Identifikatorer
URN: urn:nbn:se:kth:diva-192102OAI: oai:DiVA.org:kth-192102DiVA, id: diva2:958026
Merknad

QC 20160905

Tilgjengelig fra: 2016-09-05 Laget: 2016-09-05 Sist oppdatert: 2016-09-05bibliografisk kontrollert
Inngår i avhandling
1. Equilibrium and Dynamics on Complex Networkds
Åpne denne publikasjonen i ny fane eller vindu >>Equilibrium and Dynamics on Complex Networkds
2016 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

Complex networks are an important class of models used to describe the behaviour of a very broad category of systems which appear in different fields of science ranging from physics, biology and statistics to computer science and other disciplines. This set of models includes spin systems on a graph, neural networks, decision networks, spreading disease, financial trade, social networks and all systems which can be represented as interacting agents on some sort of graph architecture.

In this thesis, by using the theoretical framework of statistical mechanics, the equilibrium and the dynamical behaviour of such systems is studied.

For the equilibrium case, after presenting the region graph free energy approximation, the Survey Propagation method, previously used to investi- gate the low temperature phase of complex systems on tree-like topologies, is extended to the case of loopy graph architectures.

For time-dependent behaviour, both discrete-time and continuous-time dynamics are considered. It is shown how to extend the cavity method ap- proach from a tool used to study equilibrium properties of complex systems to the discrete-time dynamical scenario. A closure scheme of the dynamic message-passing equation based on a Markovian approximations is presented. This allows to estimate non-equilibrium marginals of spin models on a graph with reversible dynamics. As an alternative to this approach, an extension of region graph variational free energy approximations to the non-equilibrium case is also presented. Non-equilibrium functionals that, when minimized with constraints, lead to approximate equations for out-of-equilibrium marginals of general spin models are introduced and discussed.

For the continuous-time dynamics a novel approach that extends the cav- ity method also to this case is discussed. The main result of this part is a Cavity Master Equation which, together with an approximate version of the Master Equation, constitutes a closure scheme to estimate non-equilibrium marginals of continuous-time spin models. The investigation of dynamics of spin systems is concluded by applying a quasi-equilibrium approach to a sim- ple case. A way to test self-consistently the assumptions of the method as well as its limits is discussed.

In the final part of the thesis, analogies and differences between the graph- ical model approaches discussed in the manuscript and causal analysis in statistics are presented.

sted, utgiver, år, opplag, sider
Stockholm: KTH Royal Institute of Technology, 2016. s. 189
Serie
TRITA-CSC-A, ISSN 1653-5723 ; 2016:17
Emneord
Statistical mechanics, complex networks, spin systems, non equilibrium dynamics, generalized belief propagation, message passing, cavity method, variational approaches
HSV kategori
Forskningsprogram
Fysik
Identifikatorer
urn:nbn:se:kth:diva-191991 (URN)978-91-7729-058-2 (ISBN)
Disputas
2016-09-09, Kollegiesalen, Brinellvägen 8, plan 4, Stockholm, 10:00 (engelsk)
Opponent
Veileder
Merknad

QC 20160904

Tilgjengelig fra: 2016-09-04 Laget: 2016-09-03 Sist oppdatert: 2016-09-05bibliografisk kontrollert

Open Access i DiVA

fulltext(882 kB)140 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 882 kBChecksum SHA-512
340d5948fb9718c016146cc28cf84c8947ee28ceb9cb3b70c3c1a00e0a659038efb9cbf83e8b7f5efd4b32186f5559ce3ff3b1982f09bac48355006984df0c57
Type fulltextMimetype application/pdf

Personposter BETA

Del Ferraro, Gino

Søk i DiVA

Av forfatter/redaktør
Del Ferraro, Gino
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 140 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 277 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf