Constructive Recommendation

Paolo DragoneIJCAI 2017 · DOI

TL;DR

This paper introduces "constructive recommendation," a new paradigm for recommending complex, assembled objects (like PC configurations or travel plans) by learning user preferences to optimize a utility function over a vast combinatorial space. They propose using online preference learning techniques, specifically a Perceptron-based approach, to efficiently learn these preferences through interactive feedback.

What Problem Does This Paper Address?

Traditional recommendation systems excel at suggesting individual, "self-contained" items like movies or songs. However, they struggle with recommending configurations – objects composed of multiple parts that must adhere to structural constraints. Think of planning a trip: you don't just pick a destination; you decide where to go, when, how long, and what to do, all within constraints like time and budget. This involves searching an astronomically large space of possibilities. Constructive recommendation aims to tackle this by synthesizing new, complex objects tailored to user preferences, moving beyond simply selecting from a pre-defined catalog.

Methods

The core of the proposed approach is constructive recommendation, which involves learning a utility function that maps structured objects to a ranking score. This utility function can depend on contextual information (like a user query). The function is typically parameterized as $u(x, y) = w \cdot \phi(x,y)$, where $w$ is a parameter vector and $\phi$ is a feature map.

The key challenge is learning $w$ efficiently. Instead of traditional methods that require enumerating all possible objects (infeasible here), the authors leverage preference elicitation and online preference learning. Specifically, they adapt the Preference Perceptron algorithm from the Coactive Learning framework. In each iteration:

  1. The system receives a context $x_t$.
  2. It recommends an object $y_t$ by maximizing the current utility estimate.
  3. The user provides feedback $\hat{y}_t$, indicating a preferred object (potentially a slightly modified version of $y_t$).
  4. The system updates its parameter vector $w_{t+1}$ using the feedback.

This process is designed to be more efficient than Bayesian methods for large combinatorial domains. The paper also touches upon using mixed integer linear programming (MILP) solvers for the optimization problem of finding the best configuration, noting that while NP-hard, existing solvers can handle moderately sized problems.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Beyond Simple Selection: The fundamental shift is from recommending existing items to constructing new ones, opening up recommendations for complex, composite entities.
  • Combinatorial Explosion: The sheer size of the configuration space is a major hurdle, necessitating efficient learning and inference methods.
  • Interactive Learning is Crucial: Learning user preferences for complex configurations requires an iterative process where the system learns from user feedback on its recommendations.
  • Coactive Learning's Promise: Online preference learning techniques like Coactive Learning offer a scalable alternative to traditional Bayesian methods for this complex domain.
  • Feature Engineering is Key: Identifying and learning relevant features that define user preferences for structured objects is critical for effective recommendation.

Key Results

The paper presents preliminary results showing improvements in recommendation quality and inference time compared to a competitor approach (a large-margin method from Teso et al., 2016). While specific quantitative results are not detailed, the authors indicate that their Perceptron-based alternative can handle both Boolean and numeric variables and features, and offers formal guarantees on recommendation quality, which the competitor lacks.

Limitations and Future Work

  • User Interaction Modalities: While manipulative feedback (user directly modifies a recommendation) is useful for some tasks (e.g., layout synthesis), it may be too cognitively demanding for others (e.g., PC configuration). The paper explores choice set feedback (user picks from a set of options) as a less demanding alternative.
  • Feature Elicitation Cost: Current methods for eliciting features (e.g., asking users for "critiques") can be cognitively expensive. Future work aims to learn features from preference examples using online gradient boosting.
  • Inference Complexity: While MILP solvers are useful, scaling to larger or more complex domains remains a challenge. Future work includes exploring approximate solutions and extending inference to quadratically constrained domains.

Summary updated

BibTeX
@inproceedings{dragone2017constructive,
  author = {Paolo Dragone},
  title = {{Constructive Recommendation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/748},
}

Loading related content...

Figure