Predictor arrays provide a way to forecast behavior governed by patterns that are not known a priori. To my knowledge, Paul Schluter's use of a predictor array for detection of atrial fibrillation was the first implementation of this idea (circa 1979); more on this below.
Consider the classic game of rock, paper, scissors (RPS). Against an unknown opponent, it is likely that the best strategy is to choose randomly, because without a priori knowledge of the other player's strategy, there is no basis for predicting what his or her move will be. If, however, we have the opportunity to play a series of games against the same opponent, we have a chance to discover patterns in the series of choices he or she makes, and then to adjust our choices accordingly in order to improve our chances of winning.
The basic idea of predictor arrays is that often one might have a number of plausible ways of forecasting behavior. In iterated RPS for example, a simple strategy is to choose whatever move would have won the previous round. This strategy would be successful in the long run against an opponent who doesn't change moves often: implicitly, it is based on the prediction that the next move will be the same as the previous one. Another strategy might predict that the next move will be the same as the second previous one. Yet another might be that our opponent will match whatever our last move was. We can imagine a large number of such strategies, each based on a simple (and more or less plausible) predictor, and keep track of the accuracy of each predictor as we observe additional rounds of the game. The predictor array meta-strategy is to identify which of the simple predictors yields the best predictions, on average, and then to use that predictor to choose our moves. If our opponent's behavior changes (perhaps she notices that we are winning too often), we can use moving averages of predictor accuracy to recognize shifts in her strategy.
In 2000, Darse Billings of the University of Calgary organized an international tournament for computer programs that were written to play iterated RPS ("Rochambeau") matches against each other. I wrote PredictorArrayBot for this tournament; it used a predictor array to turn in a respectable performance against a large field of opponents (20th of 64, and 7th of 24 among the class of "small" programs).
More recently, I've written psim to control a Lego NXT robot (the psychic robot monkey) exhibited at Brickworld 2008. The object of Psim is not to play RPS, but more simply to predict which of three colored flags will be chosen by the person interacting with it. Using a predictor array, Psim can recognize many common patterns of behavior quickly and is usually able to guess with high accuracy after a small number of turns.
Paul Schluter's original application of predictor arrays has a particularly clever twist: his algorithm for detecting atrial fibrillation works when the predictor array fails. In most cardiac rhythms, the intervals between successive heart beats vary (most commonly, in response to respiration). In a healthy person, we might find that one respiratory cycle (breath) is roughly the same length as six cardiac cycles (heart beats), and in such a case a good prediction for the length of the next interval between beats might be the sixth previous interval. In another person, or in the same person at another time, perhaps the fifth previous interval would be a better predictor. In fact, in a wide variety of normal and abnormal rhythms, any of the previous 6-10 intervals might predict the next interval well, on average. Atrial fibrillation, almost uniquely among heart rhythms, exhibits a seemingly random series of intervals. So the key insight is that when the most accurate predictor of the next interval is, in fact, not accurate at all (on average), it is likely that the rhythm is atrial fibrillation.
George B. Moody (george@mit.edu), 11 June 2008.