RI: Small: Heuristic Search Algorithms 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. The goal of this research is to develop the next generation of approximate, anytime inference algorithms for graphical models. The PIs will empower search algorithms by strengthening their guiding heuristic functions using variational bounds that are both pre-compiled as well as re-computed dynamically during search. The new algorithms ensure compact search spaces by exploiting the problems' decomposition (using AND/OR search), equivalence (by caching) and pruning irrelevant subspaces using the power of their bounding heuristics. These frameworks will additionally provide automated guidance for selecting parameters to optimize the inherent trade-offs between complexity and accuracy to provide meaningful any-time bounds, while tuning those decisions to the respective benchmarks and instances.