論文の概要: Fast Approximation of the Shapley Values Based on Order-of-Addition Experimental Designs

• arxiv url: http://arxiv.org/abs/2309.08923v1
• Date: Sat, 16 Sep 2023 08:28:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-19 18:31:51.995553
• Title: Fast Approximation of the Shapley Values Based on Order-of-Addition Experimental Designs
• Title（参考訳）: 付加次数実験設計に基づくShapley値の高速近似
• Authors: Liuqing Yang, Yongdao Zhou, Haoda Fu, Min-Qian Liu, Wei Zheng
• Abstract要約: $d$-player 連立ゲームでは、Shapley の値を計算するには$d!$ または $2d$ の限界貢献値が必要である。 一般的な治療法は、置換の完全なリストを補うために、置換のランダムなサンプルを取ることである。 我々はシェープリー値のより正確な推定を行うために、高度なサンプリングスキームを設計できることを見出した。
• 参考スコア（独自算出の注目度）: 11.684428415506968
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Shapley value is originally a concept in econometrics to fairly distribute both gains and costs to players in a coalition game. In the recent decades, its application has been extended to other areas such as marketing, engineering and machine learning. For example, it produces reasonable solutions for problems in sensitivity analysis, local model explanation towards the interpretable machine learning, node importance in social network, attribution models, etc. However, its heavy computational burden has been long recognized but rarely investigated. Specifically, in a $d$-player coalition game, calculating a Shapley value requires the evaluation of $d!$ or $2^d$ marginal contribution values, depending on whether we are taking the permutation or combination formulation of the Shapley value. Hence it becomes infeasible to calculate the Shapley value when $d$ is reasonably large. A common remedy is to take a random sample of the permutations to surrogate for the complete list of permutations. We find an advanced sampling scheme can be designed to yield much more accurate estimation of the Shapley value than the simple random sampling (SRS). Our sampling scheme is based on combinatorial structures in the field of design of experiments (DOE), particularly the order-of-addition experimental designs for the study of how the orderings of components would affect the output. We show that the obtained estimates are unbiased, and can sometimes deterministically recover the original Shapley value. Both theoretical and simulations results show that our DOE-based sampling scheme outperforms SRS in terms of estimation accuracy. Surprisingly, it is also slightly faster than SRS. Lastly, real data analysis is conducted for the C. elegans nervous system and the 9/11 terrorist network.
• Abstract（参考訳）: シャプリー・バリュー(shapley value)は、econometrics(econometrics)のコンセプトで、プレイヤーに利益とコストを公平に分配する。 この数十年で、そのアプリケーションはマーケティング、エンジニアリング、機械学習など他の分野にも拡張された。 例えば、感度分析、解釈可能な機械学習へのローカルモデル説明、ソーシャルネットワークにおけるノードの重要性、属性モデルなどの問題に対する合理的なソリューションを生成する。 しかし、計算の重荷は長い間認識されてきたが、ほとんど調査されていない。 具体的には、$d$-player coalitionゲームでは、shapley値を計算するには$dの評価が必要です! Shapley値の置換や組み合わせの定式化を行うかどうかによっては、$または$2^d$の限界寄与値がある。 従って$d$が合理的に大きい場合にはShapley値を計算できない。 一般的な治療法は、置換の完全なリストのために置換のランダムなサンプルを取ることである。 単純なランダムサンプリング (srs) よりも, シャプリー値の高精度な推定を実現するために, 高度なサンプリング手法が提案されている。 提案手法は実験計画(doe)における組合せ構造に基づいており、特に成分の順序が出力にどのように影響するかを研究するための付加順序実験設計を行っている。 得られた推定値が偏りがなく、時には元のShapley値を決定的に復元できることを示す。 理論およびシミュレーションの結果から,doeに基づくサンプリング手法は推定精度でsrsを上回っていることがわかった。 驚くべきことに、SRSよりも若干速い。 最後に、C. elegans神経系と9/11テロネットワークの実際のデータ分析を行う。

関連論文リスト

• Improving the Sampling Strategy in KernelSHAP [0.8057006406834466]
  KernelSHAPフレームワークは、重み付けされた条件付き期待値のサンプルサブセットを用いて、Shapley値の近似を可能にする。 本稿では,現在最先端戦略における重みの分散を低減するための安定化手法,サンプルサブセットに基づいてShapleyカーネル重みを補正する新しい重み付け方式,および重要なサブセットを包含して修正されたShapleyカーネル重みと統合する簡単な戦略を提案する。
  論文  参考訳（メタデータ） (2024-10-07T10:02:31Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  冗長な手法を排除し、単純で効率的なシェープリー推定器SimSHAPを提案する。 既存手法の解析において、推定器は特徴部分集合からランダムに要約された値の線形変換として統一可能であることを観察する。 実験により,SimSHAPの有効性が検証され,精度の高いShapley値の計算が大幅に高速化された。
  論文  参考訳（メタデータ） (2023-11-02T06:09:24Z)
• An Efficient Shapley Value Computation for the Naive Bayes Classifier [0.0]
  本稿では, 単純ベイズ分類器の場合のShapley値の正確な解析式を提案する。 以上の結果から,本提案はアルゴリズムの複雑さを低く抑えた有意な結果をもたらすことが示唆された。
  論文  参考訳（メタデータ） (2023-07-31T14:39:10Z)
• DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation [23.646508094051768]
  我々は、データセットのバリュエーションの問題、すなわち、インクリメンタルゲインを定量化する問題を考える。 Shapleyの値は、その正式な公理的正当化のためにデータセットのバリュエーションを実行する自然なツールである。 本稿では,離散一様分布下での予測として表現される離散一様シャプリーと呼ばれる新しい近似を提案する。
  論文  参考訳（メタデータ） (2023-06-03T10:22:50Z)
• Efficient Shapley Values Estimation by Amortization for Text Classification [66.7725354593271]
  我々は,各入力特徴のシェープ値を直接予測し,追加のモデル評価を行なわずに補正モデルを開発する。 2つのテキスト分類データセットの実験結果から、アモルタイズされたモデルでは、Shapley Valuesを最大60倍のスピードアップで正確に見積もっている。
  論文  参考訳（メタデータ） (2023-05-31T16:19:13Z)
• SHAP-XRT: The Shapley Value Meets Conditional Independence Testing [21.794110108580746]
  そこで本研究では,Shapleyに基づく説明手法と条件付き独立性テストが密接に関連していることを示す。 本研究では,条件付きランダム化テスト(CRT, Conditional Randomization Test)にインスパイアされたテスト手法であるSHAPley Explanation Randomization Test(SHAP-XRT)を紹介した。 我々は、Shapley値自体が大域(つまり全体)のnull仮説の期待$p$-値に上限を与えることを示した。
  論文  参考訳（メタデータ） (2022-07-14T16:28:54Z)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  ニューラルアーキテクチャ探索のための演算寄与度(Shapley-NAS)を評価するためのShapley値に基づく手法を提案する。 提案手法は,光探索コストに比例して最先端の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-20T14:41:49Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement [75.12782480740822]
  We design novel composable sketches for WOR $ell_p$ sample。 私たちのスケッチは、サンプルサイズと直線的にしか成長しないサイズです。 我々の方法は、最初に$p>1$の重要なレギュレーションでWORサンプリングを提供し、最初に$p>0$で署名された更新を処理する。
  論文  参考訳（メタデータ） (2020-07-14T00:19:27Z)
• Towards Efficient Data Valuation Based on the Shapley Value [65.4167993220998]
  本稿では,Shapley値を用いたデータ評価の問題点について検討する。 Shapleyの値は、データ値の概念に対して多くのデシダータを満たすユニークなペイオフスキームを定義する。 本稿では,Shapley値を近似する効率的なアルゴリズムのレパートリーを提案する。
  論文  参考訳（メタデータ） (2019-02-27T00:22:43Z)

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

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