Stochastic Anytime Search for Bounding Marginal MAP
Authors: Radu Marinescu, Rina Dechter, Alexander Ihler
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The empirical evaluation demonstrates the effectiveness of our new methods against the current best-performing search-based bounds. |
| Researcher Affiliation | Collaboration | Radu Marinescu1, Rina Dechter2, Alexander Ihler2 1 IBM Research 2 University of California, Irvine |
| Pseudocode | Yes | Algorithm 1: EXPAND(n) and UPDATE(n) Algorithm 2: ANYSBFS Algorithm 3: ANYLDFS |
| Open Source Code | No | The paper does not provide any statement or link indicating that its source code is publicly available. |
| Open Datasets | Yes | Our benchmark set includes 3 standard problem domains from grid networks (grid), genetic linkage analysis (pedigree), and medical diagnosis expert systems (promedas). |
| Dataset Splits | No | The paper discusses generating instances for different problem domains but does not specify any training, validation, or test splits for the data used in its experiments. It refers to problem instances and benchmark sets. |
| Hardware Specification | No | The paper states that experiments were run with a '20GB of RAM limit' but provides no specific details about the CPU, GPU, or other hardware components used. |
| Software Dependencies | No | The paper mentions using 'WMB-MM(i)' and 'WMB-IS(i, δ)' schemes and sets 'i = 10' for both, but it does not provide version numbers for any specific software, libraries, or solvers used in its implementation. |
| Experiment Setup | Yes | The parameter p that controls the exploration strategy of ANYSBFS was set to 0.5 and its restarts threshold τ followed a standard Luby sequence (1,1,2,1,1,2,4,...). All competing algorithms used the same heuristic function WMB-MM(i). We set i = 10 for both the heuristic WMB-MM(i) and the sampling scheme WMB-IS(i), respectively. The time limit was set to 1 hour and we ran all algorithms as memory intensive schemes with a 20GB of RAM limit. We also allowed ANYLDFS and ANYSBFS to perform up to r = 10,000 calls to the lower bounding scheme for summation within the time limit and we set δ = 0.05 to ensure that they produce true lower bounds with probability at least 95%. Finally, the proposed algorithms also implemented the adaptive strategy described in the previous section and increased the number of samples used by WMB-IS(i) by 25% every time the same summation OR node m is selected for re-evaluation (the initial number of samples was set to 1,000). |