Analysis of Random Sequential Message Passing Algorithms for Approximate Inference
We analyze the dynamics of a random sequential message passing algorithm for approximate inference with large Gaussian latent variable models in a student-teacher scenario. To model nontrivial dependencies between the latent variables, we assume random covariance matrices drawn from rotation invariant ensembles. Moreover, we consider a model mismatching setting, where the teacher model and the one used by the student may be different. By means of dynamical functional approach, we obtain exact dynamical mean-field equations characterizing the dynamics of the inference algorithm. We also derive a range of model parameters for which the sequential algorithm does not converge. The boundary of this parameter range coincides with the de Almeida Thouless (AT) stability condition of the replica symmetric ansatz for the static probabilistic model.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
We show that the Survey Propagation-guided decimation algorithm fails to find satisfying assignments on random instances of the "Not-All-Equal-$K$-SAT" problem if the number of message passing iterations is bounded by a …
ClusteringExact solution to the random sequential dynamics of a message passing algorithm
We analyze the random sequential dynamics of a message passing algorithm for Ising models with random interactions in the large system limit. We derive exact results for the two-time correlation functions and the speed o…
Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs. In such applications, variables are fixed sequentially to satisfy the constraints. …
Bayesian inference as iterated random functions with applications to sequential inference in graphical models
We propose a general formalism of iterated random functions with semigroup property, under which exact and approximate Bayesian posterior updates can be viewed as specific instances. A convergence theory for iterated ran…
Bayesian InferenceChange Point DetectionFast and Differentiable Message Passing on Pairwise Markov Random Fields
Despite the availability of many Markov Random Field (MRF) optimization algorithms, their widespread usage is currently limited due to imperfect MRF modelling arising from hand-crafted model parameters and the selection …
DenoisingGPUSemantic Segmentation