Wednesday, September 19, 2012

Three Lectures by Simon DeDeo from the Santa Fe Institute 2012 Complex Systems Summer School

There are three lectures embedded in the video below given by Simon DeDeo during the Santa Fe Institute 2012 Complex Systems Summer School, an interdisciplinary course for graduate and postdoctoral students in the mathematical, biological, cognitive and social sciences.
Full bibliography.
Below the video is much more detailed information on the lectures.

CSSS 2012 — Emergence

Update: all three Emergence lectures are now online, on both youtube and iTunes U. Lecture One ; Lecture Two ; Lecture Three.

We gave two accounts of emergence: one dealing largely with the properties of a system under coarse graining, the other dealing with the phenomenon of symmetry breaking.

Effective Theories for Circuits and Automata (free copy) is the guide for the first one, and makes a case for the use of coarse-graining and renormalization (Lecture One) in computational/functional systems that are not governed by a spatial organization (Lecture Two).

The second is much more widely discussed, and has made its way into the literature beyond the physical and mathematical sciences.

Lecture 1 (Monday morning)

The Central Limit Theorem as an example of Universality (skip Sec. 3.4 on Lattice Green Functions, unless you live in a crystal.) Aggregation (i.e., considering a system with more and more agents) One Particle and Many (skip Sec. 2.3 unless you are near zero Kelvin.) Both from Leo Kadanoff's readable (if you have some background in physics, chemistry or biochemistry) book Statistical Physics: Statics, Dynamics and Renormalization.

The third “universality class” — i.e., limiting distribution — that we discussed in our cartoon introduction (in addition to the log-normal, for languages, and the Fisher log-series, for ecosystems) is introduced in a Nature paper by Bohorquez, Gourley, Dixon, Spagat and Johnson in 2009.

The failure of Black-Scholes is discussed from the Mandelbrot point of view in many places, including The Misbehavior of Markets. The somewhat less media/physicist friendly account by Warren Buffet on how the non-stationary variance of the market functions is also worth reading, from his 2008 letter to shareholders (page 19.)

Robert Batterman's book, Asymptotic Reasoning in Explanation, Reduction, and Emergence has a readable and inspiring account of "explanation" and the role of effective theories. (Note that your lecturer does not follow his later account of emergence, which we discussed in a very different fashion.)

Our account of coarse-graining and renormalization group flow draws (hopefully clearly) from the very technical literature. One nice place to look if you have a physics mind-set is Michael Fisher's article, Ch. IV.8, in Conceptual Foundations of Quantum Field Theory (which includes a number of amazing articles, if you are game, on renormalization, effective theories, and emergence.)

Lecture 2 (Monday afternoon)

Techniques for finding the Bayesian best-match probabilistic finite state machine (a.k.a., Hidden Markov Model) for a particular string of observed behavior are described in Numerical Recipes, 3rd. Ed. (Press et al.) Chapter 16.3. Tapas Kanungo has a nice implementation of the E-M algorithm that is (somewhat) industry standard for the simple case.

We played Contrapunctus XIV in an arrangement for strings by the Emerson String Quartet. Then we played it again in MIDI form in Mathematica, then we truncated to the top two voices, and shifted both into a single octave to arrive at the process with only 104 output symbols (some of the 12x12 possible chords Bach did not use.) Then we tried to fit this process by a 12-state Hidden Markov Model. It did not sound very good, and this allowed us to discuss the limitations of finite state machines for processes with multiple timescales, hierarchies of interacting processes, and systems of greater computation complexity (e.g., the parenthesis-matching game.)

You may want to know how far Machine Learning can be pushed to produce "Bach-like" music, and whether (approximations to) higher-complexity processes might improve it. This is discussed in charming detail in Baroque Forecasting, by Matthew Durst and Andres S. Weigend, in Time Series Prediction, a volume from early meeting at SFI.

Group Theory, and the extension of the Jordan-Holder decomposition of groups to semigroups (i.e., the more general class of finite state machines with irreversible operations, such as the ABBA machine), forms a central theme of our discussion. Some very charming introductions to group theory exist (if one is not able to attend Douglas Hofstadter's classes at I.U.!) -- one perhaps suitable for visual thinkers is Visual Group Theory.

The Krohn-Rhodes theorem, which proves the consistency of a hierarchy of coarse-grainings for finite state machines, gets complicated. References to excellent papers by Christopher Nehaniv, Attila Egri-Nagy, and others can be found in the Effective Theories paper referenced above. The "Wild Book", photocopied and passed around in the 1970s, that made the case for the importance of the theorem, is now re-issued in a revised and edited version as Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games (just in case you thought there was something it might not apply to.)

Lecture 3 (Tuesday morning)

Our account of symmetry breaking as a canonical form of emergence is inspired by the foundational article More is Different (free copy), by SFI co-founder Phil Anderson.

The discussion of symmetry breaking in turbulence as one alters the control parameter is described elegantly in the beginning of Uriel Frisch's Turbulence.

Order Parameters, Broken Symmetry, and Topological Defects, by James P. Sethna is a readable and clear account of how this plays out in physics (that gets very advanced by the end!)

Our major example of a phase transition in a social/decision-making system was that found for the Minority Game when agents build strategies out of a finite-history list, from a paper by Damien Challet and Matteo Marsili (free copy). An excellent summary of what we know about the humble El Farol bar is at Minority Games: Interacting Agents in Financial Markets.

No comments: