Online Learning of Capacity-Based Preference Models

Margot Herin, Patrice Perny, Nataliya SokolovskaIJCAI 2024

Abstract

This paper presents the first efficient online learning algorithms for capacity-based preference models, such as the Choquet integral. These models are essential for capturing complex interactions between decision criteria in multicriteria decision-making (MCDM). By utilizing Regularized Dual Averaging (RDA) and a specialized ADMM framework, the proposed methods scale to high-dimensional parameter spaces while strictly enforcing normative constraints like monotonicity and fairness in real-time data streams.

Introduction

In multicriteria decision-making (MCDM), the goal is to model how decision-makers weigh various factors. Traditional models often rely on simple weighted sums, which assume criteria independence. However, real-world preferences frequently exhibit synergies; for instance, two criteria may be redundant (negative synergy) or complementary (positive synergy).

To capture these interactions, researchers employ capacities—functions that assign weights to every possible subset of criteria. For $n$ criteria, this results in $2^n$ possible subsets, leading to an exponential explosion of parameters. Conventional "batch mode" learning requires the entire dataset upfront and becomes computationally intractable as $n$ increases. This paper addresses these limitations by introducing online learning algorithms that process data sequentially and maintain model sparsity.

Algorithmic Framework

The authors propose two primary algorithms based on the Möbius representation of capacities, which facilitates the development of sparse and interpretable models:

  1. RDA for Capacity Learning (Algorithm 1): This approach adapts Regularized Dual Averaging (RDA) to learn sparse Möbius masses. By employing $L_1$ regularization, the algorithm effectively "zeros out" non-essential interactions, making high-dimensional problems manageable.
  2. ADMM-RDA for Constrained Learning (Algorithm 2): Preference models must often satisfy "normative constraints," such as monotonicity (where improving a score on one criterion cannot decrease the overall utility). Enforcing these constraints online is challenging due to the computational cost of standard projection steps. The authors integrate RDA with the Alternating Direction Method of Multipliers (ADMM) to create a projection-free variant that handles linear constraints efficiently.

Experimental Evaluation

The algorithms were tested using synthetic preference data to compare performance against known ground truths. The experiments scaled from 10 to 20 criteria, with the latter involving over one million possible interactions ($2^{20}$). The study compared the online approaches against standard batch Linear Programming (LP) and other baseline methods like FOBOS.

Results and Discussion

Constraint Satisfaction

A key finding is the necessity of explicit constraint enforcement. While the unconstrained RDA (Algorithm 1) eventually learns to satisfy monotonicity as more data arrives, it exhibits high violation rates in early stages. In contrast, the ADMM-RDA variant (Algorithm 2) maintains near-zero constraint violations from the outset.

Figure 1: Average constraint violation over time, comparing the unconstrained Algo 1 with the constrained ADMM-RDA (Algo 2).

Scalability and Efficiency

The online algorithms demonstrate significant advantages in computational efficiency. For a problem with 20 criteria, the online approach generated a solution in approximately 66 seconds. The batch LP approach, by comparison, failed to compute due to the size of the interaction space. Even on smaller datasets where batch LP is feasible, the online algorithms provide a "good enough" fit—within 5% accuracy of the batch solution—while operating orders of magnitude faster.

Figure 6: Comparison of training times (in seconds) between the batch LP approach and the proposed online algorithms as the number of examples increases.

Sparsity and Accuracy

By focusing on the Möbius inverse and $L_1$ regularization, the algorithms identify the most significant interactions. On sets of 10–15 criteria, the online algorithms achieved 84–88% accuracy. The use of sparsity not only aids computation but also enhances the interpretability of the resulting preference models.

Conclusion

This work provides a scalable solution for learning complex preference models in real-time environments. By combining RDA with ADMM, the authors successfully balance the need for predictive accuracy, computational speed, and strict adherence to normative constraints. Future work may explore active learning strategies to further accelerate convergence and the application of these methods to non-linear models like the Sugeno integral.

Summary updated

BibTeX
@inproceedings{herin2024online,
  author = {Margot Herin and Patrice Perny and Nataliya Sokolovska},
  title = {{Online Learning of Capacity-Based Preference Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure