TL;DR
This paper introduces a novel, scalable algorithm (D-IRLS) for learning complex human preference models that account for interactions between decision criteria. By leveraging sparse representations and an iterative reweighted least squares approach, the method efficiently identifies significant interactions, even with over 20 criteria, outperforming traditional methods in both speed and scalability.
What Problem Does This Paper Address?
In decision-making, especially when evaluating complex alternatives with multiple criteria, human preferences often involve interactions between these criteria. For instance, the benefit of a good score on one criterion might be amplified or diminished by the score on another. Traditional linear models fail to capture these interactions, while more expressive models like multilinear utilities or Choquet integrals can become computationally intractable due to the combinatorial explosion of possible interactions (up to $2^n$ for $n$ criteria). Learning these interaction patterns from preference data is crucial for building accurate and explainable decision models, but the complexity has historically limited applications to a small number of criteria. This paper tackles the challenge of learning these complex, interacting preference models efficiently and scalably, even for a large number of criteria.
Methods
The core contribution is a new algorithm called Dual Iteratively Reweighted Least Squares (D-IRLS). It addresses the problem of learning sparse Möbius representations of capacities, which are the parameters governing these interaction models.
Here's a breakdown of the approach:
- Sparse Representation: The paper frames the problem as learning a sparse vector of "Möbius masses," where sparsity encourages simpler models with fewer significant interactions. This is achieved by penalizing the L1-norm of the Möbius vector, particularly for terms involving interactions of two or more criteria.
- Iterative Reweighted Least Squares (IRLS): To handle the non-differentiable L1-norm, the authors employ an IRLS strategy. This involves approximating the L1-norm with a differentiable term and iteratively solving a sequence of least squares problems. This is a standard technique for promoting sparsity.
- Dualization: A key innovation for scalability is the use of the dual formulation of the optimization problem at each IRLS iteration. This transforms the problem from one with an exponential number of variables (related to the number of criteria) to one with a number of variables linear in the number of preference examples. This is a significant computational advantage.
- Kernel Trick: For higher dimensions, the paper leverages the "kernel trick" in the dual formulation. This allows for efficient computation of inner products between complex feature representations without explicitly constructing those high-dimensional vectors, further enhancing scalability.
Datasets
The paper does not introduce new datasets. Instead, it uses synthetic preference data generated for evaluation. This synthetic data is created by:
- Randomly drawing sparse Möbius vectors (satisfying monotonicity constraints).
- Generating utility vectors for alternatives by drawing uniformly from $[0,1]^n$.
- Computing the overall utility values and adding Gaussian noise ($\sigma = 0.03$) to classify them as preference or indifference training examples.
The experiments involve varying the number of criteria from $n=7$ to $n=22$ and using training sets of size $|P| + |I| = 500$ and test sets of size $1000$.
Key Insights and Ideas
- Sparsity is Key for Scalability: The paper convincingly argues that enforcing sparsity on the Möbius masses is crucial for making preference learning with interactions computationally feasible for a large number of criteria.
- Dualization is a Game-Changer: By reformulating the problem in its dual form within the IRLS framework, the authors achieve a dramatic reduction in computational complexity, moving from exponential dependence on the number of criteria to a dependence on the number of data points.
- Interactions Emerge, Not Imposed: Unlike methods that pre-define interaction structures (e.g., only pairwise), this approach allows the significant interactions to be learned from the data, leading to more natural and potentially simpler models.
- Flexibility Across Models: The unified framework, based on the general form $F(x) = \sum_{S \subseteq N} m_S \phi_S(x_S)$, allows the method to learn parameters for various models like multilinear utilities and Choquet integrals (conjunctive/disjunctive forms) within a single approach.
- Monotonicity Can Be Handled Efficiently: While enforcing monotonicity constraints can be computationally expensive, the paper proposes an efficient constraint generation algorithm that adds only violated constraints iteratively, significantly improving performance.
Key Results
- Scalability: The D-IRLS algorithm successfully learns preference models with up to $n=22$ criteria, handling millions of potential coefficients. In contrast, the exact LP solver (ES) fails beyond $n=17$.
- Speed: D-IRLS achieves learning times of under 450 seconds for $n=22$, whereas ES becomes prohibitively slow.
- Accuracy: The generalizing performance (measured by preference inversion on test sets) of D-IRLS is comparable to the exact ES method, indicating that the learned sparse models are accurate.
- Comparison to k-Additive Models: D-IRLS significantly outperforms models restricted to k-additivity (e.g., 2-additive or 3-additive) in terms of test error, demonstrating the benefit of learning sparse representations of potentially higher-order interactions. For $n=16$, D-IRLS achieves a test error of 0.06, compared to 0.22 for 2-add and 0.49 for 3-add.
- Monotonicity Constraint Handling: The constraint generation algorithm for monotonicity is significantly more efficient than enforcing all constraints upfront, allowing for successful learning up to $n=15$ criteria.
Limitations and Future Work
- Model Selection for Interaction Functions: The current approach assumes the form of interaction functions ($\phi_S$) is known (e.g., product for multilinear, min/max for Choquet). Future work could extend the approach to learn these interaction functions from data, posing a model selection problem.
- Kernelization for Higher Dimensions: While kernelization is used for the first IRLS iteration, further investigation into more advanced kernel techniques could improve scalability for even higher dimensions.
- Exploration of Other Interaction Types: The paper focuses on specific interaction forms. Exploring a broader range of interaction functions and their learning is a potential avenue.
- Real-World Data: While synthetic data demonstrates the method's capabilities, applying and validating it on real-world preference data would be a valuable next step.
Summary updated