The Complexity of Learning Acyclic CP-Nets

Eisa Alanazi, Malek Mouhoub, Sandra ZillesIJCAI 2016 · OpenReview

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.

An example CP-net and its induced preference graph.

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.

Summary of complexity results for different classes of CP-nets.

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

Abstract

Learning of user preferences has become a core issue in AI research. For example, recent studies investigate learning of Conditional Preference Networks (CP-nets) from partial information. To assess the optimality of learning algorithms as well as to better understand the combinatorial structure of CP-net classes, it is helpful to calculate certain learning-theoretic information complexity parameters. This paper provides theoretical justification for exact values (or in some cases bounds) of some of the most central information complexity parameters, namely the VC dimension, the (recursive) teaching dimension, the self-directed learning complexity, and the optimal mistake bound, for classes of acyclic CP-nets. We further provide an algorithm that learns tree-structured CP-nets from membership queries. Using our results on complexity parameters, we can assess the optimality of our algorithm as well as that of another query learning algorithm for acyclic CP-nets presented in the literature.
BibTeX
@inproceedings{alanazi2016complexity,
  author = {Eisa Alanazi and Malek Mouhoub and Sandra Zilles},
  title = {{The Complexity of Learning Acyclic CP-Nets}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=Hk-E0GMdZH},
}

Loading related content...

Figure