Statistical Physics and Interdisciplinary Applications

Given some partial information about a system we like to reconstruct the interaction pattern of its elements. These elements can be neurons in a neural network, genes in a cell, pixels in an image or computers in the Internet. In the simplest scenario we assume that elements take only two states and interact pairwise. In this talk I will introduce some methods that people use to deal with this problem.

References:
[1] William Bialek et. al, Faster solutions of the inverse pairwise Ising problem, 2007.
[2] M. Mezard and T. Mora, Constraint satisfaction problems and neural networks: a statistical physics perspective, 2008.

The cavity method is a well established technique for solving classical spin models on sparse random graphs (mean-field models with finite connectivity). Laumann, Scardicchio and Sondhi [arXiv:0706.4391] proposed recently an extension of this method to quantum spin-1/2 models in a transverse field, using a discretized Suzuki-Trotter imaginary time formalism. Here we show how to take analytically the continuous imaginary time limit. Our main technical contribution is an explicit procedure to generate the spin trajectories in a path integral representation of the imaginary time dynamics. As a side result we also show how this procedure can be used in simple heat-bath like Monte Carlo simulations of generic quantum spin models. The replica symmetric continuous time quantum cavity method is formulated for a wide class of models, and applied as a simple example on the Bethe lattice ferromagnet in a transverse field. The results of the methods are confronted with various approximation schemes in this particular case. On this system we performed quantum Monte Carlo simulations that confirm the exactness of the cavity method in the thermodynamic limit.

Reference:
[1] F. Krzakala, A. Rosso, G. Semerjian and F. Zamponi, (2008) .

Go is an ancient Chinese game that originated some 4000 years ago and has still great popularity nowadays. Computer Go on the other hand has made little progress in these 4000 years: best go programs are rated like middle-to-weak amateur human players. We will discuss one recent approach to computer go [¹], based on a mixture of two relatively well known strategies: the UCT algorithm and Monte Carlo, which happens to be the most successful one to date.

Reference:
[1] Modification of UCT with Patterns in Monte-Carlo Go, S. Gerlly, Y. Wang, R. Munos and O.Teytaud, INRIA Technical Report, 2006.

I will present part of my PhD work in phylogeny. Phylogeneticists use comparative data to reconstruct the "genealogy" of taxa (usually, species or genuses): a "phylogeny". The data can be morphological characters, DNA sequences, etc. A practical problem is that on large groups, different datasets tend to produce trees that are not the same. By comparing trees obtained from different independent datasets, one can get an idea of which clades (groups of taxa) are reliable and which are not. The more a group is repeated, the more it is reliable. I tried to formalize this principle into a "repetition index" that can be attributed to clades. One essential difficulty is that datasets often contain missing data; therefore, trees are not built on the same set of species.

Gaussian mixtures have been used in many mathematical and computational models to approximate arbitrary distributions. Nonparametric Belief Propagation (NBP) algorithms use Gaussian mixtures to approximated the message and belief distributions in cases where discretized representations may become unfeasible. The key issue in Gaussian mixture based NBP is the computation of products of Gaussian mixtures. In this talk, I will introduce the approach I developed to approximate Gaussian mixture product efficiently based on a Gaussian mixture reduction technique. This approach was integrated into a NBP algorithm with a simple model for the stereo matching problem.