RI: Small: Anytime Algorithms and Bounds for Probabilistic Graphical Models

University Of California-Irvine, Irvine CA

Investigators

Abstract

Probabilistic graphical models are employed throughout science and engineering to solve difficult problems, including automated reasoning and decision making, computer vision, computational biology and genetics, and data mining. However, exact inference is often computationally intractable, necessitating approximations or bounds. While significant progress has been made, many real-world problems remain out of reach. Many techniques require a set of problem-specific customizations and choices that must be made in advance, with little guidance or automation. Our research will both improve the performance of probabilistic graphical models and will make these techniques more widely available. The investigators support education and diversity through their undergraduate and graduate teaching, and through making their software available to researchers and to the public. The goal of this research is to develop the next generation of approximate, anytime inference techniques and algorithms for graphical models. Informed by the framework of heuristic search, the investigators will create improved unified schemes for message-passing, vibrational and sampling algorithms. These new algorithms seek to effectively manage models containing mixtures of probabilistic and deterministic relationships, as well as both graph-based and context-specific independence relationships. They will provide meaningful bounds on the results and the accuracy of the algorithms, while simplifying or automating any required tuning to the problem instance, optimizing the inherent trade-offs between complexity and accuracy. The algorithms will be extended to the most challenging tasks (i.e., max-sum-product tasks) such as maximum expected utility queries for optimal decision-making. The investigators will collaborate with domain experts to apply their algorithms to applications such as planning and computational protein design. 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.