Talk by Akihiro Kishimoto : Efficient AND/OR search algorithms for exact MAP inference task over graphical models

Graphical models provide a powerful framework for reasoning with probabilistic information. Combinatorial maximization, or maximum a posteriori (MAP) tasks arise in many applications and often can be efficiently solved by search schemes, especially in the context of AND/OR search spaces that are sensitive to the underlying problem structure.

In this talk, I present the power of limited memory best-first search over AND/OR search spaces, named RBFAOO, which performs exact MAP inference over graphical models. I also present a parallelized version of RBFAOO which runs in a shared-memory environment. I show that RBFAOO is empirically superior to the current state-of-the-art approaches based on AND/OR search, especially on very hard problem instances.