A review of the Statistical Mechanics approach to Random Optimization Problems <s> D. A glimpse at the computations <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> A review of the Statistical Mechanics approach to Random Optimization Problems <s> D. A glimpse at the computations <s> Thank you for downloading exploring artificial intelligence in the new millennium. Maybe you have knowledge that, people have search hundreds times for their chosen novels like this exploring artificial intelligence in the new millennium, but end up in infectious downloads. Rather than reading a good book with a cup of coffee in the afternoon, instead they are facing with some infectious virus inside their computer. <s> BIB002
The statistical mechanics of disordered systems BIB001 was first developed on so-called fully-connected models, where each variable appears in a number of constraints which diverges in the thermodynamic limit. This is for instance the case of the perceptron problem discussed in Sec. II. On the contrary, in a random k-SAT instance a variable is typically involved in a finite number of clauses, one speaks in this case of a diluted model. This finite connectivity is a source of major technical complications. In particular the replica method, alluded to in Sec. II C and applied to random k-SAT in [19, 20] , turns out to be rather cumbersome for diluted models in the presence of clustering [43] . The cavity formalism [21, 44, 45] , formally equivalent to the replica one, is more adapted to the diluted models. In the following paragraphs we shall try to give a few hints at the strategy underlying the cavity computations, that might hopefully ease the reading of the original literature. The description of the random formula ensemble has two complementary aspects: a global (thermodynamic) one, which amounts to the computation of the typical energy and number of optimal configurations. A more ambitious description will also provide geometrical information on the organization of this set of optimal configurations inside the N -dimensional hypercube. As discussed above these two aspects are in fact interleaved, the clustering affecting both the thermodynamics (by the decomposition of the entropy into the complexity and the internal entropy) and the geometry of the configuration space. Let us for simplicity concentrate on the α < α s regime and consider a satisfiable formula F . Both thermodynamic and geometric aspects can be studied in terms of the uniform probability law over the solutions of F :  where Z is the number of solutions of F , the product runs over its clauses, and w a is the indicator function of the event "clause a is satisfied by the assignment σ" (in fact this depends only on the configuration of the k variables involved in the clause a, that we denote σ a ). For instance the (information theoretic) entropy of µ is equal to ln Z, the log degeneracy of solutions, and geometric properties can be studied by computing averages with respect to µ of well-chosen functions of σ. A convenient representation of such a law is provided by factor graphs [46] . These are bipartite graphs with two types of vertices (see Fig. 3 for an illustration): one variable node (filled circle) is associated to each of the N Boolean variables, while the clauses are represented by M constraint nodes (empty squares). By convention we use the indices a, b, . . . for the constraint nodes, i, j, . . . for the variables. An edge is drawn between variable node i and constraint node a if and only if a depends on i. To precise further by which value of σ i the clause a gets satisfied one can use two type of linestyles, solid and dashed on the figure. A notation repeatedly used in the following is ∂a (resp. ∂i) for the neighborhood of a constraint (resp. variable) node, i.e. the set of adjacent variable (resp. constraint) nodes. In this context \ denotes the subtraction from a set. We shall more precisely denote ∂ + i(a) (resp. ∂ − i(a)) the set of clauses in ∂i \ a agreeing (resp. disagreeing) with a on the satisfying value of σ i , and ∂ σ i the set of clauses in ∂i which are satisfied by σ i = σ. This graphical representation naturally suggests a notion of distance between variable nodes i and j, defined as the minimal number of constraint nodes crossed on a path of the factor graph linking nodes i and j. Suppose now that F is drawn from the random ensemble. The corresponding random factor graph enjoys several interesting properties  . The degree |∂i| of a randomly chosen variable i is, in the thermodynamic limit, a Poisson random variable of average αk. If instead of a node one chooses randomly an edge a − i, the outdegree |∂i \ a| of i has again a Poisson distribution with the same parameter. Moreover the sign of the literals being chosen uniformly, independently of the topology of the factor graph, the degrees |∂ + i|, |∂ − i|, |∂ + i(a)| and |∂ − i(a)| are Poisson random variables of parameter αk/2. Another important feature of these random factor graphs is their local tree-like character: if the portion of the formula at graph distance smaller than L of a randomly chosen variable is exposed, the probability that this subgraph is a tree goes to 1 if L is kept fixed while the size N goes to infinity. Let us for a second forget about the rest of the graph and consider a finite formula whose factor graph is a tree, as is the case for the example of Fig. 3 . The probability law µ of Eq. (24) becomes in this case a rather simple object. Tree structures are indeed naturally amenable to a recursive (dynamic programming) treatment, operating first on sub-trees which are then glued together. More precisely, for each edge between a variable node i and a constraint node a one defines the amputated tree F a→i (resp. F i→a ) by removing all clauses in ∂i apart from a (resp. removing only a). These subtrees are associated to probability laws µ a→i (resp. µ i→a ), defined as in Eq. (24) but with a product running only on the clauses present in F a→i (resp. F i→a ). The marginal law of the root variable i in these amputated probability measures can be parametrized by a single real, as σ i can take only two values (that, in the Ising spin convention, are ±1). We thus define these fields, or messages, h i→a and u a→i , by where we recall that σ i = J a i is the value of the literal i unsatisfying clause a. A standard reasoning (see for instance [47] ) allows to derive recursive equations (illustrated in Fig. 4 ) on these messages, Because the factor graph is a tree this set of equations has a unique solution which can be efficiently determined: one start from the leaves (degree 1 variable nodes) which obey the boundary condition h i→a = 0, and progresses inwards the graph. The law µ can be completely described from the values of the h's and u's solutions of these equations for all edges of the graph. For instance the marginal probability of σ i can be written as In addition the entropy s of solutions of such a tree formula, can be computed from the values of the messages h and u [47] . We shall come back to the equations (26), and justify the denomination messages, in Sec. V C; these can be interpreted as the Belief Propagation [46,  BIB002 heuristic equations for loopy factor graphs. The factor graph of random formulas is only locally tree-like; the simple computation sketched above has thus to be amended in order to take into account the effect of the distant, loopy part of the formula. Let us call F L the factor graph made of variable nodes at graph distance smaller than or equal to L from an arbitrarily chosen variable node i in a large random formula F , and B L the variable nodes at distance exactly L from i. Without loss of generality in the thermodynamic limit, we can assume that F L is a tree. The cavity method amounts to an hypothesis on the effect of the distant part of the factor graph, F \ F L , i.e. on the boundary condition it induces on F L . In its simplest (so called replica symmetric) version, that is believed to correctly describe the unclustered situation for α ≤ α d , F \ F L is replaced, for each variable node j in the boundary B L , by a fictitious constraint node which sends a bias u ext→j . In other words the boundary condition is factorized on the various nodes of B L ; such a simple description is expected to be correct for α ≤ α d because, in the amputated factor graph F \ F L , the distance between the variables of B L is typically large (of order ln N ), and these variables should thus be weakly correlated. These external biases are then turned into random variables to take into account the randomness in the construction of the factor graphs, and Eq. (26) acquires a distributional meaning. The messages h (resp. u) are supposed to be i.i.d. random variables drawn from a common distribution, the degrees ∂ ± i(a) being two independent Poisson random variables of parameter αk/2. These distributional equations can be numerically solved by a population dynamics algorithm [44] , also known as a particle representation in the statistics litterature. The typical entropy density is then computed by averaging s over these distributions of h and u. This description fails in the presence of clustering, which induces correlations between the variable nodes of B L in the amputated factor graph F \ F L . To take these correlations into account a refined version of the cavity method (termed one step of replica symmetry breaking, in short 1RSB) has been developed. It relies on the hypothesis that the partition of the solution space into clusters γ has nice decorrelation properties: once decomposed onto this partition, µ restricted to a cluster γ behaves essentially as in the unclustered phase (it is a pure state in statistical mechanics jargon). Each directed edge a → i should thus bear a family of messages u γ a→i , one for each cluster, or alternatively a distribution Q a→i (u) of the messages with respect to the choice of γ. The equations (26) are thus promoted to recursions between distributions P i→a (h), Q a→i (u), which depends on a real m known as the Parisi breaking parameter. Its role is to select the size of the investigated clusters, i.e. the number of solutions they contain. The computation of the typical entropy density is indeed replaced by a more detailed thermodynamic potential, In this formula Z γ denotes the number of solutions inside a cluster γ, and we used the hypothesis that at the leading order the number of clusters with internal entropy density s int is given by exp[N Σ(s int )]. The complexity function Σ(s int ) can thus be obtained from Φ(m) by an inverse Legendre transform. For generic values of m this approach is computationally very demanding; following the same steps as in the replica symmetric version of the cavity method one faces a distribution (with respect to the topology of the factor graph) of distributions (with respect to the choice of the clusters) of messages. Simplifications however arise for m = 1 and m = 0 [22] ; the latter case corresponds in fact to the original Survey Propagation approach of [21] . As appears clearly in Eq. (28) , for this value of m all clusters are treated on an equal footing and the dominant contribution comes from the most numerous clusters, independently of their sizes. Moreover, as we further explain in Sec. V C, the structure of the equations can be greatly simplified in this case, the distribution over the cluster of fields being parametrized by a single number.