Cavity approximation for graphical models.
SourcePhysical Review. E, Statistical, Nonlinear, and Soft Matter Physics, 76, 1 Pt 1, (2007), pp. 011102-1-011102
Article / Letter to editor
Display more detailsDisplay less details
Medical Physics and Biophysics
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
iss. 1 Pt 1
SubjectBiophysics; DCN 3: Neuroinformatics; UMCN 3.2: Cognitive neurosciences
We reformulate the cavity approximation (CA), a class of algorithms recently introduced for improving the Bethe approximation estimates of marginals in graphical models. In our formulation, which allows for the treatment of multivalued variables, a further generalization to factor graphs with arbitrary order of interaction factors is explicitly carried out, and a message passing algorithm that implements the first order correction to the Bethe approximation is described. Furthermore, we investigate an implementation of the CA for pairwise interactions. In all cases considered we could confirm that CA[k] with increasing k provides a sequence of approximations of markedly increasing precision. Furthermore, in some cases we could also confirm the general expectation that the approximation of order k , whose computational complexity is O(N(k+1)) has an error that scales as 1/N(k+1) with the size of the system. We discuss the relation between this approach and some recent developments in the field.
Upload full text
Use your RU credentials (u/z-number and password) to log in with SURFconext to upload a file for processing by the repository team.