Parallel AND/OR Search for Marginal MAP

2020-06-02

Proceedings of the AAAI Conference on Artificial Intelligence, 34

Volume

Vol. 34 No. 06: AAAI-20 Technical Tracks 6

AAAI Technical Track: Reasoning under Uncertainty

Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art algorithms for solving exactly this task are based on either depth-first or best-first sequential search over an AND/OR search space. In this paper, we explore and evaluate for the first time the power of parallel search for exact Marginal MAP inference. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm that explores the search space in a best-first manner while operating with limited memory. Subsequently, we develop a complete parallel search scheme that only parallelizes the conditional likelihood computations. We also extend the proposed algorithms into depth-first parallel search schemes. Our experiments on difficult benchmarks demonstrate the effectiveness of the parallel search algorithms against current sequential methods for solving Marginal MAP exactly.

10.1609/aaai.v34i06.6584