Abstract
Learning user preferences is a cornerstone of modern AI research, particularly the acquisition of Conditional Preference Networks (CP-nets) from partial information. This paper establishes the theoretical foundations for the information complexity of acyclic CP-nets. We provide exact values and tight bounds for central learning-theoretic parameters, including VC dimension (VCD), teaching dimension (TD), recursive teaching dimension (RTD), self-directed learning complexity (SDC), and the optimal mistake bound (OPT). Furthermore, we introduce an efficient algorithm for learning tree-structured CP-nets using only membership queries, demonstrating that these structures are more accessible than previously established.
Introduction: Modeling Preferences with CP-nets
Conditional Preference Networks (CP-nets) are a popular graphical model for representing qualitative preferences under ceteris paribus (all other things being equal) assumptions. They effectively capture conditional dependencies, such as preferring red wine over white only when the entree is meat.
Despite their popularity, the mathematical limits of learning these networks—their information complexity—remained poorly understood. Previous literature often relied on rough estimates or incorrect bounds. This research provides a rigorous theoretical framework to quantify exactly how many examples or queries are necessary for a learner to identify a specific CP-net within a given class.
Methodology and Complexity Parameters
The authors analyze acyclic CP-nets by decomposing them into a direct product of simpler concept classes. This allows for the summation of complexities across individual preference tables. The study focuses on several key information-theoretic parameters:
- VC Dimension (VCD): Measures the capacity of the class to shatter sets of instances.
- Teaching Dimension (TD) & Recursive Teaching Dimension (RTD): Quantifies the minimum number of examples a teacher must provide to uniquely identify a concept.
- Self-Directed Learning Complexity (SDC): The number of mistakes an active learner makes when selecting their own training instances.
- Optimal Mistake Bound (OPT): The worst-case mistake count in an online learning setting.
Key Results
The primary contribution of this work is the derivation of exact complexity values for various subclasses of CP-nets, summarized in the table below.
Significant findings include:
- Acyclic vs. Consistent: The VC dimension for acyclic CP-nets is identical to that of the broader class of consistent CP-nets, suggesting that acyclicity does not reduce information-theoretic complexity.
- Unbounded Acyclic CP-nets: For these networks, VCD, RTD, and SDC are all exactly $m^n - 1$, where $m$ is the domain size and $n$ is the number of variables.
- Separable CP-nets: In the absence of dependencies, complexity drops to $(m - 1)n$.
- Correcting Bounds: The paper identifies and corrects a previously accepted but erroneous lower bound for the VC dimension of $k$-bounded CP-nets.
Algorithmic Advances in Tree-Structured Learning
Beyond theoretical bounds, the paper presents a new query-based algorithm for learning tree-structured CP-nets. Unlike previous state-of-the-art methods that required both membership and equivalence queries, this algorithm relies solely on membership queries (e.g., "Is outcome $u$ preferred to $v$?").
By employing a binary search strategy to identify parent variables, the algorithm achieves a query complexity of $O(nm \log m) + e \log n$. For binary variables, this represents a significant efficiency gain, reducing the query count by a factor of two and simplifying the learning process by removing the need for complex hypothesis verification.
Conclusion and Future Directions
This work provides the first comprehensive map of the learning complexity of acyclic CP-nets. While exact values are established for unbounded and separable cases, future work remains to find matching upper bounds for $k$-bounded degree networks. Additionally, extending these algorithmic techniques to the broader class of consistent cyclic CP-nets and exploring the teaching dimensions of incomplete structures represent promising avenues for future research.
Summary updated