TL;DR
This paper introduces a novel query-based algorithm for learning acyclic conditional preference networks (CP-nets) that robustly handles contradictory or noisy user preferences. By incorporating a mechanism to manage violated rules, the algorithm achieves good accuracy on both synthetic and real-world datasets, offering a more practical approach to preference learning in complex scenarios.
What Problem Does This Paper Address?
Representing user preferences is crucial for many AI applications, such as recommendation systems. Conditional Preference Networks (CP-nets) offer a powerful and intuitive graphical framework for this, but learning them is computationally challenging, especially when user preferences are not perfectly consistent (i.e., they are noisy or contradictory). Existing methods often assume coherent preferences, which is unrealistic in practice. This paper tackles the problem of learning CP-nets from data that may contain such inconsistencies, aiming to build a more robust and practical preference learning system.
Methods
The authors propose a new query-based learning algorithm for acyclic CP-nets that is divided into two phases: a general learning phase and a parent search phase.
- General Learning Phase: This phase iteratively refines a learned CP-net (NL) based on counterexamples provided by an oracle (user or dataset). A key innovation here is the introduction of a list of "violated rules" (L) that cannot be represented in the current NL. This allows the algorithm to proceed even when faced with inconsistencies, by essentially "ignoring" these problematic rules during equivalence checks.
- Parent Search Phase: When a counterexample suggests a new rule, this phase searches for the most appropriate parent variable for the rule's target variable. The algorithm prioritizes parent variables that minimize the number of violated rules, aiming to maintain overall coherence. It also includes a check for acyclicity to ensure the learned network remains valid.
The algorithm leverages equivalence queries (EQ) and membership queries (MQ) to interact with the oracle, similar to prior work, but with the added robustness to handle inconsistencies.
Datasets
The paper evaluates its algorithm on two types of datasets:
- TripAdvisor Dataset: A real-world dataset containing approximately 240,000 hotel reviews. For this study, the review ratings were rescaled to binary values (0 or 1) to create a binary CP-net. This dataset is noted to potentially contain incoherences.
- Randomly Generated Datasets: Synthetic datasets were created to test the algorithm's scalability and robustness to incoherences. These datasets were generated with varying numbers of objects (50, 500, 10000) and attributes (5, 9, 15), and a preprocessing step transformed object data into a set of swaps.
Key Insights and Ideas
- Robustness to Incoherence is Key: The most significant insight is that explicitly handling contradictory preferences (via the "violated rules" list) is crucial for practical CP-net learning. Ignoring these inconsistencies leads to significantly lower accuracy.
- Query-Based Learning with Error Handling: The algorithm effectively adapts query-based learning by incorporating a mechanism to manage and minimize the impact of inconsistent data, making it more applicable to real-world scenarios where perfect data is rare.
- Parent Selection Matters: The parent search phase's strategy of selecting parents that minimize rule violations is critical for building a coherent and accurate CP-net.
- Trade-off Between Acyclicity and Completeness: Relaxing the acyclic condition allows for exact fitting of the target CP-net but comes at a significant computational cost, highlighting the practical benefits of focusing on acyclic structures.
Key Results
- Good Accuracy on Real Data: The algorithm achieved a good accuracy of 0.82 on the TripAdvisor dataset when allowing up to 5 parents per variable, demonstrating its effectiveness on noisy real-world data.
- Scalability: The algorithm shows reasonable scalability, with learning times increasing linearly with the number of parents and objects. For instance, learning a CP-net with 15 variables and 10,000 objects took around 150 seconds.
- Impact of Parents: Accuracy generally increases with the number of allowed parents per variable, up to a certain point. There's a notable drop in accuracy between p=1 (tree-shaped) and p=2, suggesting that more complex structures might require more data or careful handling.
- Coherence Improves Accuracy: The experiments showed a clear gap in accuracy between datasets with coherent preferences and those with incoherences, especially for larger datasets.
Limitations and Future Work
- Computational Complexity: While the algorithm is more robust, its complexity can still be exponential in the number of parents and objects (as per Proposition 2). The paper notes that the computation time increases linearly with the number of objects and parents, making large datasets a challenge.
- Parallelization: The parent search procedure is identified as a candidate for parallelization, which could significantly reduce learning time, especially for large datasets.
- Approximate Strategies: The authors suggest exploring approximate strategies for equivalence queries to reduce computational burden, potentially sacrificing perfect fitting for faster learning with accuracy guarantees.
- Randomness of Counterexamples: The random nature of counterexamples from equivalence queries can sometimes lead to erroneous rule generation, which is an area for future improvement.
Summary updated