The Decision-Theoretic Interactive Video Advisor

Hien Nguyen, Peter HaddawyUAI 1999

TL;DR

This paper introduces DIVA, a novel decision-theoretic approach to collaborative filtering for movie recommendations. DIVA distinguishes itself by using pairwise comparisons for preference representation and a unique similarity measure based on the probability of conflict between rankings, leading to more accurate recommendations than traditional methods.

What Problem Does This Paper Address?

Recommender systems, particularly those using collaborative filtering, aim to help users discover items they might like from vast catalogs. A core challenge is effectively representing and eliciting user preferences. While decision theory offers robust frameworks for preference modeling, its formal techniques have been underutilized in recommender systems. Existing systems often rely on numerical ratings and simple similarity metrics (like Pearson correlation), which may not fully capture the nuances of user taste or lead to suboptimal recommendations. This paper addresses this gap by proposing a decision-theoretic framework for collaborative filtering that emphasizes accurate preference representation and efficient elicitation.

Methods

DIVA employs several novel techniques:

  • Pairwise Comparisons for Preference Representation: Instead of numerical ratings, DIVA uses a standard decision-theoretic notion of preference order, where users provide pairwise comparisons (like, OK, dislike). This offers a more granular representation without requiring users to choose from many rating categories.
  • Decision-Theoretic Similarity Measure: DIVA introduces a similarity measure between users based on the "probability of conflict" between their preference orderings. This is a departure from the Pearson correlation coefficient used in systems like GroupLens and is shown to have practical advantages.
  • Distinguishing Long-Term and Short-Term Preferences: Recognizing that user interests can be dynamic, DIVA separates general taste (long-term preferences) from immediate interests (short-term preferences). Short-term preferences are captured through search constraints and are forgotten after a session, while long-term preferences are stored.
  • Incremental Elicitation with Feedback: DIVA uses an incremental approach, providing recommendations early and allowing users to provide feedback on the list. This feedback can be used to refine both long-term and short-term preferences, making the elicitation process more interactive and less burdensome.
  • Case-Based Preference Augmentation: To supplement directly elicited preferences, DIVA uses a case base of existing user preference structures. It computes similarity between the active user's partial structure and those in the case base, then uses the most similar structure to guide the completion of the active user's preference model. This involves approximating the number of linear extensions of partial orders, a computationally intensive task addressed using a Markov chain-based algorithm.

Datasets

  • EachMovie Database: Used for building the initial user preference case base. It contains 72,916 users, 2,811,983 numeric ratings, and 1628 movies.
  • Microsoft Cinemania 94 CD-ROM: Used to obtain movie attributes (actors, directors, genres, etc.) for 2000 movies. The paper notes that only 500 of these movies were present in the EachMovie database, leading to a filtered dataset for evaluation.

Key Insights and Ideas

  • Pairwise comparisons are more intuitive and informative: Moving away from numerical ratings to pairwise comparisons simplifies the user's task while providing a richer representation of their preferences.
  • Conflict probability is a superior similarity metric: The novel similarity measure, based on the probability of conflicting rankings, proves more robust than Pearson correlation, especially when dealing with partial preference structures. It better captures agreement over a reasonable set of items.
  • Dynamic preferences require distinct handling: Separating long-term and short-term preferences allows the system to adapt to a user's changing interests, making recommendations more relevant for a specific viewing occasion.
  • Incremental feedback is crucial for user engagement: Allowing users to provide feedback on recommendations and iteratively refine their preferences makes the system more interactive and less of a "black box."

Key Results

The paper reports empirical evaluation results comparing DIVA with the GroupLens collaborative filtering technique.

  • Precision and Recall: DIVA achieved a best precision of 86% and recall of 40%, outperforming GroupLens's 65% precision and 35% recall. These results were obtained using a case base of 500 users and a specific experimental setup involving random sampling of linear extensions.
  • Computational Efficiency: While not the primary focus, the paper mentions using heuristics (e.g., computing similarity over the top 100 ranked movies) to manage computational cost for large case bases.

Limitations and Future Work

  • Crude Short-Term Preference Representation: The authors acknowledge that their representation of short-term preferences is currently "rather crude" and aim to develop a richer representation that can be merged with long-term preferences, even when conflicts arise.
  • Preference Evolution: The system currently doesn't explicitly track how preferences evolve over time. Future work could involve keeping track of when preference information was obtained and detecting conflicts with older preferences.
  • Computational Cost: For very large case bases, the computational cost of similarity computation remains a challenge. The authors are exploring hierarchical clustering to reduce this cost and are investigating the trade-off between accuracy and computation time.
  • Interface for Richer Preferences: The current elicitation method (Like, OK, Dislike) results in only three categories. Future work includes augmenting the interface to allow users to graphically specify richer preferences, potentially improving recommendation accuracy.

Summary updated

BibTeX
@inproceedings{nguyen1999decision,
  author = {Hien Nguyen and Peter Haddawy},
  title = {{The Decision-Theoretic Interactive Video Advisor}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1999},
}
Figure