Search

Understanding the role of regularization is a central question in Statistical Inference. Empirically, well-chosen regularization schemes often dramatically improve the quality of the inferred models by avoiding overfitting of the training data. We consider here the particular case of L 2 and L 1 regularizations in the Maximum A Posteriori (MAP) inference of generative pairwise graphical models. Based on analytical calculations on Gaussian multivariate distributions and numerical experiments on Gaussian and Potts models we study the likelihoods of the training, test, and 'generated data' (with the inferred models) sets as functions of the regularization strengths. We show in particular that, at its maximum, the test likelihood and the 'generated' likelihood, which quantifies the quality of the generated samples, have remarkably close values. The optimal value for the regularization strength is found to be approximately equal to the inverse sum of the squared couplings incoming on sites on the underlying network of interactions. Our results seem largely independent of the structure of the true underlying interactions that generated the data, of the regularization scheme considered, and are valid when small fluctuations of the posterior distribution around the MAP estimator are taken into account. Connections with empirical works on protein models learned from homologous sequences are discussed.

The spontaneous transitions between D-dimensional spatial maps in an attractor neural network are studied. Two scenarios for the transition from on map to another are found, depending on the level of noise: (1) through a mixed state, partly localized in both maps around positions where the maps are most similar; (2) through a weakly localized state in one of the two maps, followed by a condensation in the arrival map. Our predictions are confirmed by numerical simulations, and qualitatively compared to recent recordings of hippocampal place cells during quick-environment-changing experiments in rats., Comment: to appear in Physical Review Letters; Supplemental Material available from the author's web page

Mean field (MF) approximation offers a simple, fast way to infer direct interactions between elements in a network of correlated variables, a common, computationally challenging problem with practical applications in fields ranging from physics and biology to the social sciences. However, MF methods achieve their best performance with strong regularization, well beyond Bayesian expectations, an empirical fact that is poorly understood. In this work, we study the influence of pseudo-count and $L_2$-norm regularization schemes on the quality of inferred Ising or Potts interaction networks from correlation data within the MF approximation. We argue, based on the analysis of small systems, that the optimal value of the regularization strength remains finite even if the sampling noise tends to zero, in order to correct for systematic biases introduced by the MF approximation. Our claim is corroborated by extensive numerical studies of diverse model systems and by the analytical study of the $m$-component spin model, for large but finite $m$. Additionally we find that pseudo-count regularization is robust against sampling noise, and often outperforms $L_2$-norm regularization, particularly when the underlying network of interactions is strongly heterogeneous. Much better performances are generally obtained for the Ising model than for the Potts model, for which only couplings incoming onto medium-frequency symbols are reliably inferred., Comment: 25 pages, 17 figures

Within the framework of Von Neumann's expanding model, we study the maximum growth rate r achievable by an autocatalytic reaction network in which reactions involve a finite (fixed or fluctuating) number D of reagents. r is calculated numerically using a variant of the Minover algorithm, and analytically via the cavity method for disordered systems. As the ratio between the number of reactions and that of reagents increases the system passes from a contracting (r<1) to an expanding regime (r>1). These results extend the scenario derived in the fully connected model ($D\to\infinity$), with the important difference that, generically, larger growth rates are achievable in the expanding phase for finite D and in more diluted networks. Moreover, the range of attainable values of r shrinks as the connectivity increases., Comment: 20 pages

We introduce and test a method to predict the sequence of DNA molecules from in silico unzipping experiments. The method is based on Bayesian inference and on the Viterbi decoding algorithm. The probability of misprediction decreases exponentially with the number of unzippings, with a decay rate depending on the applied force and the sequence content., Comment: Source as TeX file with ps figures

Recent experiments on unzipping of RNA helix-loop structures by force have shown that about 40-base molecules can undergo kinetic transitions between two well-defined `open' and `closed' states, on a timescale = 1 sec [Liphardt et al., Science 297, 733-737 (2001)]. Using a simple dynamical model, we show that these phenomena result from the slow kinetics of crossing large free energy barriers which separate the open and closed conformations. The dependence of barriers on sequence along the helix, and on the size of the loop(s) is analyzed. Some DNAs and RNAs sequences that could show dynamics on different time scales, or three(or more)-state unzipping, are proposed., Comment: 8 pages Revtex, including 4 figures

The two strands of the DNA double helix can be `unzipped' by application of 15 pN force. We analyze the dynamics of unzipping and rezipping, for the case where the molecule ends are separated and re-approached at constant velocity. For unzipping of 50 kilobase DNAs at less than about 1000 bases per second, thermal equilibrium-based theory applies. However, for higher unzipping velocities, rotational viscous drag creates a buildup of elastic torque to levels above kBT in the dsDNA region, causing the unzipping force to be well above or well below the equilibrium unzipping force during respectively unzipping and rezipping, in accord with recent experimental results of Thomen et al. [Phys. Rev. Lett. 88, 248102 (2002)]. Our analysis includes the effect of sequence on unzipping and rezipping, and the transient delay in buildup of the unzipping force due to the approach to the steady state., Comment: 15 pages Revtex file including 9 figures

We review statistical-mechanical theories of single-molecule micromanipulation experiments on nucleic acids. First, models for describing polymer elasticity are introduced. We then review how these models are used to interpret single-molecule force-extension experiments on single-stranded and double-stranded DNA. Depending on the force and the molecules used, both smooth elastic behaviors and abrupt structural transitions are observed. Third, we show how combining the elasticity of two single nucleic acid strands with a description of the base-pairing interactions between them explains much of the phenomenology and kinetics of RNA and DNA `unzipping' experiments., Comment: to appear in CRAS, special issue dedicated to Single Molecule Experiments

A constructive scheme for determining pure states (clusters) at very low temperature in the 3-spins glass model on a random lattice is provided, in full agreement with Parisi's one step replica symmetry breaking (RSB) scheme. Proof is based on the analysis of an exact decimation procedure. When the number c of couplings per spin is smaller than some critical value c_d, all spins are eliminated at the end of decimation (RS phase). In the range c_d

The analysis of the solving complexity of random 3-SAT instances using the Davis-Putnam-Loveland-Logemann (DPLL) algorithm slightly below threshold is presented. While finding a solution for such instances demands exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. We compute analytically this exponentially small probability of easy resolutions from a large deviation analysis of DPLL with the Generalized Unit Clause search heuristic, and show that the corresponding exponent is smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some quantitative basis to heuristic restart solving procedures, and suggests a natural cut-off cost (the size of the instance) for the restart., Comment: submitted to Annals of Math and Artificial Intelligence

A large deviation analysis of the solving complexity of random 3-Satisfiability instances slightly below threshold is presented. While finding a solution for such instances demands an exponential effort with high probability, we show that an exponentially small fraction of resolutions require a computation scaling linearly in the size of the instance only. This exponentially small probability of easy resolutions is analytically calculated, and the corresponding exponent shown to be smaller (in absolute value) than the growth exponent of the typical resolution time. Our study therefore gives some theoretical basis to heuristic stop-and-restart solving procedures, and suggests a natural cut-off (the size of the instance) for the restart., Comment: Revtex file, 4 figures

A theory of the unzipping of double-stranded (ds) DNA is presented, and is compared to recent micromanipulation experiments. It is shown that the interactions which stabilize the double helix and the elastic rigidity of single strands (ss) simply determine the sequence dependent =12 pN force threshold for DNA strand separation. Using a semi-microscopic model of the binding between nucleotide strands, we show that the greater rigidity of the strands when formed into dsDNA, relative to that of isolated strands, gives rise to a potential barrier to unzipping. The effects of this barrier are derived analytically. The force to keep the extremities of the molecule at a fixed distance, the kinetic rates for strand unpairing at fixed applied force, and the rupture force as a function of loading rate are calculated. The dependence of the kinetics and of the rupture force on molecule length is also analyzed., Comment: Revtex file + 6 eps Figures; published in Proc. Natl. Acad. Sci. USA 98, 8608 (2001)

Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations that lead to close ties between computer science and statistical physics. This review aims at presenting the tools and concepts designed by physicists to deal with optimization or decision problems in an accessible language for computer scientists and mathematicians, with no prerequisites in physics. We first introduce some elementary methods of statistical mechanics and then progressively cover the tools appropriate for disordered systems. In each case, we apply these methods to study the phase transitions or the statistical properties of the optimal solutions in various combinatorial problems. We cover in detail the Random Graph, the Satisfiability, and the Traveling Salesman problems. References to the physics literature on optimization are provided. We also give our perspective regarding the interdisciplinary contribution of physics to computer science., Comment: Review article, 80 pages, uses elsart.cls

Heuristic methods for solution of problems in the NP-Complete class of decision problems often reach exact solutions, but fail badly at "phase boundaries", across which the decision to be reached changes from almost always having one value to almost having a different value. We report an analytic solution and experimental investigations of the phase transition that occurs in the limit of very large problems in K-SAT. The nature of its "random first-order" phase transition, seen at values of K large enough to make the computational cost of solving typical instances increase exponenitally with problem size, suggest a mechanism for the cost increase. There has been evidence for features like the "backbone" of frozen inputs which characterizes the UNSAT phase in K-SAT in the study of models of disordered materials, but this feature and this transition are uniquely accessible to analysis in K-SAT. The random first order transition combines properties of the 1st order (discontinuous onset of order) and 2nd order (with power law scaling, e.g. of the width of the the critical region in a finite system) transitions known in the physics of pure solids. Such transitions should occur in other combinatoric problems in the large N limit. Finally, improved search heuristics may be developed when a "backbone" is known to exist., Comment: 25 pages, to appear in Random Structures and Algorithms

Geometrical disorder is present in many physical situations giving rise to eigenvalue problems. The simplest case of diffusion on a random lattice with fluctuating site connectivities is studied analytically and by exact numerical diagonalizations. Localization of eigenmodes is shown to be induced by geometrical defects, that is sites with abnormally low or large connectivities. We expose a ``single defect approximation'' (SDA) scheme founded on this mechanism that provides an accurate quantitative description of both extended and localized regions of the spectrum. We then present a systematic diagrammatic expansion allowing to use SDA for finite-dimensional problems, e.g. to determine the localized harmonic modes of amorphous media., Comment: final version as published, 6 pages, 1 ps-figure

The Glauber dynamics of the Hopfield model at low storage level is considered. We analytically derive the spectrum of relaxation times for large system sizes. The longest time scales are gathered in families, each family being in one to one correspondence with a stationary (not necessarily stable) point of the static mean-field free-energy. Inside a family, the time scales are given by the reciprocals (of the absolute values) of the eigenvalues of the free-energy Hessian matrix., Comment: 5 pages RevTex file, accepted for publication in J.Phys.A

A toy model of particles packings is presented, which consists in arranging hexagons on a triangular lattice according to local stability rules. The number of stable packings is analytically computed and found to grow exponentially with the size of the lattice, which illustrates the concept of packing entropy first proposed by Edwards and collaborators. The analysis is carried out for both the monodispersed case and the more interesting, i.e. more disordered, bidispersed case., Comment: 20 pages, 7 figures; to appear in Physica A

We analyse the eigenvalue structure of the replicated transfer matrix of one-dimensional disordered Ising models. In the limit of $n \rightarrow 0$ replicas, an infinite sequence of transfer matrices is found, each corresponding to a different irreducible representation (labelled by a positive integer $\rho$) of the permutation group. We show that the free energy can be calculated from the replica symmetric subspace ($\rho =0$). The other ``replica symmetry broken'' representations ($\rho \ne 0$) are physically meaningful since their largest eigenvalues $\lambda^{(\rho )}$ control the disorder--averaged moments $\ll( \langle S_i S_j \rangle - \langle S_i \rangle \langle S_j \rangle )^\rho \gg \propto (\lambda^{(\rho )}) ^{|i-j|}$ of the connected two-points correlations., Comment: 4 pages, REVTeX, no figures

The Random K-Satisfiability Problem, consisting in verifying the existence of an assignment of N Boolean variables that satisfy a set of M=alpha N random logical clauses containing K variables each, is studied using the replica symmetric framework of diluted disordered systems. We present an exact iterative scheme for the replica symmetric functional order parameter together for the different cases of interest K=2, K>= 3 and K>>1. The calculation of the number of solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a first order jump at the threshold where the Boolean expressions become unsatisfiable with probability one, is thoroughly displayed. In the case K=2, the (rigorously known) critical value (alpha=1) of the number of clauses per Boolean variable is recovered while for K>=3 we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large K., Comment: 34 pages + 1 table + 8 fig., submitted to Phys. Rev. E, new section added and references updated

The metastable states of a glass are counted by adding a weak pinning field which explicitly breaks the ergodicity. Their entropy, that is the logarithm of their number, is extensive in a range of temperatures $T_G < T < T_C$ only, where $T_G$ and $T_C$ correspond to the ideal calorimetric and kinetic glass transition temperatures respectively. An explicit self-consistent computation of the metastable states entropy for a non disordered model is given., Comment: 12 pages Revtex file

We analytically derive the geometrical structure of the weight space in multilayer neural networks (MLN), in terms of the volumes of couplings associated to the internal representations of the training set. Focusing on the parity and committee machines, we deduce their learning and generalization capabilities both reinterpreting some known properties and finding new exact results. The relationship between our approach and information theory as well as the Mitchison--Durbin calculation is established. Our results are exact in the limit of a large number of hidden units, showing that MLN are a class of exactly solvable models with a simple interpretation of replica symmetry breaking., Comment: 12 pages, 1 compressed ps figure (uufile), RevTeX file

The high temperature phase of the three dimensional random field Ising model is studied using replica symmetry breaking framework. It is found that, above the ferromagnetic transition temperature T_f, there appears a glassy phase at intermediate temperatures T_fT_b only. Correlation length at T_b is computed and found to be compatible with previous numerical results., Comment: 7 pages, LaTeX file, preprint 1014 - Rome I