Abstract
Conditional Preference Networks (CP-nets) provide a structured way to model "all else being equal" preferences. However, standard CP-net frameworks often fail to capture the complexity of real-world decision-making, such as multi-valued features, indifference, and cyclic dependencies. This research outlines an agenda to extend CP-nets, introducing active elicitation heuristics and reasoning techniques that accommodate these complexities while maintaining computational tractability for real-world engineering and recommender systems.
Introduction
Humans frequently express preferences conditionally. For instance, a musician might state: "I prefer a heavy guitar over a light one, but if it's heavy, I want gold hardware; if it's light, I want red." CP-nets model these ceteris paribus (all else being equal) relationships, allowing for a compact representation of complex preference structures.
Despite their popularity in preference modeling, most CP-net research relies on "clean" assumptions that rarely hold in practice:
- Binary Features: Assuming choices are limited to binary pairs (e.g., A vs. B).
- Strictness: Assuming users always have a definitive preference, ignoring indifference.
- Acyclicity: Assuming preferences do not loop.
- Static Learning: Relying on passive observation rather than active inquiry.
Proposed Methodology
To bridge the gap between theory and practice, this research details several algorithmic approaches designed to increase the flexibility and robustness of CP-nets.
Active Elicitation and SAT Integration
Instead of relying on passive observation, the proposed approach utilizes a heuristic algorithm for active elicitation. By asking users to compare outcomes that may differ in multiple attributes simultaneously, the learning process is significantly accelerated. To manage the increased complexity of multi-valued variables and indifference, the research integrates SAT solvers to reason about preference consistency efficiently.
Reasoning via Flipping Sequences
Determining preference between two outcomes involves finding a "flipping sequence"—a chain of moves where each step improves the outcome according to the CP-net's rules. While theoretically complex, experimental results suggest that the "diameter" of these networks (the length of the longest flipping sequence) is typically short in practice, making them computationally tractable.
Addressing Cyclic Dependencies
A significant challenge in preference modeling is "coordination," which often creates cycles in dependency graphs. For example, a user might choose a belt based on their shoes, but also choose shoes based on their belt.
The research proposes three strategies for handling such cycles:
- Merging: Combining coordinated variables into a single composite node.
- Latent Variables: Inferring hidden factors that drive the observed cycle.
- Consistent Learning: Learning a consistent cyclic graph that reflects natural human behavior.
Evaluation and Key Insights
The research utilizes randomly generated CP-nets and simulated query processes to evaluate the proposed algorithms. Key findings include:
- Efficiency: The learning algorithm operates in $O(n^p)$ time, where $n$ is the number of features and $p$ is the maximum number of dependencies.
- Accuracy: In simulations, learned CP-nets showed high agreement with underlying "true" models on unseen preference comparisons.
- Robustness: The heuristic approach is designed to output a valid, consistent CP-net even when the user's internal model cannot be perfectly reconstructed.
Conclusion
While reasoning with multi-valued, incomplete CP-nets is theoretically "hard," this research demonstrates that practical applications remain feasible. Future work will focus on handling noisy or inconsistent human preferences and automatically detecting latent variables in cyclic structures. There remains a critical need for "factored preference data" from human subjects to further validate these models beyond synthetic simulations.
Summary updated