RI: Inference in Large-Scale Graphical Models

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Abstract In this project, we will develop novel methods to enable inference in large-scale graphical models, emphasizing the construction of models of unstructured environments from a vast number of sensor measurements. Creating models of the world from large amounts of noisy sensor data is an inference problem of vast proportions for which current methods do not scale up well. In keeping with the most recent literature, we model such inference problems using graphical models. However, in contrast to the literature we use factor graphs rather than belief nets, and show that there is a close and hithereto under-exploited connection between Factor Graphs and the sparse linear algebra literature. This connection enables cross- fertilization between inference in graphical models and sparse linear algebra. In particular, we will develop a novel graphical model paradigm, the BayesTree, inspired by the representations used in the so-called multifrontal factorization methods from sparse linear algebra. In terms of intellectual merits, these developments are novel and are expected to significantly advance the areas of large-scale mapping and 3D modeling in the fields of robotics and computer vision. However, we expect these new classes of algorithms to have broad impact beyond robotics in vision, in every fields where vast amounts of data needs to be processed and condensed in a parametric model. We expect the new graphical language we introduce to significantly improve understanding of exact inference in graphical models, as we feel this has been largely inaccessible but to advanced researchers in the field. By stressing the connections between the modest Gaussian elimination algorithm from linear algebra and more advanced inference methods such as the junction tree algorithm, we hope to enable a new generation of researchers that will truly understand these connections and hence be able to make revolutionary contributions in many fields. Progress reports will be regularly updated at http:// www.cc.gatech.edu/~dellaert/graphs/