Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN models
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Data InteractionData ValuationSimilar Papers 제목 키워드 기반
SHAP-IQ: Unified Approximation of any-order Shapley Interactions
Predominately in explainable artificial intelligence (XAI) research, the Shapley value (SV) is applied to determine feature attributions for any black box model. Shapley interaction indices extend the SV to define any-or…
Data valuation: The partial ordinal Shapley value for machine learning
Data valuation using Shapley value has emerged as a prevalent research domain in machine learning applications. However, it is a challenge to address the role of order in data cooperation as most research lacks such disc…
Abstract AlgebraData ValuationStatistical Analysis of using the Shapley Value for Sensor Anomaly Localization with Accurate Classifiers
Recent publications have suggested using the Shap- ley value for sensor anomaly/attack localization. We study the performance of such an approach by using mathematically de- fined optimum binary classifiers in the Shaple…
Is Data Shapley Not Better than Random in Data Selection? Ask NASH
Data selection studies the problem of identifying high-quality subsets of training data. While some existing works have considered selecting the subset of data with top-$m$ Data Shapley or other semivalues as they accoun…
On Using the Shapley Value for Anomaly Localization: A Statistical Investigation
Recent publications have suggested using the Shapley value for anomaly localization for sensor data systems. Using a reasonable mathematical anomaly model for full control, experiments indicate that using a single fixed …