Timezone: »

 
Poster
Solving Marginal MAP Problems with NP Oracles and Parity Constraints
Yexiang Xue · zhiyuan li · Stefano Ermon · Carla Gomes · Bart Selman

Wed Dec 07 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #131
in Wednesday Posters »

Arising from many applications at the intersection of decision-making and machine learning, Marginal Maximum A Posteriori (Marginal MAP) problems unify the two main classes of inference, namely maximization (optimization) and marginal inference (counting), and are believed to have higher complexity than both of them. We propose XORMMAP, a novel approach to solve the Marginal MAP problem, which represents the intractable counting subproblem with queries to NP oracles, subject to additional parity constraints. XORMMAP provides a constant factor approximation to the Marginal MAP problem, by encoding it as a single optimization in a polynomial size of the original problem. We evaluate our approach in several machine learning and decision-making applications, and show that our approach outperforms several state-of-the-art Marginal MAP solvers.

Keywords: (Other) Probabilistic Models and Methods · (Other) Optimization · Graphical Models

Author Information

Yexiang Xue (Cornell University)
zhiyuan li (Tsinghua University)
Stefano Ermon (Stanford)
Carla Gomes (Cornell University)
Bart Selman (Cornell University)

More from the Same Authors