Learning Conditional Preference Networks: An Approach Based on the Minimum Description Length Principle

Pierre-François Gimenez, Jérôme MenginIJCAI 2024

Introduction

In complex combinatorial markets, such as automotive configuration or custom electronics, the number of possible product variants is vast. Traditional recommender systems often struggle to capture the nuanced, conditional preferences of users in these spaces. This paper presents a novel approach to learning Conditional Preference Networks (CP-nets) directly from sales history, bypassing the need for intrusive pairwise comparisons. By leveraging the Minimum Description Length (MDL) principle, the authors provide a computationally efficient framework for real-time preference modeling and recommendation.

Problem Statement: Learning from Sales History

CP-nets are a popular graphical model for representing qualitative preferences. They excel at handling conditional logic—for instance, a user's preference for an engine type may depend on their choice of vehicle body style.

A CP-net $\phi_0$ and its induced preference graph (swaps).

The primary challenge addressed here is unsupervised learning: extracting preference structures from "sales history" (the final configurations chosen by past customers) rather than active elicitation. While most CP-net learning algorithms rely on asking users to compare pairs of items, such data is rarely available in industrial databases.

Methodology: The MDL Principle

The authors propose an algorithm based on the MDL principle, which posits that the best model is the one that provides the most concise description of the observed data.

  1. MDL Scoring and NMCL: The researchers define a scoring function where a CP-net that accurately reflects user preferences will assign shorter codes to the items actually purchased. They introduce Normalized Mean Code Length (NMCL) as a surrogate loss function to facilitate theoretical analysis.
  2. Structural Learning: Finding the optimal CP-net structure is proven to be NP-complete. To address this, the authors employ a heuristic Hill Climbing Algorithm. It starts with an empty or simple network and iteratively performs edge additions, deletions, or reversals to minimize the MDL score.
  3. Clustering for Heterogeneity: To account for diverse user tastes, the approach uses $k$-means clustering. Sales data is grouped into similar subsets, and a distinct CP-net is learned for each cluster.
Dependency structures used to represent conditional logic in the network.

Experimental Evaluation

The approach was validated using three real-world car sales datasets from Renault, ranging from 44 to 87 attributes and containing up to 27,000 vectors. These datasets represent high-dimensional spaces where users must navigate dozens of features like color, engine type, and trim level.

Key Results

  • High Accuracy: Clustered CP-nets achieved recommendation accuracies between 88.4% and 92.8%, significantly outperforming traditional models like LP-trees.
  • Real-time Performance: Recommendation latency remained under 3ms, even for the largest dataset. In contrast, Bayesian Networks (BNs) were significantly slower, often by two orders of magnitude, and failed to scale to the 87-attribute dataset.
  • Sample Efficiency: A critical theoretical insight is that while finding the optimal network is computationally hard (NP-complete), the sample complexity is low. Only a polynomial number of examples are required to learn an accurate model.

Discussion and Future Work

The study highlights the efficiency of CP-nets for "optimal completion" tasks compared to probabilistic models like BNs. While BNs are designed for probability estimation, CP-nets are purpose-built for optimization, making them superior for configuration assistants.

Current limitations include the restriction to acyclic networks. Future research will explore cyclic CP-nets to capture more complex preference loops. Additionally, the authors aim to further explore the theoretical links between log-likelihood in BNs and the NMCL metric used in this work to develop a more unified theory of preference learning.

Summary updated

BibTeX
@inproceedings{gimenez2024learning,
  author = {Pierre-François Gimenez and Jérôme Mengin},
  title = {{Learning Conditional Preference Networks: An Approach Based on the Minimum Description Length Principle}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure