Tuesday, September 23, 2008

How Apollo's arrow misses

kw: book reviews, nonfiction, mathematics, modeling, philosophy

There is a simple, repetitive calculation called a Shift Map, based on kneading dough, that illustrates the problems caused by repeated calculations that lose precision as rounding errors accumulate. While we knead dough by repeatedly folding and stretching, in this model, the lump is stretched to twice its length, cut in half and the two halves set atop one another before the next stretch. Now imagine two points in the lump, say two yeast cells, that were once close to one another. With each cycle, they get twice as far apart, until one of them is moved beyond the cut point. At the next cycle, it starts somewhere near the opposite end, then begins to move across again. From that point, the distance between the two cells is not a simple doubling of distance any more. Also after the first time it crosses the cut, there is no simple way to calculate where the cell will be after N cycles.

The mathematical model of this situation is very simple. The position of a cell can be denoted x, and its position after the next cut is then xn+1 = 2xn mod 1. The mod function divides and leaves a remainder; in this case it removes any portion larger than 1, so 1.1938 becomes 0.1938. A cell beginning at 0.34 moves to positions, 0.68, 0.36 (1 was removed), 0.72, 0.44, 0.88, 0.76, and so forth.

In a continuous system, most positions for a cell never return to a former position, and the cell's motion soon becomes unpredictable from first principles. However, when we model this action with a computer, the whole system becomes totally predictable! The reason is the finite size of a "number" inside a computer, and the fact that only rational numbers can be computed. As a matter of fact, not all rational numbers can be stored accurately in computer memory, only those that represent a finite sum of powers of 1/2. For example, any multiple of 1/3 is stored in binary form as 0.010101010101… and so forth, but eventually you have to stop. So what is stored is not exactly one-third. In fact, 1/10 is also stored as a repeating binary decimal and cannot be exactly represented in binary form!

In most computers, a "word" is a 64-bit quantity. 8 bits are used to store an exponent, two bits for the number's sign and the exponent's sign, and the remaining 54 bits are used for a normalized binary value. Thus 1/3 is not actually stored as 0.01010101 and so forth, but as
01|0000001|101010101010101010101010101010101010101010101010101010
I put pipe signs (|) between the sections to emphasize their use. The first 01 means "positive number, negative exponent", the 00000001 is the exponent 1 (so because it is negative, it means "divide by two"), and the rest of the alternating 1's and 0's store the value 2/3, as accurately as 54 bits allows. The whole thing means 1/3, with a minor error after the 54th binary digit. That is the 16th decimal digit.

What happens, then, when we run this through the dough-stretch-and-cut routine? Doubling the number above is accomplished first by removing the negative exponent. So the first ten bits are now 00|00000000, and the whole thing means 2/3. Double it again, and the number stored begins 00|00000001, and the whole thing means 4/3. But we have to subtract one from this to get the remainder for the mod function. The "add" unit in the computer does this by lining up the internal number for -1.0, which is 10|00000001|1000000 and a whole lot more zeroes, with 00|00000001|10101010 and a whole lot more alternating ones and zeroes., then subtracting the value sections from each other (you don't subtract the exponents, but the unit does determine the final sign by checking which sign is negative).

The result is 00|00000001|001010101010 and a lot more alternating ones and zeroes, but notice that the start of the value section is two zeroes. This is "normalized" by shifting two positions to the left, and subtracting two from the exponent. It has been a 1, so now it is -1. And the resulting number becomes 01|00000001|101010 and so forth. This is just 1/3, however, the next-to-last binary digit is no longer a one but a zero. Precision has been lost.

This kind of lost precision continues to occur with each cycle. Rather than spend a lot more words, let's look at the first fifteen cycles as shown in Excel:


Binary rounding errors don't become visible as decimal rounding errors until the sixth cycle, but they compound thereafter. The number is stored with 54-bit precision, so we ought to expect it to take 54 cycles to exhaust the bits…and that is what we find!


The value at the 52d cycle, 0.625, is stored as 00|00000001|1010000000 and more zeroes. 0.25 has just one "useful" bit in the value section, as does 0.5, and the next doubling produced 1.0, which the mod function returned as zero. From that point, it is zero all the way. The model has totally succumbed to rounding error. A final bit before going on: you can look at the value section of the initial number and tell the total history for the next 54 cycles. For most starting values, after 54 cycles you'll get a zero! If you use a number like a trillionth or so, it'll take longer, but no matter what, this calculation is destined to reach zero in a relatively small number of iterations (a couple hundred or fewer). Finally, you don't gain much by using a longer computer "word" to store a number. Suppose the value section had 120 bits rather than 54. Nice idea. But it would "go to zero" after 100 iterations (or at most, 200). Small help that.

OK, all this is background for The Future of Everything: The Science of Prediction by David Orrell, PhD. Dr. Orrell is currently a controversial figure for his assertion that the forecasting of weather, economics, and public health are not a result primarily of mathematical chaos, such as the "butterfly effect", but of model error. The simple system modeled above is one example of model error making a model useless for long-term calculations. Although chaos effects make the path of the yeast cell hard to predict after several cycles, we can run the model to do so. But once it all "goes to zero", prediction is over.

Complex systems have more than one equation, and the equations are larger. A weather prediction model, such as the Global Circulation Models used by NCAR and others, may have millions of geometric elements, and a few dozen equations representing the state of the modeled weather in each element, that must be balanced across all those millions of elements. The starting point is the values of the equations for each element at some point of time. It may take hundreds of cycles to model the weather for one day, and several thousand for a ten-day forecast.

Fortunately, the kind of rounding errors I emphasized in the Shift Map model tend to compensate for one another, otherwise no model could run for more than a hundred steps or so. But there are other kinds of error. The most significant is sampling error: the "weather" in most of those millions of elements must be estimated from readings taken at a few tens of thousands of locations around the planet. Our coverage over the oceans is particularly spotty.

Also, the equations used are mostly empirical approximations of what an air mass the size of New York City, and a km or so deep, will do given the temperature, pressure, wind motion and cloud cover of all its neighboring elements, plus its own. Orrell likens these approximations to epicycles, those little circles used before Kepler to "correct" the motions of the planets and make predictions of eclipses and other syzygies. Epicycles worked well, but on p.41 the author states,
"The fact that it worked quite well as a model of the universe is a poignant reminder that a model that can be made to fit the data isn't necessarily an accurate representation of reality."
The map isn't the landscape, and the model isn't the system modeled. There is lots of room for the unexpected.

Weather isn't the only complex system that people tackle with mathematical models. The economy is a big one, but is considered less complex. For example, there are less than 300 nations, and a much smaller number of stock and commodity markets, so macroeconomic models don't have millions of "elements" to work with, just a few hundred simulated national markets. These markets are based on the "average man", which is considered a soulless bag of reactions to stimuli such as unemployment figures and corporate profit announcements. But once you realize that the behavior of a few million "average men" must be empirically modeled by some statistical beast, you find epicycles again. Both weather/climate and economic models use Ordinary Differential Equations (ODEs) in abundance as the foundation of their modeled structures. These may not be the best in all cases, but "they can be solved using mathematics" (p.115).

The trouble with both is, there are too many parameters that we don't know very well. I once knew a meteorologist (now deceased) who was brought to a campus to add the simulation of lightning to a model of thunderstorms. I asked him about it, and he said, "We don't know where, exactly, a new stroke will start. We have areas of greater likelihood, and have to pick a random spot in one of them." With some tuning, the model was a pretty good simulation of thunderstorm dynamics. But the point was that it was overdetermined: you could get it to simulate a lot of very unrealistic thunderstorms also. About this phenomenon, the Dr. Orrell writes,
"The models suffer from the same problem [that] the Greek Circle Model did: they are too flexible. As Will Keepin put it, modelers can pull the levers and make the model do whatever they want…It is the signature of uncomputability." (p.205)
Ah, uncomputability. It is his term for a phenomenon that cannot—and maybe never can—be simulated from first principles. This is not because of mathematical chaos. It is because, like Conway's game of Life (a seemingly simple cellular automaton with complex behavior), most of what happens is emergent behavior, not strictly implied in the "rules of the game."

One method used by modelers, particularly weather modelers, is to run an ensemble: to run several simulations with slightly different starting conditions, or to use a number of programs that run in slightly different ways or with different size elements. But they are all based on a similar set of simplifications. The author writes,
"[An] ensemble of wrong models does not make a right model, and the spread between the results is not an accurate measure of uncertainty." (p.301)
This is because of something Don Rumsfeld is famous for calling "unknown unknowns". There are things you know you don't know well enough, the "known unknowns". The real stinkers are the things you don't know at all, the things you don't know you don't know. Considering that, in the metabolism of a yeast cell too small to see, there are parameters we know at best only within a factor of ten, and other parameters we've never thought of, it is no surprise we don't have good models of the dynamics of cellular metabolism.

We need to be a little humble. There are things we can't hope to know well enough to simulate them. It would take a computer bigger than the weather to simulate the weather with any accuracy, assuming we got all the parameters and starting values right in the first place. There are billions of people whose emotional state and level of blood caffeine determine the motion of stock markets. And evolution is going on all the time as bacteria and viruses that don't even know we are there strive to make a living that just might come at our expense. Bohr said it best: "Prediction is hard, especially about the future".

No comments: