Probabilistic graphical models are central to automated reasoning. The past decade has seen significant progress on two basic reasoning tasks: combinatorial optimization (maximization or minimization) and marginalization (summation) tasks. Maximization queries are often used to generate predictions from a given model, such as image denoising or finding stereo correspondence. Summation queries are common in model learning, for computing and optimizing the data likelihood during fitting.
A key point is that for these tasks the model is treated homogeneously; all variables are either maximized (or minimized) or summed over. However, many important reasoning and inference tasks require a mixture of these where some variables are maximized (or minimized), while others are summed over. Such mixed problems occur in optimal estimation, decision making in single- and multi-agent systems, and worst-case or antagonistic problems that arise in robust estimation and games. Far less progress has been made on these more difficult query types.
The goals of this Faculty Early Career Development (CAREER) award are to develop a new framework for exact and approximate methods for such advanced computational reasoning problems. The project includes both theoretical and practical algorithm pieces, and studies their use in estimation and learning from data. The project extends the abilities of intelligent systems to reasoning and decision-making under uncertainty. It applies and tests these methods on a variety of application domains, including sensor networks and computer vision. The project supports graduate, undergraduate, and high-school student research, and it contributes to open and online course development. The project increases impact and algorithm adoption by deploying open-source tools, developing open standards and benchmark problems in these domains, and it encourages additional progress through open comparisons and competitions.
