Research map / Learning theory and algorithms / Prediction and decision losses
Support Vector-based Estimation of Multilinear Games for Feature Selection and Explanation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models supervised learning as a multilinear game and estimates its parameters with a dual SVM using a multilinear kernel, enabling exact Shapley value and interaction index computation via dynamic programming for feature selection and local explanation.
Problem
Computing Shapley-value feature importance and interaction indices requires exponentially many parameters; existing methods rely on additivity plus linear regression, or retrain models over all feature subsets, which is impractical.
Approach
Represent the supervised model as a multilinear extension of a cooperative game including all feature interactions, train it as an SVM with a multilinear kernel (closed form linear-time kernel, dynamic programming for q-additive kernels) so complexity scales with number of samples, and derive a dual-SVM representation of Shapley values and interaction indices computed by dynamic programming.
Key results
- On synthetic feature selection tasks, SVSVL achieves the best average rank of influential features, outperforming Lasso and RFE; mutual information is comparable.
- On IMDB LSTM explanations, SVSVL reaches MSE 0.05 versus 0.07 for BiSHAP, 0.10 for L2X, 0.11 for SHAP and 0.12 for LIME.
- SVSVL's execution time (129 s for LSTM, 3 s for RF) is comparable to Kernel SHAP and LIME and faster than Bivariate SHAP on the RF model.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SVSVL with feature interactions instead of Kernel SHAP | Local explanation of a bidirectional LSTM · IMDB sentiment explanation | MSE: 0.11 ± 0.03 -> 0.05 ± 0.01 | Helped |
| Use SVSVL instead of LIME | Local explanation of a bidirectional LSTM · IMDB sentiment explanation | MSE: 0.12 ± 0.02 -> 0.05 ± 0.01 | Helped |
| Use SVSVL instead of Bivariate SHAP | Local explanation of a bidirectional LSTM · IMDB sentiment explanation | MSE: 0.07 ± 0.02 -> 0.05 ± 0.01 | Helped |
| Use SVSVL instead of L2X | Local explanation of a bidirectional LSTM · IMDB sentiment explanation | MSE: 0.10 ± 0.01 -> 0.05 ± 0.01 | Helped |
| Use SVSVL instead of Kernel SHAP | Local explanation of a Random Forest · Boston housing explanation | MSE: 0.004 ± 0.0 -> 0.004 ± 0.0 | No clear effect |
| Use SVSVL instead of L2X | Local explanation of a Random Forest · Boston housing explanation | MSE: 0.002 ± 0.01 -> 0.004 ± 0.0 | Hurt |
| Use SVSVL instead of Kernel SHAP | Local explanation of a bidirectional LSTM · IMDB sentiment explanation | Average time (s): 310 -> 129 | Helped |
| Use SVSVL instead of LIME | Local explanation of a bidirectional LSTM · IMDB sentiment explanation | Average time (s): 123 -> 129 | Hurt |
| Use SVSVL instead of Kernel SHAP | Local explanation of a Random Forest · Boston housing explanation | Average time (s): 29 -> 3 | Helped |
| Use SVSVL instead of LIME | Local explanation of a Random Forest · Boston housing explanation | Average time (s): 2 -> 3 | Hurt |
| Use SVSVL rather than linear Lasso and REF feature selection | Feature selection · Synthesized datasets | Average rank of influential features | Helped |
| Use SVSVL feature selection rather than the compared selectors | Feature selection · Query, miles per gallon, and diabetes datasets | Random Forest performance | Helped |
Surprising findings
- Differences between explainers are marginal on the Random Forest model, where linear methods are nearly as effective.
Limitations
- Does not consider higher-order statistical moments of features for feature selection.
- Does not support L1 regularization due to kernel trick limitations.
- Feature selection theorem assumes independent Gaussian-distributed features with shared mean/variance structure.
Experimental setup
Datasets: synthetic binary classification data (3 settings, 1000 samples) housing abalone query miles per gallon breast cancer diabetes IMDB reviews Boston housing
Benchmarks: synthesized feature selection datasets six real-world tabular datasets with random forest IMDB sentiment explanation fidelity (MSE) word-masking deviation analysis
Metrics: average rank of influential features downstream random forest performance vs. number of features MSE fidelity of local surrogate execution time prediction deviation after masking
Baselines: Lasso RFE mutual information ANOVA F-test Kernel SHAP LIME Bivariate SHAP L2X
Builds on: Kernel SHAP Owen multilinear extension Shapley value Möbius transformation SVM
Closest papers by meaning
- Unlocking the Game: Estimating Games in Möbius Representation for Explanation and High-Order Interaction Detection (AAAI 2025 · similarity 0.89)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.88)
- KernelSHAP-IQ: Weighted Least Square Optimization for Shapley Interactions (ICML 2024 · similarity 0.87)
- Explaining Probabilistic Models with Distributional Values (ICML 2024 · similarity 0.84)
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.84)
- Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.