Domain-Lifted Sampling for Universal Two-Variable Logic and Extensions
Authors: Yuanhong Wang, Timothy van Bremen, Yuyi Wang, Ondřej Kuželka10070-10079
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Applications and Experiments In this section, we present some applications of the firstorder sampling problem and examine the scalability of our algorithm in practice. All experiments were performed on a computer with an 8-core Intel i7 3.60GHz processor and 32 GB of RAM. Performance Analysis We further analyse the scalability of our algorithm on the examples of k-colored trees and the friends-smokers MLN. For the experiment on k-colored trees, we evaluated the average runtime across different domain sizes (with 10 samples for every size) for 2-, 3and 4-colored trees and plotted it in Figure 2a. Similarly, the runtime for sampling possible worlds from the friends-smokers MLN over different domain sizes is shown in Figure 2b. To the best of our knowledge, this is the first exact lifted sampling algorithm for first-order logic, so the closest comparison would be against a state-of-the-art propositional sampler like Uni Gen (Soos, Gocht, and Meel 2020). We ran Uni Gen on the friends-smokers MLN, but it could only scale to domains of size 30, whereas our approach takes less than 1 second on a domain of size 100, as shown in Fig. 2b. |
| Researcher Affiliation | Collaboration | Yuanhong Wang1, Timothy van Bremen2, Yuyi Wang3, 4*, Ondˇrej Kuˇzelka5 1 Beihang University, China 2 KU Leuven, Belgium 3 CRRC Zhuzhou Institute, China 4 ETH Zurich, Switzerland 5 Czech Technical University in Prague, Czech Republic lucienwang@buaa.edu.cn, timothy.vanbremen@cs.kuleuven.be, yuyiwang920@gmail.com, ondrej.kuzelka@fel.cvut.cz *partially supported by Huawei TCS Lab |
| Pseudocode | Yes | Algorithm 1: Weighted Model Sampler for UFO2 and Algorithm 2: Weighted Model Sampler for UFO2 with Constraints |
| Open Source Code | Yes | Details can be found in the online technical report4. 4https://github.com/lucienwang1009/lifted_sampling_ufo2 |
| Open Datasets | No | The paper samples combinatorial structures (k-colored trees) and from Markov Logic Networks (friends-smokers MLN), which are formalisms or problem types, not pre-existing datasets. It does not mention using any publicly available dataset with concrete access information (link, DOI, citation). |
| Dataset Splits | No | The paper does not provide specific dataset split information (e.g., percentages, sample counts, or citations to predefined splits). The experiments involve sampling from logical sentences over varying domain sizes rather than using traditional datasets with train/validation/test splits. |
| Hardware Specification | Yes | All experiments were performed on a computer with an 8-core Intel i7 3.60GHz processor and 32 GB of RAM. |
| Software Dependencies | No | The paper does not provide specific software dependency details with version numbers for its own implementation. |
| Experiment Setup | No | The paper describes the hardware used and general experimental procedures (e.g., 'average runtime across different domain sizes (with 10 samples for every size)'), but does not provide specific experimental setup details such as hyperparameters or detailed training configurations. |