Approximate Survey Propagation for Statistical Inference <s> The 1RSB free energy and complexity <s> This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses. The authors also explain recent theoretical developments, paying particular attention to new applications in the study of optimization theory and neural networks. About two-thirds of the book are a collection of the most interesting and pedagogical articles on the subject. <s> BIB001 </s> Approximate Survey Propagation for Statistical Inference <s> The 1RSB free energy and complexity <s> Abstract This article reviews Markov chain methods for sampling from the posterior distribution of a Dirichlet process mixture model and presents two new classes of methods. One new approach is to make Metropolis—Hastings updates of the indicators specifying which mixture component is associated with each observation, perhaps supplemented with a partial form of Gibbs sampling. The other new approach extends Gibbs sampling for these indicators by using a set of auxiliary parameters. These methods are simple to implement and are more efficient than previous ways of handling general Dirichlet process mixture models with non-conjugate priors. <s> BIB002 </s> Approximate Survey Propagation for Statistical Inference <s> The 1RSB free energy and complexity <s> We study the satisfiability of randomly generated formulas formed by M clauses of exactly K literals over N Boolean variables. For a given value of N the problem is known to be most difficult when α = M/N is close to the experimental threshold αc separating the region where almost all formulas are SAT from the region where all formulas are UNSAT. Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when α is close to (but smaller than) αc. We introduce a new type of message passing algorithm which allows to find efficiently a satisfying assignment of the variables in this difficult region. This algorithm is iterative and composed of two main parts. The first is a message-passing procedure which generalizes the usual methods like Sum-Product or Belief Propagation: It passes messages that may be thought of as surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 <s> BIB003
The algorithmic interpretation of the 1RSB is not limited to the fixed point equations, but concerns the free energy as well. In the same way AMP can be interpreted as extremizing the replica symmetric Bethe free energy BIB003 , ASP can be interpreted as extremizing the 1RSB Bethe free energy (65). The 1RSB-SE equations corresponds to the stationary points of the free energy, which we give here without derivation, as it can readily be adapted from the RS one:  , where T , V (0) and V BIB002 are functions of the order parameters as for Eqs. (72)- (74). This free energy coincides with the one obtained by replica theory under 1RSB ansatz and reduces to Eq. (26) for s = 1. From the previous expression one can obtain the value of s that extremizes the free energy. From the point of view of physics, this value of s would be the one that describes the equilibrium states of the system in a 1RSB phase. From the point of view of inference, this value of s does not minimizes the MSE, as we discuss in Sec. III C. In the case the posterior measure develops a 1RSB structure, the phase space of configurations becomes clustered in exponentially many basins. In this situation, the number of basins is counted by the complexity BIB001 . The complexity Σ as function of the free energy of a single metastable state can be obtained as the Legendre transform of the 1RSB free energy of the system, obtaining From the point of view of physics, the static solution corresponds to the metastable states with the lowest free energy and null complexity. The inclusion of the 1RSB structure in ASP allows to analyze situations with nonzero complexity Σ.