Testing Self-Reducible Samplers
Authors: Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To evaluate the practical effectiveness of our proposed algorithms, we implemented prototype of Cube Probe Est and Cube Probe Tester in Python3. We use Cube Probe Est to estimate the variation distance (d TV) of three linear extension samplers from a perfect uniform sampler. The objective of our empirical evaluation was to answer the following: RQ1 Can Cube Probe Est estimate the distance of linear extension samplers from a known (e.g., uniform) sampler? RQ2 How many samples Cube Probe Est requires to estimate the distance? RQ3 How do the linear extension samplers behave with an increasing number of dimensions? ... Table 1 shows a subset of our experimental results. ... In Figure 2, at lower dimensions, both Lxt Quick Sampler and Lxt CMSGen behave relatively close to uniform sampling. |
| Researcher Affiliation | Academia | Rishiraj Bhattacharyya1*, Sourav Chakraborty 2*, Yash Pote 3,4*, Uddalok Sarkar 2*, Sayantan Sen3* 1University of Birmingham 2 Indian Statistical Institute Kolkata 3 National University of Singapore 4 CREATE |
| Pseudocode | Yes | Algorithm 1: Cube Probe Est (IG, IW, ψ, ζ, δ), Algorithm 2: Est (IG, ψ, n, x, γ, δ ), Algorithm 3: GBAS (IG, bψ, i, k, HEAD), Algorithm 4: Cube Probe Tester (IG, IW, ψ, ε, η, δ) |
| Open Source Code | Yes | Codes and experimental results are available at www.github.com/uddaloksarkar/cubeprobe. |
| Open Datasets | Yes | Poset Instances: We adopted a subset of the poset instances from the experimental setup of (Talvitie et al. 2018a) and (Talvitie et al. 2018b) to evaluate Cube Probe Est and Cube Probe Tester. The instances include three different kinds of posets. (a) posets of type avgdegk are generated from DAGs with average indegree of k = 3, 5; (b) posets of type bipartitep have been generated by from bipartite set S = A B by adding the order constraint a b (resp. b a) with probability p (resp. 1 p) for all (a, b) A B; (c) posets of type bayesiannetwork is obtained from a transitive closure a randomly sampled subgraph of bayesian networks, obtained from (Elidan 1998). |
| Dataset Splits | No | No explicit train/validation/test dataset splits (percentages, counts, or specific predefined splits) are provided in the paper. The paper mentions using 'Poset Instances' from prior work without detailing how these were split for their evaluation. |
| Hardware Specification | Yes | All experiments are carried out on a high-performance computer cluster, where each node consists of AMD EPYC 7713 CPUs with 2x64 cores and 512 GB memory. |
| Software Dependencies | No | To evaluate the practical effectiveness of our proposed algorithms, we implemented prototype of Cube Probe Est and Cube Probe Tester in Python3. ... The backend of these samplers are powered by three state-of-the-art CNF samplers: Quick Sampler (Dutra et al. 2018), STS (Ermon, Gomes, and Selman 2012), CMSGen (Golia et al. 2021). ... We utilized an exact model counter for CNF formulas to meet this need: Sharp SAT-TD (Korhonen and Järvisalo 2021). |
| Experiment Setup | Yes | Parameters Initialization: For our experiments with Cube Probe Est, the approximation parameter ζ and confidence parameter δ are set to be 0.3 and 0.2. Our tester Cube Probe Tester takes a closeness parameter ε, farness parameter η, and confidence parameter δ. For our experiments these are set to be ε : 0.01, η : 0.61, and δ : 0.1, respectively. |