Separate but Equal: Equality in Belief Propagation for Single Cycle Graphs
Authors: Erel Cohen, Omer Lev, Roie Zivan
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical results demonstrate that when the algorithm does not converge to the optimal solution, the rate of occurrences of assignment equality is high. Experimental Evaluation Following our theoretical proofs, we wanted to gain a perspective on how common is assignment equality in Min-sum when applied to a single cycle factor-graph. To do so, we created simulations in which we varied the size of the cycle and the size of the domain, and generated random instances in which each entry in the cost table of a constraint was a natural number selected uniformly from the range [1, 100]. To simulate Farinelli et al. (2008a) s method of avoiding equalities, we assigned random unary constraints, selected uniformly from the range [10 8, 10 4]. |
| Researcher Affiliation | Academia | Erel Cohen, Omer Lev and Roie Zivan Ben Gurion University of the Negev erelco@post.bgu.ac.il, omerlev@bgu.ac.il, zivanr@bgu.ac.il |
| Pseudocode | No | The paper provides mathematical formulations but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code or explicitly state its release. |
| Open Datasets | No | To do so, we created simulations in which we varied the size of the cycle and the size of the domain, and generated random instances in which each entry in the cost table of a constraint was a natural number selected uniformly from the range [1, 100]. The paper does not provide a specific link or citation for a publicly available dataset. |
| Dataset Splits | No | The paper describes generating random instances and running simulations, but it does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | The paper mentions running simulations but does not provide specific hardware details used for the experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers used for the experiments. |
| Experiment Setup | No | The paper describes generating random instances and simulating Farinelli et al. (2008a)'s method, including assigning random unary constraints uniformly from the range [10^-8, 10^-4] and varying cycle size and domain size. It also states the stopping condition for simulations ('until we had 100 instances on which Min-sum did not converge to an optimal solution'). However, it does not provide specific hyperparameters or system-level training settings for the Min-sum algorithm itself, beyond the problem instance generation parameters. |