Timezone: »

 
Oral
A Constraint Generation Approach to Learning Stable Linear Dynamical Systems
Sajid M Siddiqi · Byron Boots · Geoffrey Gordon

Wed Dec 05 04:00 PM -- 04:20 PM (PST) @
in Session 7: Systems and Applications »

Stability is a desirable characteristic for linear dynamical systems, but it is often ignored by algorithms that learn these systems from data. We propose a novel method for learning stable linear dynamical systems: we formulate an approximation of the problem as a convex program, start with a solution to a relaxed version of the program, and incrementally add constraints to improve stability. Rather than continuing to generate constraints until we reach a feasible solution, we test stability at each step; because the convex program is only an approximation of the desired problem, this early stopping rule can yield a higher-quality solution. We apply our algorithm to the task of learning dynamic textures from image sequences as well as to modeling biosurveillance drug-sales data. The constraint generation approach leads to noticeable improvement in the quality of simulated sequences. We compare our method to those of Lacy and Bernstein [1,2], with positive results in terms of accuracy, quality of simulated sequences, and efficiency.

Author Information

Sajid M Siddiqi (Google Inc.)
Byron Boots (University of Washington)
Geoffrey Gordon (MSR Montréal & CMU)

Dr. Gordon is an Associate Research Professor in the Department of Machine Learning at Carnegie Mellon University, and co-director of the Department's Ph. D. program. He works on multi-robot systems, statistical machine learning, game theory, and planning in probabilistic, adversarial, and general-sum domains. His previous appointments include Visiting Professor at the Stanford Computer Science Department and Principal Scientist at Burning Glass Technologies in San Diego. Dr. Gordon received his B.A. in Computer Science from Cornell University in 1991, and his Ph.D. in Computer Science from Carnegie Mellon University in 1999.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors