TL;DR
This paper introduces a novel Bayesian approach for incrementally eliciting decision-maker preferences for complex rank-dependent aggregation functions (like OWA and Choquet integrals). By framing the problem as Bayesian linear regression and minimizing expected regret, their method is more robust to noisy user responses than previous deterministic approaches, leading to more reliable recommendations.
What Problem Does This Paper Address?
In decision support systems, a crucial step is understanding a user's preferences to recommend the best option from a set of alternatives. This often involves eliciting parameters of aggregation functions that combine multiple criteria into a single utility score. Rank-dependent aggregation functions, such as Ordered Weighted Averages (OWA) and Choquet integrals, are powerful because they can capture complex interactions and dependencies between criteria. However, eliciting the parameters for these functions can be challenging and time-consuming for the user. Existing incremental elicitation methods often make hard constraints based on user input, which can lead to severely flawed recommendations if the user makes even a single mistake. This paper addresses the need for a more robust and adaptive elicitation process that can handle potential inaccuracies in user feedback while still efficiently converging to a good recommendation.
Methods
The core of this paper is a Bayesian incremental elicitation process that leverages Bayesian linear regression. Instead of directly learning the complex rank-dependent aggregation function, they reformulate it as a linear function in a higher-dimensional feature space using basis functions. This allows them to apply standard Bayesian linear regression techniques.
Key methodological contributions include:
- Bayesian Update: The system maintains a probability distribution (specifically, a Gaussian distribution) over the possible parameter values. User responses are used to update this distribution in a Bayesian manner, reflecting increased certainty about certain parameter ranges and decreased certainty about others.
- Expected Regret Minimization: The elicitation strategy aims to minimize the expected regret. This means at each step, the system asks a question that is expected to reduce the potential loss incurred by making a suboptimal recommendation. This is a more nuanced approach than simply trying to reduce uncertainty about parameters.
- Handling Response Errors: Unlike deterministic methods that permanently discard parameter ranges based on a single answer, this Bayesian approach is inherently more robust. Noisy or incorrect answers only slightly shift the probability distribution, rather than invalidating large portions of it.
- Basis Functions for Rank-Dependent Aggregators: The paper provides specific formulations for OWA and 2-additive Choquet integrals as linear combinations of basis functions. This is crucial for applying linear regression techniques to these non-linear aggregation functions. For OWA, this involves using the sorted performance values directly. For concave OWA and Choquet integrals, more complex basis functions are derived from cumulative sums or decompositions of capacities.
Datasets
Not discussed in the paper. The authors generated synthetic instances for their numerical tests.
Key Insights and Ideas
- Robustness to Noise is Key: The most significant insight is that a probabilistic (Bayesian) approach to preference elicitation is far more robust to user errors than deterministic methods. Even with a few incorrect answers, the Bayesian approach can still converge to a good recommendation, whereas deterministic methods can be severely misled.
- Expected Regret as an Elicitation Driver: Focusing on minimizing expected regret, rather than just parameter uncertainty, leads to more efficient elicitation. It prioritizes questions that are most likely to improve the quality of the final recommendation.
- Linearization is Powerful: The ability to reformulate complex rank-dependent aggregation functions into a linear model in a feature space is a critical enabler for applying powerful Bayesian regression techniques.
- Trade-off Between Expressivity and Complexity: The paper highlights that while 2-additive Choquet integrals offer good expressivity for modeling interactions, they lead to larger parameter spaces and thus slower computation times compared to OWA.
Key Results
- Reduced MMER: The mean Maximum Minimum Expected Regret (MMER) value dropped significantly (below 3% of the initial value) within about a dozen queries for both OWA and Choquet integrals.
- Good Recommendation Quality: Even with noisy responses (simulated with $\sigma > 0$), the recommended alternative's rank was generally good. For OWA with $\sigma=0.2$, the average rank was around 6.5 out of 100 alternatives. For Choquet integrals, it was even better.
- Bayesian vs. Deterministic: In simulations with noisy responses ($\sigma=0.2$), the Bayesian approach recommended the best alternative in 50% of cases, compared to 36% for a deterministic approach.
- Computational Cost: OWA elicitation was faster (around 5 seconds per query) than 2-additive Choquet elicitation (around 35 seconds per query), attributed to the larger parameter space for Choquet integrals.
Limitations and Future Work
- Computational Cost for Choquet: The computational cost for eliciting Choquet integrals, especially for higher-order additivity, remains a challenge.
- Extension to Higher-Order Capacities: The current work focuses on 2-additive Choquet integrals. Extending the approach to handle more complex, higher-order additive capacities would increase expressivity but also computational complexity.
- Exploration of Other Aggregation Functions: The framework could potentially be extended to other types of rank-dependent aggregation functions.
- Real-world User Studies: While simulations were performed, real-world user studies would be valuable to validate the approach's effectiveness with actual human decision-makers.
Summary updated