Book Highlights: Complexity A Guided Tour

 

What is complexity?

property:

• Complex collective behavior:
  • each typically following relatively simple rules with no central control or leader. It is the collective actions of vast numbers of components that give rise to the complex, hard-to-predict, and changing patterns of behavior
• Signaling and information processing:
• Adaptation:
  • All these systems adapt—that is, change their behavior to improve their chances of survival or success—through learning or evolutionary processes

an alternative definition of a complex system: a system that exhibits nontrivial emergent and self-organizing behaviors.

How to measure complexity

• effective complexity
  • Gell-Mann proposed that any given entity is composed of a combination of regularity and randomness.
  • To calculate the effective complexity, first one figures out the best description of the regularities of the entity; the effective complexity is defined as the amount of information contained in that description, or equivalently, the algorithmic information content of the set of regularities.
  • In short, as we would wish, both very ordered and very random entities have low effective complexity.
• Complexity as Logical Depth
  • The logical depth of an object is a measure of how difficult that object is to construct.
• Statistical Complexity
  • measures the minimum amount of information about the past behavior of a system that is needed to optimally predict the statistical behavior of the system in the future.
• Complexity as Fractal Dimension
• Complexity as Degree of Hierarchy
  • Simon proposed that the most important common attributes of complex systems are hierarchy and near-decomposibility.
  • Near-decomposibility refers to the fact that, in hierarchical complex systems, there are many more strong interactions within a subsystem than between subsystems.
  • Simon contends that evolution can design complex systems in nature only if they can be put together like building blocks—that is, only if they are hierachical and nearly decomposible; a cell can evolve and then become a building block for a higher-level organ,
  • McShea’s scale is defined in terms of levels of nestedness: a higher-level entity contains as parts entities from the next lower level.
  • nestedness only describes the structure of an organism, not any of its functions
  • maximum hierarchy seen in organisms increases over evolutionary time. Thus this is one way in which complexity seems to have quantifiably increased with evolution, although measuring the degree of hierarchy in actual organisms can involve some subjectivity in determining what counts as a “part” or even a “level.
• in general, hard to measure

Entropy

Boltzmann defined the entropy of a macrostate as a function of the number of microstates that could give rise to that macrostate.

Shannon defined the information of a macrostate (here, a source) as a function of the number of possible microstates (here, ensembles of possible messages) that could be sent by that source.

Entropy decreases (living systems become more organized, seemingly more designed) as a result of the work done by natural selection. The energy for this work comes from the ability of individual organisms to metabolize energy from their environments (e.g., sunlight and food).

Kauffman’s “fourth law” proposes that life has an innate tendency to become more complex, which is independent of any tendency of natural selection. (received many criticism)

Chaos

• Seemingly random behavior can emerge from deterministic systems, with no external source of randomness.
• The behavior of some simple, deterministic systems can be impossible, even in principle, to predict in the long term, due to sensitive dependence on initial conditions.
• Although the detailed behavior of a chaotic system cannot be predicted, there is some “order in chaos” seen in universal properties common to large sets of chaotic systems, such as the period-doubling route to chaos and Feigenbaum’s constant. Thus even though “prediction becomes impossible” at the detailed level, there are some higher-level aspects of chaotic systems that are indeed predictable.

Computation

Hilbertt proposed 3 important problems. these were not just problems in mathematics; they were problems about mathematics itself and what can be proved by using mathematics.

1. Is mathematics complete? That is, can every mathematical statement be proved or disproved from a given finite set of axioms?

2. Is mathematics consistent? In other words, can only the true statements be proved?

3. Is every statement in mathematics decidable? That is, is there a definite procedure that can be applied to every statement that will tell us in finite time whether or not the statement is true or false?

Kurt Gödel presented a proof of the so-called incompleteness theorem.

This theorem stated that if the answer to question 2 above is “yes” (i.e., mathematics is consistent), then the answer to question 1 (is mathematics complete?) has to be “no.”

an example is a sentence “This statement is not provable”

The core idea is similar to self-copying program which uses the same information stored in memory in two ways: first as instructions to be executed, and second as data to be used (i.e., printed) by those instructions.

Turing was able to see how to answer Hilbert’s third question, the Entscheidungs problem, and his answer, again, was “no.” by showing that proving of many statements result in infinite reasoning loop.

Random Fine-Grained Exploration

1. most system reacts based on encounter of certain events and rate of certain event encountered
2. information must be communicated via spatial and temporal sampling.
3. Random Components of Behavior
   1. Given the statistical nature of the information read, the actions of the system need to have random (or at least “unpredictable”) components. All three systems described above use randomness and probabilities in essential ways.
   2. It appears that such intrinsic random and probabilistic elements are needed in order for a comparatively small population of simple components (ants, cells, molecules) to explore an enormously larger space of possibilities, particularly when the information to be gained from such explorations is statistical in nature and there is little a priori knowledge about what will be encountered.
   3. However, randomness must be balanced with determinism: self-regulation in complex adaptive systems continually adjusts probabilities of where the components should move, what actions they should take, and, as a result, how deeply to explore particular pathways in these large spaces.
4. Fine-Grained Exploration
   1. many simple elements work in parallel for robustness, evolvability, efficiency
   2. explore both highly possible path and new path
   3. take simple action so that flexible to change path
   4. the redundancy inherent in fine-grained systems allows the system to work well even when the individual components are not perfectly reliable and the information available is only statistical in nature.
   5. Redundancy allows many independent samples of information to be made, and allows fine grained actions to be consequential only when taken by large numbers of components.

Scale Free Network

Like an exponential curve. x axis is the number of nodes, y axis is the number of connections a node has.

Properties

1. self similar (the exponential curve’s shape is similar in any x range)
2. small number of large hubs
3. number of edges are very diverse
4. small world (one node can connect to another without too many hoops)

network resilience

1. resilient to random node deletion , because most nodes have low number of edges
2. if hubs are deleted, then the network collapses

Example: internet, brain, metabolic networks, Epidemiology

brain

1. brain is small world network and scale free
2. which helps to process info locally and aggregate info globally
3. make brain energy efficient and avoid being too large
4. small world helps neurons fire simultaneously

Where Do Scale-Free Networks Come From?

Réka Albert proposed that a particular growing process for networks, which they called preferential attachment, is the explanation for the existence of most (if not all) scale-free networks in the real world.

The idea is that networks grow in such a way that nodes with higher degree receive more new links than nodes with lower degree

the rich get richer, or perhaps the linked get more linked

The growth of so-called scientific citation networks is one example of the effects of preferential attachment.

Preferential attachment is one mechanism for getting to what the writer Malcolm Gladwell called tipping points—points at which some process, such as citation, spread of fads, and so on, starts increasing dramatically in a positive-feedback cycle. Alternatively, tipping points can refer to failures in a system that induce an accelerating systemwide spread of additional failures, which I discuss below.

My thoughts

ML/LLM is the terminal of scale free information network which has the most connections.

Complex system behaviors are for bottom up construction. But ML/LLM algorithms are already at the top. So multi agent exploration algorithm may not be helpful for ML/LLM algorithms.

Entropy grows because of the nature of cosmos. But the growth process is not uniform across the whole universe. There are many low entropy singularities like star and planet. Entropy decreases during evolution of life because of interaction between low entropy earth and high entropy universe.