Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN models

Mohamed Karim Belaid, Dorra El Mekki, Maximilian Rabus, Eyke Hüllermeier
4/2/2023
cs.LGcs.AIcs.GT

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

With the rapid growth of data availability and usage, quantifying the added value of each training data point has become a crucial process in the field of artificial intelligence. The Shapley values have been recognized as an effective method for data valuation, enabling efficient training set summarization, acquisition, and outlier removal. In this paper, we introduce "STI-KNN", an innovative algorithm that calculates the exact pair-interaction Shapley values for KNN models in O(t n^2) time, which is a significant improvement over the O(2^n)$ time complexity of baseline methods. By using STI-KNN, we can efficiently and accurately evaluate the value of individual data points, leading to improved training outcomes and ultimately enhancing the effectiveness of artificial intelligence applications.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactions

82% match2024

Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles

80% match1 repo32024

Tractable Shapley Values and Interactions via Tensor Networks

80% match2025

A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"

79% match2023

On the Inflation of KNN-Shapley Value

79% match2024

Efficient Data Shapley for Weighted Nearest Neighbor Algorithms

78% match2024

Cite this paper

@article{belaid2023optimizing,
  title  = {Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN models},
  author = {Mohamed Karim Belaid and Dorra El Mekki and Maximilian Rabus and Eyke Hüllermeier},
  year   = {2023},
  eprint = {2304.01224},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2304.01224v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2304.01224.svg)](https://codeofpaper.com/paper/2304.01224)

Discussion