Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Searching for the M Best Solutions in Graphical Models
Authors: Natalia Flerova, Radu Marinescu, Rina Dechter
JAIR 2016 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments confirm theory that the best-first approach is largely superior when memory is available, but depth-first branch and bound is more robust. We also show that our algorithms are competitive with related schemes recently developed for the m-best task. |
| Researcher Affiliation | Collaboration | Natalia Flerova EMAIL University of California, Irvine Irvine, CA 92697, USA Radu Marinescu EMAIL IBM Research Ireland Rina Dechter EMAIL University of California, Irvine Irvine, CA 92697, USA |
| Pseudocode | Yes | Algorithm 1: AOBF exploring the AND/OR search tree (Marinescu & Dechter, 2009b)... Algorithm 2: AOBB exploring the AND/OR search tree (Marinescu & Dechter, 2009b)... Algorithm 3: Recursive computation of the heuristic evaluation function... Algorithm 4: Mini-Bucket Elimination... Algorithm 5: m-A* exploring a graph, assuming consistent heuristic... Algorithm 6: m-BB exploring a graph, assuming a consistent heuristic... Algorithm 7: m-AOBF exploring an AND/OR search tree... Algorithm 8: m-AOBB exploring an AND/OR search tree... Algorithm 9: Combining the sets of costs and partial solution trees... Algorithm 10: Merging the sets of costs and partial solution trees |
| Open Source Code | No | The paper does not provide an explicit statement or link for the open-sourcing of the authors' implementation for the methodology described. It mentions that implementations of competing schemes were provided by Dhruv Batra, but not their own code. |
| Open Datasets | Yes | The pedigrees benchmark ( pedigree* ) was used in the UAI 2008 competition.3 They arise from the domain of genetic linkage analysis and are associated with the task of haplotyping. 3. http://graphmod.ics.uci.edu/group/Repository In each of the binary grid networks ( 50-* , 75-* and 90-* )4 the nodes corresponding to binary variables are arranged in an N by N square and the functions are defined over pairs of variables and are generated uniformly randomly. 4. http://graphmod.ics.uci.edu/repos/mpe/grids/ |
| Dataset Splits | No | The paper describes the benchmarks used and how instances were generated for some, but does not provide specific train/test/validation splits (e.g., percentages or counts) or a methodology for creating such splits that would be needed for reproduction. |
| Hardware Specification | Yes | All algorithms were implemented in C++ (32-bit) and the experiments were run on a 2.6GHz quad-core processor. The memory limit was set for 4 GB per problem, the time limit to 3 hours. |
| Software Dependencies | No | The paper states that algorithms were "implemented in C++ (32-bit)" but does not provide specific version numbers for the C++ compiler or any libraries used, which are essential for reproducibility. |
| Experiment Setup | Yes | We used 10 i-bounds, ranging from 2 to 22. However, for some hard problems computing the mini-bucket heuristic with the larger i-bounds proved infeasible, so the actual range of i-bounds varies among the benchmarks and among instances within a benchmark. All algorithms were restricted to a static variable ordering computed using a min-fill heuristic (Kjærulff, 1990). Both AND/OR schemes used the same pseudo tree. |