Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Cavity approximation for graphical models.

T Rizzo1, B Wemmenhove, H J Kappen

  • 1E Fermi Center, Via Panisperna 89A, Compendio del Viminale 00184, Rome, Italy.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 7, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Erratum: Numerical test of the replica-symmetric Hamiltonian for correlations of the critical state of spin glasses in a field [Phys. Rev. E 105, 054106 (2022)].

Physical review. E·2024
Same author

Numerical test of the replica-symmetric Hamiltonian for correlations of the critical state of spin glasses in a field.

Physical review. E·2022
Same author

Minimal navigation solution for a swarm of tiny flying robots to explore an unknown environment.

Science robotics·2020
Same author

Clinical and Epidemiological Study on Tubercular Uveitis in a Tertiary Eye Care Centre in Italy.

Journal of ophthalmology·2020
Same author

Path integral control and state-dependent feedback.

Physical review. E, Statistical, nonlinear, and soft matter physics·2015
Same author

One-dimensional disordered Ising models by replica and cavity methods.

Physical review. E, Statistical, nonlinear, and soft matter physics·2014
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

We reformulated the cavity approximation (CA) for graphical models, enabling treatment of multivalued variables and arbitrary order interactions. This enhanced method offers increasingly precise estimates for model marginals with improved computational scaling.

Area of Science:

  • Statistical physics
  • Machine learning
  • Probabilistic graphical models

Background:

  • The Bethe approximation is a widely used method for estimating marginals in graphical models.
  • Existing cavity approximation (CA) algorithms improve Bethe approximation estimates but have limitations in handling multivalued variables and complex interactions.

Purpose of the Study:

  • To reformulate the cavity approximation (CA) for broader applicability.
  • To generalize CA to factor graphs with arbitrary order interaction factors.
  • To develop a message passing algorithm for the first-order corrected Bethe approximation.

Main Methods:

  • Reformulation of the cavity approximation (CA).
  • Generalization to factor graphs with arbitrary order interaction factors.

Related Experiment Videos

  • Development of a message passing algorithm for first-order correction.
  • Implementation of CA for pairwise interactions.

    • Main Results:

    • The reformulated CA handles multivalued variables and arbitrary order interactions.
    • CA[k] provides a sequence of approximations with increasing precision as k increases.
    • The error of the approximation of order k scales as 1/N(k+1) with system size N.
    • The computational complexity of the approximation of order k is O(N(k+1)).

    Conclusions:

    • The generalized cavity approximation offers a powerful framework for improving Bethe approximation estimates.
    • The precision of CA increases with the order of approximation, with predictable error scaling.
    • This work provides a foundation for further advancements in approximate inference for graphical models.