Fugu-MT 論文翻訳(概要): Efficient Data Shapley for Weighted Nearest Neighbor Algorithms

論文の概要: Efficient Data Shapley for Weighted Nearest Neighbor Algorithms

arxiv url: http://arxiv.org/abs/2401.11103v1
Date: Sat, 20 Jan 2024 03:34:18 GMT
ステータス: 処理完了
システム内更新日: 2024-01-23 18:08:46.028411
Title: Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
Title（参考訳）: 重み付き近傍アルゴリズムにおける効率的なデータ共有
Authors: Jiachen T. Wang, Prateek Mittal, and Ruoxi Jia
Abstract要約: WKNN-Shapleyは、重み付き$K$近辺アルゴリズム(WKNN-Shapley)のためのデータ共有の効率的な計算法である我々は、WKNN-Shapleyの計算効率と、データ品質を非重み付きと比較した場合の優れた性能を示す。
参考スコア（独自算出の注目度）: 47.62605581521535
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This work aims to address an open problem in data valuation literature concerning the efficient computation of Data Shapley for weighted $K$ nearest neighbor algorithm (WKNN-Shapley). By considering the accuracy of hard-label KNN with discretized weights as the utility function, we reframe the computation of WKNN-Shapley into a counting problem and introduce a quadratic-time algorithm, presenting a notable improvement from $O(N^K)$, the best result from existing literature. We develop a deterministic approximation algorithm that further improves computational efficiency while maintaining the key fairness properties of the Shapley value. Through extensive experiments, we demonstrate WKNN-Shapley's computational efficiency and its superior performance in discerning data quality compared to its unweighted counterpart.
Abstract（参考訳）: 本研究は,重み付き$k$近傍アルゴリズム (wknn-shapley) に対するデータシェープリーの効率的な計算に関するデータ評価文献のオープン問題に対処することを目的としている。離散化重み付きハードラベルKNNの精度を実用関数として考慮し、WKNN-Shapleyの計算をカウント問題に再構成し、2次時間アルゴリズムを導入し、既存の文献の最良の結果である$O(N^K)$から顕著に改善したことを示す。決定論的近似アルゴリズムを開発し,shapley値の重要な公平性を維持しつつ,計算効率をさらに向上させる。広範な実験を通じて,wknn-shapleyの計算効率とデータ品質の識別における優れた性能を示す。

関連論文リスト

Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
冗長な手法を排除し、単純で効率的なシェープリー推定器SimSHAPを提案する。既存手法の解析において、推定器は特徴部分集合からランダムに要約された値の線形変換として統一可能であることを観察する。実験により,SimSHAPの有効性が検証され,精度の高いShapley値の計算が大幅に高速化された。
論文参考訳（メタデータ） (2023-11-02T06:09:24Z)
High-dimensional Contextual Bandit Problem without Sparsity [8.782204980889077]
本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。我々は、ETCアルゴリズムの最適レートを$T$で導出し、探索とエクスプロイトのバランスをとることで、このレートを実現できることを示す。本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-19T15:29:32Z)
A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms" [18.65808473565554]
Jiaらによると、K-Nearest Neighbors(KNN)モデルでは、Data Shapleyのアルゴリズムは驚くほどシンプルで効率的である。 KNNモデルの性能をよりよく反映した、より自然で解釈可能なユーティリティ関数を提案する。我々の新しいアプローチは、ソフトラベルKNNSVと呼ばれ、元の方法と同じ時間を達成する。
論文参考訳（メタデータ） (2023-04-09T15:31:53Z)
Optimizing Data Shapley Interaction Calculation from O(2^n) to O(t n^2) for KNN models [2.365702128814616]
STI-KNNは、O(t n2)時間におけるKNNモデルに対する正確なペア相互作用シェープ値を計算する革新的なアルゴリズムである。 STI-KNNを使用することで、個々のデータポイントの価値を効率よく正確に評価することができ、トレーニング結果が改善され、最終的には人工知能アプリケーションの有効性が向上する。
論文参考訳（メタデータ） (2023-04-02T06:15:19Z)
Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文参考訳（メタデータ） (2023-02-14T22:12:16Z)
Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文参考訳（メタデータ） (2022-10-21T15:56:13Z)
Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文参考訳（メタデータ） (2022-10-02T05:03:38Z)
Accelerating Shapley Explanation via Contributive Cooperator Selection [42.11059072201565]
DNNモデルのShapley説明を著しく高速化する新しい手法SHEARを提案する。特徴連立の選定は、本提案のシェープリー連鎖則に従い、真真正値から絶対誤差を最小化する。 SHEARは、さまざまな評価指標で、最先端のベースラインメソッドを一貫して上回る。
論文参考訳（メタデータ） (2022-06-17T03:24:45Z)
Differentially Private Shapley Values for Data Evaluation [3.616258473002814]
共有値は計算コストが高く、データセット全体を含んでいる。そこで本研究では,階層型シェープアルゴリズム(Layered Shapley Algorithm)と呼ばれる新しい近似法を提案する。本手法は, 確率的精度を保証するために, データの小さな (O(polylog(n))) ランダムサンプルと小さな (O(log n)$) 連立関係で動作することを示す。
論文参考訳（メタデータ） (2022-06-01T14:14:24Z)
Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
論文参考訳（メタデータ） (2020-01-12T15:54:20Z)

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