Recht, B. "Convex Modeling with Priors"

Abstract

As the study of complex interconnected networks becomes widespread across disciplines, modeling the large-scale behavior of these systems becomes both increasingly important and increasingly difficult. In particular, it is of tantamount importance to utilize available prior information about the system's structure when building data-driven models of complex behavior. This thesis provides a framework for building models that incorporate domain specific knowledge and glean information from unlabelled data points.

I present a methodology to augment standard methods in statistical regression with priors. These priors might include how the output series should behave or the specifics of the functional form relating inputs to outputs. My approach is optimization driven: by formulating a concise set of goals and constraints, approximate models may be systematically derived. The resulting approximations are convex and thus have only global minima and can be solved efficiently. The functional relationships amongst data are given as sums of nonlinear kernels that are expressive enough to approximate any mapping. Depending on the specifics of the prior, different estimation algorithms can be derived, and relationships between various types of data can be discovered using surprisingly few examples.

The utility of this approach is demonstrated through three exemplary embodiments. When the output is constrained to be discrete, a powerful set of algorithms for semi-supervised classification and segmentation result. When the output is constrained to follow Markovian dynamics, techniques for nonlinear dimensionality reduction and system identification are derived. Finally, when the output is constrained to be zero on a given set and non-zero everywhere else, a new algorithm for learning latent constraints in high-dimensional data is recovered.

I apply the algorithms derived from this framework to a varied set of domains. The dissertation provides a new interpretation of the so-called Spectral Clustering algorithms for data segmentation and suggests how they may be improved. I demonstrate the tasks of tracking RFID tags from signal strength measurements, recovering the pose of rigid objects, deformable bodies, and articulated bodies from video sequences. Lastly, I discuss empirical methods to detect conserved quantities and learn constraints defining data sets.