Post date: 19-Feb-2012 19:25:54
Cosma Shalizi presented the ε-machine and proved that is is optimal. It goes something like this...
Imagine that you live in a feudal town where the priests run a well patronised betting ring. Each day bets are taken on the color of the moon that evening. There are 8 recognised moon colors and any number of forecasting techniques involving everything from tea leaves to goat entrails.
You happen across a hermit in the mountains known as Shalizi whose rantings have been paid little heed by passers by. Shalizi claims (amongst other things) that his method can deliver the best possible prediction. If this is true then you should be able to make a killing in the moon prediction business so you and your ever willing assistant Grunt go to work.
You buy a block of land and mark a point in the middle. From this starting point you mark out a set of paths, like a tree, that fork at regular intervals but never join. At each fork you place a signpost that assigns one of the colors to each of the paths leading away from the starting point.
Now you train Grunt to walk along the paths based on your instructions. Your route instructions take the form of a string of colored beads with a knot at one end. Grunt must walk away from the starting point and at each fork choose the path matching the color of the next bead on the string beginning always from the knotted end. Grunt must also carry a bucket of stones and place one at each fork as he passes. When Grunt gets to the end of the string of beads then he must return to the starting point for the next journey.
Now you begin to monitor the color of the moon each night. Each time that you observe the color of the moon you give the assistant a bucket of stones, all matching the moon's color and send Grunt on his way. When Grunt returns, you take one of the remaining stones out of the bucket, drill a hole thru it and thread it on the string at the knotted end. After a while Grunt begins to complain that the load is becoming too heavy and the journey too long, so you limit the number of beads on the string to 20 by removing one bead from the oldest end each time you add a new bead to the knotted end.
After this has been going on for some time you are ready to make your first prediction so you take the string of beads and follow the route accordingly. As you move further from the starting point the piles of colored stones at each fork become smaller and smaller. At the end of the journey you separate out the heap of colored stones, count each color and divide by the total using your new Intel Abacus. These probabilities are your prediction for the color of tonight's moon.
The predictions turn out to be quite accurate and life is good. You earn enough money to buy Grunt a new bucket for his birthday.
One day while travelling the return route back towards the starting point, you decide to check the proportions of the colored stones at one of the forks. Interestingly, you notice that the proportions are essentially the same as the furthest pile that you have been relying on. You then carefully check the proportions at every fork on the return route and each in turn is nearly identical. However, before you reach the staring point you find a fork where the proportions are significantly different to those further out. Those forks still closer to the starting point have even more widely varying proportions.
Curious now, you begin to routinely check the proportions of the colors at every fork on your return route each day. You find each time that the proportions are constant for some of the return journey but that there is a fork on each route where they become significantly different. However, on some routes this critical fork is quite close to the starting point and on others it is much further out.
It would appear that you do not really have to walk right to the end of the journey to make your prediction. To save yourself some effort, you place a flag at the fork which is the first fork which you can use to make a reliable prediction.
Good news, the predictions have actually become more reliable and you don't have to travel so far to make them. However, after a time the accuracy of your predictions starts to degrade and your are forced to begin walking right to the end of the journey again to regain the accuracy. It seems that the critical fork on some of the paths has moved further out while others remain unchanged.
You also realise that when you move the flag further out on one route then you must place some new flags on the other alternatives to save you travelling all of the way out to the end of the journey.
You decide that it is time to up skill Grunt. You train Grunt to check the proportions on his return journey and adjust the position of the flags when required. You are forced to upgrade your Intel abacus to the latest version so that Grunt can use your old one to assist him with his duties.
The accuracy returns to your predictions and life is good.
However, colored stones are beginning to become expensive as your system has used a vast number. It seems a waste to continue placing stones at the forks close to the starting point as they are both the largest piles and are never used in your predictions. You begin to recycle the stones at the forks closer in than those with flags.
Disaster strikes! Grunt quits and you notice that he is setting up his own set of paths in a nearby field. You can still make predictions but your system is no longer being updated. A few days later you notice that some of your piles of stones have gone missing from the outer piles closest to Grunt's new enterprise. You have a problem.
The first priority is that you do not loose the ability to make predictions. You go to each flagged fork and make a permanent record (an engraved menhir) of the number of stones of each color in its pile. That done, you consider your options.
Grunt is making progressively better predictions and threatening your monopoly on moon predictions in the region. Competition for colored stones is increasing and your intellectual property is carved into the menheirs for all to see. Not good.
The priority now is to protect your intellectual property. You decide to group the menhirs together so that they can be protected adequately from the disgruntled competition. Before doing so, you additionally engrave each menhir with a record of the route from the starting point to the fork for later identification. While lugging the menhirs you notice that some have very similar proportions inscribed on them so you arrange them into homogeneous groups accordingly.
Making a prediction now involves locating the menhir with a route matching the beads nearest the knot and reading off the proportions engraved thereon. However, searching for the matching menhir each day is time consuming.
Also, the disgruntled competition is intensifying so it would be a good time to move on to another town far away and re-establish. Unfortunately, transporting the menhirs any distance is prohibitively expensive.
You decide to revisit Shalizi on the mountain. He seems to consider you problem rather trivial and you listen for a while to his claim of the smallest possible representation. As you are walking back down the mountain the words “beware determinism” float down thru the mist.
You think that you should be able to reduce the search time by constructing some new paths between the groups of menhirs. Each time you observe the color of the moon and locate the matching menhir you create a path from the previous menhir group to the new group and assign it a color on a signpost as before. Before long you find that you can follow existing paths from one menhir group to the next, based on the latest moon color.
This is a great time saving, because you need not even read the menhirs but just follow the colored paths from one group to the next. It would appear that you only need to record the groups and their paths and this will be much cheaper to transport.
This works well for a time, but before long your predictions go haywire. On closer inspection you discover that the current group of menhirs does not contain the one that matches the string of beads. Some further inspection reveals that while all of the menhirs in a group make the same prediction for the next observation, this does not necessarily determine the next group. You remember determinism being mentioned on the mountain.
So now you set about checking one homogeneous group of menhirs very thoroughly and splitting it into sub-groups. You are hoping to obtain groups which make the same prediction for the next moon color and which reliably determine the next group once the actual color of the moon is known. To do so you must check every menhir in the group for every moon color.
Once you have done this for the first homogeneous group, you choose one of the paths and move on to a second large homogeneous group to repeat the process. When you split this second group you suddenly realise that you may have disrupted the path that you just followed because now it leads to not one group but two. You rush back to the group at the start of the path and sure enough it needs to be split again so that it is both homogeneous and deterministic.
At this point you become rather depressed and utter a few disparaging remarks about the value of hermits on mountains. However you are in a bind. You have to many menhirs to transport and the disgruntled competition is closing. In the worst case you will complete all of this work and every menhir will be in its own group and you will be back where you started. However, you have little choice but to continue and besides the hermit is developing a nasty habit of being right.
Many tedious back breaking days later you have managed to separate all of the menhirs into groups which are both homogeneous and deterministic. Better yet, there are many less groups than menhirs - few enough to transport. So, you make a permanent record of each group which contains the color prediction, a list of routes from the field, and a list of paths to other groups. You pack up and move on. On your way out of town you gift your remaining stones, painted with water soluble paint, to Grunt. When you pass over the mountains you wave to the hermit who is looking particularly smug.
On the trek over the mountain you notice a path of to one side signposted “a better way”. It bugs you.
to be continued ...