Unlocking the Secrets of Complexity and Phase Transitions in Inference 🔍 (Part 1)

There is a deep analogy between statistical inference and statistical physics. I will give a friendly introduction to both of these fields. I will then discuss phase transitions in problems like community detection in networks, and clustering of sparse high-dimensional data, where if our data becomes too sparse or too noisy it becomes impossible to find the underlying pattern; moreover, I will discuss optimal algorithms that succeed as well as possible up to this point. Along the way, I will visit ideas from computational complexity, random graphs, random matrices, and spin glass theory.


This lecture is part of Games, Epidemics and Behavior

Table of Contents (powered by https://videoken.com)
0:00:00 ICTS
0:00:04 CENTRE for
0:00:11 Christopher Moore, Santa Fe Institute
0:01:18 Statistical inference statistical physics
0:05:20 Why least squares?
0:06:26 A model of noise
0:08:12 From probability to energy
0:09:11 Changing the model
0:11:59 Uncertainty, equilibrium, and the energy landscape
0:16:03 The Ising model of magnetism
0:21:10 Bumpy landscapes
0:24:09 Divided we blog
0:24:49 Who eats whom
0:25:23 I record that I was born on a Friday
0:25:56 The stochastic block model
0:29:09 Likelihood and energy
0:33:35 Overfitting
0:35:27 Information in the block model: the effect of a link
0:39:14 Detectability thresholds
0:45:28 Clustering high-dimensional data
0:48:17 Techniques
0:52:39 A little light reading
0:53:15 Detectability thresholds