Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models
The paper presents and evaluates the power of parallel search for exact MAP inference in graphical models. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm, called SPRBFAOO, that explores the search space in a best-first manner while operating with restricted memory. Our experiments show that SPRBFAOO is often superior to the current state-of-the-art sequential AND/OR search approaches, leading to considerable speed-ups (up to 7-fold with 12 threads), especially on hard problem instances.
obtained without using sophisticated schemes, as done in previous work [8]. An extensive empirical evaluation shows that our new parallel recursive best-first AND/OR search scheme improves considerably over current state-of-the-art sequential AND/OR search approaches, in many cases leading to considerable speed-ups (up to 7-fold using 12 threads) especially on hard problem instances.
The paper is straightforward in a good way. RBFAOO is briefly described and then an appropriately detailed description of SPRBFAOO is given. It is clear that some thought (and no doubt experimentation) has gone into the presented design. As it should be, there is quite a long section on empirical results which help the reader understand the important issues.It would be interesting to see whether a "programming by optimisation (PBO)" approach would yield good results - perhaps eg fitting \zeta to features of a particular problem instance.In [2] RBFAOO is only compared against AOBB and AOBF, so although it is superior to both those algorithms it is not clear to me how it compares to alternative graphical model MAP algorithms such as those which participated in the UAI'14 inference challenge (which had a MAP competition). Note that the proteus solver, a portfolio solver, did well (beating daopt in the 20 and 60 min competitions). It included CPLEX which automatically parallelises if there are the processors available, so that's another example of parallel search for MAP. I acknowledge that the parallelisation strategy here is more sophisticated and problem-specfic than sending the problem to a general-purpose solver that happens to be able to run in parallel.I suspect this paper would be of interest to a fairly narrow pool of NIPS people since it has a narrow focus. It is no surprise that, if done competently, using more computational power can speed up (a particular approach to )MAP solving in MRFs.typos, etc:reduces the frequency of occurring the scenarios -> reduces the frequency of scenarios