This post is an update to an earlier post. Occupy Math uses digital evolution as a research tool. This is one of several different computational intelligence techniques inspired by nature. Another one of these techniques is inspired by the complex and beautiful biology of the immune system. These techniques are called, collectively, artificial immune systems. The immune system is such a complex system that multiple algorithmic techniques have been inspired by it. One of them, danger theory, turns out to allow control over digital evolution. This post is about applying danger theory to the evolution of pretty pictures, called apoptotic cellular automata, that Occupy Math has posted about before.
Death is a bummer, at least most of the time for most people. Death because something decided you were dinner or because you were not paying attention and walked off a cliff is one thing, but dying of old age just seems cruel without context. Here’s the thing: death permits change. Without death, evolution cannot happen, because either the world would remain in near stasis or we would die of some sort of overcrowding. We need to evolve to get ahead of things, from a changing environment to new germs. Most modern humans can survive the Black Death, because we are descended from people that survived it. What is the point of all this philosophizing about death? This post is about a focused form of death that may be an important new tool for work in artificial intelligence.
Cellular automata are a simple model of computation, invented to try to create a theory of self-replicating machines. To specify a cellular automata you have to give a set of “cells” (in this post the cells are a line of pixels) a set of states that the cell can take on (colors in this post) and a rule to figure out how the cell colors change over time.
An apoptotic cellular automata starts with a row of white pixels with a [blue][green][blue] in the center of the row. White is zero, blue is one, and green is two, red is three, and so on. The automata is run with a simple rule. It adds up the numbers in five adjacent cells and then uses that total to look up the new number for the cell in the center of the group of five. The new number, and hence color, for each pixel is computed simultaneously and the next row is colored in. The pictures at the top of the post are the result of many applications of their respective rules. The apoptotic part is that we require the system to go to all white before it reaches the bottom of the drawing area. We think of the white state as “dead”; apoptosis is the name for programmed cell death — when a cell destroys itself because it is damaged or infected. These constructs are self-delimiting pictures specified by a simple rule. The rule — the numbers that appear in it — are the target of evolution. Here is another example of an evolved apoptotic cellular automata.
When a cell emits a danger signal, the immune system removes and destroys the cell. This is a huge oversimplification, but it’s all we need to explain the new software idea. We start with the system that can evolve rules for automata that die before they hit the bottom of the drawing area, with no other constraints. Since pictures with more non-white pixels are, on average, more interesting, we reward an automata rule for drawing the most non-white pixels it can, as long as it does not reach the bottom of the drawing arena. We then write tests for things we do not want — we will get to those in a minute — and, inspired by danger theory from the immune system, we zero out the fitness of the things we do not like. This is a process called necrosis where death is used to remove undesirable objects. Compare the five example of automata above with the thirty examples below.
The automata above were evolved using necrosis to remove any automata that placed living pixels outside of the middle quarter of the picture. Leaving the middle quarter of the picture results in instant death and, as the pictures show, this strongly shapes the resulting pictures. The four shapes we used to constrain the automata in different experiments are shown below.
Diamond shaped automata
The four space-invader/flying saucer shapes at the top of the post were evolved using the “M”-like shape. Below are renderings of automata evolved with the diamond shaped constraint. In this case the necrosis was not “instant death”; rather, a soft form of necrosis was used — pictures that were in bounds were safe and those that were out of bounds had a chance of dying. This means that most of the automata are close to in bounds for the diamond shape, but leak out a little bit.
COLORS! I want more colors!
The shape-based constraints let us control where the picture draws, but the idea of necrosis can be used to constrain any quality of the picture that the computer can detect. If we use a necrotic filtering to remove pictures that use fewer colors, we can encourage ones with more colors. Here are thirty examples of such more colorful automata.
Are there bigger implications than pretty pictures?
Occupy Math has been working on apoptotic cellular automata for eight years now. One thing that he has figured out is that there are billions and billions of rules that make pictures that die out at some point. This huge collection of pictures is a wonderful sandbox to test ideas about how to get evolution to do what is wanted, rather than some random thing. As an added bonus, even though it is a terrifically complex space with about 35 dimensions, the results of running evolution are pictures that are relatively easy to render and think about.
Having said that, it seems clear that the technique of using necrosis to remove undesirable qualities from an evolving population has the potential for very broad application. In a recent post Occupy Math reported on the beginning of a project he is participating in to do Covid-19 vaccine deployment. One concern that has come up in this work is the potential that the inhuman logic of an AI might find highly effective strategies that are also unethical. Building a wall of vaccination around a poor, densely packed neighborhood is clearly not ethical, but might make sense if your only concern is minimizing the number of people that catch the disease. This behavior is detectable and so we can use necrotic filters to remove it from the system that creates vaccination rules.
Occupy Math has recently finished experiments that demonstrate that applying multiple necrotic filters to the same evolving population works perfectly well. This means that one arm of the vaccine deployment effort can be identifying effective but unethical solutions, building detectors for them, and then putting in necrotic filters to prevent those behaviors from being considered. Occupy Math likes the idea that we can build an immune system for an artificial intelligence that prevents it from acting in an unethical manner. It sounds like science fiction, but this is something that is now possible.
Mathematics is normally characterized as being objective. The necrosis technique from this post is an objective mathematical technique, but, the things you use it to remove are subjective. Worse, the interaction between those subjective decisions and the space of objects is unpredictable at best. A nice top spin on this is that you can state rules or laws for your system and have evolution sort out the details for you. The problem is that evolution does what you tell it to, not what you want it to, and sometimes the results are quite startling. The necrosis technique creates a playground for understanding the implications of your rules — and those implications are often unexpected.
The fact this is Part IV of “What do mathematicians do all day” means there is also a Part III, a Part II, and a first post which you can take a look at if you like reading about weird research. Remember that Occupy Math loves suggestions of topics from his readers. You can post in the comments or e-mail firstname.lastname@example.org with your notion.
I hope to see you here again, So remember to wear your mask! Daniel Ashlock, University of Guelph, Department of Mathematics and Statistics