Efficient Satisfiability Verification for Conditional Importance Networks
Conditional importance networks (CI-nets) provide a formal framework for modeling and reasoning with qualitative preferences over sets of many variables. Existing approaches for verifying the satisfiability of a CI-net operate on a complete model of the C
- PDF / 546,246 Bytes
- 5 Pages / 439.37 x 666.142 pts Page_size
- 38 Downloads / 226 Views
ditional importance networks, or CI-nets [1], provide an expressive language for specifying and reasoning over qualitative conditional preferences among sets of items. To ensure that preference reasoning over a CI-net is sound, one must verify that the CI-net is satisfiable, i.e., it contains no cycles of preferences. Existing methods for this, including [1,4], construct a preference graph that explicitly represents the (partial) preference ordering defined by a CI-net. A CInet is satisfiable if and only if its preference graph is acyclic [1], but the time cost to construct the graph dominates the time cost to verify satisfiability. This paper presents a new algorithm for verifying CI-net satisfiability without the full preference graph, which significantly reduces the average time needed to verify a CI-net’s satisfiability. We describe and empirically evaluate our implementation of this algorithm, then discuss future applications of this work.
2
Overview of CI-Nets
We use the definitions for conditional importance statements (CI-statements) and conditional importance networks (CI-nets) from [1], given here as Definition 1. Let V be a finite set of binary variables, each of which indicates whether a given proposition is true or false. We assume that each proposition is preferred to be true and that propositions do not directly contradict each other. Definition 1. A CI-statement on V is a quadruple (S + , S − , S1 , S2 ) of pairwise disjoint subsets of V. This CI-statement can be written as S + , S − : S1 S2 . A CI-net on V is a set C of CI-statements on V. c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 350–354, 2017. DOI: 10.1007/978-3-319-67504-6 26
Efficient Satisfiability Verification for Conditional Importance Networks
351
Informally, a CI-statement can be interpreted to mean: “Given two sets of items chosen from V, if both sets include the items in S + and neither set includes the items in S − , then I would rather have the set that has all items in S1 instead of the set that has all items in S2 , ceteris paribus (all else being equal).” The semantics of CI-nets are defined by [1] in terms of worsening flips, which are pairs of sets of variables (V1 , V2 ) such that V1 is preferred to V2 (V1 V2 ). In contrast, [4] defines CI-net semantics in terms of improving flips, where (V1 , V2 ) means that V2 is preferred to V1 (V2 V1 ). Our proofs are based on improving flips, but it is simple to rewrite them using worsening flips. From this point on, the word “flip” denotes either a worsening or an improving flip unless noted. Given variable sets V1 and V2 , V1 is preferred to V2 under a CI-net C (C |= V1 V2 ) if and only if C defines an improving flipping sequence from V2 to V1 . Definition 2 ([4], after [1]). A sequence of sets of variables V1 , V2 , · · · , Vn is an improving flipping sequence w.r.t. a CI-net if and only if, for 1 ≤ i < n, either 1. (Monotonicity Flip) Vi+1 ⊃ Vi ; or 2. (Importance Flip) a CI-statement S + , S − : S1 S2 satisfies the following: (a) Vi+1 ⊇ S + , Vi ⊇
Data Loading...
