論文の概要: Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases

• arxiv url: http://arxiv.org/abs/2401.06493v2
• Date: Tue, 16 Apr 2024 12:16:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-17 23:25:43.773474
• Title: Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
• Title（参考訳）: ブール関数のシェープライクなスコア:複雑さと確率データベースへの応用
• Authors: Pratik Karmakar, Mikaël Monet, Pierre Senellart, Stéphane Bressan,
• Abstract要約: 私たちはShapleyのようなスコアを確率的設定に適応させ、期待値を計算することを目的としています。 本稿では,期待値のシェープ値とブール関数の期待値の計算が時間内に解釈可能であることを示す。 本稿では,データベースの証明を通じてデータベースに適用し,このアルゴリズムをProvableシステム内で効果的に実装する。
• 参考スコア（独自算出の注目度）: 3.386124605656362
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Shapley values, originating in game theory and increasingly prominent in explainable AI, have been proposed to assess the contribution of facts in query answering over databases, along with other similar power indices such as Banzhaf values. In this work we adapt these Shapley-like scores to probabilistic settings, the objective being to compute their expected value. We show that the computations of expected Shapley values and of the expected values of Boolean functions are interreducible in polynomial time, thus obtaining the same tractability landscape. We investigate the specific tractable case where Boolean functions are represented as deterministic decomposable circuits, designing a polynomial-time algorithm for this setting. We present applications to probabilistic databases through database provenance, and an effective implementation of this algorithm within the ProvSQL system, which experimentally validates its feasibility over a standard benchmark.
• Abstract（参考訳）: 共有値はゲーム理論を起源とし、説明可能なAIにおいてますます顕著になっているが、データベース上の問合せ応答における事実の貢献と、Banzhaf値のような他の類似のパワー指標を評価するために提案されている。 この作業では、これらのシェープのようなスコアを確率的設定に適応させ、その目的は期待値を計算することである。 本研究では,期待されるシェープリー値とブール関数の期待値の計算が多項式時間で解釈可能であることを示す。 本稿では,ブール関数が決定論的分解可能回路として表現される特定のトラクタブルケースについて検討し,この設定のための多項式時間アルゴリズムを設計する。 本稿では,データベースの証明を通じて確率的データベースに適用し,このアルゴリズムをProvSQLシステム内で効果的に実装し,標準ベンチマーク上での有効性を実験的に検証する。

関連論文リスト

• Shapley Value Computation in Ontology-Mediated Query Answering [3.1952340441132474]
  Shapley値は、もともと富分配のための協調ゲーム理論で導入されたもので、KRやデータベースで使われている。 本稿では,問合せ応答設定におけるShapley値計算(SVC)の複雑さ解析について述べる。
  論文  参考訳（メタデータ） (2024-07-29T14:45:14Z)
• Variational Shapley Network: A Probabilistic Approach to Self-Explaining Shapley values with Uncertainty Quantification [2.6699011287124366]
  シェープ価値は、モデル決定プロセスの解明のための機械学習(ML)の基礎ツールとして現れている。 本稿では,Shapley値の計算を大幅に単純化し,単一のフォワードパスしか必要としない,新しい自己説明手法を提案する。
  論文  参考訳（メタデータ） (2024-02-06T18:09:05Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  本稿では、Poissonプロセスに基づくランキングベースの代理モデルを提案し、Poisson Process Bayesian Optimization(PoPBO)と呼ばれる効率的なBOフレームワークを提案する。 従来のGP-BO法と比較すると,PoPBOはコストが低く,騒音に対する堅牢性も良好であり,十分な実験により検証できる。
  論文  参考訳（メタデータ） (2024-02-05T02:54:50Z)
• 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)
• Validation Diagnostics for SBI algorithms based on Normalizing Flows [55.41644538483948]
  本研究は,NFに基づく多次元条件(後)密度推定器の検証診断を容易にすることを提案する。 また、局所的な一貫性の結果に基づいた理論的保証も提供する。 この作業は、より良い特定モデルの設計を支援したり、新しいSBIアルゴリズムの開発を促進するのに役立つだろう。
  論文  参考訳（メタデータ） (2022-11-17T15:48:06Z)
• Exact Shapley Values for Local and Model-True Explanations of Decision Tree Ensembles [0.0]
  決定木アンサンブルの説明にShapley値を適用することを検討する。 本稿では,無作為林に適応し,決定木を増強できる,Shapley値に基づく特徴属性に対する新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2021-12-16T20:16:02Z)
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption [127.439030701253]
  確率感性決定図は構造化分解可能な回路のクラスである。 本稿では,回路の論理的基盤を暗黙的に提供する部分閉世界仮定に基づく新しいスキームを提案する。 予備実験では、提案手法がトレーニングデータに適切に適合し、基礎となる論理的基盤と整合性を維持した上で、テストデータによく適合することを示した。
  論文  参考訳（メタデータ） (2021-07-26T12:01:56Z)
• Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
  確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。 我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。 まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
  論文  参考訳（メタデータ） (2020-08-19T16:04:34Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  スパースサンプリングされた場所のみの機能を計算することを提案する。 次に、効率的な手順で特徴写像を密に再構築する。 提案したネットワークは、様々なコンピュータビジョンタスクの精度を維持しながら、かなりの計算を省くために実験的に示されている。
  論文  参考訳（メタデータ） (2020-03-19T15:36:31Z)

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

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