Complex Systems Summer SChool 2012-Lecture Readings

Complex Systems Summer School 2012

Liz Bradley

NetLogo Lorenz attractor (Right click - save - open with Netlogo 3D)

Lorenz Water Wheel (Right click - save - open in Netlogo)

TISEAN

TISEAN 3.0.1: Nonlinear Time Series Analysis Software

Jim Crutchfield

Lecture 1.1
Lecture 1.2
Lecture 2.1
Lecture 2.2

Ryan

Information Theory for Tralfamadorians

Simon DeDeo

Thank you for your engagement, your willingness to join an adventure, and your contributions to critical debate. I look forward to following the collective output of CSSS 2012 for many years to come.

Computation in Natural Systems

Cris Moore's Lecture notes on automata, languages, and grammars covers, elegantly, all of the basic automata concepts in the lecture, and much more besides. A supplement to The Nature of Computation.

Jim Crutchfield & Karl Young's paper, Computation at the Onset of Chaos provides a detailed and compelling account of (among other things) how a naturalistic process (in this case, the logistic map) violates the bounds of both the regular and context-free grammars.

For an introduction to the connection between (semi)groups and the regular grammars, as well as a preview of the Emergence module, see Effective Theories for Circuits and Automata.

Data on the edit histories of the George Bush wikipedia article, along with ruby code to read in and otherwise play, can be downloaded here.

Statistics and Stochastic Processes

Overall book: David J.C. MacKay, Information Theory, Inference, and Learning Algorithms.

Lecture 1 (Thursday)

E.T. Jaynes' Information Theory and Statistical Mechanics (free copy).

Elliott W. Montroll On the entropy function in sociotechnical systems. Focus on the Sears-Roebuck Catalog; we will read this critically in class. Optional: Thermodynamic Treatment of Nonphysical Systems: Formalism and an Example (Single-Lane Traffic) (with Reiss & Hammerich; see touching "Note in Closing").

Tkacik, Schneidman, Berry, and Bialek. Ising Models for Networks of Real Neurons. Optional (but compelling; see back to Montroll's PNAS paper, top left of pg. 7841): Mora and Bialek, Are biological systems poised at criticality?

Lectures 2 & 3 (Friday)

Null models & significance testing. DeDeo, Krakauer & Flack. Evidence of strategic periodicities in collective conflict dynamics (free copy). Optional: Weidmann & Toft. Promises and Pitfalls in the Spatial Prediction of Ethnic Violence (a critical examination of the claims in this Science article.)

Parameter Estimation and Bayesian Reasoning. Clauset, Shalizi & Newman Power-law distributions in empirical data.

Model selection. Cosma Shalizi on Methods for Selection. David Deutsch on Scientific Argument. Optional: Multi-Model Inference (AIC).

Data and analysis code for the seating of students in the June 14th lecture, including basic code to implement null models for gender and field distribution, is available here.

Additional material on the thermodynamics of computation. Bennett, the Thermodynamics of Computation—a Review (free copy). Landauer, Computation: a Fundamental Physical View (free copy). Anthology of articles: Maxwell's Demon 2

Emergence

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 using the Krohn-Rhodes theorem (Lecture Two) for the construction of theories that show incommensurate symmetries.

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)

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.) The Central Limit Theorem as an example of "Universality" (skip Sec. 3.4 on Lattice Green Functions, unless you live in a crystal.) Both from Leo Kadanoff's readable (if you have some background in physics, chemistry or biochemistry) book Statistical Physics: Statics, Dynamics and Renormalization.

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 (and 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 very readable accounts of "explanation" (your lecturer does not follow his latter 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 of that mindset, 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, from an 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.