Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata
Authors: Filippo Bistaffa
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate FABE on standard benchmark datasets for exact MPE inference (i.e., protein, pedigree, grid) [Kishimoto and Marinescu, 2014; Kishimoto et al., 2015] and WCSP (i.e., spot5, mastermind, iscas89) [Marinescu and Dechter, 2009], comparing it with several state of the art approaches. |
| Researcher Affiliation | Academia | Filippo Bistaffa IIIA-CSIC filippo.bistaffa@iiia.csic.es |
| Pseudocode | Yes | Algorithm 1 Bucket Elimination [Dechter, 2013] Input: A graphical model M = X, D, F , an ordering d. Output: A max probability (resp. min cost) assignment. 1: Partition functions into buckets according to d. 2: Define ψi as the of bucketi associated with Xi. 3: for p n down to 1 do 4: for ψp and messages h1, h2, . . . , hj in bucketp do 5: hp Xp(ψp Nj i=1 hi). 6: Place hp into the largest index variable in its scope. 7: Assign maximizing (resp. minimizing) values in ordering d, consulting functions in each bucket. 8: return Optimal solution value and assignment. |
| Open Source Code | Yes | FABE and SMP are implemented in C++.5 We employ the implementations of RBFAOO and toulbar provided by the authors. 5Code available at https://github.com/filippobistaffa/FABE. |
| Open Datasets | Yes | We evaluate FABE on standard benchmark datasets4 for exact MPE inference (i.e., protein, pedigree, grid) [Kishimoto and Marinescu, 2014; Kishimoto et al., 2015] and WCSP (i.e., spot5, mastermind, iscas89) [Marinescu and Dechter, 2009], comparing it with several state of the art approaches. 4Online at: www.ics.uci.edu/ dechter/softwares/benchmarks. |
| Dataset Splits | No | The paper mentions using 'standard benchmark datasets' but does not specify the exact split percentages, sample counts, or explicit methodology for training, validation, and test sets. |
| Hardware Specification | Yes | All experiments have been run on a cluster whose computing nodes have 2.50GHz CPUs and 384 GBytes of RAM. |
| Software Dependencies | No | FABE and SMP are implemented in C++. We employ the implementations of RBFAOO and toulbar provided by the authors. It mentions toulbar [Hurley et al., 2016], CPLEX, and GUROBI, but no specific version numbers for any software dependencies are provided within the paper's text. |
| Experiment Setup | Yes | For each instance, we compute d using a weighted MIN-FILL heuristic [Dechter, 2013], and we use the same d for both algorithms. We execute RBFAOO with the parameters detailed in authors previous work [Kishimoto and Marinescu, 2014; Kishimoto et al., 2015], including cache size and i parameter. Every other approach is executed with default parameter values. As for Remark 1, for FABE we consider ϵ=10 10. |