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].
Rank Pruning for Dominance Queries in CP-Nets
Authors: Kathryn Laing, Peter Adam Thwaites, John Paul Gosling
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Through experimental results, we show that this method is more effective than existing techniques for improving dominance testing efficiency. We give an experimental comparison of the performance of our rank pruning with the existing pruning methods that preserve search completeness. |
| Researcher Affiliation | Academia | Kathryn Laing EMAIL Peter Adam Thwaites EMAIL John Paul Gosling EMAIL School of Maths University of Leeds Leeds, UK LS2 9JT |
| Pseudocode | Yes | Algorithm 1: Rank Calculation Algorithm Inputs: N = (A, CPT) CP-Net o Outcome Note: Variables and array elements are indexed from 1 (rather than 0) in our pseudocode 1 r(o) := 0 2 for i in {1, 2, ..., |V |} #Looping through the set of variables 3 Anc := ancestor(i, A) #ancestor function calls Algorithm 2 #Anc: set of ancestors of variable i 4 AF := Q Y Anc 1 |Dom(Y )| 5 d := DP(i, A) #DP function calls Algorithm 3 #d: number of descendent paths of variable i 6 Pa := {j | Aj,i = 1} #Parent set of variable i 7 u := o[Pa] #Values taken by the parents of variable i in outcome o 8 order := CPT[i][u] #Preference order over variable i given that Pa = u 9 k := order[o[i]] #o[i]: value taken by variable i in outcome o #k: position of preference of o[i] in the previous order 10 PP := |Dom(Xi)| k+1 |Dom(Xi)| 11 r(o) = r(o) + AF (d + 1) PP 12 return r(o) |
| Open Source Code | Yes | Full details of the prioritisation methods we considered and those utilised, as well as the performances of each pruning method when used in conjunction with all possible prioritisation techniques, are available online at www.github.com/Kathryn Laing/DQ-Pruning. We have made further details of the above experiment available at the online repository www.github.com/Kathryn Laing/DQ-Pruning. This includes the random CP-net generator code and a description of how this generator works, as well as the code for the different dominance testing functions. We have also uploaded the raw results of the experiment to this repository. |
| Open Datasets | Yes | For given n (number of CP-net variables) and d U (maximum domain size of the variables), 100 CP-nets were randomly generated. Each of these CP-nets has an acyclic structure over n variables, each variable has a domain size of at most d U, and all parent-child relations are valid (that is, if there is an edge X Y in the CP-net structure, it is possible to change the preference over Y by altering the value of X only). For each CP-net, 10 dominance queries were randomly generated... We have also uploaded the raw results of the experiment to this repository. |
| Dataset Splits | No | The paper describes generating '100 CP-nets were randomly generated' and '10 dominance queries were randomly generated' for each configuration of n and d_U, which serve as the test data. However, it does not specify any partitioning of this generated data into explicit training, validation, or test sets in the traditional sense of dataset splits. |
| Hardware Specification | No | Part of this work was undertaken on ARC3, part of the High Performance Computing facilities at the University of Leeds, UK. |
| Software Dependencies | No | The paper mentions that the source code for the dominance testing functions is available, implying some programming language was used. However, it does not specify any software names with version numbers (e.g., Python 3.x, specific libraries or frameworks with versions) that would be needed to replicate the experiments. |
| Experiment Setup | Yes | The experiments we ran to evaluate performance were as follows. For given n (number of CP-net variables) and d U (maximum domain size of the variables), 100 CP-nets were randomly generated... For each CP-net, 10 dominance queries were randomly generated... In our experiments, each pruning method utilised the prioritisation heuristic that was optimal for that method (given that it did not require additional calculations). For suffix fixing, this was prioritisation of leaves at minimal depth in the search tree. For penalty pruning and the combination of penalty pruning with suffix fixing, the prioritisation heuristic by Li et al. was used. For rank pruning and all other combinations, leaves of maximal rank were prioritised. |