Complexity, Phase Transitions, and Inference by Cristopher Moore (part 1)
3,071 views · Published 3 July 2016 · 1:08:59 · Indexed 30 October 2026
Channel: International Centre for Theoretical Sciences · 2016 · Science & Technology
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
More from this channel
-
49:14
The Universe Unravelled - P. James Peebles
-
1:04:26
The Origin of Life - from geophysics to biology - Albert Libchaber
-
1:15:34
Advances in Graphene, Majorana Fermions, Quantum Computation ( 2 ) - Sankar Das Sarma
-
1:14:26
Applied String Theory (Lecture 2) Dam Thanh Son
-
1:03:07
The Generalized Ramanujan Conjectures and Applications (Lecture 4) by Peter Sarnak
-
1:59:54
Scattering Without Space Time (Lecture 3) Nima Arkani Hamed
-
1:02:19
The Quantum Phases of Matter (Lecture 3) by Subir Sachdev
-
1:15:10
The Generalized Ramanujan Conjectures and Applications (Lecture 3) by Peter Sarnak