Meaningful Complexity, part 1

How do we quantify the "right" amount of complexity?

Caveat Lector: This is a Junk Drawer post, which means it’s guaranteed to be extra geeky and likely of little interest to most. This particular series of Junk Drawer posts is a detailed description of a complexity rabbit hole I’ve been exploring the past weeks — a journey triggered by

Joseph Rahi

’s April post, A Formula for Meaningful Complexity. That post is required reading to make any sense of this post.

Complexity & Meaning

The chart above illustrates a common view of a relationship between entropy (or increasing randomness) and complexity. At first, things are simple but over time become more complex. To a point. After that point, although randomness continues to increase, complexity — or more importantly, meaningful complexity — drops off again. The usual example is how cream mixes with coffee (or drops of ink with water).

At first, the two liquids are separate and easily described because all points within the liquids are the same. The boundary between them is also relatively simple and easily described. It doesn’t take much information to describe the state of the system.

Over time they begin to mix. At some point, the mixture is “interesting” and complex. Tendrils of cream (or ink) extend into the coffee (or water). Each time the shape is different. And like snowflakes, the number of possible shapes is so vast that duplicates are rare. Describing the shape requires a lot of information — a lot of data points.

As time increases, though, the two mix thoroughly, and now the system is even easier to describe than it was initially. There is just one consistent liquid throughout, no boundaries. The system description reduces to a single data point.¹

So, the general notion here is that, as complexity rises, “meaning” (or “interest”) also rises, but only to a point. After that point, it drops off again.

Important here is that the horizontal axis represents complexity from essentially zero on the left to full randomness on the right.² For example, consider a 20,000-byte text file. On the left, the file is just zeros or spaces (or any single character). On the right, each byte is entirely random. Neither extreme has any meaning. Only files with rational text have meaning — a very small subset of the possible arrangements of 20,000 text characters.

As an illustration, here is part of the text of Hamlet undistorted and with 10% distortion (altering of 10% of the characters to some other character):

And here is the text with 50% and 100% distortion:

Going the other way, increasingly replacing characters with spaces or some other specific character (like all ‘A’s) accomplishes the same thing in the decreasing complexity direction.

Note an important point here. The physical structure of the text is preserved in this case. In some sense, this distortion process tries to maintain the syntax of the text while distorting its semantics (its meaning).

As you see from the above, 10% distortion corrupts the text considerably, but the original is still mostly discernable. By 50% distortion, the original text is almost impossible to discern. At 100%, only that physical structure remains.

Alternately, we might consider an image. On the left, it’s just black (or white or any single color). On the right, each pixel is random. In the middle, a specific and meaningful arrangement of pixels. Again, the two extremes have no meaning. Again, only a small subset of arrangements of pixels do have meaning.

However, note an important point. In the image above, while the third frame is undistorted, the second and fourth frames have 50% distortion — on the left, 50% emerging from a black background, on the right, 50% towards fully random. In both cases, the meaning of the image is readily discernable. It remains so until we get fairly close to the extremes of all-black or all-random pixels:

The above two panels show the image 90% distorted, either by fading to black (left) or by becoming more random (right). In both cases, the image is at least somewhat discernable. One interesting aspect of this is that the larger the image size, the closer to all-black or all-random the image can be while still remaining discernable.³

That said, even mildly distorted images do seem to lose a degree of detail.⁴

But to say the original is discernable is not to say how meaningful the text or image is. Meaning is, in large degree, subjective. If my main goal is a perfect picture, any distortion quickly degrades meaning for me. But if I have an old snapshot of an important memory, even considerable distortion may not detract from what it means to me.

So, it seems we need some more objective measure of complexity that abstracts and generalizes what people intend in saying a text or image is meaningful to them.

Ultimately, it seems to boil down to the structure carried by the vehicle, and it seems that structure must exist at multiple levels. Mild distortion erases structure at fine levels while stronger distortion erases structure at larger levels. Complete distortion — reducing to a single color or randomness — completely erases structure.

Joseph’s post seeks to put an objective number on structure by tracking how it emerges from randomness. It turns out there is a similar but opposite curve as structure emerges from blankness.

Compression

The degree to which a text or image can be compressed (as in a ZIP file) plays a key role in Joseph’s approach, which I think is a very good starting point. There is an important caveat when it comes to file compression, though. Consider these two files:

As 1200×900 BMP image files, they both have the same file size (3,240,054 bytes), but the left one compresses to 1,649,139 bytes (to 50.9%) while the right one compresses to 2,926,070 bytes (to only 90.3% of the BMP size).

Using only compression as a metric, the left image is considerably less complex than the right image. More precisely, we can say the left image is 50% compressible whereas the right image is only 90% compressible.

The above images of an orange and Bentley (no connection), also 1200×900 BMPs, compress to 2,158,302 bytes (to 66.6%) and 1,946,786 bytes (to 60.1%), respectively. So, the compression metric indicates that Bentley is less compressible than the tree, and the orange is even less compressible than either.

The question is what structure these have that makes them more or less compressible, and what alignment that might have with “meaning” or even just the complexity of these images.⁵ I’m not that surprised about the two with trees, but the apparent structure of the image of the orange surprised me. I am also a bit surprised by the gap between the compression of tree and Bentley pictures.

I suspect it has something to do with run-length encoding during compression. Long horizonal stretches of the same pixel value increase compressibility. The sky and garage wall provide plenty of that in the tree photo, which might explain the 50% compression.

If we generate a series of images (21 of them) taking an image — say of Bentley — from all-black to fully random, we can chart the compressibility of each image:

The horizonal axis comprises the files in the ZIP file; the vertical axis (left) for the red and blue plots is size in bytes and varies depending on the files. The vertical axis (right) for the green plot is fixed and shows the relative degree of compression from 1.0 (max) to 0.0 (none).

The 11th file in these is the undistorted image, and note the inflection point between the two series of images, the emerging from black in the left 10 files versus the submerging into randomness in the right 10 files. The mathematical function behind the two curves is slightly different.

What’s less obvious here (but more prominent in other examples) is “the porch” — the flat area from file 10 to file 11. The latter, of course, is the undistorted image. File 10 is the 90% emerged-from-black image, and the porch seems to indicate it has nearly identical compressibility.

I’ll be showing lots of charts like this in the posts ahead, so their format is worth discussing in some detail here. The blue plot is the original file size; the red plot is the compressed file size. If the red plot touches the blue plot, the file has zero compressibility. (And the green plot drops to zero.)

Obviously, the green plot mirrors the red plot, but I wanted a fixed reference that didn’t vary with file size. I also wanted to explore Rahi’s notion of “structural spread”, which has the formula:

\(\displaystyle {SS} = \frac{\textit{original-size}\;-\;\textit{compressed-size}}{\textit{original-size}}\)

Which does mirror the compressed file size but normalizes the value to be between 0.0 and 1.0. Note that it can be exactly zero if the compressed size is the same as the original size — meaning the file has zero compressibility. But on the presumption the compressed size can never reach zero, the SS value can never quite reach 1.0.

The structural spread is part of the formula for emergent structural complexity (ESC) that Rahi came up with for his post. I’ll explore it more next time, but very briefly, his formula is:

\({ESC} = {AC} \times {SS} \times {EF}\)

Where AC, absolute complexity, is (essentially) the file size, SS is as discussed just above, and EF, emergence factor, is (as I understand it) a measure on the compressibility curve between the original and full randomness.

I’ll leave you with a few last graphs. Here’s the plot for the tree image:

Essentially the same but with a more prominent porch. There also seems to be one for the far right of the green plot, from file 20 (90% random) to file 21 (fully random).

The plot for the many-trees-in-the-park is a bit different:

Which will make it a topic of discussion in future posts. Note the low compressibility of file 11, the OG image. The blank version (file 1) is highly compressible, but this changes much more rapidly than in the two above.

Lastly, here’s a chart for the Hamlet text:

Which is a little weird but comes from the way these particular distortion routines leave the text’s structure in place. As in the other cases, at first the file (all spaces) is very compressible, but this rises to a point and then declines over the last few steps. The decreasing compressibility as the text is randomized shows a similar asymptotic curve to the other plots.

That even the final “fully randomized” version is still notably compressible (to 69.3%) is due to the preserved text structure. As you’ll see in future posts, randomizing more fully does result in incompressible “text” files.

The rise and decline of the left curve, I suspect, is due to how replacing random characters with spaces chops up the text. As the percentage of replaced characters drops, words emerge, which allows greater compression.

I’ll dig into this and more (in great gory detail) in future posts.

Until next time…

1. Note that the data point itself might comprise multiple numbers, such as temperature, coffee/cream ratio, cup shape, or any other properties of interest. But these properties apply to all drops of coffee in the cup.

2. Which strikes me as an amusing and somewhat accurate political metaphor.

3. I suspect because a bigger image has a larger number of “valid” image pixels your brain can integrate into a meaningful image. The noise ratio remains the same, but a bigger image has more useful data.

4. Of course they do, that’s the whole point of the distortion.

5. Personally, all four have meaning for me because they are connected to my life. That tree, for instance, is what I see outside my home office window. And it goes without saying with Bentley.