PaperlayerView exact revision on arXiv

Source-linked AI summary

On Graphical Modeling of Preference and Importance

R. I. Brafman, C. Domshlak, S. E. Shimony

arXiv:1109.6345v1cs.AI

TL;DR

Utility functions can be costly to elicit, while CP-nets do not capture intuitive statements about the relative importance of attributes. The paper introduces TCP-nets, which combine conditional preference and importance relations in a graphical qualitative model for consistency checking and constrained optimization. TCP-nets provide richer preference representations and support computational analysis, while open questions remain for dominance testing, cyclic networks, expressive power, and set-level importance.

  • Problem

    Utility-function elicitation is costly, and CP-nets do not represent intuitive statements about the relative importance of attributes needed to express tradeoffs.

  • Method

    The paper extends CP-nets with absolute and conditional relative-importance relations, forming graphical TCP-nets for qualitative preference representation and reasoning.

  • Results

    TCP-nets support consistency testing, preferential reasoning, and constrained optimization, with graphical structure exploitable for efficiency in conditionally acyclic cases.

  • Takeaways & Limitations

    Relative-importance information lets TCP-nets represent user tradeoffs more richly while retaining simple qualitative preference statements.

  • Takeaways & Limitations

    The precise complexity of dominance testing, consistency of non-conditionally-acyclic TCP-nets, and the expressive power of TCP-nets remain open questions.

Abstract

from arXiv · show

In recent years, CP-nets have emerged as a useful tool for supporting preference elicitation, reasoning, and representation. CP-nets capture and support reasoning with qualitative conditional preference statements, statements that are relatively natural for users to express. In this paper, we extend the CP-nets formalism to handle another class of very natural qualitative statements one often uses in expressing preferences in daily life - statements of relative importance of attributes. The resulting formalism, TCP-nets, maintains the spirit of CP-nets, in that it remains focused on using only simple and natural preference statements, uses the ceteris paribus semantics, and utilizes a graphical representation of this information to reason about its consistency and to perform, possibly constrained, optimization using it. The extra expressiveness it provides allows us to better model tradeoffs users would like to make, more faithfully representing their preferences.

1. Introduction

Preference representation supports many AI decision applications, but utility-function elicitation can be costly and qualitative alternatives must remain easy to obtain and reason with. TCP-nets extend CP-nets with relative-importance information while preserving intuitive qualitative statements and enabling consistency testing and preferential reasoning.

  • Explicit preference information is often required to compare alternatives in AI applications such as recommendation, configuration, and constrained optimization.
  • Utility-function elicitation is involved, time-consuming, and effortful, making it impractical when users cannot engage for lengthy periods or lack decision-analyst support.
  • Qualitative preference representations should be naturally elicitable, amenable to automation, and computationally effective for reasoning.
  • CP-nets graphically represent conditional preferences by describing how preference over one variable depends on other variables.
  • Relative-importance statements express that improving one attribute matters more than improving another, including conditional versions whose ordering depends on context.
  • TCP-nets extend CP-nets with conditional relative importance, increasing expressive power while supporting consistency testing and preferential reasoning through graphical structure.

2. Preference Orders, Independence, and Relative Importance

This section formalizes preference orders, preferential independence, and relative importance as compact qualitative components for representing and comparing outcomes. Relative importance resolves comparisons left open by independence, which is especially useful under constraints that prevent selecting the unconstrained best outcome.

  • TCP-nets model preferences as strict partial orders over outcomes, excluding indifference because the language permits incomparability but not equal preference.
  • Outcomes are complete assignments to variables, but their exponential number makes explicit preference-order representation impractical.
  • Preferential independence means that preferences over one variable set remain unchanged across assignments to another set.
  • Conditional preferential independence allows the ranking of one variable set to depend on a fixed assignment to a conditioning set while remaining independent of another set.
  • Independence alone can leave outcomes incomparable when both attributes change, whereas relative importance orders such tradeoffs by favoring improvement in the more important attribute.
  • Relative importance is valuable under budget or resource constraints because it identifies which attributes to preserve when the unconstrained best outcome is unavailable.
  • Absolute relative importance requires one attribute’s improvements to dominate another’s across assignments, while conditional relative importance permits that ordering to depend on context.

3. TCP-nets

TCP-nets extend CP-nets with absolute and conditional relative-importance statements alongside conditional preferences. Their semantics supports satisfiability and preferential entailment, while the added importance information helps compare feasible compromises under constraints.

  • Model and purpose: TCP-nets extend CP-nets by encoding conditional relative-importance statements in addition to conditional preference statements.Their graphical structure supports consistency analysis and reasoning over these combined constraints.
  • Graphical representation: A TCP-net uses directed cp-arcs for preferential dependencies, directed i-arcs for unconditional importance, and undirected ci-arcs for conditional importance.Nodes represent problem variables; CPTs encode conditional preferences, while CITs associate importance orders with ci-arcs.
  • Graphical representation: Each ci-arc has a selector set whose assignments determine the applicable relative-importance ordering between its two variables.The CIT may specify importance only for some selector-set assignments, so the mapping can be partial.
  • Semantics: TCP-net semantics defines preference orders over complete outcomes that satisfy the CPT, i-arc, and ci-arc constraints; satisfiability requires at least one such order.Preferential entailment holds when an outcome ordering appears in every preference order satisfying the TCP-net.
  • Semantics: Preferential entailment is transitive: if a satisfiable TCP-net entails o ≻ o′ and o′ ≻ o′′, it entails o ≻ o′′.The result follows because every satisfying preference order is transitive.
  • Applications and scope: Importance information helps TCP-nets select more desirable feasible compromises when resource constraints exclude an otherwise optimal assignment.The evening-dress example illustrates how preferring one attribute over another can distinguish among constrained alternatives.
  • Applications and scope: More complex importance relations can be represented by clustering variables, but this may sacrifice compactness or reasoning efficiency compared with an alternative representation.The paper identifies finding compact representations that improve reasoning efficiency as a topic for future research.

4. Conditionally Acyclic TCP-nets

The paper defines conditional acyclicity for TCP-nets by requiring every selector assignment to induce an acyclic dependency graph, then proves that every such network is satisfiable. The proof constructs a preference ordering recursively, revealing a context-dependent ordering of variable importance.

  • Definition and motivation: Conditional acyclicity requires every assignment to the selector variables to produce an acyclic w-directed dependency graph.The dependency graph adds selector-to-endpoint edges for conditional-importance arcs, while the w-directed graph orients those arcs according to the assigned context.
  • Supporting lemmas: Conditional acyclicity is hereditary: removing variables, edges, or preference and importance information preserves the property.Removing these elements can only remove cycles from the w-directed graphs.
  • Constructive proof: The constructive proof selects a root variable, restricts the remaining networks to each of its values, and recursively combines the resulting preference orders.Conditional-importance tables may become fixed directed importance arcs or disappear after restriction.
  • Satisfiability guarantee: Every conditionally acyclic TCP-net is satisfiable, and in fact has a strict total order satisfying its preference statements.The result is established constructively by induction on the number of variables.
  • Interpretation: The induced variable ordering depends on assignments to preceding variables, with earlier variables more important in the corresponding context.This context-dependent ordering explains why selector variables must precede the endpoints of conditional-importance arcs.
  • Necessity of the definition: A three-variable example shows that acyclicity of the ordinary w-directed graphs is insufficient when selector dependencies are omitted from the dependency graph.The resulting preference constraints would violate antisymmetry, so the stronger dependency-graph construction is necessary.

5. Verifying Conditional Acyclicity

The paper characterizes conditional acyclicity through semi-directed cycles in a TCP-net’s dependency graph, then analyzes the complexity of testing it and identifies tractable subclasses. Conditional acyclicity guarantees satisfiability, but general verification is computationally hard.

  • Definition and decomposition: A semi-directed cycle contains a simple mixed-edge cycle whose directed edges all point consistently around the cycle.It must contain at least one undirected edge; assignments to selector sets orient its conditional-importance arcs.
  • Definition and decomposition: Conditional acyclicity holds exactly when every semi-directed cycle remains conditionally acyclic under all relevant selector assignments.Lemma 4 makes verification decomposable across semi-directed cycles, and the figures illustrate conditionally directed versus conditionally acyclic configurations.
  • Complexity: Determining whether a binary-valued TCP-net has a conditionally directed cycle is NP-complete, even when every ci-arc has one selector.The hardness proof reduces from 3-SAT, while membership in NP follows from polynomial-time verification of a cycle under a guessed assignment.
  • Cycle conditions: For a semi-directed cycle containing directed edges, conditional acyclicity requires every shared-selector assignment to orient some ci-arc opposite the cycle’s direction.For cycles containing only ci-arcs, the corresponding condition requires two ci-arcs oriented in opposite directions for each shared-selector assignment.
  • Tractable subclasses: The number and selector-set structure of semi-directed cycles determine tractability: polynomially many cycles with selector sets of size at most two yield a polynomial-time test.More generally, small cycle counts, small shared selector sets, or small selector sets support efficient subclasses; pairwise-disjoint selector sets imply conditional directedness.

6. Reasoning about Conditionally Acyclic TCP-nets

This section develops reasoning and constrained-optimization procedures for conditionally acyclic TCP-nets. Search-TCP generates preferentially non-dominated feasible outcomes, while dominance can be tested through improving flipping sequences.

  • Reasoning tasks: Conditionally acyclic TCP-nets support efficient reasoning tasks including preference-based optimization, constrained optimization, and outcome comparison.These tasks are presented as central requirements for reasoning about qualitative preferences.
  • Generating optimal assignments: Search-TCP extends branch-and-bound optimization for acyclic CP-nets to conditionally acyclic TCP-nets while retaining an anytime property.The algorithm follows the TCP-net’s hierarchical partial orders of importance during search.
  • Generating optimal assignments: Search-TCP recursively assigns variables in a graph-guided top-down order, prunes restrictive or inconsistent branches, and searches disconnected components independently.Pruning is justified because feasible outcomes in pruned branches are dominated by outcomes from earlier branches.
  • Generating optimal assignments: Theorem 5 states that Search-TCP returns exactly the feasible outcomes that are non-dominated under the conditionally acyclic TCP-net.The generated set contains an outcome if and only if it satisfies the hard constraints and no feasible outcome is preferred to it.
  • Generating optimal assignments: For one non-dominated feasible solution, Search-TCP can stop at the first feasible outcome; obtaining multiple solutions requires preferential comparisons between outcomes.The generated global solution set does not shrink as search proceeds.
  • Dominance testing: TCP-net dominance holds exactly when an improving flipping sequence connects the less-preferred outcome to the more-preferred outcome.An improving sequence consists of successive preference-sanctioned CP-flips or I-flips.

7. Discussion

The paper extends CP-nets with relative-importance information, yielding TCP-nets for preference representation and reasoning. The discussion covers consistency, optimization, preference elicitation, and unresolved theoretical and empirical questions.

  • Contributions: TCP-nets extend CP-nets with absolute and conditional relative importance between variables, while preserving qualitative preference representation.The extended model captures both conditional preferential independence and conditional relative importance.
  • Consistency and optimization: The paper identifies conditionally acyclic TCP-nets as a wide satisfiable class and analyzes membership testing and outcome optimization with and without hard constraints.The optimization focus includes reasoning over feasible outcomes under constraints.
  • Open problems: Future work includes the complexity of dominance testing, consistency of non-conditionally-acyclic TCP-nets, and the expressive power of importance statements.The paper also notes that users’ comfort with specifying relative importance among sets of attributes requires empirical verification.
  • Preference elicitation: TCP-net elicitation can begin with variables and influencing relationships, or users can provide preference statements from which a network is extracted.Natural-language acquisition and structured interfaces are discussed as practical routes to model construction.
  • Preference elicitation: Learning a compact TCP-net from pairwise comparisons remains an open question because the model must generalize beyond the observed examples.The unresolved issue is whether a reasonably small comparison set can support justifiable generalization.
Loading 1109.6345v1…