This fall I read a couple of books about complexity: A Crude Look at the Whole by John H. Miller and Complexity: A Guided Tour by Melanie Mitchell. For my final post of the year (except for an upcoming year in review post), I've reviewed these books and the concepts they cover.

I've included two books in a book review post before (here, for example), but this time I decided to do something a bit different and read two books on the same subject for a single post. Given that the subject is complexity itself, the insight provided by more than one perspective also seemed like it would be beneficial. Miller and Mitchell are actually associated with the same institute (the Santa Fe Institute), but there was enough unique about each of their books that it certainly wasn't a waste of time to read both of them. I'll have more to say later on comparing the two books.

To start with, what is complexity? Miller contrasts it with reductionism; complex systems are ones that are more than a straightforward sum of their parts. To put it another way, complexity arises when interaction effects are a key feature of a system:

The reductionist approach to the world—breaking down complicated things to their constituent parts and then carefully dissecting these parts until we know them—has provided a useful Archimedean purchase from which to lever our complex world into the light of understanding. Unfortunately, there is only so far we can move the world using such tools. As we have seen throughout this book, knowing the parts is not equivalent to knowing the whole. Reduction does not tell us about construction. This is the fundamental insight of the study of complex systems. Even if we could fully understand how an individual worker bee’s, market trader’s, or neuron’s behavior is determined by its environment, we would have little idea about how a hive, market, or brain works. To truly understand hives, markets, and brains, we need to understand how the interactions of honeybees, traders, and neurons result in system-wide, aggregate behavior.

Mitchell points out that complexity is not a single scientific field but an interdisciplinary effort to find transferrable insights between diverse systems that exhibit complex behaviour:

As you can glean from the wide variety of topics I have covered in this book, what we might call modern complex systems science is, like its forebears, still not a unified whole but rather a collection of disparate parts with some overlapping concepts.

And she concedes that a unified whole may not be possible. It is still an area of active research. But from the variety of examples given in both books, the analytical toolkit from studying complexity seems to have a lot of potential for advancing our understanding of the world.

Miller lists some features/principles of complexity:

there are fundamental principles governing our world—such as emergence and organization—that appear in various guises across all of the nooks and crannies of science.

 

Interacting systems develop feedback loops among the agents, and these loops drive the system’s behavior. Such feedback is moderated or exacerbated depending on the degree of heterogeneity among the agents. Interacting systems also tend to be inherently noisy, and such randomness can have surprising global consequences. Of course, who interacts with whom is a fundamental property of these systems, and such networks of interaction are an essential element of complex systems. Core principles such as feedback, heterogeneity, noise, and networks can be used to understand new layers of complexity.

Some mathematical concepts that appear in both books are cellular automata and networks. These concepts have appeared before on my blog.

Having covered that background, I'm going to compare the two books then share and discuss some of the concepts and examples that they each cover.

A Crude Look at the Whole was a quicker read than Complexity: A Guided Tour (I read most of the former on a couple of domestic flights). So if you're looking for an introduction to the subject, Miller's book is probably where I'd recommend starting. However, I wouldn't say Mitchell's book gets a lot more in-depth—the added length has more to do with going through the historical developments that led to the present field of complexity, along with drawing on more examples. Miller's book felt more unified (the excerpts above about eschewing reductionistic approaches and understanding interactions capture its theme) while Mitchell's book tries to cover the breadth of the field so the specific examples don't always fit together as neatly. The strength of Mitchell's book is the clear explanation of complicated topics like Turing machines and genetic algorithms—with worked-out examples in some cases. I'll mention more of these examples below. Complexity: A Guided Tour also includes a personal touch, with photos of people who contributed to the development of the field (the author seems to have personally met most of them who are still living).

Starting with Miller's book (A Crude Look at the Whole) I want to share some things that I learned or found interesting:

  • He describes how bees maintain a comfortable temperature in their hives: individual bees can buzz to generate heat when they are cold or fan their wings to circulate air when they are hot. If every bee had exactly the same temperature setpoint the hive would oscillate rapidly between too hot and too cold as the bees alternated their behaviours. However, since each bee is slightly different, there is a smooth transition instead. As it cools off, for example, a few bees at a time will start huddling together and buzzing for warmth, according to their individual setpoints.

  • Bees are also used as an example with respect to how they choose a new hive location. Scouts go out and look for potential locations, but a single scout cannot make a decision on behalf of the entire hive. When they return to the swarm, they do a dance describing the location they have found. Other bees may be inspired to go check it out. Meanwhile, scouts from other locations are returning and doing their own dances. When enough scouts are returning and describing the same location a quorum is reached and the whole swarm will cascade to that site for a new hive.

  • Cellular automata are an example of how simple rules/behaviour and local interactions can produce complex large-scale results:

cellular automata are able to capture the essence of an important phenomenon in a very exact and sparse way. By doing so, they provide a constructive proof of how simple local rules can have complex global implications. There is an alternative form of complexity that is also of interest, namely, systems where complex local behavior results in a simple global outcome.

  • He discussed the flash crash in 2010 that was driven at least in part by unforeseen interactions between high-frequency trading algorithms. It was brought under control when an automatic "circuit breaker" halted trading for a brief window of time.

  • His discussion of the value of circuit breakers/firebreaks in an age when so many things are interconnected like never before made me think about social media. When a single thoughtless joke can trigger a global shame mob in less time than it takes for an intercontinental flight to reach its destination, maybe a good resolution for 2019 would be to pause before sharing something negative.

  • Simulated annealing is a way to introduce noise into algorithms to keep them from getting stuck at local maxima.

  • Self-organized criticality is when a system has built up enough internal energy that any further addition could trigger a cascade of any size, up to encompassing the entire system (the size distribution follows a power law). Here is a video explaining this concept. Aside from the simple sandpile model, the author gives the example of the Arab Spring which was triggered by the protest of a single merchant in Tunisia against routine bureaucratic opposition—but it resonated with enough people's grievances to start a region-wide movement.

  • Miller discusses some of his own research into game theory explanations of decentralized cooperation in irrigation in Bali in Chapter 10.

  • Finally, here are a few more excerpts from A Crude Look at the Whole that I found insightful:

Our very existence relies on the complex systems that bind our food supplies to our energy networks to our global climate to every institution in our society. We have grown to a sheer size and degree of connectivity where local actions now have global consequences.

 

Complex systems, whether intentional or not, are playing an increasingly important role in our world. While we might not ever be able to fully control such systems, we may be able to mitigate their downsides through the clever introduction of metaphorical firebreaks such as the circuit breakers that are used in financial markets. Our understanding of how to create such controls is lagging well behind our need to implement them, and we must quickly develop this knowledge so that the kingdom won’t be lost for want of a nail.

 

Anytime we interconnect systems, we build in feedback loops. ... We often hear that some disastrous event was the result of a “perfect storm” of events. However, in a world of increasing complexity, we are simply perfecting our ability to create such storms.

Moving on to Mitchell's book (Complexity: A Guided Tour), one of her main themes is how complex and adaptive behaviour can be produced from simple rules. Four areas she considers under this theme are information, computation, dynamics/chaos, and adaptation. Here are some things from her book that I found interesting.

  • Given that I'm discussing this book online, this quote about the internet is suitably meta:

the Web can be thought of as a self-organizing social system: individuals, with little or no central oversight, perform simple tasks: posting Web pages and linking to other Web pages. However, complex systems scientists have discovered that the network as a whole has many unexpected large-scale properties involving its overall structure, the way in which it grows, how information propagates over its links, and the coevolutionary relationships between the behavior of search engines and the Web’s link structure, all of which lead to what could be called “adaptive” behavior for the system as a whole.

  • Early in the book, major milestones in information and computation* theory are laid out with very clear explanations. These include Turing machines (as mentioned above), the halting problem, and the work of Claude Shannon. There is also a nice discussion of the Maxwell's demon thought experiment and Szilárd's answer to it (that the act of measuring increases entropy—amended by later scholars to the fact that erasing/overwriting memory increases entropy).
    * Mitchell uses computation as a technical term for the general process of "what a complex system does with information in order to succeed or adapt in its environment."

  • One very interesting point was how complete prediction of deterministic systems is not possible in a complex world. This is due to the uncertainty principle, chaos theory (sensitive dependence on initial conditions), and the halting problem:

However, two major discoveries of the twentieth century showed that Laplace’s dream of complete prediction is not possible, even in principle. One discovery was Werner Heisenberg’s 1927 “uncertainty principle” in quantum mechanics, which states that one cannot measure the exact values of the position and the momentum (mass times velocity) of a particle at the same time. ... But sensitive dependence on initial conditions says that in chaotic systems, even the tiniest errors in your initial measurements will eventually produce huge errors in your prediction of the future motion of an object.

 

The nineteenth century was a time of belief in infinite possibility in mathematics and science. Hilbert and others believed they were on the verge of realizing Leibniz’s dream: discovering an automatic way to prove or disprove any statement, thus showing that there is nothing mathematics could not conquer. Similarly, as we saw in chapter 2, Laplace and others believed that, using Newton’s laws, scientists could in principle predict everything in the universe. In contrast, the discoveries in mathematics and physics of the early to middle twentieth century showed that such infinite possibility did not in fact exist. Just as quantum mechanics and chaos together quashed the hope of perfect prediction, Gödel’s and Turing’s results quashed the hope of the unlimited power of mathematics and computing.

  • Chapters 8 – 11 are about genetic algorithms and cellular automata. Mitchell walks through some examples step by step which really helps make these topics understandable. This part of the book was my favourite. I now understand that genetic algorithms work with a large but finite set of inputs and outputs and their "DNA" (which is modified in each generation) encodes a table matching up input and output. The author includes a very interesting example from her own research where she used a genetic algorithm to design cellular automata rules for majority determination.

  • Self-copying programs also feature in this section. As far as I can tell, a language like Clojure, where code and data are treated as the same thing, is well-suited to this kind of problem.

  • She has an explanation of the logistic map and bifurcation.

  • The Hungarian phenomenon was a cluster of mathematicians and physicists, many of whom won a Nobel prize, who all came from a single generation in Hungary (a few of them even went to the same high school):

Von Neumann was part of what has been called the “Hungarian phenomenon,” a group of several Hungarians of similar age who went on to become world-famous scientists. This group also included Leo Szilard, whom we heard about in chapter 3, the physicists Eugene Wigner, Edward Teller, and Denis Gabor, and the mathematicians Paul Erdös, John Kemeny, and Peter Lax.

  • She discusses how ant colonies find a dynamic balance between exploration and exploitation in their search for food, without centralized command.

  • Complexity: A Guided Tour has some useful comments on modelling:

A model, in the context of science, is a simplified representation of some “real” phenomenon. Scientists supposedly study nature, but in reality much of what they do is construct and study models of nature.

 

[M]odelers need above all to emphasize the limitations of their models, so that the results of such models are not misinterpreted, taken too literally, or hyped too much.

  • Scale laws, such as the prevalence of quarter-power scaling in biology and its possible causes (admirably, she covers multiple possibilities and makes it clear that the answer is not yet definitive), are another thing the book spends some time on.

  • The focus on the latter part of the book is networks, especially "small-world" and scale-free networks. Mitchell discusses ways in which these kinds of networks can arise, such as preferential attachment. Examples of networks range from metabolic pathways to epidemiology to food webs. Hubs in these kinds of networks are vulnerable (or a good point for targetted interventions, depending on your objective) but otherwise the overall structure is quite robust.

  • In addition to genetic algorithms, this book includes a couple of chapters on actual genetics. The explanation of how genes can regulate the expression of other genes—in a network structure—was interesting to learn about. Some genes can make proteins the bind to certain DNA sequences (formerly called "junk"), activating or deactivating nearby genes. The networked structure of these interactions leads to a great deal of complexity. Here is some of Mitchell's explanation of this topic:

One casualty of the molecular revolution is the straightforward concept of gene. The mechanics of DNA that I sketched in chapter 6 still holds true—chromosomes contain stretches of DNA that are transcribed and translated to create proteins—but it turns out to be only part of the story.
...
The complexity of living systems is largely due to networks of genes rather than the sum of independent effects of individual genes. As I described in chapter 16, genetic regulatory networks are currently a major focus of the field of genetics. In the old genes-as-beads-on-a-string view, as in Mendel’s laws, genes are linear—each gene independently contributes to the entire phenotype. The new, generally accepted view, is that genes in a cell operate in nonlinear information-processing networks, in which some genes control the actions of other genes in response to changes in the cell’s state—that is, genes do not operate independently.

 

Where do these special regulator proteins come from? Like all proteins, they come from genes, in this case regulatory genes that encode such proteins in order to turn other genes on or off, depending on the current state of the cell. How do these regulatory genes determine the current state of the cell? By the presence or absence of proteins that signal the state of the cell by binding to the regulatory genes’ own switches. Such proteins are often encoded by other regulatory genes, and so forth.

Obviously there are a lot of ideas to digest from these books. I would like to explore some of them further. For example, I might try some simulated annealing, sandpile model, cellular automata, random Boolean network, or genetic algorithm problems to practice programming.

With that, I'll wrap this post up and wish a Merry Christmas to all my readers!

Permalink

Tagged: Book, Review, Math, Computer