Spectral Approaches to Learning Dynamical Systems

If we hope to build an intelligent agent, we have to solve (at least!) the following problem: by watching an incoming stream of sensor data, hypothesize a model which explains that data. For this purpose, an appealing model representation is a dynamical system"”a recursive rule for updating a "state," a concise summary of past experience that we can use to predict future observations. Unfortunately, to discover the right state representation and parameters for a dynamical system, we must solve difficult temporal and structural credit assignment problems, often leading to a search space with a host of bad local optima. Responding to these difficulties, researchers have designed many special-purpose tools for pieces of this problem: e.g., system identification for learning Kalman filters, the Baum-Welsh algorithm for learning hidden Markov models, the Tomasi-Kanade structure-from-motion algorithm, or the many approaches to simultaneous localization and mapping (SLAM) from sensors such as lidars, cameras, or radio beacons. In this talk I will discuss a recently-discovered class of spectral learning algorithms which holds the promise of unifying these separate tools and special cases into a single general-purpose toolkit. These spectral algorithms are computationally efficient, statistically consistent, and have no local optima; in addition, they can be simple to implement, and have state-of-the-art practical performance for some interesting learning problems.