The edge of chaos

Computation, evolution, competition and other past-times of faculty

December 2, 2016 — October 30, 2022

dynamical systems
machine learning
neural nets
stochastic processes
Figure 1

I did not create an edge-of-chaos notebook for a while because I could not face the task of sifting through the woo-woo silt to find the gold. There is some gold, though, and also some iron pyrites which is still nice to look at, and some fun ideas, and also a wacky story of cranks, mavericks and Nobel prizes and hype which is interesting in its own right.

Name check: criticality, which is also perhaps related to dynamical stability, and ergodicity, and inevitably to fractals because of scaling relations. Somewhere out of this, a theory of algorithmic statistics might emerge.

Maybe information bottlenecks also?

1 History

Start with Crutchfield and Young (1988);Chris G. Langton (1990) which introduce the association between the edge of chaos and computing.

2 Which chaos? Which edge?

Two ingredients seem to be popular: a phase transition model and an assumed computation model. TBD

3 In life

Figure 2


4 Neural nets

A resurgence of interest in edge of chaos is in the undifferentiated, random computational mess of neural networks, which do look in fact a lot like a system which should demonstrate edge-of-chaos computation if anything does. See also statistical mechanics of statistics.

Hayou et al. (2020) argues that deep networks are trainable when they are in some sense poised upon an edge-of-chaos. Apparently build upon (Hayou, Doucet, and Rousseau 2019; Schoenholz et al. 2017). To revisit.

Roberts, Yaida, and Hanin (2021) may or may not relate:

This book develops an effective theory approach to understanding deep neural networks of practical relevance. Beginning from a first-principles component-level picture of networks, we explain how to determine an accurate description of the output of trained networks by solving layer-to-layer iteration equations and nonlinear learning dynamics. A main result is that the predictions of networks are described by nearly-Gaussian distributions, with the depth-to-width aspect ratio of the network controlling the deviations from the infinite-width Gaussian description. We explain how these effectively-deep networks learn nontrivial representations from training and more broadly analyze the mechanism of representation learning for nonlinear models. From a nearly-kernel-methods perspective, we find that the dependence of such models’ predictions on the underlying learning algorithm can be expressed in a simple and universal way. To obtain these results, we develop the notion of representation group flow (RG flow) to characterize the propagation of signals through the network. By tuning networks to criticality, we give a practical solution to the exploding and vanishing gradient problem. We further explain how RG flow leads to near-universal behavior and lets us categorize networks built from different activation functions into universality classes. Altogether, we show that the depth-to-width ratio governs the effective model complexity of the ensemble of trained networks. By using information-theoretic techniques, we estimate the optimal aspect ratio at which we expect the network to be practically most useful and show how residual connections can be used to push this scale to arbitrary depths. With these tools, we can learn in detail about the inductive bias of architectures, hyperparameters, and optimizers.

To read: (Bertschinger, Natschläger, and Legenstein 2004; Bertschinger and Natschläger 2004).

5 Incoming

6 References

Bak, Tang, and Wiesenfeld. 1988. Self-Organized Criticality.” Physical Review A.
Bertschinger, and Natschläger. 2004. Real-Time Computation at the Edge of Chaos in Recurrent Neural Networks.” Neural Computation.
Bertschinger, Natschläger, and Legenstein. 2004. At the Edge of Chaos: Real-Time Computations and Self-Organized Criticality in Recurrent Neural Networks.” In Advances in Neural Information Processing Systems.
Colley, and Dean. 2019. Origins of 1/f Noise in Human Music Performance from Short-Range Autocorrelations Related to Rhythmic Structures.” PLoS ONE.
Crutchfield. 1994. The Calculi of Emergence: Computation, Dynamics and Induction.” Physica D: Nonlinear Phenomena.
Crutchfield, and Young. 1988. “Computation at the Onset of Chaos.”
Hayou, Doucet, and Rousseau. 2019. On the Impact of the Activation Function on Deep Neural Networks Training.” In Proceedings of the 36th International Conference on Machine Learning.
Hayou, Ton, Doucet, et al. 2020. Pruning Untrained Neural Networks: Principles and Analysis.” arXiv:2002.08797 [Cs, Stat].
Hsü, and Hsü. 1991. Self-Similarity of the ‘1/f Noise’ Called Music. Proceedings of the National Academy of Sciences.
Kanders, Lorimer, and Stoop. 2017. Avalanche and Edge-of-Chaos Criticality Do Not Necessarily Co-Occur in Neural Networks.” Chaos: An Interdisciplinary Journal of Nonlinear Science.
Kauffman. 1993. The Origins of Order: Self-Organization and Selection in Evolution.
Kelso, Mandell, and Shlesinger. 1988. Dynamic Patterns in Complex Systems.” In Dynamic Patterns in Complex Systems.
Krishnamurthy, Can, and Schwab. 2022. Theory of Gating in Recurrent Neural Networks.” Physical Review. X.
Krotov, Dubuis, Gregor, et al. 2014. Morphogenesis at Criticality.” Proceedings of the National Academy of Sciences.
Langton, Christopher G. 1986. Studying Artificial Life with Cellular Automata.” Physica D: Nonlinear Phenomena, Proceedings of the Fifth Annual International Conference,.
Langton, Chris G. 1990. Computation at the Edge of Chaos: Phase Transitions and Emergent Computation.” Physica D: Nonlinear Phenomena.
Laurent, and von Brecht. 2016. A Recurrent Neural Network Without Chaos.” arXiv:1612.06212 [Cs].
Mitchell, M., Crutchfield, and Hraber. 1993. Dynamics, Computation, and the ‘Edge of Chaos’: A Re-Examination.”
Mitchell, Melanie, Hraber, and Crutchfield. 1993. Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations.” arXiv:adap-Org/9303003.
Mora, and Bialek. 2011. Are Biological Systems Poised at Criticality? Journal of Statistical Physics.
Packard. 1988. Adaptation Toward the Edge of Chaos.
Prokopenko, Boschetti, and Ryan. 2009. An Information-Theoretic Primer on Complexity, Self-Organization, and Emergence.” Complexity.
Roberts, Yaida, and Hanin. 2021. The Principles of Deep Learning Theory.” arXiv:2106.10165 [Hep-Th, Stat].
Scarle. 2009. Implications of the Turing completeness of reaction-diffusion models, informed by GPGPU simulations on an XBox 360: cardiac arrhythmias, re-entry and the Halting problem.” Computational Biology and Chemistry.
Schoenholz, Gilmer, Ganguli, et al. 2017. Deep Information Propagation.” In.
Sompolinsky, Crisanti, and Sommers. 1988. Chaos in Random Neural Networks.” Physical Review Letters.
Su, Chen, Cai, et al. 2020. Sanity-Checking Pruning Methods: Random Tickets Can Win the Jackpot.” In Advances In Neural Information Processing Systems.
Torres-Sosa, Huang, and Aldana. 2012. Criticality Is an Emergent Property of Genetic Networks That Exhibit Evolvability.” PLOS Computational Biology.
Upadhyay. 2009. Dynamics of an Ecological Model Living on the Edge of Chaos.” Applied Mathematics and Computation.
Voss, and Clarke. 1978. ‘1/f Noise’ in Music: Music from 1/f Noise.” The Journal of the Acoustical Society of America.
Zhang, Li, Shen, et al. 2020. The Expressivity and Training of Deep Neural Networks: Toward the Edge of Chaos? Neurocomputing.