A dynamical systems’ perspective of the expectation-maximization-like algorithms

30 May 2019

Sérgio Pequito Rensselaer Polytechnic Institute

The Expectation-Maximization (EM) algorithm is one of the most popular methods used to solve the problem of distribution-based clustering in unsupervised learning. In this talk, we propose a dynamical systems perspective of the EM algorithm. More precisely, we can analyze the EM algorithm as a nonlinear state-space dynamical system. This algorithm belongs to a large class of iterative algorithms known as proximal point methods. In particular, we re-interpret limit points of the EM algorithm and other local maximizers of the likelihood function it seeks to optimize as equilibria in its dynamical system representation. Furthermore, we propose to assess its convergence as asymptotic stability in the sense of Lyapunov. Consequently, we proceed by leveraging recent results regarding discrete-time Lyapunov stability theory in order to establish asymptotic stability (and thus, convergence) in the dynamical system representation of the EM algorithm.

Next, we show how to leverage leveraging tools from robust control theory, particularly integral quadratic constraints (IQCs) to interpret EM-like algorithm as linear time-invariant (LTI) systems with a feedback nonlinearity. This analysis allows us to design a novel EM-like algorithm for Gaussian mixture models (GMMs). Furthermore, it allows us to establish bounds on the convergence rates of the studied algorithms. In particular, the derived bounds for our proposed EM-like algorithm generalize bounds found in the literature for the EM algorithm on GMMs.



Sérgio Pequito is an assistant professor at the Department of Industrial and Systems Engineering at the Rensselaer Polytechnic Institute. He also holds a courtesy appointment at the Electrical, Computer, and Systems Engineering department. From 2014 to 2017, he was a postdoctoral researcher in General Robotics, Automation, Sensing & Perception Laboratory (GRASP lab) at University of Pennsylvania. He obtained his Ph.D. in Electrical and Computer Engineering from Carnegie Mellon University and Instituto Superior Técnico, through the CMU-Portugal program, in 2014. Previously, he received his B.Sc. and M.Sc. in Applied Mathematics from the Instituto Superior Técnico in 2007 and 2009, respectively. Pequito's research consists of understanding the global qualitative behavior of large-scale systems from their structural or parametric descriptions and provide a rigorous framework for the design, analysis, optimization and control of large scale (real-world) systems. Pequito was awarded the best student paper finalist in the 48th IEEE Conference on Decision and Control (2009). Also, Pequito received the ECE Outstanding Teaching Assistant Award from the Electrical and Computer Engineering Department at Carnegie Mellon University, and the Carnegie Mellon Graduate Teaching Award (University-wide) honorable mention, both in 2012. Also, Pequito was a 2016 EECI European Ph.D. Award on Control for Complex and Heterogeneous Systems finalist and received the 2016 O. Hugo Schuck Award in the Theory Category.