New Frontiers in Representation Discovery

A Tutorial to be given at AAAI 2007

Vancouver, Canada Monday July 23, 2007

Sridhar Mahadevan (University of Massachusetts, Amherst)

Tutorial Slides (PDF) (7/17/07, Final slides)


The problem of learning representations has long been considered a fundamental problem -- some would say the fundamental problem -- of AI. While considerable technical advances have been made in many areas of AI, including probabilistic techniques for search, planning, learning, and robotics, with few exceptions most of these advances are based on systems that act within the confines of a fixed representation. The goal of designing agents that can discover novel representations from their environment has been a longstanding challenge. Significant early research on this topic was carried out by some of the early pioneers of AI, notably Saul Amarel. However, while this work provided some influential ideas, the techniques were largely applicable to deterministic discrete environments, and it was unclear how to generalize these insights to real-world domains.

This tutorial provides a state-of-the-art overview of new emerging research directions in representation discovery for real-world stochastic environments, which build on recent developments in machine learning and mathematics, principally harmonic analysis, manifold learning and spectral graph theoretic methods. Harmonic analysis is a field of mathematics that traditionally includes Fourier and wavelet analysis, and has played a central role in science and technology for two centuries. Spectral graph theory is the study of graphs using the tools of linear algebra. Recent advances in harmonic analysis have shown how to generalize the traditional analytic tools of Fourier and wavelet analysis from restricted Euclidean spaces to more general discrete and continuous state spaces with arbitrary topology. These advances yield crucial new insights into how to design a new generation of AI planning and search agents that can solve tasks in discrete and continuous state spaces by discovering novel representations. These developments could have profound influence on the design of the next generation of AI applications in a large variety of areas, including information retrieval over the web, natural language, robotics, sensor networks, perception, and human-robot interaction.

The tutorial will be presented by Professor Sridhar Mahadevan of the University of Massachusetts, Amherst. Professor Mahadevan pioneered a novel unified framework for jointly learning representation and behavior, giving an invited talk at AAAI 2005 introducing this research field to the AI audience. This tutorial now represents a much broader overview of research since then, including not only his own research, but also related work on representation discovery from researchers across a wide spectrum of backgrounds in AI and mathematics. Since much of the underlying mathematics may be unfamiliar to AI researchers, the goal of this tutorial is two-fold. One, it will provide a detailed introduction to the underlying theory of harmonic analysis, including Fourier and wavelet analysis on graphs, as well as techniques for constructing representations on graphs. Second, it will show how these ideas can be applied to design a new generation of AI learning, planning and search agents. In particular the tutorial will describe novel techniques for solving Markov decision processes, such as proto-value functions and representation policy iteration, and new ways to apply these techniques to applications such as robotics.

The tutorial will be accesssible to researchers and graduate students working in any area of AI or related areas (mathematics, statistics etc.). The tutorial will include a detailed introduction to the underlying mathematics as well as algorithms and how these lead to novel ways of solving a variety of problems in AI. All the ideas will be illustrated using hands-on MATLAB demonstrations.

Related Tutorials and Talks ICML 2006 Tutorial on Learning Representation and Behavior

  • IJCAI 2007 Tutorial on Recent Advances in Reinforcement Learning