Statistical physics of inference: thresholds and algorithms

Many questions of fundamental interest in today's science can be formulated as inference problems: some partial, or noisy, observations are performed over a set of variables and the goal is to recover, or infer, the values of the variables based on the indirect information contained in the measurements. For such problems, the central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? A growing body of work has shown that often we can understand and locate these fundamental barriers by thinking of them as phase transitions in the sense of statistical physics. Moreover, it turned out that we can use the gained physical insight to develop new promising algorithms. The connection between inference and statistical physics is currently witnessing an impressive renaissance and we review here the current state-of-the-art, with a pedagogical focus on the Ising model which, formulated as an inference problem, we call the planted spin glass. In terms of applications we review two classes of problems: (i) inference of clusters on graphs and networks, with community detection as a special case and (ii) estimating a signal from its noisy linear measurements, with compressed sensing as a case of sparse estimation. Our goal is to provide a pedagogical review for researchers in physics and other fields interested in this fascinating topic.     

Twenty Five Years After KLS: A Celebration of Non-equilibrium Statistical Mechanics

When Lenz proposed a simple model for phase transitions in magnetism, he couldn’t have imagined that the “Ising model” was to become a jewel in field of equilibrium statistical mechanics. Its role spans the spectrum, from a good pedagogical example to a universality class in critical phenomena. A quarter century ago, Katz, Lebowitz and Spohn found a similar treasure. By introducing a seemingly trivial modification to the Ising lattice gas, they took it into the vast realms of non-equilibrium statistical mechanics. An abundant variety of unexpected behavior emerged and caught many of us by surprise. We present a brief review of some of the new insights garnered and some of the outstanding puzzles, as well as speculate on the model’s role in the future of non-equilibrium statistical physics.     

Statistical physics on cellular neural network computers

The computational paradigm represented by Cellular Neural/nonlinear Networks (CNN) and the CNN Universal Machine (CNN-UM) as a Cellular Wave Computer, gives new perspectives also for computational statistical physics. Thousands of locally interconnected cells working in parallel, analog signals giving the possibility of generating truly random numbers, continuity in time and the optical sensors included on the chip are just a few important advantages of such computers. Although CNN computers are mainly used and designed for image processing, here we argue that they are also suitable for solving complex problems in computational statistical physics. This study presents two examples of stochastic simulations on CNN: the site-percolation problem and the two-dimensional Ising model. Promising results are obtained using an ACE16K chip with 128×128 cells. In the second part of the work we discuss the possibility of using the CNN architecture in studying problems related to spin-glasses. A CNN with locally variant parameters is used for developing an optimization algorithm on spin-glass type models. Speed of the algorithms and further trends in developing the CNN chips are discussed.     

Beyond Inverse Ising Model: Structure of the Analytical Solution

I consider the problem of deriving couplings of a statistical model from measured correlations, a task which generalizes the well-known inverse Ising problem. After reminding that such problem can be mapped on the one of expressing the entropy of a system as a function of its corresponding observables, I show the conditions under which this can be done without resorting to iterative algorithms. I find that inverse problems are local (the inverse Fisher information is sparse) whenever the corresponding models have a factorized form, and the entropy can be split in a sum of small cluster contributions. I illustrate these ideas through two examples (the Ising model on a tree and the one-dimensional periodic chain with arbitrary order interaction) and support the results with numerical simulations. The extension of these methods to more general scenarios is finally discussed.     

Fluctuation behaviors of financial time series by a stochastic Ising system on a Sierpinski carpet lattice

We develop a financial market model using an Ising spin system on a Sierpinski carpet lattice that breaks the equal status of each spin. To study the fluctuation behavior of the financial model, we present numerical research based on Monte Carlo simulation in conjunction with the statistical analysis and multifractal analysis of the financial time series. We extract the multifractal spectra by selecting various lattice size values of the Sierpinski carpet, and the inverse temperature of the Ising dynamic system. We also investigate the statistical fluctuation behavior, the time-varying volatility clustering, and the multifractality of returns for the indices SSE, SZSE, DJIA, IXIC, S&P500, HSI, N225, and for the simulation data derived from the Ising model on the Sierpinski carpet lattice. A numerical study of the model’s dynamical properties reveals that this financial model reproduces important features of the empirical data.     

Triangular approximation for Ising model and its application to Boltzmann machine

When we consider a problem in information processing, it is convenient to formulate the problem by using a random Ising model in statistical physics. However, a kind of computational difficulty arises in a case that the number of nodes becomes large. Hence approximation schemes such as a mean field approximation and a Bethe approximation have been used extensively for overcoming the difficulty. When frustration is essential in some problems, the Bethe approximation gives unfavorable results. In those problems, more advanced approximation schemes are needed beyond the Bethe approximation. In the present paper, we present explicitly the triangular approximation, which is the next approximation to the Bethe approximation. We apply the obtained approximation scheme to a Boltzmann machine in order to investigate the validity of the triangular approximation.     

Adaptive Cluster Expansion for the Inverse Ising Problem: Convergence,Algorithm and Tests

We present a procedure to solve the inverse Ising problem, that is, to find the interactions between a set of binary variables from the measure of their equilibrium correlations. The method consists in constructing and selecting specific clusters of spins, based on their contributions to the cross-entropy of the Ising model. Small contributions are discarded to avoid overfitting and to make the computation tractable. The properties of the cluster expansion and its performances on synthetic data are studied. To make the implementation easier we give the pseudo-code of the algorithm.     

Monte Carlo Transition Dynamics and Variance Reduction

For Metropolis Monte Carlo simulations in statistical physics, efficient, easy- to-implement, and unbiased statistical estimators of thermodynamic properties are based on the transition dynamics. Using an Ising model example, we demonstrate (problem-specific) variance reductions compared to conventional histogram estimators. A proof of variance reduction in a microstate limit is presented.     

Potts model on complex networks

We consider the general p-state Potts model on random networks with a given degree distribution (random Bethe lattices). We find the effect of the suppression of a first order phase transition in this model when the degree distribution of the network is fat-tailed, that is, in more precise terms, when the second moment of the distribution diverges. In this situation the transition is continuous and of infinite order, and size effect is anomalously strong. In particular, in the case of p = 1, we arrive at the exact solution, which coincides with the known solution of the percolation problem on these networks.Received: 3 December 2003, Published online: 17 February 2004PACS: 05.10.-a Computational methods in statistical physics and nonlinear dynamics - 05.40.-a Fluctuation phenomena, random processes, noise, and Brownian motion - 05.50. + q Lattice theory and statistics (Ising, Potts, etc.) - 87.18.Sn Neural networks     

Vertex cover problem studied by cavity method: Analytics and population dynamics

We study the vertex cover problem on finite connectivity random graphs by zero-temperature cavity method. The minimum vertex cover corresponds to the ground state(s) of a proposed Ising spin model. When the connectivity c > e = 2.718282, there is no state for this system as the reweighting parameter y, which takes a similar role as the inverse temperature β in conventional statistical physics, approaches infinity; consequently the ground state energy is obtained at a finite value of y when the free energy function attains its maximum value. The minimum vertex cover size at given c is estimated using population dynamics and compared with known rigorous bounds and numerical results. The backbone size is also calculated. Received 11 November 2002 Published online 1st April 2003 RID="a" ID="a"e-mail: zhou@mpikg-golm.mpg.de     

Relaxation phenomena at criticality

The collective behaviour of statistical systems close to critical points is characterized by an extremely slow dynamics which, in the thermodynamic limit, eventually prevents them from relaxing to an equilibrium state after a change in the thermodynamic control parameters. The non-equilibrium evolution following this change displays some of the features typically observed in glassy materials, such as ageing, and it can be monitored via dynamic susceptibilities and correlation functions of the order parameter, the scaling behaviour of which is characterized by universal exponents, scaling functions, and amplitude ratios. This universality allows one to calculate these quantities in suitable simplified models and field-theoretical methods are a natural and viable approach for this analysis. In addition, if a statistical system is spatially confined, universal Casimir-like forces acting on the confining surfaces emerge and they build up in time when the temperature of the system is tuned to its critical value. We review here some of the theoretical results that have been obtained in recent years for universal quantities, such as the fluctuation-dissipation ratio, associated with the non-equilibrium critical dynamics, with particular focus on the Ising model with Glauber dynamics in the bulk. The non-equilibrium dynamics of the Casimir force acting in a film is discussed within the Gaussian model.     

Non-Abelian Random Polygons: A New Model in Statistical Physics

A model in statistical physics is presented based on assigning non-Abelian phase factors to the turning points of polygons in three dimensions. This model allows for an exact solution and exhibits an unexpectedly rich phase structure. The model as well as the solution are obtained by a generalization of the methods of Kac and Ward and by mapping the problem to a Markov process as was done by Feynman for the two-dimensional Ising model     

Inference and phase transitions in the detection of modules in sparse networks

We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks generated by stochastic block models. Using the cavity method of statistical physics and its relationship to belief propagation, we unveil a phase transition from a regime where we can infer the correct group assignments of the nodes to one where these groups are undetectable. Our approach yields an optimal inference algorithm for detecting modules, including both assortative and disassortative functional modules, assessing their significance, and learning the parameters of the underlying block model. Our algorithm is scalable and applicable to real-world networks, as long as they are well described by the block model.     

Orthogonal Polynomials on the Unit Circle with Fibonacci Verblunsky Coefficients, II. Applications

We consider CMV matrices with Verblunsky coefficients determined in an appropriate way by the Fibonacci sequence and present two applications of the spectral theory of such matrices to problems in mathematical physics. In our first application we estimate the spreading rates of quantum walks on the line with time-independent coins following the Fibonacci sequence. The estimates we obtain are explicit in terms of the parameters of the system. In our second application, we establish a connection between the classical nearest neighbor Ising model on the one-dimensional lattice in the complex magnetic field regime, and CMV operators. In particular, given a sequence of nearest-neighbor interaction couplings, we construct a sequence of Verblunsky coefficients, such that the support of the Lee-Yang zeros of the partition function for the Ising model in the thermodynamic limit coincides with the essential spectrum of the CMV matrix with the constructed Verblunsky coefficients. Under certain technical conditions, we also show that the zeros distribution measure coincides with the density of states measure for the CMV matrix.     

Non-equilibrium physical systems approach to modeling evolution of optical fiber reliability

We propose a new approach, based on physics of non-equilibrium systems, to modeling optical fiber reliability. Unlike the traditional approach to statistical modeling of fracture, the presented one describes the phenomenon in terms of its dynamics and links the thermal-fluctuation damage events with the corresponding strength deterioration, thereby establishing an evolution equation of the time-dependent strength distribution. The developed model is validated by both simulations and experimental data.     

Progress in physical properties of Chinese stock markets

In the past two decades, statistical physics was brought into the field of finance, applying new methods and concepts to financial time series and developing a new interdiscipline “econophysics”. In this review, we introduce several commonly used methods for stock time series in econophysics including distribution functions, correlation functions, detrended fluctuation analysis method, detrended moving average method, and multifractal analysis. Then based on these methods, we review some statistical properties of Chinese stock markets including scaling behavior, long-term correlations, cross-correlations, leverage effects, antileverage effects, and multifractality. Last, based on an agent-based model, we develop a new option pricing model — financial market model that shows a good agreement with the prices using real Shanghai Index data. This review is helpful for people to understand and research statistical physics of financial markets.     

Tricritical Points and Reentry in the Quantum Hopfield Neural-Network Model

We examine a quantum Hopfield neural-network model in the presence of trimodal random transverse fields and random neuronal thresholds within the method of statistical physics. We use the Trotter decomposition to map the problem into an equivalent classical random Hopfield-type Ising model and obtain phase transitions between the ferromagnetic retrieval and the paramagnetic phases. The influence of competition between the diluted random transverse fields and the diluted random thresholds on the system is discussed, and some interesting results such as tricritical points and reentrance are analyzed.     

Ernst Ising—Physicist and Teacher

The Ising model is one of the standard models in statistical physics. Since 1969 more than 13800 publications using this model have appeared. In 1997 Ernst Ising celebrated his 97th birthday. Some biographical notes and milestones of the development of the Ising model are given.     

Connectivity degrees in the threshold preferential attachment model

In this paper we present a study of the connectivity degrees of the threshold preferential attachment model, a generalization of the Barabási-Albert model to heterogeneous complex networks. The threshold model incorporates the states of the nodes in its preferential linking rule and assumes that the affinity between network nodes follows an inverse relationship with the distance between their states. We numerically analyze the connectivity degrees of the model, studying the influence of the main parameters on the distribution of connectivity degrees and its statistics, the average degree and highest degree of the network. We show that such statistics exhibit markedly different behaviors in the dependence on the model parameters, particularly as regards the interaction threshold. Nevertheless, we show that the two statistics converge in the limit of null threshold and often exhibit scaling that can be described by power laws of the model parameters.     

Credit risk—A structural model with jumps and correlations

We set up a structural model to study credit risk for a portfolio containing several or many credit contracts. The model is based on a jump-diffusion process for the risk factors, i.e. for the company assets. We also include correlations between the companies. We discuss that models of this type have much in common with other problems in statistical physics and in the theory of complex systems. We study a simplified version of our model analytically. Furthermore, we perform extensive numerical simulations for the full model. The observables are the loss distribution of the credit portfolio, its moments and other quantities derived thereof. We compile detailed information about the parameter dependence of these observables. In the course of setting up and analyzing our model, we also give a review of credit risk modeling for a physics audience.