論文の概要: Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification

• arxiv url: http://arxiv.org/abs/2605.21033v1
• Date: Wed, 20 May 2026 11:10:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.638059
• Title: Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
• Title（参考訳）: $k$-Nearest Neighbors分類のための効率的なBanzhafに基づくデータ評価
• Authors: Guangyi Zhang, Lutz Oettershagen, Lixu Wang, Aristides Gionis,
• Abstract要約: 我々は、Banzhaf値の計算に適した効率的なアルゴリズムを、$k$-nearest neighbor(k$NN)分類器で開発する。 私たちの主な貢献は、計算の大幅な改善を実現する動的プログラミングフレームワークです。
• 参考スコア（独自算出の注目度）: 23.4280718098929
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Data valuation, the task of quantifying the contribution of individual data points to model performance, has emerged as a fundamental challenge in machine learning. Game-theoretic approaches, such as the Banzhaf value, offer principled frameworks for fair data valuation; however, they suffer from exponential computational complexity. We address this challenge by developing efficient algorithms specifically tailored for computing Banzhaf values in $k$-nearest neighbor ($k$NN) classifiers. We first establish the theoretical hardness of the problem by proving that it is \#P-hard. Despite this intractability, we exploit the locality properties of $k$NN classifiers to develop practical exact algorithms. Our main contribution is a dynamic programming framework that achieves significant computational improvements: we present a pseudo-polynomial algorithm with $O(Wkn^2)$ time complexity for weighted $k$NN classifiers, where $W$ is the maximum sum of top-$k$ weights, and a specialized algorithm for unweighted $k$NN that achieves $O(nk^2)$ time complexity, that is, linear in the number of data points. We also offer efficient Monte Carlo estimation methods. Extensive experiments on real-world datasets demonstrate the practical efficiency of our approach and its effectiveness in data valuation applications.
• Abstract（参考訳）: データ評価(Data valuation)は、個々のデータポイントのモデルパフォーマンスへの貢献を定量化するタスクであり、機械学習における根本的な課題として現れている。 Banzhaf値のようなゲーム理論のアプローチは、公正なデータ評価のための原則化されたフレームワークを提供するが、それらは指数的な計算複雑性に悩まされる。 我々は、Banzhaf値の計算に適した効率的なアルゴリズムを、隣接する$k$-nearest(k$NN)分類器で開発することで、この問題に対処する。 まず、この問題の理論的硬さを、それが \#P-ハードであることを証明することによって確立する。 このような難易度にもかかわらず、$k$NN分類器の局所性を利用して、実用的な正確なアルゴリズムを開発する。 重み付き$k$NN分類器の擬似多項式アルゴリズムに$O(Wkn^2)の時間複雑性を示す。ここでは、$W$は最上位の$k$重みの最大和であり、$O(nk^2)の時間複雑性を達成できる非重み付き$k$NNの特殊アルゴリズムを示す。 効率的なモンテカルロ推定法も提案する。 実世界のデータセットに関する大規模な実験は、我々のアプローチの実践的効率と、データ評価アプリケーションにおけるその有効性を示す。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Finding a Fair Scoring Function for Top-$k$ Selection: From Hardness to Practice [0.0]
  我々は、上位k$選択のための公平な線形スコアリング関数を同定する問題に対処する。 既存のアルゴリズムは特に高次元において効率的にスケールしない。 我々は、この効率のポテンシャルを、実用的なパフォーマンス向上を実現する最適化されたアルゴリズムに変える。
  論文  参考訳（メタデータ） (2025-03-14T16:40:36Z)
• The Limits of Assumption-free Tests for Algorithm Performance [5.68594452139461]
  与えられたモデリングタスクにおいてアルゴリズムはどの程度うまく機能し、どのアルゴリズムが最善を尽くすか? 一方、特定のトレーニングデータセットに対して$A$を実行して生成された特定の適合モデルが$n$であるのか?
  論文  参考訳（メタデータ） (2024-02-12T03:19:30Z)
• Efficient Data Shapley for Weighted Nearest Neighbor Algorithms [47.62605581521535]
  WKNN-Shapleyは、重み付き$K$近辺アルゴリズム(WKNN-Shapley)のためのデータ共有の効率的な計算法である 我々は、WKNN-Shapleyの計算効率と、データ品質を非重み付きと比較した場合の優れた性能を示す。
  論文  参考訳（メタデータ） (2024-01-20T03:34:18Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。