Approximation of group explainers with coalition structure using Monte Carlo sampling on the product space of coalitions and features

• URL: http://arxiv.org/abs/2303.10216v2
• Date: Thu, 18 Apr 2024 18:14:32 GMT
• Title: Approximation of group explainers with coalition structure using Monte Carlo sampling on the product space of coalitions and features
• Authors: Konstandinos Kotsiopoulos, Alexey Miroshnikov, Khashayar Filom, Arjun Ravi Kannan,
• Abstract summary: We focus on a wide class of linear game values, as well as coalitional values, for the marginal game based on a given ML model and predictor vector. We design a novel Monte Carlo sampling algorithm that estimates them at a reduced complexity that depends linearly on the size of the background dataset.
• Score: 0.11184789007828977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, many Machine Learning (ML) explanation techniques have been designed using ideas from cooperative game theory. These game-theoretic explainers suffer from high complexity, hindering their exact computation in practical settings. In our work, we focus on a wide class of linear game values, as well as coalitional values, for the marginal game based on a given ML model and predictor vector. By viewing these explainers as expectations over appropriate sample spaces, we design a novel Monte Carlo sampling algorithm that estimates them at a reduced complexity that depends linearly on the size of the background dataset. We set up a rigorous framework for the statistical analysis and obtain error bounds for our sampling methods. The advantage of this approach is that it is fast, easily implementable, and model-agnostic. Furthermore, it has similar statistical accuracy as other known estimation techniques that are more complex and model-specific. We provide rigorous proofs of statistical convergence, as well as numerical experiments whose results agree with our theoretical findings.

Related papers

• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• Fusion of Gaussian Processes Predictions with Monte Carlo Sampling [61.31380086717422]
  In science and engineering, we often work with models designed for accurate prediction of variables of interest. Recognizing that these models are approximations of reality, it becomes desirable to apply multiple models to the same data and integrate their outcomes.
  arXiv  Detail & Related papers  (2024-03-03T04:21:21Z)
• Sparse Variational Student-t Processes [8.46450148172407]
  Student-t Processes are used to model heavy-tailed distributions and datasets with outliers. We propose a sparse representation framework to allow Student-t Processes to be more flexible for real-world datasets. We evaluate two proposed approaches on various synthetic and real-world datasets from UCI and Kaggle.
  arXiv  Detail & Related papers  (2023-12-09T12:55:20Z)
• Curvature-Sensitive Predictive Coding with Approximate Laplace Monte Carlo [1.1470070927586016]
  Predictive coding (PC) accounts of perception now form one of the dominant computational theories of the brain. Despite this, they have enjoyed little export to the broader field of machine learning. This has been due to the poor performance of models trained with PC when evaluated by both sample quality and marginal likelihood.
  arXiv  Detail & Related papers  (2023-03-09T01:29:58Z)
• Approximate Gibbs Sampler for Efficient Inference of Hierarchical Bayesian Models for Grouped Count Data [0.0]
  This research develops an approximate Gibbs sampler (AGS) to efficiently learn the HBPRMs while maintaining the inference accuracy. Numerical experiments using real and synthetic datasets with small and large counts demonstrate the superior performance of AGS.
  arXiv  Detail & Related papers  (2022-11-28T21:00:55Z)
• Low-variance estimation in the Plackett-Luce model via quasi-Monte Carlo sampling [58.14878401145309]
  We develop a novel approach to producing more sample-efficient estimators of expectations in the PL model. We illustrate our findings both theoretically and empirically using real-world recommendation data from Amazon Music and the Yahoo learning-to-rank challenge.
  arXiv  Detail & Related papers  (2022-05-12T11:15:47Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• Efficient Debiased Evidence Estimation by Multilevel Monte Carlo Sampling [0.0]
  We propose a new optimization algorithm for Bayesian inference based multilevel Monte Carlo (MLMC) methods. Our numerical results confirm considerable computational savings compared to the conventional estimators.
  arXiv  Detail & Related papers  (2020-01-14T09:14:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.