Introduction
Traditional recommendation systems typically focus on identifying the single "best" item for a user. However, many real-world applications—such as curating a news feed, forming a committee, or programming a film festival—require the selection of a collection of items. In these contexts, the quality of a set is not merely the sum of its parts. A desirable set often requires balance, diversity, and synergy, while avoiding redundancy.
The computational challenge is significant: for a database of $n$ objects, there are $2^n$ possible subsets. For a dataset of 3,200 items, the number of potential subsets exceeds the number of atoms in the observable universe. This paper introduces a framework for eliciting and reasoning about preferences over sets of objects by abstracting them into properties and using TCP-nets to model complex relationships efficiently.
Methodology: Property Abstraction and TCP-nets
The authors propose a three-step approach to navigate the exponential search space of subsets:
- Property Abstraction: Instead of evaluating every possible subset, the user defines "set properties." These can include counts (e.g., "number of news articles") or Boolean conditions (e.g., "at least two articles about politics").
- TCP-nets for Preferences: The framework utilizes TCP-nets (an extension of CP-nets) to model preferences over these properties. TCP-nets facilitate "ceteris paribus" (all else equal) statements and relative importance rankings. Crucially, these preferences can be conditional, allowing for sophisticated trade-offs (e.g., "If the overall tone is negative, then topic diversity becomes more important").
- Preference-based CSP Generation: To find the optimal set, the algorithm searches through property assignments in order of desirability. For each assignment, it generates a Constraint Satisfaction Problem (CSP). A CSP solver then attempts to find a subset of actual objects that satisfies these property counts. If a solution is found, that set is guaranteed to be optimal.
This "lifting" of preferences from individual objects to abstract set properties reduces the search space from the power set of objects to a much smaller space of property combinations. Furthermore, because the preference model is defined over abstract properties, it remains static even as the underlying database of objects changes.
Experimental Evaluation
The researchers evaluated their approach using the AMDb (All Movie Database), which contains over 3,200 movies. They simulated the task of generating a three-day film festival program based on complex user preferences involving between 5 and 14 different set properties.
Key Results
The algorithm demonstrated practical feasibility for real-world database sizes. As shown in the performance data, the system handles varying scales of complexity effectively:
- Efficiency: For a database of 3,200 movies with a small preference network (5 properties), the optimal set was identified in just 0.95 seconds.
- Scalability: With a larger, more realistic network of 14 properties, the search took approximately 356 seconds (roughly 6 minutes).
- Space Complexity: Unlike naive approaches, this method maintains polynomial space requirements, making it suitable for standard hardware.
Conclusion and Future Work
While the average-case performance is promising, the problem remains NP-hard in the worst case. Future improvements could involve specialized search heuristics for cardinality constraints to further speed up processing for larger property networks. Additionally, extending the model to include structural properties, such as the sequential "flow" of items, remains an area for future exploration.
Summary updated