Temporal Sequence Prediction Using an Actively Pruned Hypothesis Space

Abstract

We propose a novel time/space efficient method for learning temporal sequences that operates on-line, is rapid (requiring few exemplars), and adapts easily to changes in the underlying stochastic world model. This work is motivated by humans' remarkable ability to learnspatio-temporal patterns and make short-term predictions much faster than most existing machine learning methods. Using a short-term memory of recent observations, our method maintains a dynamic space of candidate hypotheses in which the growth of the space is systematically and dynamically pruned using an entropy measure over the observed predictive quality of each candidate hypothesis. We further demonstrate the application of this method in the domain of ``matching pennies'' and ``rock-paper-scissors'' games.