Cristopher Moore - Santa Fe Institute
Wednesday, August 30th, 10:45AM EDT (Zoom meeting starts at 10:30 EDT)
The physics of inference, phase transitions, and networks
Finding patterns in data is a lot like finding ground states in physics. Each "state" corresponds to a hypothesis about the data, and the most-likely state is the one with the lowest energy. More generally, the Boltzmann distribution corresponds to the posterior distribution in Bayesian statistics. But reaching equilibrium can be hard, especially in glassy systems. We can get stuck for exponential time at local optima that have nothing to do with the true pattern, and are separated from the "correct" state by energy barriers. In many problems, this creates phase transitions where finding patterns in noisy data suddenly becomes computationally hard or impossible. These transitions occur when the amount of noise in the data-which is analogous to the temperature-crosses a critical threshold. I'll discuss these phase transitions using an example from the study of social networks, where we try to classify nodes according to which community they belong to.