Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Robust sequence prediction is an essential component of an intelligent agent acting in a dynamic world. We consider the case of near-future event prediction by an online learning agent operating in a non-stationary environment. The challenge for a learning agent under these conditions is to exploit the relevant experience from a limited environmental event history while preserving flexibility.We propose a novel time/space efficient method for learning temporal sequences and making short-term predictions. Our method operates on-line, requires few exemplars, and adapts easily and quickly to changes in the underlying stochastic world model. Using a short-term memory of recent observations, the 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.The method compares well against Markov-chain predictions, and adapts faster than learned Markov-chain models to changes in the underlying distribution of events. We demonstrate the method using both synthetic data and empirical experience from a game-playing scenario with human opponents.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Yoshua Bengio , Samy Bengio , Jean-François Isabelle , Yoram Singer, Shared context probabilistic transducers, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.409-415, July 1998, Denver, Colorado, United States
• 3: Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
• 4: D. Fudenberg and D. K. Levine. The Theory of Learning in Games. MIT Press, Cambridge, Massachusetts, 1999.
• 5: I. Guyon , F. Pereira, Design of a linguistic postprocessor using variable memory length Markov models, Proceedings of the Third International Conference on Document Analysis and Recognition (Volume 1), p.454, August 14-15, 1995
• 6: S. A. Huettel, P. B. Mack, and G. McCarthy. Perceiving patterns in random series: dynamic processing of sequence in prefrontal cortex. Nature Neuroscience, 5(5):485--490, May 2002.
• 7: G. A. Miller. The magical number 7 plus or minus two: Some limits on our capacity in processing information. Psychol. Rev., 63:81--97, 1956.
• 8: Dana Ron , Yoram Singer , Naftali Tishby, The power of amnesia: learning probabilistic automata with variable memory length, Machine Learning, v.25 n.2-3, p.117-149, Nov./Dec. 1996 [doi>10.1007/BF00114008]
• 9: L. K. Saul and M. I. Jordan. Mixed memory Markov models: decomposing complex stochastic processes as mixtures of simpler ones. Machine Learning, pages 1--11, 1998.
• 10: Yoram Singer, Adaptive mixtures of probabilistic transducers, Neural Computation, v.9 n.9, p.1711-1733, Nov. 15, 1997 [doi>10.1162/neco.1997.9.8.1711]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms

Keywords:
markov decision process, n-gram, rapid learning, sequence prediction