PaperlayerView exact revision on arXiv

Source-linked AI summary

CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements

C. Boutilier, R. I. Brafman, C. Domshlak, H. H. Hoos, D. Poole

arXiv:1107.0023v1cs.AI

TL;DR

Preference elicitation needs representations that support qualitative judgments without requiring exhaustive quantitative assessments. The paper introduces CP-nets, a graphical model with conditional ceteris paribus semantics, and develops inference procedures for comparison and optimization. It shows that optimization and ordering are tractable in key cases, while dominance is generally hard but admits polynomial algorithms for tree- and polytree-structured binary networks.

  • Problem

    Preference elicitation is arduous, and typical users may be unable or unwilling to provide detailed preference relations or utility functions.

  • Method

    The paper introduces CP-nets, a compact graphical representation of conditional ceteris paribus preferences, and develops algorithms and search techniques for outcome inference.

  • Results

    Outcome optimization and ordering are solvable in time linear in the number of variables, while dominance is NP-hard in general and polynomial for tree- and polytree-structured binary CP-nets.

  • Takeaways & Limitations

    CP-nets support structured qualitative preference reasoning across outcome comparison, ordering, optimization, and applications such as constraint-based product configuration.

  • Takeaways & Limitations

    Binary-valued acyclic dominance queries may require flipping sequences exponential in the number of variables, and their exact complexity remains open.

Abstract

from arXiv · show

Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.

1. Introduction

The paper introduces CP-nets as a compact, intuitive graphical language for eliciting qualitative preferences through conditional ceteris paribus statements. It targets preference comparison and optimization while balancing flexible expression against structured representation.

  • Motivation: Preference elicitation is arduous, especially for non-expert users who often can provide only qualitative rankings of circumscribed outcomes.The paper situates this need across applications including collaborative filtering, recommender systems, product configuration, and medical decision making.
  • Contribution: CP-nets represent preference relations compactly and intuitively using conditional ceteris paribus statements.The representation captures conditional dependence and independence by specifying preferences over an attribute’s values for each parent-variable assignment.
  • Scope: The model primarily addresses preferences over decision outcomes, while also accommodating likelihood orderings over possible world states.The paper’s inference techniques focus on comparing outcomes and finding an optimal outcome under partial assignments.
  • Inference tasks: The paper develops inference techniques for preferential comparison and for finding optimal outcomes given partial information.These tasks are presented as central uses of the proposed representation.
  • Novelty: CP-nets aim to balance flexible preference expression with a structured preference form that captures conditional statements.This distinguishes the representation from approaches that impose stronger utility or preference structures while omitting conditional preferences.

2. Model Definition

The paper defines CP-nets as graphical representations of qualitative preference relations using conditional ceteris paribus semantics. It establishes core entailment and satisfiability properties, while showing that cyclic networks and unresolved tradeoffs require care.

  • 2.1 Preference Relations: Preference relations rank complete outcomes, while assignments may be complete or partial over the problem variables.The framework assumes single-stage decision problems with complete information and excludes sequential decisions and risk under uncertainty.
  • 2.1 Preference Relations: Directly assessing preferences is usually infeasible because the number of assignments grows exponentially with the variables’ domain sizes.Structural regularities therefore motivate concise preference representations.
  • 2.3 Semantics: Ceteris paribus semantics deliberately leaves some tradeoffs unspecified when preferences concern independently assessed attributes.For example, separate preferences over A and B do not determine which mixed outcome is preferred when the jointly best outcome is infeasible.
  • 2.2 CP-Networks: CP-nets are directed graphs whose variables are annotated with conditional preference tables specifying local value orders.The structures exploit conditional preferential independence to organize user preferences.
  • 2.3 Semantics: Every acyclic CP-net is satisfiable, and preferential entailment is transitive through the closure of directly specified preference relations.The semantics can therefore derive indirect comparisons from sequences of directly supported comparisons.
  • 2.4 Cyclic Networks: Cyclic CP-net consistency depends on the actual conditional preference tables, so some cyclic networks are satisfiable and others are not.The paper notes that clustering variables can preserve acyclicity but may increase description space and reduce reasoning efficiency.
  • 2.3 Semantics: Equal preference statements have strong consequences under ceteris paribus semantics.The paper flags this as a nontrivial property of the model’s interpretation of indifference.

3. Outcome Optimization

CP-nets identify the best outcome by sweeping variables from ancestors to descendants, selecting each variable’s preferred value conditional on its parents. The same procedure optimizes outcomes under evidence constraints and supports adaptive multimedia presentation after viewer choices.

  • Outcome Optimization: The procedure takes time linear in the number of variables.It can optimize a constrained outcome by sweeping the network while preserving the imposed evidence.
  • Outcome Optimization: A forward sweep through an acyclic CP-net sets each unconstrained variable to its most preferred value given its parents.The variables are processed in topological order while evidence-constrained variables remain fixed.
  • Outcome Optimization: The forward sweep constructs the most preferred completion of any partial assignment.The result is unique when the CP-net contains no indifference.
  • An Example Application: In the multimedia application, an acyclic CP-net captures the content provider’s presentation preferences and initializes the document presentation.The viewing tool then recomputes an optimal presentation subject to the viewer’s recent content choices.
  • An Example Application: The multimedia document example contains six medical components whose presentation options and conditional preferences are represented in the CP-net.The components include CT-image, X-ray, Graph, Notes, X-ray-old, and Notes-old.
  • An Example Application: Viewer choices constrain document components, after which the forward sweep updates dependent presentations such as X-ray, Notes, and other medical-content components.The example shows successive updates after zooming into CT-image, hiding X-ray, and displaying the whole CT-image.

4. Comparing Outcomes

CP-nets support preferential comparison through dominance and ordering queries. Dominance establishes that one outcome is preferred to another, whereas ordering asks whether that preference is consistent with the network’s information.

  • Comparing Outcomes: A CP-net may leave two outcomes incomparable when it cannot prove either outcome preferred to the other.The third possible relation is that neither directional preference is entailed.
  • Comparing Outcomes: A dominance query asks whether a CP-net entails that outcome o is preferred to outcome o′.If so, o dominates o′ with respect to the network.
  • Comparing Outcomes: An ordering query asks whether a preference ordering consistent with the CP-net can place o above o′.Ordering is weaker than dominance because it need not establish that o is preferred to o′ in every model.
  • Comparing Outcomes: For acyclic CP-nets, the paper develops linear-time ordering queries, outcome sorting using ordering queries, and complexity results for dominance queries.The analysis uses flipping sequences to study dominance-query complexity, especially for binary-valued networks.

4.1 Ordering Queries Are Easy

Ordering queries on acyclic CP-nets can be answered in linear time, and ordering queries can produce a consistent non-increasing ordering of any given set of outcomes. The query test is sound but incomplete for individual directions, while paired queries provide enough information for polynomial-time sorting.

  • Ordering Queries Are Easy: Acyclic CP-nets support linear-time ordering queries even when variables are not binary-valued.The algorithm exploits the graphical structure of the network.
  • Ordering Queries Are Easy: The sufficient condition from Corollary 4 identifies a direction that can be consistently ordered but is not necessary for consistent orderability.The dinner example contains incomparable outcomes that the condition fails to recognize.
  • Ordering Queries Are Easy: O(n) time is sufficient to determine whether at least one of two opposing ordering queries holds for outcomes in an acyclic CP-net.The algorithm identifies variables where the outcomes differ while sharing assignments on relevant ancestors.
  • Ordering Queries Are Easy: Theorem 5 guarantees that at least one of the two opposing ordering queries can be resolved in O(n) time.This gives a consistent ordering for each pair even though a single directional test may be incomplete.
  • Ordering Queries Are Easy: The single-query algorithm is sound but incomplete: a negative response does not rule out the queried ordering relation.Paired queries are partially complete because they return a positive answer for at least one direction.
  • Ordering Queries Are Easy: Theorem 6 establishes that any set of outcomes can be ordered consistently with an acyclic CP-net using ordering queries only.The result relies on the asymmetric relation generated by paired ordering queries.
  • Ordering Queries Are Easy: Ordering any m outcomes consistently with an acyclic CP-net using pairwise ordering queries has complexity O(nm^2).This corresponds to comparing every pair of outcomes and ordering them accordingly.

4.2 Dominance Queries and Flipping Sequences

CP-nets use improving flips—single-variable changes sanctioned by conditional preferences—to establish dominance between outcomes, while some outcomes remain incomparable. For acyclic networks, flipping sequences are both sound and complete for dominance queries.

  • Limitations: CP-net semantics leaves some trade-offs unresolved when multiple lower-level violations must be weighed against one higher-level ancestor violation.Consequently, two outcomes can be unordered even though ancestor preferences have greater importance than descendant preferences.
  • Preference graphs: Every improving flipping sequence corresponds to a directed path in the preference graph induced by the CP-net.In the Evening Dress example, four paths connect ¯a¯bc to abc, establishing abc ≻ ¯a¯bc; the reverse comparison has no path and is incomparable.
  • Flipping sequences: An improving flip changes one variable to a more preferred value while holding the other variables fixed.Such flips are conditioned on the current values of the variable’s parents.
  • Flipping sequences: An improving flipping sequence is a chain of outcomes in which each step is an improving flip; reversing it yields a worsening sequence.These sequences provide constructive paths between outcomes in the preference graph.
  • Dominance results: Theorem 7 establishes soundness: an improving flipping sequence from o to o′ entails that o′ is preferred to o.The result follows because each improving flip is preference-entailing and preferential entailment is transitive.
  • Dominance results: For acyclic CP-nets, Theorem 8 establishes completeness: without an improving sequence from o to o′, the network does not entail o′ ≻o.Thus, absence of a directed path certifies that the queried dominance relation is not entailed.

4.3 Flipping Sequences as Plans

The paper recasts dominance queries as planning problems by translating conditional preference statements into value-improving operators. A dominance query holds exactly when the corresponding planning problem has a plan, connecting CP-net reasoning to established planning complexity analyses.

  • Operator construction: Each conditional preference statement in a CPT can be converted into d−1 planning operators for improving a variable with d domain values.The operators improve xi to xi−1 under the parent assignment u; inverse operators represent worsening sequences.
  • Query reduction: A dominance query N |= x ≻y treats y as the planning start state and x as the goal state.The query is entailed exactly when a plan exists, because plans correspond to improving flipping sequences.
  • Complexity connection: Dominance queries over binary-valued CP-nets correspond to a specific class of STRIPS planning problems whose complexity has been analyzed previously.General finite-domain planning is known to be PSPACE-complete, including under binary-variable restrictions.
  • Complexity connection: For binary-valued CP-nets, the generated planning problems have unary operators and causal graphs matching the CP-net graph.This correspondence permits use of results for binary-variable planning with unary operators and acyclic causal graphs.

4.4 Complexity of Dominance Queries for Binary-valued, Acyclic CP-nets

For binary-valued acyclic CP-nets, dominance-query complexity depends sharply on network structure, ranging from quadratic or polynomial cases to NP-complete cases. Tree-structured networks admit a sound, complete, asymptotically optimal backtrack-free search, while the general acyclic case remains unresolved.

  • General properties: For directed-path singly connected CP-nets, each variable changes value at most n times in an irreducible improving flipping sequence.This bound follows from the network structure and is used in the complexity analysis of dominance testing.
  • Tree-structured CP-nets: Binary-valued tree-structured CP-nets support a sound and complete deterministic dominance algorithm, TreeDT, that generates only irreducible improving flipping sequences.The algorithm is backtrack-free and therefore provides correct positive answers to dominance queries.
  • Tree-structured CP-nets: O(n^2) is both the time complexity and a lower bound for flipping-sequence search over binary-valued tree-structured CP-nets.Quadratic-length minimal flipping sequences occur even for chain CP-nets, making TreeDT asymptotically optimal.
  • Polytree CP-nets: Dominance testing for binary-valued polytree CP-nets is polynomial in the size of the CP-net description.Polytrees are acyclic when their directed edges are treated as undirected, extending directed trees while retaining polynomial-time dominance testing.
  • Intractable dominance queries: Dominance testing is NP-complete for binary-valued directed-path singly connected CP-nets, even when node in-degree is bounded by a low constant.The same hardness persists when the number of alternative paths between node pairs is polynomially bounded.
  • Intractable dominance queries: The exact complexity of dominance testing for multiply connected binary-valued acyclic CP-nets remains open, with the problem known to be hard.With unbounded node in-degree, some dominance queries may require flipping sequences exponential in n.

5. Search Techniques for Dominance Queries

The paper develops search techniques for dominance queries by exploiting CP-net structure to prune improving-flip search trees. Suffix fixing preserves completeness generally, whereas least-variable flipping is complete only under specific structural conditions and can be incomplete in multiply connected networks.

  • Search trees: Improving search trees represent all improving flipping sequences from an outcome and can be searched to answer dominance queries.Each tree node’s children are outcomes reachable by one improving flip.
  • Suffix fixing: Suffix fixing prunes paths that destroy a suffix already matching the target outcome.The rule retains only paths preserving the matching suffix values.
  • Suffix fixing: Any complete improving-search algorithm remains complete when suffix fixing is applied.This follows because an existing path can be transformed into one that preserves the matched suffix throughout.
  • Least-variable flipping: The least-variable rule restricts search to flips of variables that are lowest among those that can be improved, reducing candidate branches and backtracking.TreeDT implements this rule for binary-valued, tree-structured CP-nets, where the procedure is complete and backtrack-free.
  • Least-variable flipping: For binary-valued, directed-path singly connected CP-nets, a path to the target implies that some permitted least-variable flip also leads to the target.This structural result supports completeness of least-variable pruning in that class.
  • Least-variable flipping: The least-variable rule can be incomplete in multiply connected CP-nets because the only permitted least-improvable flip may lead to an unreachable target.A valid sequence may instead require flipping a non-least-improvable variable first.

6. Incompletely Specified Preferences and Indifference

The paper extends most CP-net results to partially specified preferences and preferential indifference, while identifying unresolved complexity questions. Optimization can return multiple nondominated outcomes, and its extended procedure branches over those alternatives.

  • Extensions: Most results extend to CP-nets with partially specified CPTs and satisfiable CP-nets expressing preferential indifference.The stated exception is the linear-time procedure for ordering queries.
  • Complexity: Flipping-sequence search for multi-valued CP-nets with partially specified preferences is not in np, even for chain networks with three-valued variables.This result is stated as Theorem 20.
  • Optimization: Partially specified preferences or indifference can produce multiple nondominated outcomes instead of a single optimum.The paper illustrates this with a dinner configuration where two wine choices remain nondominated.
  • Optimization: The extended forward-sweep optimization procedure branches whenever a variable has multiple nondominated values under the current parent assignment.Its complexity is O(nα), where α is the number of nondominated outcomes.
  • Optimization: Generating k nondominated solutions is linear in k because adding each generated solution costs O(n).The tight upper bound on the number of nondominated outcomes is α = 2^n when all CPTs are unspecified.
  • Extensions: Ordering-query complexity for extended CP-nets remains open, and the authors conjecture that the problem is hard.The standard ordering algorithm remains sound, but the paper’s stronger theorem does not extend to these settings.

7. Concluding Remarks

The paper concludes that CP-nets provide a compact qualitative preference model with efficient inference for several query types, while dominance reasoning remains difficult in general. It also identifies applications, extensions, and open theoretical boundaries.

  • Contributions: CP-nets represent qualitative preference orderings with conditional dependence and independence under ceteris paribus semantics.The framework is presented as compact and natural for preference information.
  • Results: Outcome optimization and outcome ordering are solvable in time linear in the number of network variables.Dominance queries are treated separately because their general complexity is higher.
  • Results: Dominance queries are np-hard in general, while polynomial algorithms exist for binary-valued CP-nets with tree or polytree structure.The paper connects dominance to improving or worsening flip-sequence existence and to a subclass of classical planning problems.
  • Search techniques: Search techniques can preserve soundness and completeness for some CP-net classes, while other techniques are proposed as general heuristics for reducing expanded search trees.The latter techniques may significantly reduce search effort without the same universal guarantee.
  • Applications: The framework is applied or proposed for adaptive multimedia presentation, meeting scheduling, product sorting, and constraint-based product configuration.Configuration combines user preferences with compatibility constraints to seek preferred feasible products.
  • Open questions: Open questions include dominance complexity for acyclic binary and multi-valued CP-nets, ordering complexity for extended CP-nets, and the expressive power of CP-nets.Cyclic networks additionally require satisfiability and inference methods.

Appendix A.

Appendix A establishes complexity bounds for CP-net inference by analyzing improving flipping sequences and reductions. It shows that some dominance and search problems become computationally difficult even for restricted network structures.

  • Flipping-sequence search: Θ(n^2) is a lower bound for flipping-sequence search over binary-valued, tree-structured CP-nets.The proof uses a binary directed-chain construction whose required variable flips accumulate quadratically.
  • Dominance testing: Dominance testing for binary-valued, directed-path singly connected CP-nets is NP-complete.Membership in NP follows because a guessed minimal improving flipping sequence can be verified in polynomial time; hardness is shown by reduction from 3-SAT.
  • Dominance testing: The 3-SAT reduction constructs a binary directed-path singly connected CP-net with at most six parents per variable.An improving sequence from the all-false outcome to the all-true outcome exists exactly when the encoded formula has a satisfying assignment.
  • Dominance testing: For binary-valued CP-nets with polynomially bounded δ, dominance testing remains NP-complete.A polynomial upper bound on minimal flipping-sequence length gives polynomial verification, while the theorem establishes hardness for the class.
  • Multi-valued preferences: Flipping-sequence search over multi-valued CP-nets with partially specified preferences is harder than NP.The construction yields dominance queries with exponentially sized minimal flipping sequences.
Loading 1107.0023v1…