論文の概要: Sampling Permutations for Shapley Value Estimation

• arxiv url: http://arxiv.org/abs/2104.12199v1
• Date: Sun, 25 Apr 2021 16:44:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-28 05:33:51.578847
• Title: Sampling Permutations for Shapley Value Estimation
• Title（参考訳）: シャプレー値推定のためのサンプリング順列
• Authors: Rory Mitchell, Joshua Cooper, Eibe Frank, Geoffrey Holmes
• Abstract要約: Shapley値に基づくゲーム理論属性技術は、機械学習モデルの解釈に広く使用される。 シャプリー値の計算は置換集合上の和として表現できるので、近似のためのこれらの置換のサブセットをサンプリングする共通のアプローチである。 残念なことに、標準的なモンテカルロサンプリング法は遅い収束を示すことができ、より洗練された準モンテカルロ法は置換の空間でよく定義されていない。
• 参考スコア（独自算出の注目度）: 1.0323063834827415
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Game-theoretic attribution techniques based on Shapley values are used extensively to interpret black-box machine learning models, but their exact calculation is generally NP-hard, requiring approximation methods for non-trivial models. As the computation of Shapley values can be expressed as a summation over a set of permutations, a common approach is to sample a subset of these permutations for approximation. Unfortunately, standard Monte Carlo sampling methods can exhibit slow convergence, and more sophisticated quasi Monte Carlo methods are not well defined on the space of permutations. To address this, we investigate new approaches based on two classes of approximation methods and compare them empirically. First, we demonstrate quadrature techniques in a RKHS containing functions of permutations, using the Mallows kernel to obtain explicit convergence rates of $O(1/n)$, improving on $O(1/\sqrt{n})$ for plain Monte Carlo. The RKHS perspective also leads to quasi Monte Carlo type error bounds, with a tractable discrepancy measure defined on permutations. Second, we exploit connections between the hypersphere $\mathbb{S}^{d-2}$ and permutations to create practical algorithms for generating permutation samples with good properties. Experiments show the above techniques provide significant improvements for Shapley value estimates over existing methods, converging to a smaller RMSE in the same number of model evaluations.
• Abstract（参考訳）: Shapley値に基づくゲーム理論属性技術は、ブラックボックス機械学習モデルの解釈に広く用いられているが、その正確な計算は一般にNPハードであり、非自明なモデルの近似法を必要とする。 シャプリー値の計算は置換集合上の和として表現できるので、近似のためのこれらの置換のサブセットをサンプリングする共通のアプローチである。 残念なことに、標準モンテカルロサンプリング法は緩やかな収束を示し、より洗練された準モンテカルロ法は置換空間において十分に定義されていない。 そこで本研究では,2つの近似法に基づく新しいアプローチについて検討し,経験的に比較する。 まず, 置換関数を含む rkhs において, mallows カーネルを用いて明示的な収束率である $o(1/n)$ を求め, モンテカルロの $o(1/\sqrt{n})$ を改善した。 RKHSパースペクティブはまた、擬モンテカルロ型エラー境界(英語版)を導き、置換で定義されるトラクタブルな離散測度を持つ。 次に、超球面$\mathbb{S}^{d-2}$と置換の間の接続を利用して、良好な性質を持つ置換サンプルを生成するための実用的なアルゴリズムを作成する。 実験の結果, 従来の手法に比べてシェープ値の推定精度が大幅に向上し, RMSEがより小さいモデル評価値に収束することがわかった。

関連論文リスト

• A Stein Gradient Descent Approach for Doubly Intractable Distributions [5.63014864822787]
  そこで本研究では,2重に抽出可能な分布を推定するために,モンテカルロ・スタイン変分勾配勾配(MC-SVGD)法を提案する。 提案手法は,後続分布に匹敵する推論性能を提供しながら,既存のアルゴリズムよりもかなりの計算ゲインを達成する。
  論文  参考訳（メタデータ） (2024-10-28T13:42:27Z)
• Multi-fidelity Hamiltonian Monte Carlo [1.86413150130483]
  代理モデルを用いた2段階ハミルトニアンモンテカルロアルゴリズムを提案する。 受け入れられた確率は、標準のHMC提案によって第一段階で計算される。 提案が受理された場合、後部を高忠実度数値解法を用いて第2段階で評価する。
  論文  参考訳（メタデータ） (2024-05-08T13:03:55Z)
• Stochastic automatic differentiation for Monte Carlo processes [1.1279808969568252]
  自動微分法(AD)のモンテカルロプロセスへの拡張について検討する。 ハミルトン的アプローチは、再重み付け手法の変数の変化と解釈できることを示す。
  論文  参考訳（メタデータ） (2023-07-28T08:59:01Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) が提案されている。 提案アルゴリズムは,文脈的帯域幅の特別な場合において,最高のトンプソンサンプリングアルゴリズムと同じサブ線形残差を達成できることを示す。
  論文  参考訳（メタデータ） (2022-06-22T17:58:23Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  汎用性を維持しつつ高い忠実度近似を提供する,スケーラブルな変分ガウス過程近似を導入する。 様々な回帰問題や分類問題において,本手法は変換やリフレクションなどの入力空間対称性を活用できることを実証する。 提案手法は, 純粋なGPモデルのうち, CIFAR-10 の最先端化を実現する。
  論文  参考訳（メタデータ） (2021-06-10T18:17:57Z)
• A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples [0.0]
  低ランク行列補完のための反復アルゴリズムを提案する。 ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
  論文  参考訳（メタデータ） (2021-06-03T20:31:00Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  ハイブリッドモンテカルロ(Hybrid Monte Carlo)は、複素連続分布からサンプリングする強力なマルコフ連鎖モンテカルロ法である。 本稿では,SurVAEフローを用いたモンテカルロ法の拡張に基づく新しい手法を提案する。 本稿では,統計学,計算物理学,機械学習など,様々な分野におけるアルゴリズムの有効性を実証し,代替アルゴリズムと比較した改良点を考察する。
  論文  参考訳（メタデータ） (2021-02-04T02:21:08Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。 近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。 準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
  論文  参考訳（メタデータ） (2020-01-06T23:33:31Z)
• Sparse Orthogonal Variational Inference for Gaussian Processes [34.476453597078894]
  誘導点を用いたガウス過程に対するスパース変分近似の新しい解釈を導入する。 この定式化は既存の近似を復元し、同時に限界確率と新しい変分推論アルゴリズムのより厳密な下界を得ることができることを示す。
  論文  参考訳（メタデータ） (2019-10-23T15:01:28Z)

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

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