Scientific and technological problems require representing and reasoning about many spatial and temporal relationships. Examples tasks include: from video data, tracking the full articulated pose of humans performing various activities; from specification of a robotic manipulation goal, identify feasible and efficient motion plans; from an input sequence of amino acids, and low-resolution observations provided by modern imaging technologies, predicting the 3D structures into which proteins are most likely to fold. However, as problems grow in size and complexity, current algorithms for handling this kind of continuous data become intractable. The proposed work will overcome this problem by creating a new class of algorithms, called "particle-based belief propagation", that efficiently handles continuous relational data. Broader impacts of the project include the creation of educational materials targeting graduate and undergraduate courses, as well as community outreach to local middle and high school students. The project's open source statistical software also enables a number of important real-world applications, which are explored via diverse teams of undergraduate and graduate students. This work may contribute to technological problems like the development of autonomous robots and vehicles, and scientific problems like the study of diseases caused by incorrect folding of proteins.
The technical research significantly advances the theory and practice of message-passing algorithms for inference in graphical models with non-Gaussian, continuous variables. This work will substantially generalize a recently developed family of diverse particle belief propagation inference algorithms, that replace the (unstable) stochastic resampling of classic particle filters with provably accurate discrete optimization. The first research aim is to explore a number of improvements to the computational algorithms, and supporting theory, that enables effective particle-based inference. Motivated by problems where precise quantification of posterior uncertainty is important, the project generalizes existing work on "max-product" belief propagation optimization to support "sum-product" belief propagation integration, and "mixed-product" updates for more general inference queries. The project also generalizes prior work on discrete graphical models to study how errors made in local messages propagate throughout the model. Furthermore, the researchers study how particle-based inference can enable new types of loss-sensitive structured learning for continuous estimation problems, including semi-supervised learning from partially labeled training data.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
