A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice

Alejandro Lage Castellanos

Spin glasses are ubiquitous models because of their statistical physics properties, and also because they are one of the simplest models where inference algorithms can be tested. We study the application of message passing inference algorithms to finite dimensional Edwards Anderson model. While the naive belief propagation (Bethe approximation) is quite poor in finite dimensional lattice, and does not converge at low temperatures, the generalized belief propagation algorithm shall be a more powerful approximation, but also suffer from convergence problems. We develop a (generalized) message passing algorithm for solving the stationary points of the free energy Edwards Anderson model in 2D and 3D. The messages flow from square plaquettes to links in the graph, and are equivalent to a naive Belief Propagation algorithm in a dual lattice. With the drawback that only the ferromagnetic phase can be explored with our algorithm, it reproduces the results obtained by more general algorithms (GBP-DoubleLoop) in a time that is 3 orders of magnitude smaller. We show the results for the energy at different temperatures for the 2D and 3D models, comparing it with the exact (Monte Carlo) results. The correspondence between exact correlations and inferred correlations of neighboring spins is quite good, specially in 2D model. From a correlation information, a decimation
procedure is implemented to find an approximation to the ground state configuration.

Zero temperature solutions of the Edwards-Anderson model in random Husimi lattices

Alejandro Lage Castellanos

We solve the Edwards-Anderson model (EA) in different Husimi lattices using the cavity method at replica symmetric (RS) and 1-step of replica symmetry breaking (1RSB) levels. We show that, at T = 0, the structure of the solution space depends on the parity of the loop sizes. Husimi lattices with odd loop sizes may have a trivial paramagnetic solution thermodynamically relevant for highly frustrated systems while, in Husimi lattices with even loop sizes, this solution is absent. The range of stability under 1RSB perturbations of this and other RS solutions is computed analytically (when possible) or numerically. We also study the transition from 1RSB solutions to paramagnetic and ferromagnetic RS solutions. Finally we compare the solutions of the EA model in Husimi lattices with that on the (short loops free) Bethe lattices, showing that already for loop sizes of order 8 both models behave similarly.

Statistical mechanics of sparse generalization and graphical model selection

Alejandro Lage Castellanos

One of the crucial tasks in many inference problems is the extraction of an underlying sparse graphical model from a given number of high-dimensional measurements. In machine learning, this is frequently achieved using, as a penalty term, the Lp norm of the model parameters, with p≤1 for efficient dilution.
Here we propose a statistical mechanics analysis of the problem in the setting of perceptron memorization and generalization. Using a replica approach, we are able to evaluate the relative performance of naive dilution (obtained by learning without dilution, following by applying a threshold to the model parameters),
L1 dilution (which is frequently used in convex optimization) and L0 dilution (which is optimal but computationally hard to implement). Whereas both Lp diluted approaches clearly outperform the naive
approach, we find a small region where L0 works almost perfectly and strongly outperforms the simpler to implement L1 dilution.

Maximum entropy models of antibody repertoires

Thierry Mora (Princeton)

Recognition of pathogens relies on families of proteins showing great diversity. Here we construct maximum entropy models of the sequence repertoire, building on recent experiments that provide a nearly exhaustive sampling of the IgM sequences in zebrafish. These models are based solely on pairwise correlations between residue positions but correctly capture the higher order statistical properties of the repertoire. By exploiting the interpretation of these models as statistical physics problems, we make several predictions for the collective properties of the sequence ensemble: The distribution of sequences obeys Zipf’s law, the repertoire decomposes into several clusters, and there is a massive restriction of diversity because of the correlations. These predictions are completely inconsistent with models in which amino acid substitutions are made independently at each site and are in good agreement with the data. Our results suggest that antibody diversity is not limited by the sequences encoded in the genome and may reflect rapid adaptation to antigenic challenges. This approach should be applicable to the study of the global properties of other protein families.

(*) seminar at Aula Aristotele, MBC, via Nizza 52

Information processing in small gene regulatory networks and cascades

Aleksandra Walczak (Princeton)

Many of the biological networks inside cells can be thought of as transmitting information from their inputs (e.g., the concentrations of proteins or other signaling molecules) to their outputs (e.g., the expression levels of various genes). On the molecular level, the relatively small concentrations of the relevant molecules and the intrinsic randomness of chemical reactions provide sources of noise that set physical limits on this information transmission. Given these
limits, not all networks perform equally well, and maximizing information transmission provides a optimization principle from which we might hope to derive the properties of real regulatory networks. I will discuss the properties of specific small networks that can transmit the maximum information. Concretely, I will show how the form of molecular noise drives predictions not just of the qualitative network topology but also the quantitative parameters for the
input/output relations at the nodes of the network. In an attempt to link these general theoretical considerations to real biological systems, I will illustrate the predictions on the example of transmission of positional information in the early development of the fly embryo. Lastly, I will discuss different approaches of how a stochastic molecular level description can be successfully expanded to larger regulatory systems.

(*) seminar at Aula Aristotele, MBC, via Nizza 52

Add to calendar
Syndicate content