論文の概要: Efficient inference of interventional distributions

• arxiv url: http://arxiv.org/abs/2107.11712v1
• Date: Sun, 25 Jul 2021 02:40:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-28 02:52:04.062200
• Title: Efficient inference of interventional distributions
• Title（参考訳）: 介入分布の効率的な推定
• Authors: Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, Vedant Raval, N. V. Vinodchandran
• Abstract要約: 有限個の観測値から因果ベイズネットワーク内の干渉分布を効率的に推定する問題を考察する。 我々は、$mathbfY$ が任意の集合であるとき、グラフ同型問題を含む統計的ゼロ知識を持つ全ての問題が効率的なランダム化アルゴリズムを持っていなければ、$varepsilon$-close である分布の評価器を$P_bf x(mathbfY)$ に出力する効率的なアルゴリズムは存在しないことを示した。
• 参考スコア（独自算出の注目度）: 13.31079561447385
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of efficiently inferring interventional distributions in a causal Bayesian network from a finite number of observations. Let $\mathcal{P}$ be a causal model on a set $\mathbf{V}$ of observable variables on a given causal graph $G$. For sets $\mathbf{X},\mathbf{Y}\subseteq \mathbf{V}$, and setting ${\bf x}$ to $\mathbf{X}$, let $P_{\bf x}(\mathbf{Y})$ denote the interventional distribution on $\mathbf{Y}$ with respect to an intervention ${\bf x}$ to variables ${\bf x}$. Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), gave an exact characterization of the class of causal graphs for which the interventional distribution $P_{\bf x}({\mathbf{Y}})$ can be uniquely determined. We give the first efficient version of the Shpitser-Pearl algorithm. In particular, under natural assumptions, we give a polynomial-time algorithm that on input a causal graph $G$ on observable variables $\mathbf{V}$, a setting ${\bf x}$ of a set $\mathbf{X} \subseteq \mathbf{V}$ of bounded size, outputs succinct descriptions of both an evaluator and a generator for a distribution $\hat{P}$ that is $\varepsilon$-close (in total variation distance) to $P_{\bf x}({\mathbf{Y}})$ where $Y=\mathbf{V}\setminus \mathbf{X}$, if $P_{\bf x}(\mathbf{Y})$ is identifiable. We also show that when $\mathbf{Y}$ is an arbitrary set, there is no efficient algorithm that outputs an evaluator of a distribution that is $\varepsilon$-close to $P_{\bf x}({\mathbf{Y}})$ unless all problems that have statistical zero-knowledge proofs, including the Graph Isomorphism problem, have efficient randomized algorithms.
• Abstract（参考訳）: 有限個の観測値から因果ベイズネットワーク内の干渉分布を効率的に推定する問題を考察する。 与えられた因果グラフ上の可観測変数のセット $\mathbf{v}$ 上の因果モデルとして $\mathcal{p}$ とする。 集合 $\mathbf{x},\mathbf{y}\subseteq \mathbf{v}$, and set ${\bf x}$ to $\mathbf{x}$, let $p_{\bf x}(\mathbf{y})$ は変数 ${\bf x}$ に対する介入${\bf x}$ に関して$\mathbf{y}$ 上の介入分布を表す。 Shpitser and Pearl (AAAI 2006), building on the work of Tian and Pearl (AAAI 2001), given a exact Characterization of the class of causal graphs that the interventional distribution $P_{\bf x}({\mathbf{Y}})$ can be uniquely determined。 shpitser-pearlアルゴリズムの最初の効率的なバージョンを与える。 特に、自然仮定の下では、可観測変数 $\mathbf{v}$, a set $\mathbf{x} \subseteq \mathbf{v}$ of bounded size, outputs succinct descriptions of a evaluator and a distribution $\hat{p}$ that is $\varepsilon$-close (in total variation distance) to $p_{\bf x}({\mathbf{y}})$ where $y=\mathbf{v}\setminus \mathbf{x}$, if $p_{\bf x}(\mathbf{y})$, if $p_{\bf x}(\mathbf{y})$ の因果グラフを入力する多項式時間アルゴリズムを与える。 また、$\mathbf{y}$ が任意の集合である場合、グラフ同型問題を含む統計的ゼロ知識証明を持つすべての問題が効率的なランダム化アルゴリズムを持つ場合を除き、$\varepsilon$-closeから$p_{\bf x}({\mathbf{y}})$となる分布の蒸発器を出力する効率的なアルゴリズムは存在しないことを示した。

関連論文リスト

• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。 ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-11-11T03:43:52Z)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。 具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。 本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
  論文  参考訳（メタデータ） (2023-11-22T04:34:09Z)
• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。 提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
  論文  参考訳（メタデータ） (2021-10-05T09:33:49Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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