Learning Lexicographic Preference Trees From Positive Examples

Hélène Fargier, Pierre-François Gimenez, Jérôme MenginAAAI 2018 · DOI

Abstract

Traditional preference learning often relies on explicit pairwise comparisons or rankings. However, real-world data, such as e-commerce sales history, typically consists only of "positive examples"—items users actually chose. This paper presents a novel approach to learning user preferences from such data using Lexicographic Preference Trees (LP-trees). By minimizing the empirical mean rank of observed items, the proposed greedy algorithm and its generalizations (k-LP-trees) efficiently induce models that explain user choices even in complex combinatorial domains.

Introduction: Learning from Choices, Not Comparisons

Most preference elicitation systems require active user participation, asking them to rank options or choose between pairs. In practice, especially in large-scale retail, we often only have access to a user's purchase history. A significant challenge is that a chosen item is not necessarily a global favorite; it is merely the best option among those available at the time of purchase.

The authors address this by modeling preferences through LP-trees. The goal is to construct a ranking where the items previously selected by users appear as high as possible. This approach accounts for "mass confusion"—situations where users are overwhelmed by options—by focusing on the relative ranking of observed choices against all other possible combinations.

Methodology

The core of the proposed framework is the Lexicographic Preference Tree (LP-tree). Similar to a dictionary's alphabetical ordering, an LP-tree ranks alternatives by evaluating attributes in a specific order of importance, starting from the root.

Technical Contributions

  • Greedy Learning Algorithm: Due to the exponential search space of tree structures, the authors employ a top-down greedy approach. It selects attributes that best differentiate chosen items from the rest based on their frequency in the dataset.
  • k-LP-trees: This generalization allows a single node to contain up to $k$ attributes, enabling the model to capture interdependencies between features that a simple linear tree might miss.
  • Pruning: To ensure the model generalizes well to unseen data, a bottom-up pruning phase simplifies the tree structure without significantly compromising the ranking score.
Comparison of different LP-tree structures: (a) standard LP-tree, (b) linear LP-tree, and (c) 2-LP-tree.

Evaluation Datasets

The methodology was tested on synthetic data with 10 attributes and a real-world Renault sales history dataset containing 27,088 vehicles described by 48 attributes. This represents a highly complex combinatorial domain where users choose from millions of possible configurations.

Key Insights

The researchers found that frequency serves as a powerful proxy for preference. If an attribute value appears more frequently in sales data, it likely indicates a higher preference, provided the context of other attributes is considered. LP-trees are particularly adept at representing conditional importance, where the preference for one attribute (e.g., interior fabric) depends on a prior choice (e.g., car model).

Furthermore, LP-trees offer high computational efficiency. Unlike deep learning models that may require significant resources for inference, finding the optimal item in an LP-tree is a polynomial-time operation, making it suitable for real-time recommendation engines.

Results

On the Renault dataset, the model achieved a recommendation precision of up to 88%. Key findings include:

  • Clustering: Grouping users with similar tastes via $k$-means before training the trees significantly boosted precision.
  • Model Complexity: Transitioning from standard LP-trees ($k=1$) to $k$-LP-trees ($k=3$) reduced model size from 2300 nodes to just 90 while maintaining accuracy.
  • Pruning Effectiveness: Pruning effectively manages the number of nodes as sample size increases, preventing overfitting while keeping the model interpretable and efficient.
Impact of pruning and tree type on the number of nodes relative to sample size.

Conclusion and Future Directions

While the current greedy approach is highly effective, finding a mathematically optimal LP-tree remains a hard problem. Future work includes conducting a formal PAC learning analysis to determine exact data requirements and extending the framework to handle partial orders where users may be indifferent between certain options. Despite these open questions, the use of LP-trees for learning from positive examples provides a robust and efficient path for personalized recommendation in complex domains.

Summary updated

BibTeX
@inproceedings{fargier2018learning,
  author = {Hélène Fargier and Pierre-François Gimenez and Jérôme Mengin},
  title = {{Learning Lexicographic Preference Trees From Positive Examples}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11808},
}
Figure