TL;DR
This paper introduces a novel method for learning "Generalized Additive Independence" (GAI) decomposable utility models, which can represent complex human preferences involving attribute interactions. By leveraging sparse multiple kernel learning and ANOVA decomposition, their approach can automatically discover and model these interactions, leading to more accurate and interpretable decision-making models.
What Problem Does This Paper Address?
In artificial intelligence and decision support systems, accurately modeling human preferences is crucial for tasks like recommendation, planning, and negotiation. Traditional utility models often assume "preferential independence" between attributes, meaning preferences for one attribute don't depend on the value of another. While simple, this assumption is frequently violated in real-world scenarios where attributes interact (e.g., preferring a red car color for a sports car but a blue color for a family sedan). Existing methods for handling these interactions either require prior knowledge of the interaction structure or are limited to simple interactions (e.g., pairs of attributes). This paper addresses the challenge of learning general GAI utility models that can capture arbitrary attribute interactions without prior structural assumptions, while still maintaining a degree of simplicity and decomposability for interpretability.
Methods
The core of the proposed method lies in learning a sparse GAI decomposition of a utility function. This is achieved through a two-pronged approach:
- ANOVA Decomposition: The paper leverages the unique and identifiable ANOVA decomposition of a function. This decomposition breaks down a utility function into additive components, each associated with a subset of attributes. Crucially, each component is "centered" (integrates to zero), ensuring uniqueness.
- Sparse Multiple Kernel Learning (MKL): To learn this decomposition from data, the authors employ a Multiple Kernel Learning framework. They construct a basis of kernels, where each kernel corresponds to a potential subset of interacting attributes. By using an L1-regularization penalty on the kernel weights, the method encourages sparsity, effectively selecting only the most important attribute interactions (factors) for the decomposition. This is framed as a Support Vector Regression (SVR) problem in a high-dimensional feature space, solved using Lagrangian duality.
- Zero-Integral Kernels: To ensure the learned decomposition is specifically an ANOVA decomposition (where factors integrate to zero), they utilize specialized "zero-integral" kernels. These kernels are constructed to inherently satisfy the centering property required for ANOVA decomposition.
Datasets
The paper evaluates its method on both synthetic and real-world datasets:
- Synthetic Data:
- A 6-dimensional model generated using quadratic spline functions and tensor products, representing interactions of up to two attributes.
- A model with a high degree of interaction (n=6) using a sum of terms and a product of all attributes.
- More general models for n=10, generated as sums of tensor products of quadratic splines with varying maximal interaction sizes.
- Real-world Datasets:
- Employee Selection (ESL)
- Lecture Evaluation (LEV)
- Employee Rejection/Acceptance (ERA)
- CPU performance (CPU)
- Car MPG (MPG)
- City quality ranking (CITY)
These real-world datasets are standard benchmarks in multi-criteria decision-making, containing overall evaluations of alternatives described by continuous or discrete attributes.
Key Insights and Ideas
- GAI as a Sweet Spot: The paper argues that GAI decomposition offers a valuable balance between expressiveness (capturing complex interactions) and simplicity (decomposability for interpretability), making it ideal for modeling human preferences.
- ANOVA Uniqueness: The ANOVA decomposition is highlighted as a key tool for ensuring the learned model is uniquely identifiable, avoiding the ambiguity that can arise with other decomposable models.
- Sparse MKL for Feature Selection: Applying L1-regularization within an MKL framework is a powerful way to automatically discover which attribute interactions are important, leading to sparser and more interpretable models. This is akin to feature selection for interactions.
- Zero-Integral Kernels for ANOVA Guarantee: The clever use of zero-integral kernels provides a principled way to enforce the ANOVA decomposition structure, ensuring the learned factors meet the required mathematical properties.
- Flexibility Across Attribute Types: The method's ability to handle both continuous and discrete attributes without prior assumptions on interaction size is a significant practical advantage.
Key Results
- Synthetic Data Performance: The method successfully recovers ground truth utility factors on synthetic data. It significantly outperforms p-additive GAI models (which assume limited interaction sizes) when interactions are present, achieving a much lower Mean Absolute Error (MAE) while maintaining reasonable training times. For a model with high interaction, their method reduced MAE by a factor of 10 compared to p-additive models.
- Model Recovery: On synthetic data with increasing interaction degrees, the method accurately identifies the maximal interaction sizes and maintains a low False Discovery Rate (FDR), indicating it selects relevant interactions without too many false positives.
- Real-world Datasets: SMKGAI generally achieves the best or near-best average MAE across several real-world preference datasets, outperforming linear regression and simpler GAI models, especially on datasets where interactions are more pronounced.
Limitations and Future Work
- Scalability: The authors acknowledge that the number of possible interaction factors grows exponentially with the number of attributes, posing a scalability challenge.
- Hierarchical Regularization: They suggest exploring grouped hierarchical regularization to simultaneously penalize factors and their sub-factors, potentially leading to more structured decompositions.
- Iterative Optimization: Investigating iterative optimization procedures (e.g., projected gradient descent) could improve scalability and efficiency, especially for large numbers of attributes.
- Factor Aggregation: While the learned ANOVA decomposition is unique, the paper notes that further simplification by aggregating factors into a more compact, well-formed GAI decomposition is possible and could be an area for future work.
Summary updated