Parallel AND/OR Search for Marginal MAP
Authors: Radu Marinescu, Akihiro Kishimoto, Adi Botea10226-10234
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments on difficult benchmarks demonstrate the effectiveness of the parallel search algorithms against current sequential methods for solving Marginal MAP exactly. |
| Researcher Affiliation | Industry | Radu Marinescu, Akihiro Kishimoto IBM Research Dublin, Ireland {radu.marinescu, akihirok}@ie.ibm.com Eaton Dublin, Ireland adibotea@eaton.com |
| Pseudocode | Yes | Algorithm 1: SPRBFAOO-MMAP |
| Open Source Code | No | The paper does not provide any explicit statement or link indicating that the source code for the described methodology is publicly available. |
| Open Datasets | Yes | Our benchmark set includes three domains from genetic linkage analysis (pedigree), computational protein design (pdb) and probabilistic conformant planning (planning), respectively. Since the original pedigree and pdb problems are pure MAP tasks (Elidan, Globerson, and Heinemann 2012), we generated 5 synthetic MMAP instances for each pure MAP instance by randomly selecting P% of the variables to act as MAP variables, where we chose P {20, 50, 80}. |
| Dataset Splits | No | The paper mentions generating instances and using benchmark problems but does not specify details regarding training, validation, or testing splits, or cross-validation methods. |
| Hardware Specification | Yes | All algorithms were implemented in C++ (64-bit) and the experiments were run on a 2.0GHz IBM Cloud virtual machine with 12 cores and 64GB of RAM. |
| Software Dependencies | No | The paper states that algorithms were implemented in 'C++ (64-bit)' but does not provide specific version numbers for compilers, libraries, or other software dependencies. |
| Experiment Setup | Yes | The time limit was set to 1 hour and all algorithms used a 10GB cache table to record partial search results. When the cache table is full, the algorithms use the Small-Tree GC strategy (Nagai 1999) to discard R% entries with small subtrees. As in (Akagi, Kishimoto, and Fukunaga 2010; Kishimoto and Marinescu 2014), we set R to 30. For numerical stability, our implementation solves MMAP as a minimization problem in log space as suggested in (Marinescu et al. 2018) and therefore we used parameters δ = 1 and ζ = 0.01, respectively. The parallel search algorithms ran with 12 threads each and all competing algorithms used the same heuristic function WMB(i) with the i-bound set to 10 for pedigree and planning domains, and to 2 for the pdb domain, respectively. |